#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SCCIterator.h"
+#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/RegionIterator.h"
#include "llvm/Analysis/RegionPass.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
using namespace llvm;
Region *ParentRegion;
DominatorTree *DT;
+ LoopInfo *LI;
RNVector Order;
BBSet Visited;
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequiredID(LowerSwitchID);
AU.addRequired<DominatorTreeWrapperPass>();
+ AU.addRequired<LoopInfoWrapperPass>();
AU.addPreserved<DominatorTreeWrapperPass>();
RegionPass::getAnalysisUsage(AU);
}
/// \brief Build up the general order of nodes
void StructurizeCFG::orderNodes() {
- scc_iterator<Region *> I = scc_begin(ParentRegion);
- for (Order.clear(); !I.isAtEnd(); ++I) {
- const std::vector<RegionNode *> &Nodes = *I;
- Order.append(Nodes.begin(), Nodes.end());
+ RNVector TempOrder;
+ ReversePostOrderTraversal<Region*> RPOT(ParentRegion);
+ TempOrder.append(RPOT.begin(), RPOT.end());
+
+ std::map<Loop*, unsigned> LoopBlocks;
+
+
+ // The reverse post-order traversal of the list gives us an ordering close
+ // to what we want. The only problem with it is that sometimes backedges
+ // for outer loops will be visited before backedges for inner loops.
+ for (RegionNode *RN : TempOrder) {
+ BasicBlock *BB = RN->getEntry();
+ Loop *Loop = LI->getLoopFor(BB);
+ if (!LoopBlocks.count(Loop)) {
+ LoopBlocks[Loop] = 1;
+ continue;
+ }
+ LoopBlocks[Loop]++;
}
+
+ unsigned CurrentLoopDepth = 0;
+ Loop *CurrentLoop = nullptr;
+ BBSet TempVisited;
+ for (RNVector::iterator I = TempOrder.begin(), E = TempOrder.end(); I != E; ++I) {
+ BasicBlock *BB = (*I)->getEntry();
+ unsigned LoopDepth = LI->getLoopDepth(BB);
+
+ if (std::find(Order.begin(), Order.end(), *I) != Order.end())
+ continue;
+
+ if (LoopDepth < CurrentLoopDepth) {
+ // Make sure we have visited all blocks in this loop before moving back to
+ // the outer loop.
+
+ RNVector::iterator LoopI = I;
+ while(LoopBlocks[CurrentLoop]) {
+ LoopI++;
+ BasicBlock *LoopBB = (*LoopI)->getEntry();
+ if (LI->getLoopFor(LoopBB) == CurrentLoop) {
+ LoopBlocks[CurrentLoop]--;
+ Order.push_back(*LoopI);
+ }
+ }
+ }
+
+ CurrentLoop = LI->getLoopFor(BB);
+ if (CurrentLoop) {
+ LoopBlocks[CurrentLoop]--;
+ }
+
+ CurrentLoopDepth = LoopDepth;
+ Order.push_back(*I);
+ }
+
+ // This pass originally used a post-order traversal and then operated on
+ // the list in reverse. Now that we are using a reverse post-order traversal
+ // rather than re-working the whole pass to operate on the list in order,
+ // we just reverse the list and continue to operate on it in reverse.
+ std::reverse(Order.begin(), Order.end());
}
/// \brief Determine the end of the loops
BasicBlock *BB = N->getNodeAs<BasicBlock>();
BranchInst *Term = cast<BranchInst>(BB->getTerminator());
- for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
- BasicBlock *Succ = Term->getSuccessor(i);
-
+ for (BasicBlock *Succ : Term->successors())
if (Visited.count(Succ))
Loops[Succ] = BB;
- }
}
}
BBPredicates &Pred = Predicates[BB];
BBPredicates &LPred = LoopPreds[BB];
- for (BasicBlock *Predecessor : predecessors(BB)) {
+ for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+ PI != PE; ++PI) {
+
// Ignore it if it's a branch from outside into our region entry
- if (!ParentRegion->contains(Predecessor))
+ if (!ParentRegion->contains(*PI))
continue;
- Region *R = RI->getRegionFor(Predecessor);
+ Region *R = RI->getRegionFor(*PI);
if (R == ParentRegion) {
// It's a top level block in our region
- BranchInst *Term = cast<BranchInst>(Predecessor->getTerminator());
+ 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;
- if (Visited.count(Predecessor)) {
+ 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) && !Loops.count(Other) &&
- !Pred.count(Other) && !Pred.count(Predecessor)) {
+ !Pred.count(Other) && !Pred.count(*PI)) {
Pred[Other] = BoolFalse;
- Pred[Predecessor] = BoolTrue;
+ Pred[*PI] = BoolTrue;
continue;
}
}
- Pred[Predecessor] = buildCondition(Term, i, false);
+ Pred[*PI] = buildCondition(Term, i, false);
} else {
// Back edge
- LPred[Predecessor] = buildCondition(Term, i, true);
+ LPred[*PI] = buildCondition(Term, i, true);
}
}
for (RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend();
OI != OE; ++OI) {
+ DEBUG(dbgs() << "Visiting: " <<
+ ((*OI)->isSubRegion() ? "SubRegion with entry: " : "") <<
+ (*OI)->getEntry()->getName() << " Loop Depth: " << LI->getLoopDepth((*OI)->getEntry()) << "\n");
+
// Analyze all the conditions leading to a node
gatherPredicates(*OI);
if (!Term)
return;
- for (BasicBlock *Succ : successors(BB))
- delPhiValues(BB, Succ);
+ for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
+ SI != SE; ++SI) {
+
+ delPhiValues(BB, *SI);
+ }
Term->eraseFromParent();
}
BasicBlock *Dominator = nullptr;
// Find all the edges from the sub region to the exit
- for (BasicBlock *BB : predecessors(OldExit)) {
+ for (pred_iterator I = pred_begin(OldExit), E = pred_end(OldExit);
+ I != E;) {
+
+ BasicBlock *BB = *I++;
if (!SubRegion->contains(BB))
continue;
/// no longer dominate all their uses. Not sure if this is really nessasary
void StructurizeCFG::rebuildSSA() {
SSAUpdater Updater;
- for (const auto &BB : ParentRegion->blocks())
+ for (auto *BB : ParentRegion->blocks())
for (BasicBlock::iterator II = BB->begin(), IE = BB->end();
II != IE; ++II) {
continue;
}
- if (DT->dominates(II, User))
+ if (DT->dominates(&*II, User))
continue;
if (!Initialized) {
Value *Undef = UndefValue::get(II->getType());
Updater.Initialize(II->getType(), "");
Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
- Updater.AddAvailableValue(BB, II);
+ Updater.AddAvailableValue(BB, &*II);
Initialized = true;
}
Updater.RewriteUseAfterInsertions(U);
ParentRegion = R;
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+ LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
orderNodes();
collectInfos();
projects / oota-llvm.git / blobdiff