LoopStrengthReduce.cpp

//===- LoopStrengthReduce.cpp - Strength Reduce GEPs in Loops -------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by Nate Begeman and is distributed under the
// University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass performs a strength reduction on array references inside loops that
// have as one or more of their components the loop induction variable.  This is
// accomplished by creating a new Value to hold the initial value of the array
// access for the first iteration, and then creating a new GEP instruction in
// the loop to increment the value by the appropriate amount.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "loop-reduce"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Type.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Target/TargetData.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Target/TargetLowering.h"
#include <algorithm>
#include <set>
using namespace llvm;

STATISTIC(NumReduced ,    "Number of GEPs strength reduced");
STATISTIC(NumInserted,    "Number of PHIs inserted");
STATISTIC(NumVariable,    "Number of PHIs with variable strides");
STATISTIC(NumEliminated , "Number of strides eliminated");

namespace {

  struct BasedUser;

  /// IVStrideUse - Keep track of one use of a strided induction variable, where
  /// the stride is stored externally.  The Offset member keeps track of the 
  /// offset from the IV, User is the actual user of the operand, and
  /// 'OperandValToReplace' is the operand of the User that is the use.
  struct VISIBILITY_HIDDEN IVStrideUse {
    SCEVHandle Offset;
    Instruction *User;
    Value *OperandValToReplace;

    // isUseOfPostIncrementedValue - True if this should use the
    // post-incremented version of this IV, not the preincremented version.
    // This can only be set in special cases, such as the terminating setcc
    // instruction for a loop or uses dominated by the loop.
    bool isUseOfPostIncrementedValue;
    
    IVStrideUse(const SCEVHandle &Offs, Instruction *U, Value *O)
      : Offset(Offs), User(U), OperandValToReplace(O),
        isUseOfPostIncrementedValue(false) {}
  };
  
  /// IVUsersOfOneStride - This structure keeps track of all instructions that
  /// have an operand that is based on the trip count multiplied by some stride.
  /// The stride for all of these users is common and kept external to this
  /// structure.
  struct VISIBILITY_HIDDEN IVUsersOfOneStride {
    /// Users - Keep track of all of the users of this stride as well as the
    /// initial value and the operand that uses the IV.
    std::vector<IVStrideUse> Users;
    
    void addUser(const SCEVHandle &Offset,Instruction *User, Value *Operand) {
      Users.push_back(IVStrideUse(Offset, User, Operand));
    }
  };

  /// IVInfo - This structure keeps track of one IV expression inserted during
  /// StrengthReduceStridedIVUsers. It contains the stride, the common base, as
  /// well as the PHI node and increment value created for rewrite.
  struct VISIBILITY_HIDDEN IVExpr {
    SCEVHandle  Stride;
    SCEVHandle  Base;
    PHINode    *PHI;
    Value      *IncV;

    IVExpr(const SCEVHandle &stride, const SCEVHandle &base, PHINode *phi,
           Value *incv)
      : Stride(stride), Base(base), PHI(phi), IncV(incv) {}
  };

  /// IVsOfOneStride - This structure keeps track of all IV expression inserted
  /// during StrengthReduceStridedIVUsers for a particular stride of the IV.
  struct VISIBILITY_HIDDEN IVsOfOneStride {
    std::vector<IVExpr> IVs;

    void addIV(const SCEVHandle &Stride, const SCEVHandle &Base, PHINode *PHI,
               Value *IncV) {
      IVs.push_back(IVExpr(Stride, Base, PHI, IncV));
    }
  };

  class VISIBILITY_HIDDEN LoopStrengthReduce : public LoopPass {
    LoopInfo *LI;
    DominatorTree *DT;
    ScalarEvolution *SE;
    const TargetData *TD;
    const Type *UIntPtrTy;
    bool Changed;

    /// IVUsesByStride - Keep track of all uses of induction variables that we
    /// are interested in.  The key of the map is the stride of the access.
    std::map<SCEVHandle, IVUsersOfOneStride> IVUsesByStride;

    /// IVsByStride - Keep track of all IVs that have been inserted for a
    /// particular stride.
    std::map<SCEVHandle, IVsOfOneStride> IVsByStride;

    /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable:
    /// We use this to iterate over the IVUsesByStride collection without being
    /// dependent on random ordering of pointers in the process.
    SmallVector<SCEVHandle, 16> StrideOrder;

    /// CastedValues - As we need to cast values to uintptr_t, this keeps track
    /// of the casted version of each value.  This is accessed by
    /// getCastedVersionOf.
    DenseMap<Value*, Value*> CastedPointers;

    /// DeadInsts - Keep track of instructions we may have made dead, so that
    /// we can remove them after we are done working.
    SmallPtrSet<Instruction*,16> DeadInsts;

    /// TLI - Keep a pointer of a TargetLowering to consult for determining
    /// transformation profitability.
    const TargetLowering *TLI;

  public:
    static char ID; // Pass ID, replacement for typeid
    explicit LoopStrengthReduce(const TargetLowering *tli = NULL) : 
      LoopPass((intptr_t)&ID), TLI(tli) {
    }

    bool runOnLoop(Loop *L, LPPassManager &LPM);

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      // We split critical edges, so we change the CFG.  However, we do update
      // many analyses if they are around.
      AU.addPreservedID(LoopSimplifyID);
      AU.addPreserved<LoopInfo>();
      AU.addPreserved<DominanceFrontier>();
      AU.addPreserved<DominatorTree>();

      AU.addRequiredID(LoopSimplifyID);
      AU.addRequired<LoopInfo>();
      AU.addRequired<DominatorTree>();
      AU.addRequired<TargetData>();
      AU.addRequired<ScalarEvolution>();
    }
    
    /// getCastedVersionOf - Return the specified value casted to uintptr_t.
    ///
    Value *getCastedVersionOf(Instruction::CastOps opcode, Value *V);
private:
    bool AddUsersIfInteresting(Instruction *I, Loop *L,
                               SmallPtrSet<Instruction*,16> &Processed);
    SCEVHandle GetExpressionSCEV(Instruction *E);
    ICmpInst *ChangeCompareStride(Loop *L, ICmpInst *Cond,
                                  IVStrideUse* &CondUse,
                                  const SCEVHandle* &CondStride);
    void OptimizeIndvars(Loop *L);
    bool FindIVForUser(ICmpInst *Cond, IVStrideUse *&CondUse,
                       const SCEVHandle *&CondStride);
    bool RequiresTypeConversion(const Type *Ty, const Type *NewTy);
    unsigned CheckForIVReuse(bool, bool, const SCEVHandle&,
                             IVExpr&, const Type*,
                             const std::vector<BasedUser>& UsersToProcess);
    bool ValidStride(bool, int64_t,
                     const std::vector<BasedUser>& UsersToProcess);
    SCEVHandle CollectIVUsers(const SCEVHandle &Stride,
                              IVUsersOfOneStride &Uses,
                              Loop *L,
                              bool &AllUsesAreAddresses,
                              std::vector<BasedUser> &UsersToProcess);
    void StrengthReduceStridedIVUsers(const SCEVHandle &Stride,
                                      IVUsersOfOneStride &Uses,
                                      Loop *L, bool isOnlyStride);
    void DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*,16> &Insts);
  };
  char LoopStrengthReduce::ID = 0;
  RegisterPass<LoopStrengthReduce> X("loop-reduce", "Loop Strength Reduction");
}