ScalarEvolution.h

//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// The ScalarEvolution class is an LLVM pass which can be used to analyze and
// categorize scalar expressions in loops.  It specializes in recognizing
// general induction variables, representing them with the abstract and opaque
// SCEV class.  Given this analysis, trip counts of loops and other important
// properties can be obtained.
//
// This analysis is primarily useful for induction variable substitution and
// strength reduction.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
#define LLVM_ANALYSIS_SCALAREVOLUTION_H

#include "llvm/Pass.h"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/System/DataTypes.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/DenseMap.h"
#include <map>

namespace llvm {
  class APInt;
  class Constant;
  class ConstantInt;
  class DominatorTree;
  class Type;
  class ScalarEvolution;
  class TargetData;
  class LLVMContext;
  class Loop;
  class LoopInfo;
  class Operator;

  class SCEV : public FoldingSetNode {
    FoldingSetNodeIDRef FastID;

    // The SCEV baseclass this node corresponds to
    const unsigned short SCEVType;

  protected:
    unsigned short SubclassData;

  private:
    SCEV(const SCEV &);            // DO NOT IMPLEMENT
    void operator=(const SCEV &);  // DO NOT IMPLEMENT
  protected:
    virtual ~SCEV();
  public:
    explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) :
      FastID(ID), SCEVType(SCEVTy), SubclassData(0) {}

    unsigned getSCEVType() const { return SCEVType; }

    void Profile(FoldingSetNodeID& ID) { ID = FastID; }

    virtual bool isLoopInvariant(const Loop *L) const = 0;

    virtual bool hasComputableLoopEvolution(const Loop *L) const = 0;

    virtual const Type *getType() const = 0;

    bool isZero() const;

    bool isOne() const;

    bool isAllOnesValue() const;

    virtual bool hasOperand(const SCEV *Op) const = 0;

    virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0;

    virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const = 0;

    virtual void print(raw_ostream &OS) const = 0;

