LoopStrengthReduce.cpp

//===- LoopStrengthReduce.cpp - Strength Reduce IVs in Loops --------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file 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.
//
//===----------------------------------------------------------------------===//

#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/IVUsers.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/AddrModeMatcher.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Target/TargetLowering.h"
#include <algorithm>
using namespace llvm;

STATISTIC(NumReduced ,    "Number of IV uses strength reduced");
STATISTIC(NumInserted,    "Number of PHIs inserted");
STATISTIC(NumVariable,    "Number of PHIs with variable strides");
STATISTIC(NumEliminated,  "Number of strides eliminated");
STATISTIC(NumShadow,      "Number of Shadow IVs optimized");
STATISTIC(NumImmSunk,     "Number of common expr immediates sunk into uses");
STATISTIC(NumLoopCond,    "Number of loop terminating conds optimized");

static cl::opt<bool> EnableFullLSRMode("enable-full-lsr",
                                       cl::init(false),
                                       cl::Hidden);

namespace {

  struct BasedUser;

  /// 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;

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

  /// 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) {
      IVs.push_back(IVExpr(Stride, Base, PHI));
    }
  };

  class VISIBILITY_HIDDEN LoopStrengthReduce : public LoopPass {
    IVUsers *IU;
    LoopInfo *LI;
    DominatorTree *DT;
    ScalarEvolution *SE;
    bool Changed;

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

    /// StrideNoReuse - Keep track of all the strides whose ivs cannot be
    /// reused (nor should they be rewritten to reuse other strides).
    SmallSet<SCEVHandle, 4> StrideNoReuse;

    /// DeadInsts - Keep track of instructions we may have made dead, so that
    /// we can remove them after we are done working.
    SmallVector<WeakVH, 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(&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<ScalarEvolution>();
      AU.addPreserved<ScalarEvolution>();
      AU.addRequired<IVUsers>();
      AU.addPreserved<IVUsers>();
    }

  private:
    ICmpInst *ChangeCompareStride(Loop *L, ICmpInst *Cond,
                                  IVStrideUse* &CondUse,
                                  const SCEVHandle* &CondStride);

    void OptimizeIndvars(Loop *L);
    void OptimizeLoopCountIV(Loop *L);
    void OptimizeLoopTermCond(Loop *L);

    /// OptimizeShadowIV - If IV is used in a int-to-float cast
    /// inside the loop then try to eliminate the cast opeation.
    void OptimizeShadowIV(Loop *L);

    /// OptimizeSMax - Rewrite the loop's terminating condition
    /// if it uses an smax computation.
    ICmpInst *OptimizeSMax(Loop *L, ICmpInst *Cond,
                           IVStrideUse* &CondUse);

    bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse,
                           const SCEVHandle *&CondStride);
    bool RequiresTypeConversion(const Type *Ty, const Type *NewTy);
    SCEVHandle CheckForIVReuse(bool, bool, bool, const SCEVHandle&,
                             IVExpr&, const Type*,
                             const std::vector<BasedUser>& UsersToProcess);
    bool ValidScale(bool, int64_t,
                    const std::vector<BasedUser>& UsersToProcess);
    bool ValidOffset(bool, int64_t, int64_t,
                     const std::vector<BasedUser>& UsersToProcess);
    SCEVHandle CollectIVUsers(const SCEVHandle &Stride,
                              IVUsersOfOneStride &Uses,
                              Loop *L,
                              bool &AllUsesAreAddresses,
                              bool &AllUsesAreOutsideLoop,
                              std::vector<BasedUser> &UsersToProcess);
    bool ShouldUseFullStrengthReductionMode(
                                const std::vector<BasedUser> &UsersToProcess,
                                const Loop *L,
                                bool AllUsesAreAddresses,
                                SCEVHandle Stride);
    void PrepareToStrengthReduceFully(
                             std::vector<BasedUser> &UsersToProcess,
                             SCEVHandle Stride,
                             SCEVHandle CommonExprs,
                             const Loop *L,
                             SCEVExpander &PreheaderRewriter);
    void PrepareToStrengthReduceFromSmallerStride(
                                         std::vector<BasedUser> &UsersToProcess,
                                         Value *CommonBaseV,
                                         const IVExpr &ReuseIV,
                                         Instruction *PreInsertPt);
    void PrepareToStrengthReduceWithNewPhi(
                                  std::vector<BasedUser> &UsersToProcess,
                                  SCEVHandle Stride,
                                  SCEVHandle CommonExprs,
                                  Value *CommonBaseV,
                                  Instruction *IVIncInsertPt,
                                  const Loop *L,
                                  SCEVExpander &PreheaderRewriter);
    void StrengthReduceStridedIVUsers(const SCEVHandle &Stride,
                                      IVUsersOfOneStride &Uses,
                                      Loop *L);
    void DeleteTriviallyDeadInstructions();
  };
}

char LoopStrengthReduce::ID = 0;
static RegisterPass<LoopStrengthReduce>
X("loop-reduce", "Loop Strength Reduction");

Pass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) {
  return new LoopStrengthReduce(TLI);
}

/// DeleteTriviallyDeadInstructions - If any of the instructions is the
/// specified set are trivially dead, delete them and see if this makes any of