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

//===- LoopIndexSplit.cpp - Loop Index Splitting Pass ---------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by Devang Patel and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements Loop Index Splitting Pass.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "loop-index-split"

#include "llvm/Transforms/Scalar.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Support/Compiler.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"

using namespace llvm;

STATISTIC(NumIndexSplit, "Number of loops index split");

namespace {

  class VISIBILITY_HIDDEN LoopIndexSplit : public LoopPass {

  public:
    static char ID; // Pass ID, replacement for typeid
    LoopIndexSplit() : LoopPass((intptr_t)&ID) {}

    // Index split Loop L. Return true if loop is split.
    bool runOnLoop(Loop *L, LPPassManager &LPM);

    void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<ScalarEvolution>();
      AU.addPreserved<ScalarEvolution>();
      AU.addRequiredID(LCSSAID);
      AU.addPreservedID(LCSSAID);
      AU.addRequired<LoopInfo>();
      AU.addPreserved<LoopInfo>();
      AU.addRequiredID(LoopSimplifyID);
      AU.addPreservedID(LoopSimplifyID);
      AU.addRequired<DominatorTree>();
      AU.addRequired<DominanceFrontier>();
      AU.addPreserved<DominatorTree>();
      AU.addPreserved<DominanceFrontier>();
    }

  private:

    class SplitInfo {
    public:
      SplitInfo() : SplitValue(NULL), SplitCondition(NULL), 
                    UseTrueBranchFirst(true), A_ExitValue(NULL), 
                    B_StartValue(NULL) {}

      // Induction variable's range is split at this value.
      Value *SplitValue;
      
      // This compare instruction compares IndVar against SplitValue.
      ICmpInst *SplitCondition;

      // True if after loop index split, first loop will execute split condition's
      // true branch.
      bool UseTrueBranchFirst;

      // Exit value for first loop after loop split.
      Value *A_ExitValue;

      // Start value for second loop after loop split.
      Value *B_StartValue;

      // Clear split info.
      void clear() {
        SplitValue = NULL;
        SplitCondition = NULL;
        UseTrueBranchFirst = true;
        A_ExitValue = NULL;
        B_StartValue = NULL;
      }

    };
    
  private:
    /// Find condition inside a loop that is suitable candidate for index split.
    void findSplitCondition();

    /// Find loop's exit condition.
    void findLoopConditionals();

    /// Return induction variable associated with value V.
    void findIndVar(Value *V, Loop *L);

    /// processOneIterationLoop - Current loop L contains compare instruction
    /// that compares induction variable, IndVar, agains loop invariant. If
    /// entire (i.e. meaningful) loop body is dominated by this compare
    /// instruction then loop body is executed only for one iteration. In
    /// such case eliminate loop structure surrounding this loop body. For
    bool processOneIterationLoop(SplitInfo &SD);
    
    /// If loop header includes loop variant instruction operands then
    /// this loop may not be eliminated.
    bool safeHeader(SplitInfo &SD,  BasicBlock *BB);

    /// If Exiting block includes loop variant instructions then this
    /// loop may not be eliminated.
    bool safeExitingBlock(SplitInfo &SD, BasicBlock *BB);

    /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB.
    /// This routine is used to remove split condition's dead branch, dominated by
    /// DeadBB. LiveBB dominates split conidition's other branch.
    void removeBlocks(BasicBlock *DeadBB, Loop *LP, BasicBlock *LiveBB);

    /// safeSplitCondition - Return true if it is possible to
    /// split loop using given split condition.
    bool safeSplitCondition(SplitInfo &SD);

    /// calculateLoopBounds - ALoop exit value and BLoop start values are calculated
    /// based on split value. 
    void calculateLoopBounds(SplitInfo &SD);

    /// splitLoop - Split current loop L in two loops using split information
    /// SD. Update dominator information. Maintain LCSSA form.
    bool splitLoop(Split