Coverage Report

Created: 2023-10-30 17:15

/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