From 048f14fd3bf9a22d1f2a8693fe06def9d2347e6b Mon Sep 17 00:00:00 2001 From: Tom Stellard Date: Fri, 8 Feb 2013 22:24:37 +0000 Subject: [PATCH] R600: fix loop analyses in the structurizer MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Patch by: Christian König Intersecting loop handling was wrong. Signed-off-by: Christian König Tested-by: Michel Dänzer llvm-svn: 174761 --- llvm/lib/Target/R600/AMDGPUStructurizeCFG.cpp | 296 ++++++++++++++++---------- 1 file changed, 183 insertions(+), 113 deletions(-) diff --git a/llvm/lib/Target/R600/AMDGPUStructurizeCFG.cpp b/llvm/lib/Target/R600/AMDGPUStructurizeCFG.cpp index 7f3a35e..e1c7790 100644 --- a/llvm/lib/Target/R600/AMDGPUStructurizeCFG.cpp +++ b/llvm/lib/Target/R600/AMDGPUStructurizeCFG.cpp @@ -30,12 +30,14 @@ namespace { // Definition of the complex types used in this pass. typedef std::pair BBValuePair; -typedef ArrayRef BBVecRef; typedef SmallVector RNVector; typedef SmallVector BBVector; +typedef SmallVector BranchVector; typedef SmallVector BBValueVector; +typedef SmallPtrSet BBSet; + typedef DenseMap PhiMap; typedef DenseMap BBPhiMap; typedef DenseMap BBPredicates; @@ -111,23 +113,27 @@ class AMDGPUStructurizeCFG : public RegionPass { PredMap Predicates; BBPhiMap DeletedPhis; BB2BBVecMap AddedPhis; - BBVector FlowsInserted; + BranchVector Conditions; BasicBlock *LoopStart; BasicBlock *LoopEnd; + BBSet LoopTargets; BBPredicates LoopPred; void orderNodes(); - void buildPredicate(BranchInst *Term, unsigned Idx, - BBPredicates &Pred, bool Invert); + Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert); + + bool analyzeLoopStart(BasicBlock *From, BasicBlock *To, Value *Condition); - void analyzeBlock(BasicBlock *BB); + void analyzeNode(RegionNode *N); - void analyzeLoop(BasicBlock *BB, unsigned &LoopIdx); + void analyzeLoopEnd(RegionNode *N); void collectInfos(); + void insertConditions(); + void delPhiValues(BasicBlock *From, BasicBlock *To); void addPhiValues(BasicBlock *From, BasicBlock *To); @@ -148,8 +154,6 @@ class AMDGPUStructurizeCFG : public RegionPass { void createFlow(); - void insertConditions(); - void rebuildSSA(); public: @@ -202,114 +206,209 @@ void AMDGPUStructurizeCFG::orderNodes() { } } -/// \brief Build blocks and loop predicates -void AMDGPUStructurizeCFG::buildPredicate(BranchInst *Term, unsigned Idx, - BBPredicates &Pred, bool Invert) { - Value *True = Invert ? BoolFalse : BoolTrue; - Value *False = Invert ? BoolTrue : BoolFalse; +/// \brief Build the condition for one edge +Value *AMDGPUStructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx, + bool Invert) { + Value *Cond = Invert ? BoolFalse : BoolTrue; + if (Term->isConditional()) { + Cond = Term->getCondition(); - RegionInfo *RI = ParentRegion->getRegionInfo(); - BasicBlock *BB = Term->getParent(); + if (Idx != Invert) + Cond = BinaryOperator::CreateNot(Cond, "", Term); + } + return Cond; +} - // Handle the case where multiple regions start at the same block - Region *R = BB != ParentRegion->getEntry() ? - RI->getRegionFor(BB) : ParentRegion; +/// \brief Analyze the start of a loop and insert predicates as necessary +bool AMDGPUStructurizeCFG::analyzeLoopStart(BasicBlock *From, BasicBlock *To, + Value *Condition) { + LoopPred[From] = Condition; + LoopTargets.insert(To); + if (!LoopStart) { + LoopStart = To; + return true; + + } else if (LoopStart == To) + return true; + + // We need to handle the case of intersecting loops, e. g. + // + // /----<----- + // | | + // -> A -> B -> C -> D + // | | + // -----<----/ - if (R == ParentRegion) { - // It's a top level block in our region - Value *Cond = True; - if (Term->isConditional()) { - BasicBlock *Other = Term->getSuccessor(!Idx); + RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend(); - if (Visited.count(Other)) { - if (!Pred.count(Other)) - Pred[Other] = False; + for (;OI != OE; ++OI) + if ((*OI)->getEntry() == LoopStart) + break; - if (!Pred.count(BB)) - Pred[BB] = True; - return; - } - Cond = Term->getCondition(); + for (;OI != OE && (*OI)->getEntry() != To; ++OI) { + BBPredicates &Pred = Predicates[(*OI)->getEntry()]; + if (!Pred.count(From)) + Pred[From] = Condition; + } + return false; +} - if (Idx != Invert) - Cond = BinaryOperator::CreateNot(Cond, "", Term); - } +/// \brief Analyze the predecessors of each block and build up predicates +void AMDGPUStructurizeCFG::analyzeNode(RegionNode *N) { + RegionInfo *RI = ParentRegion->getRegionInfo(); + BasicBlock *BB = N->getEntry(); + BBPredicates &Pred = Predicates[BB]; - Pred[BB] = Cond; + for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); + PI != PE; ++PI) { - } else if (ParentRegion->contains(R)) { - // It's a block in a sub region - while(R->getParent() != ParentRegion) - R = R->getParent(); + if (!ParentRegion->contains(*PI)) { + // It's a branch from outside into our region entry + Pred[*PI] = BoolTrue; + continue; + } - Pred[R->getEntry()] = True; + Region *R = RI->getRegionFor(*PI); + if (R == ParentRegion) { - } else { - // It's a branch from outside into our parent region - Pred[BB] = True; - } -} + // It's a top level block in our region + BranchInst *Term = cast((*PI)->getTerminator()); + for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { + BasicBlock *Succ = Term->getSuccessor(i); + if (Succ != BB) + continue; -/// \brief Analyze the successors of each block and build up predicates -void AMDGPUStructurizeCFG::analyzeBlock(BasicBlock *BB) { - pred_iterator PI = pred_begin(BB), PE = pred_end(BB); - BBPredicates &Pred = Predicates[BB]; + if (Visited.count(*PI)) { + // Normal forward edge + if (Term->isConditional()) { + // Try to treat it like an ELSE block + BasicBlock *Other = Term->getSuccessor(!i); + if (Visited.count(Other) && !LoopTargets.count(Other) && + !Pred.count(Other) && !Pred.count(*PI)) { + + Pred[Other] = BoolFalse; + Pred[*PI] = BoolTrue; + continue; + } + } + + } else { + // Back edge + if (analyzeLoopStart(*PI, BB, buildCondition(Term, i, true))) + continue; + } + Pred[*PI] = buildCondition(Term, i, false); + } - for (; PI != PE; ++PI) { - BranchInst *Term = cast((*PI)->getTerminator()); + } else { - for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { - BasicBlock *Succ = Term->getSuccessor(i); - if (Succ != BB) + // It's an exit from a sub region + while(R->getParent() != ParentRegion) + R = R->getParent(); + + // Edge from inside a subregion to its entry, ignore it + if (R == N) continue; - buildPredicate(Term, i, Pred, false); + + BasicBlock *Entry = R->getEntry(); + if (!Visited.count(Entry)) + if (analyzeLoopStart(Entry, BB, BoolFalse)) + continue; + + Pred[Entry] = BoolTrue; } } } -/// \brief Analyze the conditions leading to loop to a previous block -void AMDGPUStructurizeCFG::analyzeLoop(BasicBlock *BB, unsigned &LoopIdx) { - BranchInst *Term = cast(BB->getTerminator()); +/// \brief Determine the end of the loop +void AMDGPUStructurizeCFG::analyzeLoopEnd(RegionNode *N) { - for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { - BasicBlock *Succ = Term->getSuccessor(i); + if (N->isSubRegion()) { + // Test for exit as back edge + BasicBlock *Exit = N->getNodeAs()->getExit(); + if (Visited.count(Exit)) + LoopEnd = N->getEntry(); - // Ignore it if it's not a back edge - if (!Visited.count(Succ)) - continue; + } else { + // Test for sucessors as back edge + BasicBlock *BB = N->getNodeAs(); + BranchInst *Term = cast(BB->getTerminator()); - buildPredicate(Term, i, LoopPred, true); + for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { + BasicBlock *Succ = Term->getSuccessor(i); - LoopEnd = BB; - if (Visited[Succ] < LoopIdx) { - LoopIdx = Visited[Succ]; - LoopStart = Succ; + if (Visited.count(Succ)) + LoopEnd = BB; } } } /// \brief Collect various loop and predicate infos void AMDGPUStructurizeCFG::collectInfos() { - unsigned Number = 0, LoopIdx = ~0; + unsigned Number = 0; // Reset predicate Predicates.clear(); // and loop infos LoopStart = LoopEnd = 0; + LoopTargets.clear(); LoopPred.clear(); - RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend(); - for (Visited.clear(); OI != OE; Visited[(*OI++)->getEntry()] = ++Number) { + // Reset the visited nodes + Visited.clear(); + + for (RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend(); + OI != OE; ++OI) { // Analyze all the conditions leading to a node - analyzeBlock((*OI)->getEntry()); + analyzeNode(*OI); - if ((*OI)->isSubRegion()) - continue; + // Remember that we've seen this node + Visited[(*OI)->getEntry()] = ++Number; - // Find the first/last loop nodes and loop predicates - analyzeLoop((*OI)->getNodeAs(), LoopIdx); + // Find the last back edge + analyzeLoopEnd(*OI); + } + + // Both or neither must be set + assert(!LoopStart == !LoopEnd); +} + +/// \brief Insert the missing branch conditions +void AMDGPUStructurizeCFG::insertConditions() { + SSAUpdater PhiInserter; + + for (BranchVector::iterator I = Conditions.begin(), + E = Conditions.end(); I != E; ++I) { + + BranchInst *Term = *I; + BasicBlock *Parent = Term->getParent(); + + assert(Term->isConditional()); + + PhiInserter.Initialize(Boolean, ""); + if (Parent == LoopEnd) { + PhiInserter.AddAvailableValue(LoopStart, BoolTrue); + } else { + PhiInserter.AddAvailableValue(&Func->getEntryBlock(), BoolFalse); + PhiInserter.AddAvailableValue(Parent, BoolFalse); + } + + bool ParentHasValue = false; + BasicBlock *Succ = Term->getSuccessor(0); + BBPredicates &Preds = (Parent == LoopEnd) ? LoopPred : Predicates[Succ]; + for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); + PI != PE; ++PI) { + + PhiInserter.AddAvailableValue(PI->first, PI->second); + ParentHasValue |= PI->first == Parent; + } + + if (ParentHasValue) + Term->setCondition(PhiInserter.GetValueAtEndOfBlock(Parent)); + else + Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent)); } } @@ -474,7 +573,6 @@ RegionNode *AMDGPUStructurizeCFG::skipChained(RegionNode *Node) { assert(I != E); killTerminator(BB); - FlowsInserted.push_back(BB); Visited.erase(Succ); Order.erase(I); return ParentRegion->getNode(wireFlowBlock(BB, Next)); @@ -489,7 +587,6 @@ BasicBlock *AMDGPUStructurizeCFG::getNextFlow(BasicBlock *Prev) { Func, Insert); DT->addNewBlock(Flow, Prev); ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion); - FlowsInserted.push_back(Flow); return Flow; } @@ -517,10 +614,8 @@ BasicBlock *AMDGPUStructurizeCFG::wireFlowBlock(BasicBlock *Prev, RegionNode *Node) { BasicBlock *Entry = Node->getEntry(); - if (LoopStart == Entry) { + if (LoopStart == Entry) LoopStart = Prev; - LoopPred[Prev] = BoolTrue; - } // Wire it up temporary, skipChained may recurse into us BranchInst::Create(Entry, Prev); @@ -533,7 +628,7 @@ BasicBlock *AMDGPUStructurizeCFG::wireFlowBlock(BasicBlock *Prev, if (!isPredictableTrue(Prev, Entry)) { // Let Prev point to entry and next block Prev->getTerminator()->eraseFromParent(); - BranchInst::Create(Entry, Next, BoolUndef, Prev); + Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Prev)); } else { DT->changeImmediateDominator(Next, Entry); } @@ -591,7 +686,6 @@ void AMDGPUStructurizeCFG::createFlow() { ParentRegion->getRegionInfo()->setRegionFor(Split, ParentRegion); Predicates[Split] = Predicates[Prev]; Order.push_back(ParentRegion->getBBNode(Split)); - LoopPred[Prev] = BoolTrue; } else if (LoopStart == Order.back()->getEntry()) { // Loop starts behind entry, split entry so that we can jump to it @@ -603,8 +697,6 @@ void AMDGPUStructurizeCFG::createFlow() { } killTerminator(Prev); - FlowsInserted.clear(); - FlowsInserted.push_back(Prev); while (!Order.empty()) { RegionNode *Node = Order.pop_back_val(); @@ -614,7 +706,8 @@ void AMDGPUStructurizeCFG::createFlow() { // Create an extra loop end node LoopEnd = Prev; Prev = getNextFlow(LoopEnd); - BranchInst::Create(Prev, LoopStart, BoolUndef, LoopEnd); + Conditions.push_back(BranchInst::Create(Prev, LoopStart, + BoolUndef, LoopEnd)); addPhiValues(LoopEnd, LoopStart); } } @@ -629,32 +722,6 @@ void AMDGPUStructurizeCFG::createFlow() { assert(Visited.empty()); } -/// \brief Insert the missing branch conditions -void AMDGPUStructurizeCFG::insertConditions() { - SSAUpdater PhiInserter; - - for (BBVector::iterator FI = FlowsInserted.begin(), FE = FlowsInserted.end(); - FI != FE; ++FI) { - - BranchInst *Term = cast((*FI)->getTerminator()); - if (Term->isUnconditional()) - continue; - - PhiInserter.Initialize(Boolean, ""); - PhiInserter.AddAvailableValue(&Func->getEntryBlock(), BoolFalse); - - BasicBlock *Succ = Term->getSuccessor(0); - BBPredicates &Preds = (*FI == LoopEnd) ? LoopPred : Predicates[Succ]; - for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); - PI != PE; ++PI) { - - PhiInserter.AddAvailableValue(PI->first, PI->second); - } - - Term->setCondition(PhiInserter.GetValueAtEndOfBlock(*FI)); - } -} - /// Handle a rare case where the disintegrated nodes instructions /// no longer dominate all their uses. Not sure if this is really nessasary void AMDGPUStructurizeCFG::rebuildSSA() { @@ -714,12 +781,15 @@ bool AMDGPUStructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { setPhiValues(); rebuildSSA(); + // Cleanup Order.clear(); Visited.clear(); Predicates.clear(); DeletedPhis.clear(); AddedPhis.clear(); - FlowsInserted.clear(); + Conditions.clear(); + LoopTargets.clear(); + LoopPred.clear(); return true; } -- 2.7.4