path: root/lib/Transforms/Utils/LoopSimplify.cpp

//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass performs several transformations to transform natural loops into a
// simpler form, which makes subsequent analyses and transformations simpler and
// more effective.
//
// Loop pre-header insertion guarantees that there is a single, non-critical
// entry edge from outside of the loop to the loop header.  This simplifies a
// number of analyses and transformations, such as LICM.
//
// Loop exit-block insertion guarantees that all exit blocks from the loop
// (blocks which are outside of the loop that have predecessors inside of the
// loop) only have predecessors from inside of the loop (and are thus dominated
// by the loop header).  This simplifies transformations such as store-sinking
// that are built into LICM.
//
// This pass also guarantees that loops will have exactly one backedge.
//
// Indirectbr instructions introduce several complications. If the loop
// contains or is entered by an indirectbr instruction, it may not be possible
// to transform the loop and make these guarantees. Client code should check
// that these conditions are true before relying on them.
//
// Note that the simplifycfg pass will clean up blocks which are split out but
// end up being unnecessary, so usage of this pass should not pessimize
// generated code.
//
// This pass obviously modifies the CFG, but updates loop information and
// dominator information.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "loop-simplify"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Function.h"
#include "llvm/LLVMContext.h"
#include "llvm/Type.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/DepthFirstIterator.h"
using namespace llvm;

STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted");
STATISTIC(NumNested  , "Number of nested loops split out");

namespace {
  struct LoopSimplify : public LoopPass {
    static char ID; // Pass identification, replacement for typeid
    LoopSimplify() : LoopPass(ID) {
      initializeLoopSimplifyPass(*PassRegistry::getPassRegistry());
    }

    // AA - If we have an alias analysis object to update, this is it, otherwise
    // this is null.
    AliasAnalysis *AA;
    LoopInfo *LI;
    DominatorTree *DT;
    ScalarEvolution *SE;
    Loop *L;
    virtual bool runOnLoop(Loop *L, LPPassManager &LPM);

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      // We need loop information to identify the loops...
      AU.addRequired<DominatorTree>();
      AU.addPreserved<DominatorTree>();

      AU.addRequired<LoopInfo>();
      AU.addPreserved<LoopInfo>();

      AU.addPreserved<AliasAnalysis>();
      AU.addPreserved<ScalarEvolution>();
      AU.addPreserved<DependenceAnalysis>();
      AU.addPreservedID(BreakCriticalEdgesID);  // No critical edges added.
    }

    /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
    void verifyAnalysis() const;

  private:
    bool ProcessLoop(Loop *L, LPPassManager &LPM);
    BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
    BasicBlock *InsertPreheaderForLoop(Loop *L);
    Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM,
                             BasicBlock *Preheader);
    BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader);
    void PlaceSplitBlockCarefully(BasicBlock *NewBB,
                                  SmallVectorImpl<BasicBlock*> &SplitPreds,
                                  Loop *L);
  };
}

char LoopSimplify::ID = 0;
INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
                "Canonicalize natural loops", true, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
                "Canonicalize natural loops", true, false)

// Publicly exposed interface to pass...
char &llvm::LoopSimplifyID = LoopSimplify::ID;
Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }

/// runOnLoop - Run down all loops in the CFG (recursively, but we could do
/// it in any convenient order) inserting preheaders...
///
bool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) {
  L = l;
  bool Changed = false;
  LI = &getAnalysis<LoopInfo>();
  AA = getAnalysisIfAvailable<AliasAnalysis>();
  DT = &getAnalysis<DominatorTree>();
  SE = getAnalysisIfAvailable<ScalarEvolution>();

  Changed |= ProcessLoop(L, LPM);

  return Changed;
}

/// ProcessLoop - Walk the loop structure in depth first order, ensuring that
/// all loops have preheaders.
///
bool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) {
  bool Changed = false;
ReprocessLoop:

  // Check to see that no blocks (other than the header) in this loop have
  // predecessors that are not in the loop.  This is not valid for natural
  // loops, but can occur if the blocks are unreachable.  Since they are
  // unreachable we can just shamelessly delete those CFG edges!
  for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
       BB != E; ++BB) {
    if (*BB == L->getHeader()) continue;

    SmallPtrSet<BasicBlock*, 4> BadPreds;
    for (pred_iterator PI = pred_begin(*BB),
         PE = pred_end(*BB); PI != PE; ++PI) {
      BasicBlock *P = *PI;
      if (!L->contains(P))
        BadPreds.insert(P);
    }

    // Delete each unique out-of-loop (and thus dead) predecessor.
    for (SmallPtrSet<BasicBlock*, 4>::iterator I = BadPreds.begin(),
         E = BadPreds.end(); I != E; ++I) {

      DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "
                   << (*I)->getName() << "\n");

      // Inform each successor of each dead pred.
      for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI)
        (*SI)->removePredecessor(*I);
      // Zap the dead pred's terminator and replace it with unreachable.
      TerminatorInst