path: root/lib/Transforms/Scalar/IndVarSimplify.cpp

//===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This transformation analyzes and transforms the induction variables (and
// computations derived from them) into simpler forms suitable for subsequent
// analysis and transformation.
//
// This transformation make the following changes to each loop with an
// identifiable induction variable:
//   1. All loops are transformed to have a SINGLE canonical induction variable
//      which starts at zero and steps by one.
//   2. The canonical induction variable is guaranteed to be the first PHI node
//      in the loop header block.
//   3. Any pointer arithmetic recurrences are raised to use array subscripts.
//
// If the trip count of a loop is computable, this pass also makes the following
// changes:
//   1. The exit condition for the loop is canonicalized to compare the
//      induction value against the exit value.  This turns loops like:
//        'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'
//   2. Any use outside of the loop of an expression derived from the indvar
//      is changed to compute the derived value outside of the loop, eliminating
//      the dependence on the exit value of the induction variable.  If the only
//      purpose of the loop is to compute the exit value of some derived
//      expression, this transformation will make the loop dead.
//
// This transformation should be followed by strength reduction after all of the
// desired loop transformations have been performed.  Additionally, on targets
// where it is profitable, the loop could be transformed to count down to zero
// (the "do loop" optimization).
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"
#include "llvm/BasicBlock.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Type.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;

namespace {
  Statistic<> NumRemoved ("indvars", "Number of aux indvars removed");
  Statistic<> NumPointer ("indvars", "Number of pointer indvars promoted");
  Statistic<> NumInserted("indvars", "Number of canonical indvars added");
  Statistic<> NumReplaced("indvars", "Number of exit values replaced");
  Statistic<> NumLFTR    ("indvars", "Number of loop exit tests replaced");

  class IndVarSimplify : public FunctionPass {
    LoopInfo        *LI;
    ScalarEvolution *SE;
    bool Changed;
  public:
    virtual bool runOnFunction(Function &) {
      LI = &getAnalysis<LoopInfo>();
      SE = &getAnalysis<ScalarEvolution>();
      Changed = false;

      // Induction Variables live in the header nodes of loops
      for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
        runOnLoop(*I);
      return Changed;
    }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequiredID(LoopSimplifyID);
      AU.addRequired<ScalarEvolution>();
      AU.addRequired<LoopInfo>();
      AU.addPreservedID(LoopSimplifyID);
      AU.setPreservesCFG();
    }
  private:
    void runOnLoop(Loop *L);
    void EliminatePointerRecurrence(PHINode *PN, BasicBlock *Preheader,
                                    std::set<Instruction*> &DeadInsts);
    void LinearFunctionTestReplace(Loop *L, SCEV *IterationCount,
                                   SCEVExpander &RW);
    void RewriteLoopExitValues(Loop *L);

    void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
  };
  RegisterOpt<IndVarSimplify> X("indvars", "Canonicalize Induction Variables");
}

FunctionPass *llvm::createIndVarSimplifyPass() {
  return new IndVarSimplify();
}

/// DeleteTriviallyDeadInstructions - If any of the instructions is the
/// specified set are trivially dead, delete them and see if this makes any of
/// their operands subsequently dead.
void IndVarSimplify::
DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
  while (!Insts.empty()) {
    Instruction *I = *Insts.begin();
    Insts.erase(Insts.begin());
    if (isInstructionTriviallyDead(I)) {
      for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
        if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
          Insts.insert(U);
      SE->deleteInstructionFromRecords(I);
      I->eraseFromParent();
      Changed = true;
    }
  }
}


/// EliminatePointerRecurrence - Check to see if this is a trivial GEP pointer
/// recurrence.  If so, change it into an integer recurrence, permitting
/// analysis by the SCEV routines.
void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN,
                                                BasicBlock *Preheader,
                                            std::set<Instruction*> &DeadInsts) {
  assert(PN->getNumIncomingValues() == 2 && "Noncanonicalized loop!");
  unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader);
  unsigned BackedgeIdx = PreheaderIdx^1;
  if (GetElementPtrInst *GEPI =
      dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx)))
    if (GEPI->getOperand(0) == PN) {
      assert(GEPI->getNumOperands() == 2 && "GEP types must mismatch!");

      // Okay, we found a pointer recurrence.  Transform this pointer
      // recurrence into an integer recurrence.  Compute the value that gets
      // added to the pointer at every iteration.
      Value *AddedVal = GEPI->getOperand(1);

      // Insert a new integer PHI node into the top of the block.
      PHINode *NewPhi = new PHINode(AddedVal->getType(),
                                    PN->getName()+".rec", PN);
      NewPhi->addIncoming(Constant::getNullValue(NewPhi->getType()), Preheader);

      // Create the new add instruction.
      Value *NewAdd = BinaryOperator::createAdd(NewPhi, AddedVal,
                                                GEPI->getName()+".rec", GEPI);
      NewPhi->addIncoming(NewAdd, PN->getIncomingBlock(BackedgeIdx));

      // Update the existing GEP to use the recurrence.
      GEPI->setOperand(0, PN->getIncomingValue(PreheaderIdx));

      // Update the GEP to use the new recurrence we just inserted.
      GEPI->setOperand(1, NewAdd);

      // If the incoming value is a constant expr GEP, try peeling out the array
      // 0 index if possible to make things simpler.
      if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEPI->getOperand(0)))
        if (CE->getOpcode() == Instruction::GetElementPtr) {
          unsigned NumOps = CE->getNumOperands();
          assert(NumOps > 1 && "CE folding didn't work!");
          if (CE->getOperand(NumOps-1)->isNullValue()) {
            // Check to make sure the last index really is an array index.
            gep_type_iterator GTI = gep_type_begin(GEPI);
            for (unsigned i = 1, e = GEPI->getNumOperands()-1;
                 i != e; ++i, ++GTI)
              /*empty*/;
            if (isa<SequentialType>(*GTI)) {
              // Pull the last index out of the constant expr GEP.
              std::vector<Value*> CEIdxs(CE->op_begin()+1, CE->op_end()-1);
              Constant *NCE = ConstantExpr::getGetElementPtr(CE->getOperand(0),
                                                             CEIdxs);
              GetElementPtrInst *NGEPI =
                new GetElementPtrInst(NCE, Constant::getNullValue(Type::IntTy),
                                      NewAdd, GEPI->getName(), GEPI);
              GEPI->replaceAllUsesWith(NGEPI);
              GEPI->eraseFromParent();
              GEPI = NGEPI;
            }
          }
        }


      // Finally, if there are any other users of the PHI node, we must
      // insert a new GEP instruction that uses the pre-incremented version
      // of the induction amount.
      if (!PN->use_empty()) {
        BasicBlock::iterator InsertPos = PN; ++InsertPos;
        while (isa<PHINode>(InsertPos)) ++InsertPos;
        std::string Name = PN->getName(); PN->setName("");
        Value *PreInc =
          new GetElementPtrInst(PN->getIncomingValue(PreheaderIdx),
                                std::vector<Value*>(1, NewPhi), Name,
                                InsertPos);