-/// GetValueForBlock - Get the value to use within the specified basic block.
-/// available values are in Phis.
-Value *LCSSA::GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst,
- DenseMap<DomTreeNode*, Value*> &Phis) {
- // If there is no dominator info for this BB, it is unreachable.
- if (BB == 0)
- return UndefValue::get(OrigInst->getType());
-
- // If we have already computed this value, return the previously computed val.
- if (Phis.count(BB)) return Phis[BB];
-
- DomTreeNode *IDom = BB->getIDom();
-
- // Otherwise, there are two cases: we either have to insert a PHI node or we
- // don't. We need to insert a PHI node if this block is not dominated by one
- // of the exit nodes from the loop (the loop could have multiple exits, and
- // though the value defined *inside* the loop dominated all its uses, each
- // exit by itself may not dominate all the uses).
- //
- // The simplest way to check for this condition is by checking to see if the
- // idom is in the loop. If so, we *know* that none of the exit blocks
- // dominate this block. Note that we *know* that the block defining the
- // original instruction is in the idom chain, because if it weren't, then the
- // original value didn't dominate this use.
- if (!inLoop(IDom->getBlock())) {
- // Idom is not in the loop, we must still be "below" the exit block and must
- // be fully dominated by the value live in the idom.
- Value* val = GetValueForBlock(IDom, OrigInst, Phis);
- Phis.insert(std::make_pair(BB, val));
- return val;
+/// Process a loop nest depth first.
+bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
+ ScalarEvolution *SE) {
+ bool Changed = false;
+
+ // Recurse depth-first through inner loops.
+ for (Loop::iterator I = L.begin(), E = L.end(); I != E; ++I)
+ Changed |= formLCSSARecursively(**I, DT, LI, SE);
+
+ Changed |= formLCSSA(L, DT, LI, SE);
+ return Changed;
+}
+
+namespace {
+struct LCSSA : public FunctionPass {
+ static char ID; // Pass identification, replacement for typeid
+ LCSSA() : FunctionPass(ID) {
+ initializeLCSSAPass(*PassRegistry::getPassRegistry());
+ }
+
+ // Cached analysis information for the current function.
+ DominatorTree *DT;
+ LoopInfo *LI;
+ ScalarEvolution *SE;
+
+ bool runOnFunction(Function &F) override;
+
+ /// This transformation requires natural loop information & requires that
+ /// loop preheaders be inserted into the CFG. It maintains both of these,
+ /// as well as the CFG. It also requires dominator information.
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.setPreservesCFG();
+
+ AU.addRequired<DominatorTreeWrapperPass>();
+ AU.addRequired<LoopInfoWrapperPass>();
+ AU.addPreservedID(LoopSimplifyID);
+ AU.addPreserved<AliasAnalysis>();
+ AU.addPreserved<ScalarEvolution>();