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

//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
//
// This pass is a simple loop invariant code motion pass.  An interesting aspect
// of this pass is that it uses alias analysis for two purposes:
//
//  1. Moving loop invariant loads out of loops.  If we can determine that a
//     load inside of a loop never aliases anything stored to, we can hoist it
//     like any other instruction.
//  2. Scalar Promotion of Memory - If there is a store instruction inside of
//     the loop, we try to move the store to happen AFTER the loop instead of
//     inside of the loop.  This can only happen if a few conditions are true:
//       A. The pointer stored through is loop invariant
//       B. There are no stores or loads in the loop which _may_ alias the
//          pointer.  There are no calls in the loop which mod/ref the pointer.
//     If these conditions are true, we can promote the loads and stores in the
//     loop of the pointer to use a temporary alloca'd variable.  We then use
//     the mem2reg functionality to construct the appropriate SSA form for the
//     variable.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Instructions.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/CFG.h"
#include "Support/Statistic.h"
#include "Support/CommandLine.h"
#include "llvm/Assembly/Writer.h"
#include <algorithm>

namespace {
  cl::opt<bool> DisablePromotion("disable-licm-promotion", cl::Hidden,
                             cl::desc("Disable memory promotion in LICM pass"));

  Statistic<> NumHoisted("licm", "Number of instructions hoisted out of loop");
  Statistic<> NumHoistedLoads("licm", "Number of load insts hoisted");
  Statistic<> NumPromoted("licm", "Number of memory locations promoted to registers");

  /// LoopBodyInfo - We recursively traverse loops from most-deeply-nested to
  /// least-deeply-nested.  For all of the loops nested within the current one,
  /// we keep track of information so that we don't have to repeat queries.
  ///
  struct LoopBodyInfo {
    std::vector<CallInst*> Calls;          // Call instructions in loop
    std::vector<InvokeInst*> Invokes;      // Invoke instructions in loop

    // StoredPointers - Targets of store instructions...
    std::set<Value*> StoredPointers;

    // LoadedPointers - Source pointers for load instructions...
    std::set<Value*> LoadedPointers;

    enum PointerClass {
      PointerUnknown = 0, // Nothing is known about this pointer yet
      PointerMustStore,   // Memory is stored to ONLY through this pointer
      PointerMayStore,    // Memory is stored to through this or other pointers
      PointerNoStore      // Memory is not modified in this loop
    };

    // PointerIsModified - Keep track of information as we find out about it in
    // the loop body...
    //
    std::map<Value*, enum PointerClass> PointerIsModified;

    /// CantModifyAnyPointers - Return true if no memory modifying instructions
    /// occur in this loop.  This is just a conservative approximation, because
    /// a call may not actually store anything.
    bool CantModifyAnyPointers() const {
      return Calls.empty() && Invokes.empty() && StoredPointers.empty();
    }

    /// incorporate - Incorporate information about a subloop into the current
    /// loop.
    void incorporate(const LoopBodyInfo &OtherLBI);
    void incorporate(BasicBlock &BB);  // do the same for a basic block

    PointerClass getPointerInfo(Value *V, AliasAnalysis &AA) {
      PointerClass &VInfo = PointerIsModified[V];
      if (VInfo == PointerUnknown)
        VInfo = calculatePointerInfo(V, AA);
      return VInfo;
    }
  private:
    /// calculatePointerInfo - Calculate information about the specified
    /// pointer.
    PointerClass calculatePointerInfo(Value *V, AliasAnalysis &AA) const;
  };
}

/// incorporate - Incorporate information about a subloop into the current loop.
void LoopBodyInfo::incorporate(const LoopBodyInfo &OtherLBI) {
  // Do not incorporate NonModifiedPointers (which is just a cache) because it
  // is too much trouble to make sure it's still valid.
  Calls.insert  (Calls.end(),  OtherLBI.Calls.begin(),  OtherLBI.Calls.end());
  Invokes.insert(Invokes.end(),OtherLBI.Invokes.begin(),OtherLBI.Invokes.end());
  StoredPointers.insert(OtherLBI.StoredPointers.begin(),
                        OtherLBI.StoredPointers.end());
  LoadedPointers.insert(OtherLBI.LoadedPointers.begin(),
                        OtherLBI.LoadedPointers.end());
}

