aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
diff options
context:
space:
mode:
authorWei Mi <wmi@google.com>2016-02-03 17:05:12 +0000
committerWei Mi <wmi@google.com>2016-02-03 17:05:12 +0000
commited133978a0eed72b40f1a86c220445acb24f32f9 (patch)
treef2c6e1ad7942af2d652c4ba3b28f7e3749d942c6 /llvm/lib/Analysis/ScalarEvolutionExpander.cpp
parent38a36c4f1ca7a0a42ac6524a9f0a5a701f3bc88a (diff)
downloadllvm-ed133978a0eed72b40f1a86c220445acb24f32f9.zip
llvm-ed133978a0eed72b40f1a86c220445acb24f32f9.tar.gz
llvm-ed133978a0eed72b40f1a86c220445acb24f32f9.tar.bz2
[SCEV] Try to reuse existing value during SCEV expansion
Current SCEV expansion will expand SCEV as a sequence of operations and doesn't utilize the value already existed. This will introduce redundent computation which may not be cleaned up throughly by following optimizations. This patch introduces an ExprValueMap which is a map from SCEV to the set of equal values with the same SCEV. When a SCEV is expanded, the set of values is checked and reused whenever possible before generating a sequence of operations. Differential Revision: http://reviews.llvm.org/D12090 llvm-svn: 259662
Diffstat (limited to 'llvm/lib/Analysis/ScalarEvolutionExpander.cpp')
-rw-r--r--llvm/lib/Analysis/ScalarEvolutionExpander.cpp26
1 files changed, 25 insertions, 1 deletions
diff --git a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
index 921403d..5b49019 100644
--- a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -1600,6 +1600,12 @@ Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) {
return V;
}
+// The expansion of SCEV will either reuse a previous Value in ExprValueMap,
+// or expand the SCEV literally. Specifically, if the expansion is in LSRMode,
+// and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
+// literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,
+// the expansion will try to reuse Value from ExprValueMap, and only when it
+// fails, expand the SCEV literally.
Value *SCEVExpander::expand(const SCEV *S) {
// Compute an insertion point for this SCEV object. Hoist the instructions
// as far out in the loop nest as possible.
@@ -1639,7 +1645,25 @@ Value *SCEVExpander::expand(const SCEV *S) {
Builder.SetInsertPoint(InsertPt);
// Expand the expression into instructions.
- Value *V = visit(S);
+ SetVector<Value *> *Set = SE.getSCEVValues(S);
+ Value *V = nullptr;
+ // If the expansion is in LSRMode, and the SCEV contains any sub scAddRecExpr
+ // type SCEV, it will be expanded literally, to prevent LSR's transformed SCEV
+ // from being reverted.
+ if (!(LSRMode && SE.containsAddRecurrence(S))) {
+ if (Set) {
+ // Choose a Value from the set which dominates the insertPt.
+ for (auto const &Ent : *Set) {
+ if (Ent && isa<Instruction>(Ent) && S->getType() == Ent->getType() &&
+ SE.DT.dominates(cast<Instruction>(Ent), InsertPt)) {
+ V = Ent;
+ break;
+ }
+ }
+ }
+ }
+ if (!V)
+ V = visit(S);
// Remember the expanded value for this SCEV at this location.
//