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 transformation analyzes and transforms the induction variables (and
// computations derived from them) into forms suitable for efficient execution
// on the target.
//
// This pass performs a strength reduction on array references inside loops that
// have as one or more of their components the loop induction variable, it
// rewrites expressions to take advantage of scaled-index addressing modes
// available on the target, and it performs a variety of other optimizations
// related to loop induction variables.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "loop-reduce"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Analysis/IVUsers.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/Debug.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.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");
STATISTIC(NumCountZero,   "Number of count iv optimized to count toward zero");

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 IVExpr {
    const SCEV *Stride;
    const SCEV *Base;
    PHINode    *PHI;

    IVExpr(const SCEV *const stride, const SCEV *const 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 IVsOfOneStride {
    std::vector<IVExpr> IVs;

    void addIV(const SCEV *const Stride, const SCEV *const Base, PHINode *PHI) {
      IVs.push_back(IVExpr(Stride, Base, PHI));
    }
  };

  class LoopStrengthReduce : public LoopPass {
    IVUsers *IU;
    ScalarEvolution *SE;
    bool Changed;

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

    /// 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("loops");
      AU.addPreserved("domfrontier");
      AU.addPreserved("domtree");

      AU.addRequiredID(LoopSimplifyID);
      AU.addRequired<ScalarEvolution>();
      AU.addPreserved<ScalarEvolution>();
      AU.addRequired<IVUsers>();
      AU.addPreserved<IVUsers>();
    }

  private:
    void OptimizeIndvars(Loop *L);

    /// OptimizeLoopTermCond - Change loop terminating condition to use the
    /// postinc iv when possible.
    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);

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

    /// OptimizeLoopCountIV - If, after all sharing of IVs, the IV used for
    /// deciding when to exit the loop is used only for that purpose, try to
    /// rearrange things so it counts down to a test against zero.
    bool OptimizeLoopCountIV(Loop *L);
    bool OptimizeLoopCountIVOfStride(const SCEV* &Stride,
                                     IVStrideUse* &CondUse, Loop *L);

    /// StrengthReduceIVUsersOfStride - Strength reduce all of the users of a
    /// single stride of IV.  All of the users may have different starting
    /// values, and this may not be the only stride.
    void StrengthReduceIVUsersOfStride(const SCEV *Stride,
                                      IVUsersOfOneStride &Uses,
                                      Loop *L);
    void StrengthReduceIVUsers(Loop *L);

    ICmpInst *ChangeCompareStride(Loop *L, ICmpInst *Cond,
                                  IVStrideUse* &CondUse,
                                  const SCEV* &CondStride,
                                  bool PostPass = false);

    bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse,
                           const SCEV* &CondStride);
    bool RequiresTypeConversion(const Type *Ty, const Type *NewTy);
    const SCEV *CheckForIVReuse(bool, bool, bool, const SCEV *,
                             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);
    const SCEV *CollectIVUsers(const SCEV *Stride,
                              IVUsersOfOneStride &Uses,
                              Loop *L,
                              bool &AllUsesAreAddresses,
                              bool &AllUsesAreOutsideLoop,
                              std::vector<BasedUser> &UsersToProcess);
    bool StrideMightBeShared(const SCEV *Stride, Loop *L, bool CheckPreInc);
    bool ShouldUseFullStrengthReductionMode(
                                const std::vector<BasedUser> &UsersToProcess,
                                const Loop *L,
                                bool AllUsesAreAddresses,
                                const SCEV *Stride);
    void PrepareToStrengthReduceFully(
                             std::vector<BasedUser> &UsersToProcess,
                             const SCEV *Stride,
                             const SCEV *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,
                                  const SCEV *Stride,
                                  const SCEV *CommonExprs,
                                  Value *CommonBaseV,
                                  Instruction *IVIncInsertPt,
                                  const Loop *L,
                                  SCEVExpander &PreheaderRewriter);

    void DeleteTriviallyDeadInstructions();
  };