void LoopBodyInfo::incorporate(BasicBlock &BB) {
  for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I)
    if (CallInst *CI = dyn_cast<CallInst>(&*I))
      Calls.push_back(CI);
    else if (StoreInst *SI = dyn_cast<StoreInst>(&*I))
      StoredPointers.insert(SI->getOperand(1));
    else if (LoadInst *LI = dyn_cast<LoadInst>(&*I))
      LoadedPointers.insert(LI->getOperand(0));

  if (InvokeInst *II = dyn_cast<InvokeInst>(BB.getTerminator()))
    Invokes.push_back(II);
}


// calculatePointerInfo - Calculate information about the specified pointer.
LoopBodyInfo::PointerClass LoopBodyInfo::calculatePointerInfo(Value *V,
                                                      AliasAnalysis &AA) const {
  for (unsigned i = 0, e = Calls.size(); i != e; ++i)
    if (AA.getModRefInfo(Calls[i], V, ~0))
      return PointerMayStore;

  for (unsigned i = 0, e = Invokes.size(); i != e; ++i)
    if (AA.getModRefInfo(Invokes[i], V, ~0))
      return PointerMayStore;

  PointerClass Result = PointerNoStore;
  for (std::set<Value*>::const_iterator I = StoredPointers.begin(),
         E = StoredPointers.end(); I != E; ++I)
    if (AA.alias(V, ~0, *I, ~0))
      if (V == *I)
        Result = PointerMustStore;   // If this is the only alias, return must
      else
        return PointerMayStore;      // We have to return may
  return Result;
}

namespace {
  struct LICM : public FunctionPass, public InstVisitor<LICM> {
    virtual bool runOnFunction(Function &F);

    /// This transformation requires natural loop information & requires that
    /// loop preheaders be inserted into the CFG...
    ///
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesCFG();
      AU.addRequiredID(LoopPreheadersID);
      AU.addRequired<LoopInfo>();
      AU.addRequired<DominatorTree>();
      AU.addRequired<DominanceFrontier>();
      AU.addRequired<AliasAnalysis>();
    }

  private:
    LoopInfo      *LI;       // Current LoopInfo
    AliasAnalysis *AA;       // Current AliasAnalysis information
    bool Changed;            // Set to true when we change anything.
    BasicBlock *Preheader;   // The preheader block of the current loop...
    Loop *CurLoop;           // The current loop we are working on...
    LoopBodyInfo *CurLBI;    // Information about the current loop...

    /// visitLoop - Hoist expressions out of the specified loop...    
    ///
    void visitLoop(Loop *L, LoopBodyInfo &LBI);

    /// HoistRegion - Walk the specified region of the CFG (defined by all
    /// blocks dominated by the specified block, and that are in the current
    /// loop) in depth first order w.r.t the DominatorTree.  This allows us to
    /// visit defintions before uses, allowing us to hoist a loop body in one
    /// pass without iteration.
    ///
    void HoistRegion(DominatorTree::Node *N);

    /// inSubLoop - Little predicate that returns true if the specified basic
    /// block is in a subloop of the current one, not the current one itself.
    ///
    bool inSubLoop(BasicBlock *BB) {
      assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
      for (unsigned i = 0, e = CurLoop->getSubLoops().size(); i != e; ++i)
        if (CurLoop->getSubLoops()[i]->contains(BB))
          return true;  // A subloop actually contains this block!
      return false;
    }

    /// hoist - When an instruction is found to only use loop invariant operands
    /// that is safe to hoist, this instruction is called to do the dirty work.
    ///
    void hoist(Instruction &I);

    /// pointerInvalidatedByLoop - Return true if the body of this loop may
    /// store into the memory location pointed to by V.
    /// 
    bool pointerInvalidatedByLoop(Value *V) {
      // Check to see if any of the basic blocks in CurLoop invalidate V.
      return CurLBI->getPointerInfo(