[Mesa-dev] [PATCH 3/3] R600: fix assumption in the CFG structurizers loop handling
Christian König
deathsimple at vodafone.de
Thu Jan 24 04:46:38 PST 2013
From: Christian König <christian.koenig at amd.com>
The loop handling in the CFG structurizer incorrectly assumed
that only BasicBlock nodes can have a back edge, but that is
also possible for the exit edges of subregions.
Fixing 4 more piglit tests on radeonsi.
Signed-off-by: Christian König <christian.koenig at amd.com>
---
lib/Target/R600/AMDGPUStructurizeCFG.cpp | 135 ++++++++++++++++++------------
1 file changed, 81 insertions(+), 54 deletions(-)
diff --git a/lib/Target/R600/AMDGPUStructurizeCFG.cpp b/lib/Target/R600/AMDGPUStructurizeCFG.cpp
index 70622e7..9528fc2 100644
--- a/lib/Target/R600/AMDGPUStructurizeCFG.cpp
+++ b/lib/Target/R600/AMDGPUStructurizeCFG.cpp
@@ -120,9 +120,9 @@ class AMDGPUStructurizeCFG : public RegionPass {
void buildPredicate(BranchInst *Term, unsigned Idx,
BBPredicates &Pred, bool Invert);
- void analyzeBlock(BasicBlock *BB);
+ void analyzeNode(RegionNode *N);
- void analyzeLoop(BasicBlock *BB, unsigned &LoopIdx);
+ void analyzeLoop(RegionNode *N);
void collectInfos();
@@ -227,72 +227,92 @@ void AMDGPUStructurizeCFG::buildPredicate(BranchInst *Term, unsigned Idx,
Pred[Parent] = Cond;
}
-/// \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);
+/// \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];
- for (; PI != PE; ++PI) {
+ for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+ PI != PE; ++PI) {
+
+ // Handle the case where multiple regions start at the same block
+ Region *R = *PI != ParentRegion->getEntry() ?
+ RI->getRegionFor(*PI) : ParentRegion;
- // Ignore self loops
- if (*PI == BB)
+ // Edge from inside a subregion to its entry, ignore it
+ if (R == N)
continue;
- BranchInst *Term = cast<BranchInst>((*PI)->getTerminator());
+ if (R == ParentRegion) {
- for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
- BasicBlock *Succ = Term->getSuccessor(i);
- if (Succ != BB)
- continue;
+ // It's a top level block in our region
+ BranchInst *Term = cast<BranchInst>((*PI)->getTerminator());
+ for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
+ BasicBlock *Succ = Term->getSuccessor(i);
+ if (Succ != BB)
+ continue;
+
+ // Ignore self loops
+ if (*PI != BB)
+ buildPredicate(Term, i, Pred, false);
+
+ if (!Visited.count(*PI)) {
+ if (!LoopStart)
+ LoopStart = BB;
- // Handle the case where multiple regions start at the same block
- Region *R = *PI != ParentRegion->getEntry() ?
- RI->getRegionFor(*PI) : ParentRegion;
+ buildPredicate(Term, i, LoopPred, true);
+ }
+ }
- if (R == ParentRegion) {
- // It's a top level block in our region
- buildPredicate(Term, i, Pred, false);
+ } else if (ParentRegion->contains(R)) {
- } else if (ParentRegion->contains(R)) {
- // It's a block in a sub region
- while(R->getParent() != ParentRegion)
- R = R->getParent();
+ // It's an exit from a sub region
+ while(R->getParent() != ParentRegion)
+ R = R->getParent();
- Pred[R->getEntry()] = BoolTrue;
+ BasicBlock *Entry = R->getEntry();
+ Pred[Entry] = BoolTrue;
+ if (!Visited.count(Entry)) {
+ if (!LoopStart)
+ LoopStart = BB;
- } else {
- // It's a branch from outside into our parent region
- Pred[*PI] = BoolTrue;
+ LoopPred[Entry] = BoolFalse;
}
+
+ } else {
+ // It's a branch from outside into our entry region
+ Pred[*PI] = BoolTrue;
}
}
}
-/// \brief Analyze the conditions leading to loop to a previous block
-void AMDGPUStructurizeCFG::analyzeLoop(BasicBlock *BB, unsigned &LoopIdx) {
- BranchInst *Term = cast<BranchInst>(BB->getTerminator());
+/// \brief Determine the end of the loop
+void AMDGPUStructurizeCFG::analyzeLoop(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<Region>()->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<BasicBlock>();
+ BranchInst *Term = cast<BranchInst>(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();
@@ -304,17 +324,17 @@ void AMDGPUStructurizeCFG::collectInfos() {
RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend();
for (Visited.clear(); OI != OE; ++OI) {
- Visited[(*OI)->getEntry()] = ++Number;
-
// Analyze all the conditions leading to a node
- analyzeBlock((*OI)->getEntry());
+ analyzeNode(*OI);
- if ((*OI)->isSubRegion())
- continue;
+ Visited[(*OI)->getEntry()] = ++Number;
- // Find the first/last loop nodes and loop predicates
- analyzeLoop((*OI)->getNodeAs<BasicBlock>(), LoopIdx);
+ // Find the last loop node
+ analyzeLoop(*OI);
}
+
+ // Both or neither must be set
+ assert(!LoopStart == !LoopEnd);
}
/// \brief Does A dominate all the predicates of B ?
@@ -355,6 +375,9 @@ RegionNode *AMDGPUStructurizeCFG::skipChained(RegionNode *Node) {
// Skip forward as long as it is just a linear flow
while (true) {
BasicBlock *Entry = Node->getEntry();
+ if (Entry == LoopEnd)
+ return Node;
+
BasicBlock *Exit;
if (Node->isSubRegion()) {
@@ -502,10 +525,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);
@@ -545,6 +566,9 @@ BasicBlock *AMDGPUStructurizeCFG::wireFlowBlock(BasicBlock *Prev,
// Update the region info
SubRegion->replaceExit(Next);
+ if (SubRegion->getEntry() == LoopEnd)
+ LoopEnd = 0;
+
} else {
BasicBlock *BB = Node->getNodeAs<BasicBlock>();
killTerminator(BB);
@@ -575,7 +599,6 @@ void AMDGPUStructurizeCFG::createFlow() {
ParentRegion->getRegionInfo()->setRegionFor(Split, ParentRegion);
Predicates[Split] = Predicates[Prev];
Order.push_back(ParentRegion->getBBNode(Split));
- LoopPred[Prev] = BoolTrue;
if (LoopEnd == Prev)
LoopEnd = Split;
@@ -636,10 +659,14 @@ void AMDGPUStructurizeCFG::insertConditions() {
if (Term->isUnconditional())
continue;
+ BasicBlock *Succ = Term->getSuccessor(0);
+
PhiInserter.Initialize(Boolean, "");
- PhiInserter.AddAvailableValue(&Func->getEntryBlock(), BoolFalse);
+ if (*FI == LoopEnd)
+ PhiInserter.AddAvailableValue(LoopStart, BoolTrue);
+ else
+ 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) {
--
1.7.9.5
More information about the mesa-dev
mailing list