From 12f3ca4cdb95b193af905a00e722a4dcb40b3de3 Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Wed, 26 Apr 2017 19:45:00 +0000 Subject: Vendor import of llvm trunk r301441: https://llvm.org/svn/llvm-project/llvm/trunk@301441 --- include/llvm/Analysis/ScalarEvolution.h | 41 +++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+) (limited to 'include/llvm/Analysis/ScalarEvolution.h') diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 91aeae0f728f..54bc4dcfd2cd 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -877,6 +877,47 @@ private: bool ControlsExit, bool AllowPredicates = false); + // Helper functions for computeExitLimitFromCond to avoid exponential time + // complexity. + + class ExitLimitCache { + // It may look like we need key on the whole (L, TBB, FBB, ControlsExit, + // AllowPredicates) tuple, but recursive calls to + // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only + // vary the in \c ExitCond and \c ControlsExit parameters. We remember the + // initial values of the other values to assert our assumption. + SmallDenseMap, ExitLimit> TripCountMap; + + const Loop *L; + BasicBlock *TBB; + BasicBlock *FBB; + bool AllowPredicates; + + public: + ExitLimitCache(const Loop *L, BasicBlock *TBB, BasicBlock *FBB, + bool AllowPredicates) + : L(L), TBB(TBB), FBB(FBB), AllowPredicates(AllowPredicates) {} + + Optional find(const Loop *L, Value *ExitCond, BasicBlock *TBB, + BasicBlock *FBB, bool ControlsExit, + bool AllowPredicates); + + void insert(const Loop *L, Value *ExitCond, BasicBlock *TBB, + BasicBlock *FBB, bool ControlsExit, bool AllowPredicates, + const ExitLimit &EL); + }; + + typedef ExitLimitCache ExitLimitCacheTy; + ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache, + const Loop *L, Value *ExitCond, + BasicBlock *TBB, BasicBlock *FBB, + bool ControlsExit, + bool AllowPredicates); + ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L, + Value *ExitCond, BasicBlock *TBB, + BasicBlock *FBB, bool ControlsExit, + bool AllowPredicates); + /// 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. If AllowPredicates is set, this call will try -- cgit v1.2.3