/builds/2mk6rsew/0/parcoach/parcoach/src/include/parcoach/CollectiveList.h
Line | Count | Source (jump to first uncovered line) |
1 | | #pragma once |
2 | | |
3 | | #include "parcoach/Collectives.h" |
4 | | |
5 | | #include "llvm/ADT/DenseMap.h" |
6 | | |
7 | | #include <deque> |
8 | | #include <memory> |
9 | | #include <optional> |
10 | | #include <string> |
11 | | |
12 | | namespace llvm { |
13 | | class BasicBlock; |
14 | | class Value; |
15 | | } // namespace llvm |
16 | | class PTACallGraph; |
17 | | namespace parcoach { |
18 | | |
19 | | struct Element { |
20 | 25.0k | virtual ~Element() = default; |
21 | | virtual std::string toString() const = 0; |
22 | | virtual std::unique_ptr<Element> copy() const = 0; |
23 | | virtual bool navs() const = 0; |
24 | | }; |
25 | | |
26 | | struct CollElement : Element { |
27 | 22.3k | CollElement(Collective const &C) : Value(C) {} |
28 | 22.3k | ~CollElement() = default; |
29 | | Collective const &Value; |
30 | 17.0k | std::string toString() const override { return Value.Name; } |
31 | 2.37k | bool navs() const override { return false; } |
32 | 15.4k | inline std::unique_ptr<Element> copy() const override { |
33 | 15.4k | return std::make_unique<CollElement>(Value); |
34 | 15.4k | } |
35 | | }; |
36 | | |
37 | | // Not a valid set. |
38 | | struct NavsElement : Element { |
39 | 2.62k | ~NavsElement() = default; |
40 | 1.43k | std::string toString() const override { return "NAVS"; } |
41 | | // Maybe this method can be an isa |
42 | 2.57k | bool navs() const override { return true; } |
43 | 1.82k | inline std::unique_ptr<Element> copy() const override { |
44 | 1.82k | return std::make_unique<NavsElement>(); |
45 | 1.82k | } |
46 | | }; |
47 | | |
48 | | class CollectiveList { |
49 | | // An optional LoopHeader for the loop this may represent. |
50 | | // Used with two objectives: |
51 | | // - be able to identify if the CL belongs to a list |
52 | | // - be able to emit two different strings for two different loops |
53 | | // even if they have the same list of collectives. We must do that because |
54 | | // we don't know the boundaries. |
55 | | std::optional<llvm::BasicBlock *> LoopHeader_; |
56 | | using ListTy = std::deque<std::unique_ptr<Element>>; |
57 | | ListTy List_; |
58 | | static void add(CollectiveList const &Other, |
59 | | std::insert_iterator<ListTy> Inserter); |
60 | | |
61 | | public: |
62 | | using BBToCollListMap = llvm::DenseMap<llvm::BasicBlock *, CollectiveList>; |
63 | | using CommToBBToCollListMap = llvm::DenseMap<llvm::Value *, BBToCollListMap>; |
64 | | std::string toString() const; |
65 | 59.3k | CollectiveList() = default; |
66 | 4.37k | CollectiveList(CollectiveList &&From) = default; |
67 | 29.4k | CollectiveList &operator=(CollectiveList &&From) = default; |
68 | | // This forces move-assignment, or explicit copy. |
69 | | CollectiveList &operator=(CollectiveList const &From) = delete; |
70 | | CollectiveList(CollectiveList const &From); |
71 | | CollectiveList(llvm::BasicBlock *Header, CollectiveList const &LoopList); |
72 | | bool navs() const; |
73 | 0 | bool empty() const { return List_.empty(); } |
74 | 0 | auto const &getLoopHeader() const { return LoopHeader_; } |
75 | | // Poperly "push" a CL to our CL. |
76 | | void extendWith(CollectiveList const &Other); |
77 | | void prependWith(CollectiveList const &Other); |
78 | | |
79 | | template <typename ElementTy, typename... ArgsTy> |
80 | 7.73k | void extendWith(ArgsTy &&...Args) { |
81 | 7.73k | List_.emplace_back(std::make_unique<ElementTy>(Args...)); |
82 | 7.73k | } _ZN8parcoach14CollectiveList10extendWithINS_11NavsElementEJEEEvDpOT0_ Line | Count | Source | 80 | 800 | void extendWith(ArgsTy &&...Args) { | 81 | 800 | List_.emplace_back(std::make_unique<ElementTy>(Args...)); | 82 | 800 | } |
_ZN8parcoach14CollectiveList10extendWithINS_11CollElementEJRKNS_10CollectiveEEEEvDpOT0_ Line | Count | Source | 80 | 6.93k | void extendWith(ArgsTy &&...Args) { | 81 | 6.93k | List_.emplace_back(std::make_unique<ElementTy>(Args...)); | 82 | 6.93k | } |
|
83 | | |
84 | | // This is likely too expensive. |
85 | 5.28k | inline bool operator==(CollectiveList const &Other) const { |
86 | 5.28k | return toString() == Other.toString(); |
87 | 5.28k | } |
88 | 5.28k | inline bool operator!=(CollectiveList const &Other) const { |
89 | 5.28k | return !operator==(Other); |
90 | 5.28k | } |
91 | | |
92 | | template <typename ContainerTy, typename IteratorTy> |
93 | | static bool NeighborsAreNAVS(ContainerTy &Computed, llvm::BasicBlock *BB, |
94 | | IteratorTy NeighborsBegin, |
95 | 15.6k | IteratorTy NeighborsEnd) { |
96 | | // If at least one pair of neighbors are not equal, then the result |
97 | | // is NAVS. We leverage std::adjacent_find to figure this out. |
98 | 15.6k | auto NotEqual = [&](llvm::BasicBlock *A, llvm::BasicBlock *B) { |
99 | 5.28k | assert(Computed.count(A) && Computed.count(B) && |
100 | 5.28k | "Both BB should be computed already"); |
101 | 5.28k | return Computed[A] != Computed[B]; |
102 | 5.28k | }; _ZZN8parcoach14CollectiveList16NeighborsAreNAVSIN4llvm8DenseMapIPNS2_10BasicBlockES0_NS2_12DenseMapInfoIS5_vEENS2_6detail12DenseMapPairIS5_S0_EEEEPKS5_EEbRT_S5_T0_SG_ENKUlS5_S5_E_clES5_S5_ Line | Count | Source | 98 | 2 | auto NotEqual = [&](llvm::BasicBlock *A, llvm::BasicBlock *B) { | 99 | 2 | assert(Computed.count(A) && Computed.count(B) && | 100 | 2 | "Both BB should be computed already"); | 101 | 2 | return Computed[A] != Computed[B]; | 102 | 2 | }; |
_ZZN8parcoach14CollectiveList16NeighborsAreNAVSIN4llvm8DenseMapIPNS2_10BasicBlockES0_NS2_12DenseMapInfoIS5_vEENS2_6detail12DenseMapPairIS5_S0_EEEENS2_12SuccIteratorINS2_11InstructionES4_EEEEbRT_S5_T0_SH_ENKUlS5_S5_E_clES5_S5_ Line | Count | Source | 98 | 5.27k | auto NotEqual = [&](llvm::BasicBlock *A, llvm::BasicBlock *B) { | 99 | 5.27k | assert(Computed.count(A) && Computed.count(B) && | 100 | 5.27k | "Both BB should be computed already"); | 101 | 5.27k | return Computed[A] != Computed[B]; | 102 | 5.27k | }; |
_ZZN8parcoach14CollectiveList16NeighborsAreNAVSIN4llvm8DenseMapIPNS2_10BasicBlockES0_NS2_12DenseMapInfoIS5_vEENS2_6detail12DenseMapPairIS5_S0_EEEENS2_12PredIteratorIS4_NS2_5Value18user_iterator_implINS2_4UserEEEEEEEbRT_S5_T0_SK_ENKUlS5_S5_E_clES5_S5_ Line | Count | Source | 98 | 15 | auto NotEqual = [&](llvm::BasicBlock *A, llvm::BasicBlock *B) { | 99 | 15 | assert(Computed.count(A) && Computed.count(B) && | 100 | 15 | "Both BB should be computed already"); | 101 | 15 | return Computed[A] != Computed[B]; | 102 | 15 | }; |
|
103 | 15.6k | return std::adjacent_find(NeighborsBegin, NeighborsEnd, NotEqual) != |
104 | 15.6k | NeighborsEnd; |
105 | 15.6k | } _ZN8parcoach14CollectiveList16NeighborsAreNAVSIN4llvm8DenseMapIPNS2_10BasicBlockES0_NS2_12DenseMapInfoIS5_vEENS2_6detail12DenseMapPairIS5_S0_EEEEPKS5_EEbRT_S5_T0_SG_ Line | Count | Source | 95 | 459 | IteratorTy NeighborsEnd) { | 96 | | // If at least one pair of neighbors are not equal, then the result | 97 | | // is NAVS. We leverage std::adjacent_find to figure this out. | 98 | 459 | auto NotEqual = [&](llvm::BasicBlock *A, llvm::BasicBlock *B) { | 99 | 459 | assert(Computed.count(A) && Computed.count(B) && | 100 | 459 | "Both BB should be computed already"); | 101 | 459 | return Computed[A] != Computed[B]; | 102 | 459 | }; | 103 | 459 | return std::adjacent_find(NeighborsBegin, NeighborsEnd, NotEqual) != | 104 | 459 | NeighborsEnd; | 105 | 459 | } |
_ZN8parcoach14CollectiveList16NeighborsAreNAVSIN4llvm8DenseMapIPNS2_10BasicBlockES0_NS2_12DenseMapInfoIS5_vEENS2_6detail12DenseMapPairIS5_S0_EEEENS2_12SuccIteratorINS2_11InstructionES4_EEEEbRT_S5_T0_SH_ Line | Count | Source | 95 | 14.2k | IteratorTy NeighborsEnd) { | 96 | | // If at least one pair of neighbors are not equal, then the result | 97 | | // is NAVS. We leverage std::adjacent_find to figure this out. | 98 | 14.2k | auto NotEqual = [&](llvm::BasicBlock *A, llvm::BasicBlock *B) { | 99 | 14.2k | assert(Computed.count(A) && Computed.count(B) && | 100 | 14.2k | "Both BB should be computed already"); | 101 | 14.2k | return Computed[A] != Computed[B]; | 102 | 14.2k | }; | 103 | 14.2k | return std::adjacent_find(NeighborsBegin, NeighborsEnd, NotEqual) != | 104 | 14.2k | NeighborsEnd; | 105 | 14.2k | } |
_ZN8parcoach14CollectiveList16NeighborsAreNAVSIN4llvm8DenseMapIPNS2_10BasicBlockES0_NS2_12DenseMapInfoIS5_vEENS2_6detail12DenseMapPairIS5_S0_EEEENS2_12PredIteratorIS4_NS2_5Value18user_iterator_implINS2_4UserEEEEEEEbRT_S5_T0_SK_ Line | Count | Source | 95 | 965 | IteratorTy NeighborsEnd) { | 96 | | // If at least one pair of neighbors are not equal, then the result | 97 | | // is NAVS. We leverage std::adjacent_find to figure this out. | 98 | 965 | auto NotEqual = [&](llvm::BasicBlock *A, llvm::BasicBlock *B) { | 99 | 965 | assert(Computed.count(A) && Computed.count(B) && | 100 | 965 | "Both BB should be computed already"); | 101 | 965 | return Computed[A] != Computed[B]; | 102 | 965 | }; | 103 | 965 | return std::adjacent_find(NeighborsBegin, NeighborsEnd, NotEqual) != | 104 | 965 | NeighborsEnd; | 105 | 965 | } |
|
106 | | |
107 | | static CollectiveList CreateFromBB(BBToCollListMap const &CollLists, |
108 | | PTACallGraph const &PTACG, |
109 | | bool NeighborsAreNAVS, |
110 | | llvm::BasicBlock &BB, |
111 | | llvm::Value *Comm = nullptr); |
112 | | }; |
113 | | |
114 | | struct CollListElement : Element { |
115 | | CollectiveList Value; |
116 | 77 | CollListElement(CollectiveList Val) : Value(std::move(Val)) {} |
117 | 77 | ~CollListElement() = default; |
118 | 18 | std::string toString() const override { return Value.toString(); } |
119 | 19 | bool navs() const override { return Value.navs(); } |
120 | 62 | inline std::unique_ptr<Element> copy() const override { |
121 | 62 | return std::make_unique<CollListElement>(Value); |
122 | 62 | } |
123 | | }; |
124 | | |
125 | | } // namespace parcoach |