LoopSimplify.cpp revision 90c579de5a383cee278acc3f7e7b9d0a656e6a35
167a9801bc510ff2c28068361fb30ae397fd1e026Chris Lattner//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman//
3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//                     The LLVM Compiler Infrastructure
4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//
54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source
64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details.
7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman//
8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===//
938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner//
10ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// This pass performs several transformations to transform natural loops into a
11ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// simpler form, which makes subsequent analyses and transformations simpler and
12ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// more effective.
13dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner//
14dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Loop pre-header insertion guarantees that there is a single, non-critical
15dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// entry edge from outside of the loop to the loop header.  This simplifies a
16dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// number of analyses and transformations, such as LICM.
17dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner//
18dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Loop exit-block insertion guarantees that all exit blocks from the loop
19dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// (blocks which are outside of the loop that have predecessors inside of the
2066ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner// loop) only have predecessors from inside of the loop (and are thus dominated
2166ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner// by the loop header).  This simplifies transformations such as store-sinking
2266ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner// that are built into LICM.
23dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner//
242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner// This pass also guarantees that loops will have exactly one backedge.
252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner//
26f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman// Indirectbr instructions introduce several complications. If the loop
27f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman// contains or is entered by an indirectbr instruction, it may not be possible
28f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman// to transform the loop and make these guarantees. Client code should check
29f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman// that these conditions are true before relying on them.
30f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman//
31dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Note that the simplifycfg pass will clean up blocks which are split out but
32ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// end up being unnecessary, so usage of this pass should not pessimize
33ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// generated code.
34ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner//
35ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// This pass obviously modifies the CFG, but updates loop information and
36ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// dominator information.
3738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner//
3838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner//===----------------------------------------------------------------------===//
3938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner
40d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner#define DEBUG_TYPE "loopsimplify"
4138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Transforms/Scalar.h"
423cb63ddd5183a1469e4557b3e22735ed3ace05b2Chris Lattner#include "llvm/Constants.h"
4347b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h"
44689fac02268929b756086753b4656d6dabc5cf2dDevang Patel#include "llvm/IntrinsicInst.h"
452ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Function.h"
460a205a459884ec745df1c529396dd921f029dafdOwen Anderson#include "llvm/LLVMContext.h"
472ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Type.h"
48cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner#include "llvm/Analysis/AliasAnalysis.h"
490f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner#include "llvm/Analysis/Dominators.h"
50d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman#include "llvm/Analysis/LoopPass.h"
51d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman#include "llvm/Analysis/ScalarEvolution.h"
5254b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h"
534b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman#include "llvm/Transforms/Utils/Local.h"
5438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Support/CFG.h"
55c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman#include "llvm/Support/Debug.h"
56551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetOperations.h"
57551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetVector.h"
58551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h"
59551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h"
6066ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattnerusing namespace llvm;
61d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke
62d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumInserted, "Number of pre-header or exit blocks inserted");
63d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumNested  , "Number of nested loops split out");
6438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner
65d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattnernamespace {
666726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky  struct LoopSimplify : public LoopPass {
67ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky    static char ID; // Pass identification, replacement for typeid
6890c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson    LoopSimplify() : LoopPass(ID) {}
69794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel
70cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner    // AA - If we have an alias analysis object to update, this is it, otherwise
71cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner    // this is null.
72cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner    AliasAnalysis *AA;
73c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner    LoopInfo *LI;
740e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel    DominatorTree *DT;
75d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman    Loop *L;
76d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman    virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
77fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman
7838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
7938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner      // We need loop information to identify the loops...
80052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman      AU.addRequired<DominatorTree>();
8138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner      AU.addPreserved<DominatorTree>();
821e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman
83052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman      AU.addRequired<LoopInfo>();
841e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman      AU.addPreserved<LoopInfo>();
851e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman
864c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel      AU.addPreserved<AliasAnalysis>();
87d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman      AU.addPreserved<ScalarEvolution>();
8894f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner      AU.addPreservedID(BreakCriticalEdgesID);  // No critical edges added.
89052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman      AU.addPreserved<DominanceFrontier>();
90052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman      AU.addPreservedID(LCSSAID);
9138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner    }
9258e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel
93f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
94f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    void verifyAnalysis() const;
9558e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel
9638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner  private:
97d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman    bool ProcessLoop(Loop *L, LPPassManager &LPM);
9859fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner    BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
990df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman    BasicBlock *InsertPreheaderForLoop(Loop *L);
100d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman    Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM);
101f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader);
102120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner    void PlaceSplitBlockCarefully(BasicBlock *NewBB,
10354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner                                  SmallVectorImpl<BasicBlock*> &SplitPreds,
104120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner                                  Loop *L);
10538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner  };
10638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner}
10738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner
108844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopSimplify::ID = 0;
109844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LoopSimplify>
110844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("loopsimplify", "Canonicalize natural loops", true);
111844731a7f1909f55935e3514c9e713a62d67662eDan Gohman
11238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// Publically exposed interface to pass...
11390c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::LoopSimplifyID = LoopSimplify::ID;
114d84db1133345234738b646c70b907bf8a0983ac9Dan GohmanPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
11538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner
11634d2b90d09226ebf6189775acfd2801e127b10ecDan Gohman/// runOnLoop - Run down all loops in the CFG (recursively, but we could do
11738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// it in any convenient order) inserting preheaders...
11838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner///
119d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) {
120d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman  L = l;
12138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner  bool Changed = false;
122c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner  LI = &getAnalysis<LoopInfo>();
1231465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands  AA = getAnalysisIfAvailable<AliasAnalysis>();
1240e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel  DT = &getAnalysis<DominatorTree>();
12538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner
126d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman  Changed |= ProcessLoop(L, LPM);
12738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner
12838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner  return Changed;
12938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner}
13038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner
13138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// ProcessLoop - Walk the loop structure in depth first order, ensuring that
13238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// all loops have preheaders.
13338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner///
134d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) {
13538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner  bool Changed = false;
1363bb4657488f700bbe3376fb547017163b8fbbd8fChris LattnerReprocessLoop:
137d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman
1382d0a91cd6c3df32014d547255d6a615bd1bc84fbDan Gohman  // Check to see that no blocks (other than the header) in this loop have
139d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman  // predecessors that are not in the loop.  This is not valid for natural
140d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman  // loops, but can occur if the blocks are unreachable.  Since they are
141d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman  // unreachable we can just shamelessly delete those CFG edges!
142d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman  for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
143d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman       BB != E; ++BB) {
144d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman    if (*BB == L->getHeader()) continue;
145d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman
146481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif    SmallPtrSet<BasicBlock*, 4> BadPreds;
147481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif    for (pred_iterator PI = pred_begin(*BB),
148481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif         PE = pred_end(*BB); PI != PE; ++PI) {
1499672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif      BasicBlock *P = *PI;
1509672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif      if (!L->contains(P))
1519672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif        BadPreds.insert(P);
1529672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif    }
153d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman
154d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman    // Delete each unique out-of-loop (and thus dead) predecessor.
155481c4c07347c40fa666d09f3b31fbe2ca27e2d52Gabor Greif    for (SmallPtrSet<BasicBlock*, 4>::iterator I = BadPreds.begin(),
156d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman         E = BadPreds.end(); I != E; ++I) {
157c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman
158c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman      DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor ";
159c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman            WriteAsOperand(dbgs(), *I, false);
160c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman            dbgs() << "\n");
161c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman
162d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman      // Inform each successor of each dead pred.
163d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman      for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI)
164d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman        (*SI)->removePredecessor(*I);
165d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman      // Zap the dead pred's terminator and replace it with unreachable.
166d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman      TerminatorInst *TI = (*I)->getTerminator();
167d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman       TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
168d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman      (*I)->getTerminator()->eraseFromParent();
169d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman      new UnreachableInst((*I)->getContext(), *I);
170d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman      Changed = true;
171d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman    }
172d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman  }
1732ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner
17485669637139089eaed8def1583ac04266c9654e2Dan Gohman  // If there are exiting blocks with branches on undef, resolve the undef in
17585669637139089eaed8def1583ac04266c9654e2Dan Gohman  // the direction which will exit the loop. This will help simplify loop
17685669637139089eaed8def1583ac04266c9654e2Dan Gohman  // trip count computations.
17785669637139089eaed8def1583ac04266c9654e2Dan Gohman  SmallVector<BasicBlock*, 8> ExitingBlocks;
17885669637139089eaed8def1583ac04266c9654e2Dan Gohman  L->getExitingBlocks(ExitingBlocks);
17985669637139089eaed8def1583ac04266c9654e2Dan Gohman  for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
18085669637139089eaed8def1583ac04266c9654e2Dan Gohman       E = ExitingBlocks.end(); I != E; ++I)
18185669637139089eaed8def1583ac04266c9654e2Dan Gohman    if (BranchInst *BI = dyn_cast<BranchInst>((*I)->getTerminator()))
18285669637139089eaed8def1583ac04266c9654e2Dan Gohman      if (BI->isConditional()) {
18385669637139089eaed8def1583ac04266c9654e2Dan Gohman        if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
184c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman
185c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman          DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in ";
186c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman                WriteAsOperand(dbgs(), *I, false);
187c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman                dbgs() << "\n");
188c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman
18985669637139089eaed8def1583ac04266c9654e2Dan Gohman          BI->setCondition(ConstantInt::get(Cond->getType(),
19085669637139089eaed8def1583ac04266c9654e2Dan Gohman                                            !L->contains(BI->getSuccessor(0))));
19185669637139089eaed8def1583ac04266c9654e2Dan Gohman          Changed = true;
19285669637139089eaed8def1583ac04266c9654e2Dan Gohman        }
19385669637139089eaed8def1583ac04266c9654e2Dan Gohman      }
19485669637139089eaed8def1583ac04266c9654e2Dan Gohman
195fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner  // Does the loop already have a preheader?  If so, don't insert one.
1960df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman  BasicBlock *Preheader = L->getLoopPreheader();
1970df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman  if (!Preheader) {
1980df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman    Preheader = InsertPreheaderForLoop(L);
199f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    if (Preheader) {
200fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman      ++NumInserted;
201f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      Changed = true;
202f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    }
20338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner  }
20438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner
20566ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner  // Next, check to make sure that all exit nodes of the loop only have
20666ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner  // predecessors that are inside of the loop.  This check guarantees that the
20766ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner  // loop preheader/header will dominate the exit blocks.  If the exit block has
208ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner  // predecessors from outside of the loop, split the edge now.
209b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel  SmallVector<BasicBlock*, 8> ExitBlocks;
210ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner  L->getExitBlocks(ExitBlocks);
211c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner
21217146baef5b79114f05e0f99fcba389f2764b65dDan Gohman  SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(),
21317146baef5b79114f05e0f99fcba389f2764b65dDan Gohman                                               ExitBlocks.end());
21417146baef5b79114f05e0f99fcba389f2764b65dDan Gohman  for (SmallSetVector<BasicBlock *, 8>::iterator I = ExitBlockSet.begin(),
215fed22aac4337c589841c443be70fe05559693f6aChris Lattner         E = ExitBlockSet.end(); I != E; ++I) {
216fed22aac4337c589841c443be70fe05559693f6aChris Lattner    BasicBlock *ExitBlock = *I;
217de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner    for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
218de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner         PI != PE; ++PI)
2198587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner      // Must be exactly this loop: no subloops, parent loops, or non-loop preds
2208587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner      // allowed.
221ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner      if (!L->contains(*PI)) {
222f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman        if (RewriteLoopExitBlock(L, ExitBlock)) {
223fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman          ++NumInserted;
224f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman          Changed = true;
225f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman        }
226de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner        break;
227de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner      }
228fed22aac4337c589841c443be70fe05559693f6aChris Lattner  }
229dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner
230529b28da455a703d226a31a03400e6662ff569feChris Lattner  // If the header has more than two predecessors at this point (from the
231529b28da455a703d226a31a03400e6662ff569feChris Lattner  // preheader and from multiple backedges), we must adjust the loop.
232f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  BasicBlock *LoopLatch = L->getLoopLatch();
233f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  if (!LoopLatch) {
2343bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner    // If this is really a nested loop, rip it out into a child loop.  Don't do
2353bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner    // this for loops with a giant number of backedges, just factor them into a
2363bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner    // common backedge instead.
237f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    if (L->getNumBackEdges() < 8) {
238d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman      if (SeparateNestedLoop(L, LPM)) {
2393bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner        ++NumNested;
2403bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner        // This is a big restructuring change, reprocess the whole loop.
2413bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner        Changed = true;
2423bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner        // GCC doesn't tail recursion eliminate this.
2433bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner        goto ReprocessLoop;
2443bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner      }
245529b28da455a703d226a31a03400e6662ff569feChris Lattner    }
246529b28da455a703d226a31a03400e6662ff569feChris Lattner
2473bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner    // If we either couldn't, or didn't want to, identify nesting of the loops,
2483bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner    // insert a new block that all backedges target, then make it jump to the
2493bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner    // loop header.
250f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    LoopLatch = InsertUniqueBackedgeBlock(L, Preheader);
251f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    if (LoopLatch) {
252fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman      ++NumInserted;
253f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      Changed = true;
254f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    }
2552ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  }
2562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
25794f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner  // Scan over the PHI nodes in the loop header.  Since they now have only two
25894f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner  // incoming values (the loop is canonicalized), we may have simplified the PHI
25994f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner  // down to 'X = phi [X, Y]', which should be replaced with 'Y'.
26094f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner  PHINode *PN;
26194f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner  for (BasicBlock::iterator I = L->getHeader()->begin();
26294f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner       (PN = dyn_cast<PHINode>(I++)); )
263bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman    if (Value *V = PN->hasConstantValue(DT)) {
2644c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel      if (AA) AA->deleteValue(PN);
2654c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel      PN->replaceAllUsesWith(V);
2664c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel      PN->eraseFromParent();
2674c37c07ee3bfacaaf90ea57165ef6855b4ed8b22Devang Patel    }
26894f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner
2695cd8770412f98f6e6416c439e01222b3643b9e22Bob Wilson  // If this loop has multiple exits and the exits all go to the same
2704b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman  // block, attempt to merge the exits. This helps several passes, such
2714b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman  // as LoopRotation, which do not support loops with multiple exits.
2724b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman  // SimplifyCFG also does this (and this code uses the same utility
2734b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman  // function), however this code is loop-aware, where SimplifyCFG is
2744b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman  // not. That gives it the advantage of being able to hoist
2754b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman  // loop-invariant instructions out of the way to open up more
2764b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman  // opportunities, and the disadvantage of having the responsibility
2774b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman  // to preserve dominator information.
278b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman  bool UniqueExit = true;
279b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman  if (!ExitBlocks.empty())
280b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman    for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i)
281b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman      if (ExitBlocks[i] != ExitBlocks[0]) {
282b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman        UniqueExit = false;
283b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman        break;
284b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman      }
285b1dc915a8d4971880a016e678ccf563d1a03a916Dan Gohman  if (UniqueExit) {
2864b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman    for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
2874b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      BasicBlock *ExitingBlock = ExitingBlocks[i];
2884b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      if (!ExitingBlock->getSinglePredecessor()) continue;
2894b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
2904b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      if (!BI || !BI->isConditional()) continue;
2914b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
2924b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      if (!CI || CI->getParent() != ExitingBlock) continue;
2934b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman
2944b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      // Attempt to hoist out all instructions except for the
2954b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      // comparison and the branch.
2964b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      bool AllInvariant = true;
2972aa93efa0c983449e5464165e80ebd9c0fb5f6c1Dan Gohman      for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) {
2984b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman        Instruction *Inst = I++;
299689fac02268929b756086753b4656d6dabc5cf2dDevang Patel        // Skip debug info intrinsics.
300689fac02268929b756086753b4656d6dabc5cf2dDevang Patel        if (isa<DbgInfoIntrinsic>(Inst))
301689fac02268929b756086753b4656d6dabc5cf2dDevang Patel          continue;
3022aa93efa0c983449e5464165e80ebd9c0fb5f6c1Dan Gohman        if (Inst == CI)
3034b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman          continue;
304f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman        if (!L->makeLoopInvariant(Inst, Changed,
305f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman                                  Preheader ? Preheader->getTerminator() : 0)) {
3064b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman          AllInvariant = false;
3074b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman          break;
3084b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman        }
3094b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      }
3104b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      if (!AllInvariant) continue;
3114b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman
3124b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      // The block has now been cleared of all instructions except for
3134b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      // a comparison and a conditional branch. SimplifyCFG may be able
3144b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      // to fold it now.
3154b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      if (!FoldBranchToCommonDest(BI)) continue;
3164b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman
3174b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      // Success. The block is now dead, so remove it from the loop,
3184b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      // update the dominator tree and dominance frontier, and delete it.
319c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman
320c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman      DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block ";
321c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman            WriteAsOperand(dbgs(), ExitingBlock, false);
322c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman            dbgs() << "\n");
323c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman
3244b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock));
3254b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      Changed = true;
326a1baee20c4b042eca1f182fc003f38ab52efc7a9Dan Gohman      LI->removeBlock(ExitingBlock);
3274b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman
3284b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>();
3294b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      DomTreeNode *Node = DT->getNode(ExitingBlock);
3304b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      const std::vector<DomTreeNodeBase<BasicBlock> *> &Children =
3314b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman        Node->getChildren();
3325184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman      while (!Children.empty()) {
3335184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman        DomTreeNode *Child = Children.front();
3345184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman        DT->changeImmediateDominator(Child, Node->getIDom());
3355184635eda68a0cdcd39c958ccc11ba1843bcc7bDan Gohman        if (DF) DF->changeImmediateDominator(Child->getBlock(),
3364b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman                                             Node->getIDom()->getBlock(),
3374b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman                                             DT);
3384b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      }
3394b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      DT->eraseNode(ExitingBlock);
3404b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      if (DF) DF->removeBlock(ExitingBlock);
3414b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman
3424b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      BI->getSuccessor(0)->removePredecessor(ExitingBlock);
3434b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      BI->getSuccessor(1)->removePredecessor(ExitingBlock);
3444b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman      ExitingBlock->eraseFromParent();
3454b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman    }
3464b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman  }
3474b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman
34838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner  return Changed;
34938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner}
35038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner
351dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
352dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader, this method is called to insert one.  This method has two phases:
353dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader insertion and analysis updating.
354dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner///
3550df6e09d43d6d733555a10d22572ddb0006e7d23Dan GohmanBasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) {
356dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner  BasicBlock *Header = L->getHeader();
357dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner
358dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner  // Compute the set of predecessors of the loop that are not in the loop.
35954b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner  SmallVector<BasicBlock*, 8> OutsideBlocks;
360dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner  for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
3619672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif       PI != PE; ++PI) {
3629672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif    BasicBlock *P = *PI;
3639672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif    if (!L->contains(P)) {         // Coming in from outside the loop?
364f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      // If the loop is branched to from an indirect branch, we won't
365f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      // be able to fully transform the loop, because it prohibits
366f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      // edge splitting.
3679672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif      if (isa<IndirectBrInst>(P->getTerminator())) return 0;
368f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman
369f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      // Keep track of it.
3709672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif      OutsideBlocks.push_back(P);
371f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    }
3729672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif  }
373fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman
374c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner  // Split out the loop pre-header.
375dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner  BasicBlock *NewBB =
37654b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner    SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(),
37754b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner                           ".preheader", this);
3789f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner
379c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman  DEBUG(dbgs() << "LoopSimplify: Creating pre-header ";
380c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman        WriteAsOperand(dbgs(), NewBB, false);
381c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman        dbgs() << "\n");
382c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman
383120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // Make sure that NewBB is put someplace intelligent, which doesn't mess up
384120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // code layout too horribly.
385120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L);
3860df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman
3870df6e09d43d6d733555a10d22572ddb0006e7d23Dan Gohman  return NewBB;
388dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner}
389dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner
390529b28da455a703d226a31a03400e6662ff569feChris Lattner/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit
391529b28da455a703d226a31a03400e6662ff569feChris Lattner/// blocks.  This method is used to split exit blocks that have predecessors
392529b28da455a703d226a31a03400e6662ff569feChris Lattner/// outside of the loop.
39359fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris LattnerBasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
39454b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner  SmallVector<BasicBlock*, 8> LoopBlocks;
3959672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif  for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) {
3969672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif    BasicBlock *P = *I;
3979672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif    if (L->contains(P)) {
398f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      // Don't do this if the loop is exited via an indirect branch.
3999672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif      if (isa<IndirectBrInst>(P->getTerminator())) return 0;
400f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman
4019672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif      LoopBlocks.push_back(P);
402f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    }
4039672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif  }
404dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner
4057e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner  assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?");
40654b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner  BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0],
40754b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner                                             LoopBlocks.size(), ".loopexit",
40854b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner                                             this);
4097e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner
410c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman  DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block ";
411c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman        WriteAsOperand(dbgs(), NewBB, false);
412c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman        dbgs() << "\n");
413c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman
41459fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner  return NewBB;
4152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner}
4162ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
417529b28da455a703d226a31a03400e6662ff569feChris Lattner/// AddBlockAndPredsToSet - Add the specified block, and all of its
418529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessors, to the specified set, if it's not already in there.  Stop
419529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessor traversal when we reach StopBlock.
42058d7fbf250659246fcca9417a91170a681b1850aDevang Patelstatic void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
421529b28da455a703d226a31a03400e6662ff569feChris Lattner                                  std::set<BasicBlock*> &Blocks) {
42258d7fbf250659246fcca9417a91170a681b1850aDevang Patel  std::vector<BasicBlock *> WorkList;
42358d7fbf250659246fcca9417a91170a681b1850aDevang Patel  WorkList.push_back(InputBB);
42458d7fbf250659246fcca9417a91170a681b1850aDevang Patel  do {
42558d7fbf250659246fcca9417a91170a681b1850aDevang Patel    BasicBlock *BB = WorkList.back(); WorkList.pop_back();
42658d7fbf250659246fcca9417a91170a681b1850aDevang Patel    if (Blocks.insert(BB).second && BB != StopBlock)
42758d7fbf250659246fcca9417a91170a681b1850aDevang Patel      // If BB is not already processed and it is not a stop block then
42858d7fbf250659246fcca9417a91170a681b1850aDevang Patel      // insert its predecessor in the work list
42958d7fbf250659246fcca9417a91170a681b1850aDevang Patel      for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
43058d7fbf250659246fcca9417a91170a681b1850aDevang Patel        BasicBlock *WBB = *I;
43158d7fbf250659246fcca9417a91170a681b1850aDevang Patel        WorkList.push_back(WBB);
43258d7fbf250659246fcca9417a91170a681b1850aDevang Patel      }
43358d7fbf250659246fcca9417a91170a681b1850aDevang Patel  } while(!WorkList.empty());
434529b28da455a703d226a31a03400e6662ff569feChris Lattner}
435529b28da455a703d226a31a03400e6662ff569feChris Lattner
4361f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
4371f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// PHI node that tells us how to partition the loops.
438dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patelstatic PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT,
439ad190145912facc6fbf2fbe58023bb238fbf2365Owen Anderson                                        AliasAnalysis *AA) {
440200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
441200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos    PHINode *PN = cast<PHINode>(I);
4421f62f82b05563df9c83094608de24ea581014d1eChris Lattner    ++I;
443bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman    if (Value *V = PN->hasConstantValue(DT)) {
444bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman      // This is a degenerate PHI already, don't modify it!
445bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman      PN->replaceAllUsesWith(V);
446bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman      if (AA) AA->deleteValue(PN);
447bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman      PN->eraseFromParent();
448bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman      continue;
449bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman    }
450c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner
451c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner    // Scan this PHI node looking for a use of the PHI node by itself.
452c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
453c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner      if (PN->getIncomingValue(i) == PN &&
454c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner          L->contains(PN->getIncomingBlock(i)))
455c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner        // We found something tasty to remove.
456c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner        return PN;
4571f62f82b05563df9c83094608de24ea581014d1eChris Lattner  }
4581f62f82b05563df9c83094608de24ea581014d1eChris Lattner  return 0;
4591f62f82b05563df9c83094608de24ea581014d1eChris Lattner}
4601f62f82b05563df9c83094608de24ea581014d1eChris Lattner
461120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// PlaceSplitBlockCarefully - If the block isn't already, move the new block to
462120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// right after some 'outside block' block.  This prevents the preheader from
463120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// being placed inside the loop body, e.g. when the loop hasn't been rotated.
464120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattnervoid LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB,
46554b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner                                       SmallVectorImpl<BasicBlock*> &SplitPreds,
466120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner                                            Loop *L) {
467120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // Check to see if NewBB is already well placed.
468120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  Function::iterator BBI = NewBB; --BBI;
469120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
470120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner    if (&*BBI == SplitPreds[i])
471120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner      return;
472120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  }
473120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner
474120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // If it isn't already after an outside block, move it after one.  This is
475120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // always good as it makes the uncond branch from the outside block into a
476120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // fall-through.
477120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner
478120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // Figure out *which* outside block to put this after.  Prefer an outside
479120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // block that neighbors a BB actually in the loop.
480120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  BasicBlock *FoundBB = 0;
481120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
482120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner    Function::iterator BBI = SplitPreds[i];
483120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner    if (++BBI != NewBB->getParent()->end() &&
484120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner        L->contains(BBI)) {
485120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner      FoundBB = SplitPreds[i];
486120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner      break;
487120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner    }
488120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  }
489120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner
490120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // If our heuristic for a *good* bb to place this after doesn't find
491120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // anything, just pick something.  It's likely better than leaving it within
492120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // the loop.
493120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  if (!FoundBB)
494120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner    FoundBB = SplitPreds[0];
495120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  NewBB->moveAfter(FoundBB);
496120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner}
497120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner
498120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner
499529b28da455a703d226a31a03400e6662ff569feChris Lattner/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of
500529b28da455a703d226a31a03400e6662ff569feChris Lattner/// them out into a nested loop.  This is important for code that looks like
501529b28da455a703d226a31a03400e6662ff569feChris Lattner/// this:
502529b28da455a703d226a31a03400e6662ff569feChris Lattner///
503529b28da455a703d226a31a03400e6662ff569feChris Lattner///  Loop:
504529b28da455a703d226a31a03400e6662ff569feChris Lattner///     ...
505529b28da455a703d226a31a03400e6662ff569feChris Lattner///     br cond, Loop, Next
506529b28da455a703d226a31a03400e6662ff569feChris Lattner///     ...
507529b28da455a703d226a31a03400e6662ff569feChris Lattner///     br cond2, Loop, Out
508529b28da455a703d226a31a03400e6662ff569feChris Lattner///
509529b28da455a703d226a31a03400e6662ff569feChris Lattner/// To identify this common case, we look at the PHI nodes in the header of the
510529b28da455a703d226a31a03400e6662ff569feChris Lattner/// loop.  PHI nodes with unchanging values on one backedge correspond to values
511529b28da455a703d226a31a03400e6662ff569feChris Lattner/// that change in the "outer" loop, but not in the "inner" loop.
512529b28da455a703d226a31a03400e6662ff569feChris Lattner///
513529b28da455a703d226a31a03400e6662ff569feChris Lattner/// If we are able to separate out a loop, return the new outer loop that was
514529b28da455a703d226a31a03400e6662ff569feChris Lattner/// created.
515529b28da455a703d226a31a03400e6662ff569feChris Lattner///
516d84db1133345234738b646c70b907bf8a0983ac9Dan GohmanLoop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) {
517dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel  PHINode *PN = FindPHIToPartitionLoops(L, DT, AA);
5181f62f82b05563df9c83094608de24ea581014d1eChris Lattner  if (PN == 0) return 0;  // No known way to partition.
519529b28da455a703d226a31a03400e6662ff569feChris Lattner
5201f62f82b05563df9c83094608de24ea581014d1eChris Lattner  // Pull out all predecessors that have varying values in the loop.  This
5211f62f82b05563df9c83094608de24ea581014d1eChris Lattner  // handles the case when a PHI node has multiple instances of itself as
5221f62f82b05563df9c83094608de24ea581014d1eChris Lattner  // arguments.
52354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner  SmallVector<BasicBlock*, 8> OuterLoopPreds;
5241f62f82b05563df9c83094608de24ea581014d1eChris Lattner  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
5251f62f82b05563df9c83094608de24ea581014d1eChris Lattner    if (PN->getIncomingValue(i) != PN ||
526a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman        !L->contains(PN->getIncomingBlock(i))) {
527a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman      // We can't split indirectbr edges.
528a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman      if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator()))
529a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman        return 0;
530a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman
5311f62f82b05563df9c83094608de24ea581014d1eChris Lattner      OuterLoopPreds.push_back(PN->getIncomingBlock(i));
532a58a04921deba911d6ead8d24f495cec234681c1Dan Gohman    }
533529b28da455a703d226a31a03400e6662ff569feChris Lattner
534c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman  DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");
535c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman
5364b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner  BasicBlock *Header = L->getHeader();
53754b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner  BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0],
53854b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner                                             OuterLoopPreds.size(),
53954b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner                                             ".outer", this);
540529b28da455a703d226a31a03400e6662ff569feChris Lattner
541120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // Make sure that NewBB is put someplace intelligent, which doesn't mess up
542120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  // code layout too horribly.
543120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner  PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L);
544120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner
545529b28da455a703d226a31a03400e6662ff569feChris Lattner  // Create the new outer loop.
546529b28da455a703d226a31a03400e6662ff569feChris Lattner  Loop *NewOuter = new Loop();
547529b28da455a703d226a31a03400e6662ff569feChris Lattner
548529b28da455a703d226a31a03400e6662ff569feChris Lattner  // Change the parent loop to use the outer loop as its child now.
549529b28da455a703d226a31a03400e6662ff569feChris Lattner  if (Loop *Parent = L->getParentLoop())
550529b28da455a703d226a31a03400e6662ff569feChris Lattner    Parent->replaceChildLoopWith(L, NewOuter);
551529b28da455a703d226a31a03400e6662ff569feChris Lattner  else
552c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner    LI->changeTopLevelLoop(L, NewOuter);
553529b28da455a703d226a31a03400e6662ff569feChris Lattner
554529b28da455a703d226a31a03400e6662ff569feChris Lattner  // L is now a subloop of our outer loop.
555529b28da455a703d226a31a03400e6662ff569feChris Lattner  NewOuter->addChildLoop(L);
556529b28da455a703d226a31a03400e6662ff569feChris Lattner
557d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman  // Add the new loop to the pass manager queue.
558d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman  LPM.insertLoopIntoQueue(NewOuter);
559d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman
5609b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
5619b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman       I != E; ++I)
5629b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman    NewOuter->addBlockEntry(*I);
563529b28da455a703d226a31a03400e6662ff569feChris Lattner
5645c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman  // Now reset the header in L, which had been moved by
5655c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman  // SplitBlockPredecessors for the outer loop.
5665c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman  L->moveToHeader(Header);
5675c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman
568529b28da455a703d226a31a03400e6662ff569feChris Lattner  // Determine which blocks should stay in L and which should be moved out to
569529b28da455a703d226a31a03400e6662ff569feChris Lattner  // the Outer loop now.
570529b28da455a703d226a31a03400e6662ff569feChris Lattner  std::set<BasicBlock*> BlocksInL;
5719672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif  for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) {
5729672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif    BasicBlock *P = *PI;
5739672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif    if (DT->dominates(Header, P))
5749672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif      AddBlockAndPredsToSet(P, Header, BlocksInL);
5759672414017e9d5d764a56e5c8c61b39163d2d5e5Gabor Greif  }
576529b28da455a703d226a31a03400e6662ff569feChris Lattner
577529b28da455a703d226a31a03400e6662ff569feChris Lattner  // Scan all of the loop children of L, moving them to OuterLoop if they are
578529b28da455a703d226a31a03400e6662ff569feChris Lattner  // not part of the inner loop.
579c08fa28897356be54fba724056c3aa91da8b3e39David Greene  const std::vector<Loop*> &SubLoops = L->getSubLoops();
580c08fa28897356be54fba724056c3aa91da8b3e39David Greene  for (size_t I = 0; I != SubLoops.size(); )
581c08fa28897356be54fba724056c3aa91da8b3e39David Greene    if (BlocksInL.count(SubLoops[I]->getHeader()))
582529b28da455a703d226a31a03400e6662ff569feChris Lattner      ++I;   // Loop remains in L
583529b28da455a703d226a31a03400e6662ff569feChris Lattner    else
584c08fa28897356be54fba724056c3aa91da8b3e39David Greene      NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
585529b28da455a703d226a31a03400e6662ff569feChris Lattner
586529b28da455a703d226a31a03400e6662ff569feChris Lattner  // Now that we know which blocks are in L and which need to be moved to
587529b28da455a703d226a31a03400e6662ff569feChris Lattner  // OuterLoop, move any blocks that need it.
588529b28da455a703d226a31a03400e6662ff569feChris Lattner  for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
589529b28da455a703d226a31a03400e6662ff569feChris Lattner    BasicBlock *BB = L->getBlocks()[i];
590529b28da455a703d226a31a03400e6662ff569feChris Lattner    if (!BlocksInL.count(BB)) {
591529b28da455a703d226a31a03400e6662ff569feChris Lattner      // Move this block to the parent, updating the exit blocks sets
592529b28da455a703d226a31a03400e6662ff569feChris Lattner      L->removeBlockFromLoop(BB);
593c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner      if ((*LI)[BB] == L)
594c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner        LI->changeLoopFor(BB, NewOuter);
595529b28da455a703d226a31a03400e6662ff569feChris Lattner      --i;
596529b28da455a703d226a31a03400e6662ff569feChris Lattner    }
597529b28da455a703d226a31a03400e6662ff569feChris Lattner  }
598529b28da455a703d226a31a03400e6662ff569feChris Lattner
599529b28da455a703d226a31a03400e6662ff569feChris Lattner  return NewOuter;
600529b28da455a703d226a31a03400e6662ff569feChris Lattner}
601529b28da455a703d226a31a03400e6662ff569feChris Lattner
602529b28da455a703d226a31a03400e6662ff569feChris Lattner
603529b28da455a703d226a31a03400e6662ff569feChris Lattner
6042ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// InsertUniqueBackedgeBlock - This method is called when the specified loop
6052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// has more than one backedge in it.  If this occurs, revector all of these
6062ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// backedges to target a new basic block and have that block branch to the loop
6072ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// header.  This ensures that loops have exactly one backedge.
6082ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner///
609f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan GohmanBasicBlock *
610f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan GohmanLoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) {
6112ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
6122ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
6132ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  // Get information about the loop
6142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  BasicBlock *Header = L->getHeader();
6152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  Function *F = Header->getParent();
6162ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
617f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  // Unique backedge insertion currently depends on having a preheader.
618f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  if (!Preheader)
619f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    return 0;
620f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman
6212ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  // Figure out which basic blocks contain back-edges to the loop header.
6222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  std::vector<BasicBlock*> BackedgeBlocks;
623bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif  for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I){
624bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif    BasicBlock *P = *I;
625bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif    if (P != Preheader) BackedgeBlocks.push_back(P);
626bf2eefdb0dac4e331ca26fa0792a1dfd420b06f6Gabor Greif  }
6272ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
6282ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  // Create and insert the new backedge block...
6291d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson  BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(),
6301d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson                                           Header->getName()+".backedge", F);
631051a950000e21935165db56695e35bade668193bGabor Greif  BranchInst *BETerminator = BranchInst::Create(Header, BEBlock);
6322ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
633c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman  DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block ";
634c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman        WriteAsOperand(dbgs(), BEBlock, false);
635c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman        dbgs() << "\n");
636c5e49c64d18eacdd72c80c04855df846df97f8a8Dan Gohman
6372ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  // Move the new backedge block to right after the last backedge block.
6382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos;
6392ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock);
640fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman
6412ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  // Now that the block has been inserted into the function, create PHI nodes in
6422ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  // the backedge block which correspond to any PHI nodes in the header block.
643200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
644200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos    PHINode *PN = cast<PHINode>(I);
645051a950000e21935165db56695e35bade668193bGabor Greif    PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".be",
646051a950000e21935165db56695e35bade668193bGabor Greif                                     BETerminator);
6475551706b0f8e970720deea0bf6aa34116030d6beChris Lattner    NewPN->reserveOperandSpace(BackedgeBlocks.size());
648cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner    if (AA) AA->copyValue(PN, NewPN);
6492ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
6502ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    // Loop over the PHI node, moving all entries except the one for the
6512ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    // preheader over to the new PHI node.
6522ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    unsigned PreheaderIdx = ~0U;
6532ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    bool HasUniqueIncomingValue = true;
6542ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    Value *UniqueValue = 0;
6552ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
6562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner      BasicBlock *IBB = PN->getIncomingBlock(i);
6572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner      Value *IV = PN->getIncomingValue(i);
6582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner      if (IBB == Preheader) {
6592ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner        PreheaderIdx = i;
6602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner      } else {
6612ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner        NewPN->addIncoming(IV, IBB);
6622ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner        if (HasUniqueIncomingValue) {
6632ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner          if (UniqueValue == 0)
6642ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner            UniqueValue = IV;
6652ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner          else if (UniqueValue != IV)
6662ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner            HasUniqueIncomingValue = false;
6672ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner        }
6682ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner      }
6692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    }
670fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman
6712ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    // Delete all of the incoming values from the old PN except the preheader's
6722ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    assert(PreheaderIdx != ~0U && "PHI has no preheader entry??");
6732ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    if (PreheaderIdx != 0) {
6742ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner      PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
6752ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner      PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
6762ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    }
6775551706b0f8e970720deea0bf6aa34116030d6beChris Lattner    // Nuke all entries except the zero'th.
6785551706b0f8e970720deea0bf6aa34116030d6beChris Lattner    for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i)
6795551706b0f8e970720deea0bf6aa34116030d6beChris Lattner      PN->removeIncomingValue(e-i, false);
6802ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
6812ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    // Finally, add the newly constructed PHI node as the entry for the BEBlock.
6822ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    PN->addIncoming(NewPN, BEBlock);
6832ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
6842ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    // As an optimization, if all incoming values in the new PhiNode (which is a
6852ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    // subset of the incoming values of the old PHI node) have the same value,
6862ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    // eliminate the PHI Node.
6872ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    if (HasUniqueIncomingValue) {
6882ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner      NewPN->replaceAllUsesWith(UniqueValue);
689cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner      if (AA) AA->deleteValue(NewPN);
6902ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner      BEBlock->getInstList().erase(NewPN);
6912ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    }
6922ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  }
6932ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
6942ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  // Now that all of the PHI nodes have been inserted and adjusted, modify the
695280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky  // backedge blocks to just to the BEBlock instead of the header.
6962ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) {
6972ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    TerminatorInst *TI = BackedgeBlocks[i]->getTerminator();
6982ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner    for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op)
6992ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner      if (TI->getSuccessor(Op) == Header)
7002ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner        TI->setSuccessor(Op, BEBlock);
7012ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  }
7022ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
7032ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  //===--- Update all analyses which we must preserve now -----------------===//
7042ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
7052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  // Update Loop Information - we know that this block is now in the current
7062ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner  // loop and all parent loops.
707d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson  L->addBasicBlockToLoop(BEBlock, LI->getBase());
7082ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner
7090e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel  // Update dominator information
7100e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel  DT->splitBlock(BEBlock);
7111465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands  if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>())
7120e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel    DF->splitBlock(BEBlock);
713f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman
714f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  return BEBlock;
715f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman}
716f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman
717f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohmanvoid LoopSimplify::verifyAnalysis() const {
718f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  // It used to be possible to just assert L->isLoopSimplifyForm(), however
719f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  // with the introduction of indirectbr, there are now cases where it's
720f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  // not possible to transform a loop as necessary. We can at least check
721f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  // that there is an indirectbr near any time there's trouble.
722f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman
723f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  // Indirectbr can interfere with preheader and unique backedge insertion.
724f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  if (!L->getLoopPreheader() || !L->getLoopLatch()) {
725f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    bool HasIndBrPred = false;
726f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    for (pred_iterator PI = pred_begin(L->getHeader()),
727f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman         PE = pred_end(L->getHeader()); PI != PE; ++PI)
728f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      if (isa<IndirectBrInst>((*PI)->getTerminator())) {
729f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman        HasIndBrPred = true;
730f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman        break;
731f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      }
732f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    assert(HasIndBrPred &&
733f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman           "LoopSimplify has no excuse for missing loop header info!");
734f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  }
735f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman
736f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  // Indirectbr can interfere with exit block canonicalization.
737f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  if (!L->hasDedicatedExits()) {
738f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    bool HasIndBrExiting = false;
739f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    SmallVector<BasicBlock*, 8> ExitingBlocks;
740f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    L->getExitingBlocks(ExitingBlocks);
741f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i)
742f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) {
743f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman        HasIndBrExiting = true;
744f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman        break;
745f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman      }
746f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman    assert(HasIndBrExiting &&
747f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman           "LoopSimplify has no excuse for missing exit block info!");
748f4e82d1f2e25f7cf8b7e9c3bd42b0e384139e07eDan Gohman  }
74938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner}
750