128 #include <functional>
130 #define DEBUG_TYPE "sync-dependence"
141 using namespace llvm;
151 using VisitedSet = std::set<const BasicBlock *>;
152 using BlockStack = std::vector<const BasicBlock *>;
156 VisitedSet &Finalized);
159 static void computeStackPO(BlockStack &Stack,
const LoopInfo &LI,
Loop *
Loop,
160 POCB CallBack, VisitedSet &Finalized) {
162 while (!Stack.empty()) {
163 const auto *NextBB = Stack.back();
166 bool IsNestedLoop = NestedLoop !=
Loop;
171 NestedLoop->getUniqueExitBlocks(NestedExits);
172 bool PushedNodes =
false;
173 for (
const auto *NestedExitBB : NestedExits) {
174 if (NestedExitBB == LoopHeader)
178 if (Finalized.count(NestedExitBB))
181 Stack.push_back(NestedExitBB);
186 computeLoopPO(LI, *NestedLoop, CallBack, Finalized);
192 bool PushedNodes =
false;
193 for (
const auto *SuccBB :
successors(NextBB)) {
194 if (SuccBB == LoopHeader)
198 if (Finalized.count(SuccBB))
201 Stack.push_back(SuccBB);
206 if (!Finalized.insert(NextBB).second)
214 VisitedSet Finalized;
217 Stack.push_back(&
F.getEntryBlock());
218 computeStackPO(Stack, LI,
nullptr, CallBack, Finalized);
222 VisitedSet &Finalized) {
224 std::vector<const BasicBlock *> Stack;
228 Finalized.insert(LoopHeader);
229 CallBack(*LoopHeader);
235 if (
BB == LoopHeader)
241 computeStackPO(Stack, LI, &
Loop, CallBack, Finalized);
253 : DT(DT), PDT(PDT), LI(LI) {
276 std::unique_ptr<ControlDivergenceDesc>
DivDesc;
286 Out <<
"Propagator::BlockLabels {\n";
287 for (
int BlockIdx = (
int)
BlockLabels.size() - 1; BlockIdx > 0; --BlockIdx) {
294 Out << Label->getName() <<
"\n";
307 if (!OldLabel || (OldLabel == &PushedLabel)) {
320 const BasicBlock &DefBlock,
bool FromParentLoop) {
329 DivDesc->LoopDivBlocks.insert(&ExitBlock);
341 DivDesc->JoinDivBlocks.insert(&SuccBlock);
366 BlockIdx = std::max<int>(BlockIdx, SuccIdx);
367 FloorIdx = std::min<int>(FloorIdx, SuccIdx);
374 if (BlockLoop && DivBlockLoop->contains(BlockLoop))
376 DivDesc->LoopDivBlocks.insert(SuccBlock);
378 << SuccBlock->getName() <<
"\n");
382 for (; BlockIdx >= FloorIdx; --BlockIdx) {
392 LLVM_DEBUG(
dbgs() <<
"SDA::joins. visiting " << Block->getName() <<
"\n");
395 bool IsLoopHeader = BlockLoop && BlockLoop->
getHeader() == Block;
396 bool CausedJoin =
false;
397 int LoweredFloorIdx = FloorIdx;
402 BlockLoop->getExitBlocks(BlockLoopExits);
405 for (
const auto *BlockLoopExit : BlockLoopExits) {
407 LoweredFloorIdx = std::min<int>(LoweredFloorIdx,
412 for (
const auto *SuccBlock :
successors(Block)) {
413 CausedJoin |=
visitEdge(*SuccBlock, *Label);
422 FloorIdx = LoweredFloorIdx;
423 }
else if (FloorLabel != Label) {
426 FloorIdx = LoweredFloorIdx;
441 for (
const auto *
BB : Blocks)
442 Out <<
LS <<
BB->getName();
450 if (
Term.getNumSuccessors() <= 1) {
451 return EmptyDivergenceDesc;
455 auto ItCached = CachedControlDivDescs.find(&
Term);
456 if (ItCached != CachedControlDivDescs.end())
457 return *ItCached->second;
461 const auto &TermBlock = *
Term.getParent();
466 dbgs() <<
"JoinDivBlocks: ";
468 dbgs() <<
"\nLoopDivBlocks: ";
471 auto ItInserted = CachedControlDivDescs.emplace(&
Term,
std::move(DivDesc));
472 assert(ItInserted.second);
473 return *ItInserted.first->second;