    void dump() const;
  };

  inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
    S.print(OS);
    return OS;
  }

  struct SCEVCouldNotCompute : public SCEV {
    SCEVCouldNotCompute();

    // None of these methods are valid for this object.
    virtual bool isLoopInvariant(const Loop *L) const;
    virtual const Type *getType() const;
    virtual bool hasComputableLoopEvolution(const Loop *L) const;
    virtual void print(raw_ostream &OS) const;
    virtual bool hasOperand(const SCEV *Op) const;

    virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const {
      return true;
    }

    virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
      return true;
    }

    static inline bool classof(const SCEVCouldNotCompute *S) { return true; }
    static bool classof(const SCEV *S);
  };

  class ScalarEvolution : public FunctionPass {
    class SCEVCallbackVH : public CallbackVH {
      ScalarEvolution *SE;
      virtual void deleted();
      virtual void allUsesReplacedWith(Value *New);
    public:
      SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0);
    };

    friend class SCEVCallbackVH;
    friend class SCEVExpander;

    Function *F;

    LoopInfo *LI;

    TargetData *TD;

    DominatorTree *DT;

    SCEVCouldNotCompute CouldNotCompute;

    std::map<SCEVCallbackVH, const SCEV *> Scalars;

    struct BackedgeTakenInfo {
      const SCEV *Exact;

      const SCEV *Max;

      /*implicit*/ BackedgeTakenInfo(const SCEV *exact) :
        Exact(exact), Max(exact) {}

      BackedgeTakenInfo(const SCEV *exact, const SCEV *max) :
        Exact(exact), Max(max) {}

      bool hasAnyInfo() const {
        return !isa<SCEVCouldNotCompute>(Exact) ||
               !isa<SCEVCouldNotCompute>(Max);
      }
    };

    std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts;

    std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;

    std::map<const SCEV *,
             std::map<const Loop *, const SCEV *> > ValuesAtScopes;

    const SCEV *createSCEV(Value *V);

    const SCEV *createNodeForPHI(PHINode *PN);

    const SCEV *createNodeForGEP(GEPOperator *GEP);

    const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);

    void ForgetSymbolicName(Instruction *I, const SCEV *SymName);

    const SCEV *getBECount(const SCEV *Start,
                           const SCEV *End,
                           const SCEV *Step,
                           bool NoWrap);

    const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);

    BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L);

    BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L,
                                                      BasicBlock *ExitingBlock);

    BackedgeTakenInfo
      ComputeBackedgeTakenCountFromExitCond(const Loop *L,
                                            Value *ExitCond,
                                            BasicBlock *TBB,
                                            BasicBlock *FBB);

    BackedgeTakenInfo
      ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
                                                ICmpInst *ExitCond,
                                                BasicBlock *TBB,
                                                BasicBlock *FBB);

    BackedgeTakenInfo
      ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI,
                                                   Constant *RHS,
                                                   const Loop *L,
                                                   ICmpInst::Predicate p);

    const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L,
                                                      Value *Cond,
                                                      bool ExitWhen);

    BackedgeTakenInfo HowFarToZero(const SCEV *V, const Loop *L);

    BackedgeTakenInfo HowFarToNonZero(const SCEV *V, const Loop *L);

    BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
                                       const Loop *L, bool isSigned);

    BasicBlock *getLoopPredecessor(const Loop *L);

    BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);

    bool isImpliedCond(Value *Cond, ICmpInst::Predicate Pred,
                       const SCEV *LHS, const SCEV *RHS,
                       bool Inverse);

    bool isImpliedCondOperands(ICmpInst::Predicate Pred,
                               const SCEV *LHS, const SCEV *RHS,
                               const SCEV *FoundLHS, const SCEV *FoundRHS);

    bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
                                     const SCEV *LHS, const SCEV *RHS,
                                     const SCEV *FoundLHS, const SCEV *FoundRHS);

    Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs,
                                                const Loop *L);

  public:
    static char ID; // Pass identification, replacement for typeid
    ScalarEvolution();

    LLVMContext &getContext() const { return F->getContext(); }

    bool isSCEVable(const Type *Ty) const;

    uint64_t getTypeSizeInBits(const Type *Ty) const;

    const Type *getEffectiveSCEVType(const Type *Ty) const;

    const SCEV *getSCEV(Value *V);

    const SCEV *getConstant(ConstantInt *V);
    const SCEV *getConstant(const APInt& Val);
    const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false);
    const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty);
    const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty);
    const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty);
    const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty);
    const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                           bool HasNUW = false, bool HasNSW = false);
    const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
                           bool HasNUW = false, bool HasNSW = false) {
      SmallVector<const SCEV *, 2> Ops;
      Ops.push_back(LHS);
      Ops.push_back(RHS);
      return getAddExpr(Ops, HasNUW, HasNSW);
    }
    const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1,
                           const SCEV *Op2,
                           bool HasNUW = false, bool HasNSW = false) {
      SmallVector<const SCEV *, 3> Ops;
      Ops.push_back(Op0);
      Ops.push_back(Op1);
      Ops.push_back(Op2);
      return getAddExpr(Ops, HasNUW, HasNSW);
    }
    const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
                           bool HasNUW = false, bool HasNSW = false);
    const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
                           bool HasNUW = false, bool HasNSW = false) {
      SmallVector<const SCEV *, 2> Ops;
      Ops.push_back(LHS);
      Ops.push_back(RHS);
      return getMulExpr(Ops, HasNUW, HasNSW);
    }
    const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
    const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step,
                              const Loop *L,
                              bool HasNUW = false, bool HasNSW = false);
    const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
                              const Loop *L,
                              bool HasNUW = false, bool HasNSW = false);
    const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
                              const Loop *L,
                              bool HasNUW = false, bool HasNSW = false) {
      SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
      return getAddRecExpr(NewOp, L, HasNUW, HasNSW);
    }
    const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
    const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
    const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
    const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
    const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
    const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS);
    const SCEV *getUnknown(Value *V);
    const SCEV *getCouldNotCompute();

    const SCEV *getSizeOfExpr(const Type *AllocTy);

    const SCEV *getAlignOfExpr(const Type *AllocTy);

    const SCEV *getOffsetOfExpr(const StructType *STy, unsigned FieldNo);

    const SCEV *getOffsetOfExpr(const Type *CTy, Constant *FieldNo);

    const SCEV *getNegativeSCEV(const SCEV *V);

    const SCEV *getNotSCEV(const SCEV *V);

    const SCEV *getMinusSCEV(const SCEV *LHS,
                             const SCEV *RHS);

    const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty);

    const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty);

    const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty);

    const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty);

    const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty);

    const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty);

    const SCEV *getIntegerSCEV(int64_t Val, const Type *Ty);

    const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS,
                                           const SCEV *RHS);

    const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS,
                                           const SCEV *RHS);

    const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);

    const SCEV *getSCEVAtScope(Value *V, const Loop *L);

    bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
                             const SCEV *LHS, const SCEV *RHS);

    bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
                                     const SCEV *LHS, const SCEV *RHS);

    const SCEV *getBackedgeTakenCount(const Loop *L);

    const SCEV *getMaxBackedgeTakenCount(const Loop *L);

    bool hasLoopInvariantBackedgeTakenCount(const Loop *L);

    void forgetLoop(const Loop *L);

    void forgetValue(Value *V);

    uint32_t GetMinTrailingZeros(const SCEV *S);

    ConstantRange getUnsignedRange(const SCEV *S);

    ConstantRange getSignedRange(const SCEV *S);

    bool isKnownNegative(const SCEV *S);

    bool isKnownPositive(const SCEV *S);

    bool isKnownNonNegative(const SCEV *S);

    bool isKnownNonPositive(const SCEV *S);

    bool isKnownNonZero(const SCEV *S);

    bool isKnownPredicate(ICmpInst::Predicate Pred,
                          const SCEV *LHS, const SCEV *RHS);

    virtual bool runOnFunction(Function &F);
    virtual void releaseMemory();
    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
    virtual void print(raw_ostream &OS, const Module* = 0) const;

  private:
    FoldingSet<SCEV> UniqueSCEVs;
    BumpPtrAllocator SCEVAllocator;
  };
}

#endif

---