IntervalPartition.cpp Source File (original) (raw)

15#include "llvm/ADT/BitVector.h"

16#include "llvm/ADT/STLExtras.h"

17#include

18#include

19#include

28 std::vector<const Node *> Nodes;

31};

33namespace internal {

38template

40 const Node *Header) {

41 assert(Header != nullptr);

43 Interval.Nodes.push_back(Header);

44 Partitioned.set(getID(*Header));

50 std::queue<const Node *> Worklist;

51 llvm::BitVector Workset(Partitioned.size(), false);

52 for (const Node *S : Header->succs())

53 if (S != nullptr)

54 if (auto SID = getID(*S); !Partitioned.test(SID)) {

57 Worklist.push(S);

58 Workset.set(SID);

59 }

68 std::vector<const Node *> MaybeSuccessors;

70 while (!Worklist.empty()) {

71 const auto *B = Worklist.front();

73 Worklist.pop();

74 Workset.reset(ID);

78 bool AllInInterval = llvm::all_of(B->preds(), [&](const Node *P) {

79 return llvm::is_contained(Interval.Nodes, P);

80 });

81 if (AllInInterval) {

82 Interval.Nodes.push_back(B);

83 Partitioned.set(ID);

84 for (const Node *S : B->succs())

85 if (S != nullptr)

86 if (auto SID = getID(*S);

87 !Partitioned.test(SID) && !Workset.test(SID)) {

88 Worklist.push(S);

89 Workset.set(SID);

90 }

91 } else {

92 MaybeSuccessors.push_back(B);

93 }

94 }

97 for (const Node *B : MaybeSuccessors)

98 if (!llvm::is_contained(Interval.Nodes, B))

100

101 return Interval;

102}

103

104template

106 std::vector<CFGIntervalNode *> &Index,

107 std::queue<const Node *> &Successors,

108 llvm::BitVector &Partitioned, const Node *Header) {

110 for (const auto *S : Result.Successors)

111 Successors.push(S);

112

113 CFGIntervalNode &Interval = Graph.emplace_back(Graph.size());

114

115

116

117

118

119 for (const auto *N : Result.Nodes) {

120 assert(N != nullptr);

121 assert(getID(*N) < Index.size());

122 Index[getID(*N)] = &Interval;

123 }

124

125 if constexpr (std::is_same_v<std::decay_t, CFGBlock>)

126 Interval.Nodes = std::move(Result.Nodes);

127 else {

128 std::vector<const CFGBlock *> Nodes;

129

130 size_t Count = 0;

131 for (auto &N : Result.Nodes)

132 Count += N->Nodes.size();

133 Nodes.reserve(Count);

134 for (auto &N : Result.Nodes)

135 Nodes.insert(Nodes.end(), N->Nodes.begin(), N->Nodes.end());

137 }

138}

139

140template

142 const Node *EntryBlock) {

143 assert(EntryBlock != nullptr);

145

146

147

148 std::vector<CFGIntervalNode *> Index(NumBlockIDs, nullptr);

149

150

151

152

153

154 std::vector<std::pair<const Node *, CFGIntervalNode *>> Intervals;

155 llvm::BitVector Partitioned(NumBlockIDs, false);

156 std::queue<const Node *> Successors;

157

158 fillIntervalNode(Graph, Index, Successors, Partitioned, EntryBlock);

159 Intervals.emplace_back(EntryBlock, &Graph.back());

160

161 while (!Successors.empty()) {

162 const auto *B = Successors.front();

163 Successors.pop();

164 assert(B != nullptr);

165 if (Partitioned.test(getID(*B)))

166 continue;

167

168

169

171 Intervals.emplace_back(B, &Graph.back());

172 }

173

174

175 for (auto [H, N] : Intervals) {

176

177

178 for (const Node *P : H->preds()) {

179 if (P == nullptr)

180 continue;

181

182 assert(getID(*P) < NumBlockIDs);

184 if (Pred == nullptr)

185

186 continue;

187 if (Pred != N

189

190

191

193 }

194 }

195

196 return Graph;

197}

198

202}

203

206}

207

210}

211}

212

214

215 unsigned PrevSize = Cfg.size();

216 if (PrevSize == 0)

217 return {};

219 unsigned Size = Graph.size();

220 while (Size > 1 && Size < PrevSize) {

221 PrevSize = Graph.size();

223 Size = Graph.size();

224 }

225 if (Size > 1)

226

227 return std::nullopt;

228

229 assert(Size != 0);

230 return std::move(Graph[0].Nodes);

231}

232

234 if (WTO.empty())

235 return;

236 auto N = WTO[0]->getParent()->getNumBlockIDs();

238 for (unsigned I = 0, S = WTO.size(); I < S; ++I)

239 BlockOrder[WTO[I]->getBlockID()] = I + 1;

240}

241}

BoundNodesTreeBuilder Nodes

Represents a single basic block in a source-level CFG.

unsigned getBlockID() const

Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.

unsigned size() const

Return the total number of CFGBlocks within the CFG This is simply a renaming of the getNumBlockIDs()...

unsigned getNumBlockIDs() const

Returns the total number of BlockIDs allocated (which start at 0).

static void fillIntervalNode(CFGIntervalGraph &Graph, std::vector< CFGIntervalNode * > &Index, std::queue< const Node * > &Successors, llvm::BitVector &Partitioned, const Node *Header)

static unsigned getID(const CFGBlock &B)

std::vector< const CFGBlock * > buildInterval(const CFGBlock *Header)

std::deque< CFGIntervalNode > CFGIntervalGraph

static CFGIntervalGraph partitionIntoIntervalsImpl(unsigned NumBlockIDs, const Node *EntryBlock)

CFGIntervalGraph partitionIntoIntervals(const CFG &Cfg)

The JSON file list parser is used to communicate input to InstallAPI.

@ Result

The result type of a method or function.

std::vector< const CFGBlock * > WeakTopologicalOrdering

A weak topological ordering (WTO) of CFG nodes provides a total order over the CFG (defined in WTOCom...

std::optional< WeakTopologicalOrdering > getIntervalWTO(const CFG &Cfg)

llvm::SmallDenseSet< const Node * > Successors

std::vector< const Node * > Nodes

std::vector< unsigned > BlockOrder

WTOCompare(const WeakTopologicalOrdering &WTO)

std::vector< const CFGBlock * > Nodes

llvm::SmallDenseSet< const CFGIntervalNode * > Predecessors

llvm::SmallDenseSet< const CFGIntervalNode * > Successors