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

//===- LoopIndexSplit.cpp - Loop Index Splitting Pass ---------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements Loop Index Splitting Pass. This pass handles three
// kinds of loops.
//
// [1] A loop may be eliminated if the body is executed exactly once.
//     For example,
//
// for (i = 0; i < N; ++i) {
//   if (i == X) {
//     body;
//   }
// }
//
// is transformed to
//
// i = X;
// body;
//
// [2] A loop's iteration space may be shrunk if the loop body is executed
//     for a proper sub-range of the loop's iteration space. For example,
//
// for (i = 0; i < N; ++i) {
//   if (i > A && i < B) {
//     ...
//   }
// }
//
// is transformed to iterators from A to B, if A > 0 and B < N.
//
// [3] A loop may be split if the loop body is dominated by a branch.
//     For example,
//
// for (i = LB; i < UB; ++i) { if (i < SV) A; else B; }
//
// is transformed into
//
// AEV = BSV = SV
// for (i = LB; i < min(UB, AEV); ++i)
//    A;
// for (i = max(LB, BSV); i < UB; ++i);
//    B;
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "loop-index-split"
#include "llvm/Transforms/Scalar.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/LLVMContext.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"

using namespace llvm;

STATISTIC(NumIndexSplit, "Number of loop index split");
STATISTIC(NumIndexSplitRemoved, "Number of loops eliminated by loop index split");
STATISTIC(NumRestrictBounds, "Number of loop iteration space restricted");

namespace {

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

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

    void getAnalysisUsage(AnalysisUsage &AU) const {
      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:
    /// processOneIterationLoop -- Eliminate loop if loop body is executed 
    /// only once. For example,
    /// for (i = 0; i < N; ++i) {
    ///   if ( i == X) {
    ///     ...
    ///   }
    /// }
    ///
    bool processOneIterationLoop();

    // -- Routines used by updateLoopIterationSpace();

    /// updateLoopIterationSpace -- Update loop's iteration space if loop 
    /// body is executed for certain IV range only. For example,
    /// 
    /// for (i = 0; i < N; ++i) {
    ///   if ( i > A && i < B) {
    ///     ...
    ///   }
    /// }
    /// is transformed to iterators from A to B, if A > 0 and B < N.
    ///
    bool updateLoopIterationSpace();

    /// restrictLoopBound - Op dominates loop body. Op compares an IV based value