+ };
+
+ /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for
+ /// this function as they are computed.
+ std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts;
+
+ /// ConstantEvolutionLoopExitValue - This map contains entries for all of
+ /// the PHI instructions that we attempt to compute constant evolutions for.
+ /// This allows us to avoid potentially expensive recomputation of these
+ /// properties. An instruction maps to null if we are unable to compute its
+ /// exit value.
+ std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
+
+ /// ValuesAtScopes - This map contains entries for all the expressions
+ /// that we attempt to compute getSCEVAtScope information for, which can
+ /// be expensive in extreme cases.
+ std::map<const SCEV *,
+ std::map<const Loop *, const SCEV *> > ValuesAtScopes;
+
+ /// createSCEV - We know that there is no SCEV for the specified value.
+ /// Analyze the expression.
+ const SCEV *createSCEV(Value *V);
+
+ /// createNodeForPHI - Provide the special handling we need to analyze PHI
+ /// SCEVs.
+ const SCEV *createNodeForPHI(PHINode *PN);
+
+ /// createNodeForGEP - Provide the special handling we need to analyze GEP
+ /// SCEVs.
+ const SCEV *createNodeForGEP(Operator *GEP);
+
+ /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called
+ /// at most once for each SCEV+Loop pair.
+ ///
+ const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
+
+ /// ForgetSymbolicValue - This looks up computed SCEV values for all
+ /// instructions that depend on the given instruction and removes them from
+ /// the Scalars map if they reference SymName. This is used during PHI
+ /// resolution.
+ void ForgetSymbolicName(Instruction *I, const SCEV *SymName);
+
+ /// getBECount - Subtract the end and start values and divide by the step,
+ /// rounding up, to get the number of times the backedge is executed. Return
+ /// CouldNotCompute if an intermediate computation overflows.
+ const SCEV *getBECount(const SCEV *Start,
+ const SCEV *End,
+ const SCEV *Step);
+
+ /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given
+ /// loop, lazily computing new values if the loop hasn't been analyzed
+ /// yet.
+ const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
+
+ /// ComputeBackedgeTakenCount - Compute the number of times the specified
+ /// loop will iterate.
+ BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L);
+
+ /// ComputeBackedgeTakenCountFromExit - Compute the number of times the
+ /// backedge of the specified loop will execute if it exits via the
+ /// specified block.
+ BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L,
+ BasicBlock *ExitingBlock);
+
+ /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the
+ /// backedge of the specified loop will execute if its exit condition
+ /// were a conditional branch of ExitCond, TBB, and FBB.
+ BackedgeTakenInfo
+ ComputeBackedgeTakenCountFromExitCond(const Loop *L,
+ Value *ExitCond,
+ BasicBlock *TBB,
+ BasicBlock *FBB);
+
+ /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of
+ /// times the backedge of the specified loop will execute if its exit
+ /// condition were a conditional branch of the ICmpInst ExitCond, TBB,
+ /// and FBB.
+ BackedgeTakenInfo
+ ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
+ ICmpInst *ExitCond,
+ BasicBlock *TBB,
+ BasicBlock *FBB);
+
+ /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition
+ /// of 'icmp op load X, cst', try to see if we can compute the
+ /// backedge-taken count.
+ const SCEV *
+ ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI,
+ Constant *RHS,
+ const Loop *L,
+ ICmpInst::Predicate p);
+
+ /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute
+ /// a constant number of times (the condition evolves only from constants),
+ /// try to evaluate a few iterations of the loop until we get the exit
+ /// condition gets a value of ExitWhen (true or false). If we cannot
+ /// evaluate the backedge-taken count of the loop, return CouldNotCompute.
+ const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L,
+ Value *Cond,
+ bool ExitWhen);
+
+ /// HowFarToZero - Return the number of times a backedge comparing the
+ /// specified value to zero will execute. If not computable, return
+ /// CouldNotCompute.
+ const SCEV *HowFarToZero(const SCEV *V, const Loop *L);
+
+ /// HowFarToNonZero - Return the number of times a backedge checking the
+ /// specified value for nonzero will execute. If not computable, return
+ /// CouldNotCompute.
+ const SCEV *HowFarToNonZero(const SCEV *V, const Loop *L);
+
+ /// HowManyLessThans - Return the number of times a backedge containing the
+ /// specified less-than comparison will execute. If not computable, return
+ /// CouldNotCompute. isSigned specifies whether the less-than is signed.
+ BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
+ const Loop *L, bool isSigned);
+
+ /// getLoopPredecessor - If the given loop's header has exactly one unique
+ /// predecessor outside the loop, return it. Otherwise return null.
+ BasicBlock *getLoopPredecessor(const Loop *L);
+
+ /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
+ /// (which may not be an immediate predecessor) which has exactly one
+ /// successor from which BB is reachable, or null if no such block is
+ /// found.
+ BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
+
+ /// isImpliedCond - Test whether the condition described by Pred, LHS,
+ /// and RHS is true whenever the given Cond value evaluates to true.
+ bool isImpliedCond(Value *Cond, ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS,
+ bool Inverse);
+
+ /// isImpliedCondOperands - Test whether the condition described by Pred,
+ /// LHS, and RHS is true whenever the condition desribed by Pred, FoundLHS,
+ /// and FoundRHS is true.
+ bool isImpliedCondOperands(ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS,
+ const SCEV *FoundLHS, const SCEV *FoundRHS);
+
+ /// isImpliedCondOperandsHelper - Test whether the condition described by
+ /// Pred, LHS, and RHS is true whenever the condition desribed by Pred,
+ /// FoundLHS, and FoundRHS is true.
+ bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS,
+ const SCEV *FoundLHS, const SCEV *FoundRHS);
+
+ /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
+ /// in the header of its containing loop, we know the loop executes a
+ /// constant number of times, and the PHI node is just a recurrence
+ /// involving constants, fold it.
+ Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs,
+ const Loop *L);