svn commit: r312832 - in head/contrib/llvm: include/llvm/Analysis lib/Analysis lib/Transforms/Scalar
Dimitry Andric
dim at FreeBSD.org
Thu Jan 26 20:39:45 UTC 2017
Author: dim
Date: Thu Jan 26 20:39:43 2017
New Revision: 312832
URL: https://svnweb.freebsd.org/changeset/base/312832
Log:
Pull in r278160 from upstream llvm trunk (by Wei Mi):
Recommit "Use ValueOffsetPair to enhance value reuse during SCEV
expansion".
The fix for PR28705 will be committed consecutively.
In D12090, the ExprValueMap was added to reuse existing value during
SCEV expansion. However, const folding and sext/zext distribution can
make the reuse still difficult.
A simplified case is: suppose we know S1 expands to V1 in
ExprValueMap, and
S1 = S2 + C_a
S3 = S2 + C_b
where C_a and C_b are different SCEVConstants. Then we'd like to
expand S3 as V1 - C_a + C_b instead of expanding S2 literally. It is
helpful when S2 is a complex SCEV expr and S2 has no entry in
ExprValueMap, which is usually caused by the fact that S3 is
generated from S1 after const folding.
In order to do that, we represent ExprValueMap as a mapping from SCEV
to ValueOffsetPair. We will save both S1->{V1, 0} and S2->{V1, C_a}
into the ExprValueMap when we create SCEV for V1. When S3 is
expanded, it will first expand S2 to V1 - C_a because of S2->{V1,
C_a} in the map, then expand S3 to V1 - C_a + C_b.
Differential Revision: https://reviews.llvm.org/D21313
Pull in r278161 from upstream llvm trunk (by Wei Mi):
Fix the runtime error caused by "Use ValueOffsetPair to enhance value
reuse during SCEV expansion".
The patch is to fix the bug in PR28705. It was caused by setting
wrong return value for SCEVExpander::findExistingExpansion. The
return values of findExistingExpansion have different meanings when
the function is used in different ways so it is easy to make mistake.
The fix creates two new interfaces to replace
SCEVExpander::findExistingExpansion, and specifies where each
interface is expected to be used.
Differential Revision: https://reviews.llvm.org/D22942
Pull in r281439 from upstream llvm trunk (by Wei Mi):
Create a getelementptr instead of sub expr for ValueOffsetPair if the
value is a pointer.
This patch is to fix PR30213. When expanding an expr based on
ValueOffsetPair, if the value is of pointer type, we can only create
a getelementptr instead of sub expr.
Differential Revision: https://reviews.llvm.org/D24088
This should fix assertion failures when building OpenCV >= 3.1, and also
allow building lang/spidermonkey24 without any further assertions.
PR: 215649
MFC after: 1 week
Modified:
head/contrib/llvm/include/llvm/Analysis/ScalarEvolution.h
head/contrib/llvm/include/llvm/Analysis/ScalarEvolutionExpander.h
head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp
head/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
head/contrib/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
Modified: head/contrib/llvm/include/llvm/Analysis/ScalarEvolution.h
==============================================================================
--- head/contrib/llvm/include/llvm/Analysis/ScalarEvolution.h Thu Jan 26 20:18:28 2017 (r312831)
+++ head/contrib/llvm/include/llvm/Analysis/ScalarEvolution.h Thu Jan 26 20:39:43 2017 (r312832)
@@ -495,10 +495,29 @@ namespace llvm {
/// The typedef for ExprValueMap.
///
- typedef DenseMap<const SCEV *, SetVector<Value *>> ExprValueMapType;
+ typedef std::pair<Value *, ConstantInt *> ValueOffsetPair;
+ typedef DenseMap<const SCEV *, SetVector<ValueOffsetPair>> ExprValueMapType;
/// ExprValueMap -- This map records the original values from which
/// the SCEV expr is generated from.
+ ///
+ /// We want to represent the mapping as SCEV -> ValueOffsetPair instead
+ /// of SCEV -> Value:
+ /// Suppose we know S1 expands to V1, and
+ /// S1 = S2 + C_a
+ /// S3 = S2 + C_b
+ /// where C_a and C_b are different SCEVConstants. Then we'd like to
+ /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally.
+ /// It is helpful when S2 is a complex SCEV expr.
+ ///
+ /// In order to do that, we represent ExprValueMap as a mapping from
+ /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and
+ /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3
+ /// is expanded, it will first expand S2 to V1 - C_a because of
+ /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b.
+ ///
+ /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded
+ /// to V - Offset.
ExprValueMapType ExprValueMap;
/// The typedef for ValueExprMap.
@@ -1181,7 +1200,7 @@ namespace llvm {
bool containsAddRecurrence(const SCEV *S);
/// Return the Value set from which the SCEV expr is generated.
- SetVector<Value *> *getSCEVValues(const SCEV *S);
+ SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S);
/// Erase Value from ValueExprMap and ExprValueMap.
void eraseValueFromMap(Value *V);
Modified: head/contrib/llvm/include/llvm/Analysis/ScalarEvolutionExpander.h
==============================================================================
--- head/contrib/llvm/include/llvm/Analysis/ScalarEvolutionExpander.h Thu Jan 26 20:18:28 2017 (r312831)
+++ head/contrib/llvm/include/llvm/Analysis/ScalarEvolutionExpander.h Thu Jan 26 20:39:43 2017 (r312832)
@@ -14,6 +14,7 @@
#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
+#include "llvm/ADT/Optional.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionNormalization.h"
#include "llvm/Analysis/TargetFolder.h"
@@ -284,7 +285,15 @@ namespace llvm {
void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
- /// \brief Try to find LLVM IR value for S available at the point At.
+ /// Try to find existing LLVM IR value for S available at the point At.
+ Value *getExactExistingExpansion(const SCEV *S, const Instruction *At,
+ Loop *L);
+
+ /// Try to find the ValueOffsetPair for S. The function is mainly
+ /// used to check whether S can be expanded cheaply.
+ /// If this returns a non-None value, we know we can codegen the
+ /// `ValueOffsetPair` into a suitable expansion identical with S
+ /// so that S can be expanded cheaply.
///
/// L is a hint which tells in which loop to look for the suitable value.
/// On success return value which is equivalent to the expanded S at point
@@ -292,7 +301,9 @@ namespace llvm {
///
/// Note that this function does not perform an exhaustive search. I.e if it
/// didn't find any value it does not mean that there is no such value.
- Value *findExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
+ ///
+ Optional<ScalarEvolution::ValueOffsetPair>
+ getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
private:
LLVMContext &getContext() const { return SE.getContext(); }
@@ -325,7 +336,8 @@ namespace llvm {
PointerType *PTy, Type *Ty, Value *V);
/// \brief Find a previous Value in ExprValueMap for expand.
- Value *FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
+ ScalarEvolution::ValueOffsetPair
+ FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
Value *expand(const SCEV *S);
Modified: head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp
==============================================================================
--- head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp Thu Jan 26 20:18:28 2017 (r312831)
+++ head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp Thu Jan 26 20:39:43 2017 (r312832)
@@ -3378,8 +3378,28 @@ bool ScalarEvolution::containsAddRecurre
return F.FoundOne;
}
-/// Return the Value set from S.
-SetVector<Value *> *ScalarEvolution::getSCEVValues(const SCEV *S) {
+/// Try to split a SCEVAddExpr into a pair of {SCEV, ConstantInt}.
+/// If \p S is a SCEVAddExpr and is composed of a sub SCEV S' and an
+/// offset I, then return {S', I}, else return {\p S, nullptr}.
+static std::pair<const SCEV *, ConstantInt *> splitAddExpr(const SCEV *S) {
+ const auto *Add = dyn_cast<SCEVAddExpr>(S);
+ if (!Add)
+ return {S, nullptr};
+
+ if (Add->getNumOperands() != 2)
+ return {S, nullptr};
+
+ auto *ConstOp = dyn_cast<SCEVConstant>(Add->getOperand(0));
+ if (!ConstOp)
+ return {S, nullptr};
+
+ return {Add->getOperand(1), ConstOp->getValue()};
+}
+
+/// Return the ValueOffsetPair set for \p S. \p S can be represented
+/// by the value and offset from any ValueOffsetPair in the set.
+SetVector<ScalarEvolution::ValueOffsetPair> *
+ScalarEvolution::getSCEVValues(const SCEV *S) {
ExprValueMapType::iterator SI = ExprValueMap.find_as(S);
if (SI == ExprValueMap.end())
return nullptr;
@@ -3387,24 +3407,31 @@ SetVector<Value *> *ScalarEvolution::get
if (VerifySCEVMap) {
// Check there is no dangling Value in the set returned.
for (const auto &VE : SI->second)
- assert(ValueExprMap.count(VE));
+ assert(ValueExprMap.count(VE.first));
}
#endif
return &SI->second;
}
-/// Erase Value from ValueExprMap and ExprValueMap. If ValueExprMap.erase(V) is
-/// not used together with forgetMemoizedResults(S), eraseValueFromMap should be
-/// used instead to ensure whenever V->S is removed from ValueExprMap, V is also
-/// removed from the set of ExprValueMap[S].
+/// Erase Value from ValueExprMap and ExprValueMap. ValueExprMap.erase(V)
+/// cannot be used separately. eraseValueFromMap should be used to remove
+/// V from ValueExprMap and ExprValueMap at the same time.
void ScalarEvolution::eraseValueFromMap(Value *V) {
ValueExprMapType::iterator I = ValueExprMap.find_as(V);
if (I != ValueExprMap.end()) {
const SCEV *S = I->second;
- SetVector<Value *> *SV = getSCEVValues(S);
- // Remove V from the set of ExprValueMap[S]
- if (SV)
- SV->remove(V);
+ // Remove {V, 0} from the set of ExprValueMap[S]
+ if (SetVector<ValueOffsetPair> *SV = getSCEVValues(S))
+ SV->remove({V, nullptr});
+
+ // Remove {V, Offset} from the set of ExprValueMap[Stripped]
+ const SCEV *Stripped;
+ ConstantInt *Offset;
+ std::tie(Stripped, Offset) = splitAddExpr(S);
+ if (Offset != nullptr) {
+ if (SetVector<ValueOffsetPair> *SV = getSCEVValues(Stripped))
+ SV->remove({V, Offset});
+ }
ValueExprMap.erase(V);
}
}
@@ -3419,11 +3446,26 @@ const SCEV *ScalarEvolution::getSCEV(Val
S = createSCEV(V);
// During PHI resolution, it is possible to create two SCEVs for the same
// V, so it is needed to double check whether V->S is inserted into
- // ValueExprMap before insert S->V into ExprValueMap.
+ // ValueExprMap before insert S->{V, 0} into ExprValueMap.
std::pair<ValueExprMapType::iterator, bool> Pair =
ValueExprMap.insert({SCEVCallbackVH(V, this), S});
- if (Pair.second)
- ExprValueMap[S].insert(V);
+ if (Pair.second) {
+ ExprValueMap[S].insert({V, nullptr});
+
+ // If S == Stripped + Offset, add Stripped -> {V, Offset} into
+ // ExprValueMap.
+ const SCEV *Stripped = S;
+ ConstantInt *Offset = nullptr;
+ std::tie(Stripped, Offset) = splitAddExpr(S);
+ // If stripped is SCEVUnknown, don't bother to save
+ // Stripped -> {V, offset}. It doesn't simplify and sometimes even
+ // increase the complexity of the expansion code.
+ // If V is GetElementPtrInst, don't save Stripped -> {V, offset}
+ // because it may generate add/sub instead of GEP in SCEV expansion.
+ if (Offset != nullptr && !isa<SCEVUnknown>(Stripped) &&
+ !isa<GetElementPtrInst>(V))
+ ExprValueMap[Stripped].insert({V, Offset});
+ }
}
return S;
}
@@ -3436,8 +3478,8 @@ const SCEV *ScalarEvolution::getExisting
const SCEV *S = I->second;
if (checkValidity(S))
return S;
+ eraseValueFromMap(V);
forgetMemoizedResults(S);
- ValueExprMap.erase(I);
}
return nullptr;
}
@@ -3675,8 +3717,8 @@ void ScalarEvolution::forgetSymbolicName
if (!isa<PHINode>(I) ||
!isa<SCEVUnknown>(Old) ||
(I != PN && Old == SymName)) {
+ eraseValueFromMap(It->first);
forgetMemoizedResults(Old);
- ValueExprMap.erase(It);
}
}
@@ -4055,7 +4097,7 @@ const SCEV *ScalarEvolution::createAddRe
// to create an AddRecExpr for this PHI node. We can not keep this temporary
// as it will prevent later (possibly simpler) SCEV expressions to be added
// to the ValueExprMap.
- ValueExprMap.erase(PN);
+ eraseValueFromMap(PN);
}
return nullptr;
@@ -5435,8 +5477,8 @@ ScalarEvolution::getBackedgeTakenInfo(co
// case, createNodeForPHI will perform the necessary updates on its
// own when it gets to that point.
if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) {
+ eraseValueFromMap(It->first);
forgetMemoizedResults(Old);
- ValueExprMap.erase(It);
}
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
@@ -5481,8 +5523,8 @@ void ScalarEvolution::forgetLoop(const L
ValueExprMapType::iterator It =
ValueExprMap.find_as(static_cast<Value *>(I));
if (It != ValueExprMap.end()) {
+ eraseValueFromMap(It->first);
forgetMemoizedResults(It->second);
- ValueExprMap.erase(It);
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
}
@@ -5515,8 +5557,8 @@ void ScalarEvolution::forgetValue(Value
ValueExprMapType::iterator It =
ValueExprMap.find_as(static_cast<Value *>(I));
if (It != ValueExprMap.end()) {
+ eraseValueFromMap(It->first);
forgetMemoizedResults(It->second);
- ValueExprMap.erase(It);
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
}
Modified: head/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
==============================================================================
--- head/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp Thu Jan 26 20:18:28 2017 (r312831)
+++ head/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp Thu Jan 26 20:39:43 2017 (r312832)
@@ -1625,9 +1625,10 @@ Value *SCEVExpander::expandCodeFor(const
return V;
}
-Value *SCEVExpander::FindValueInExprValueMap(const SCEV *S,
- const Instruction *InsertPt) {
- SetVector<Value *> *Set = SE.getSCEVValues(S);
+ScalarEvolution::ValueOffsetPair
+SCEVExpander::FindValueInExprValueMap(const SCEV *S,
+ const Instruction *InsertPt) {
+ SetVector<ScalarEvolution::ValueOffsetPair> *Set = SE.getSCEVValues(S);
// If the expansion is not in CanonicalMode, and the SCEV contains any
// sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
if (CanonicalMode || !SE.containsAddRecurrence(S)) {
@@ -1636,21 +1637,21 @@ Value *SCEVExpander::FindValueInExprValu
// Choose a Value from the set which dominates the insertPt.
// insertPt should be inside the Value's parent loop so as not to break
// the LCSSA form.
- for (auto const &Ent : *Set) {
+ for (auto const &VOPair : *Set) {
+ Value *V = VOPair.first;
+ ConstantInt *Offset = VOPair.second;
Instruction *EntInst = nullptr;
- if (Ent && isa<Instruction>(Ent) &&
- (EntInst = cast<Instruction>(Ent)) &&
- S->getType() == Ent->getType() &&
+ if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) &&
+ S->getType() == V->getType() &&
EntInst->getFunction() == InsertPt->getFunction() &&
SE.DT.dominates(EntInst, InsertPt) &&
(SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
- SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt))) {
- return Ent;
- }
+ SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
+ return {V, Offset};
}
}
}
- return nullptr;
+ return {nullptr, nullptr};
}
// The expansion of SCEV will either reuse a previous Value in ExprValueMap,
@@ -1698,11 +1699,33 @@ Value *SCEVExpander::expand(const SCEV *
Builder.SetInsertPoint(InsertPt);
// Expand the expression into instructions.
- Value *V = FindValueInExprValueMap(S, InsertPt);
+ ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt);
+ Value *V = VO.first;
if (!V)
V = visit(S);
-
+ else if (VO.second) {
+ if (PointerType *Vty = dyn_cast<PointerType>(V->getType())) {
+ Type *Ety = Vty->getPointerElementType();
+ int64_t Offset = VO.second->getSExtValue();
+ int64_t ESize = SE.getTypeSizeInBits(Ety);
+ if ((Offset * 8) % ESize == 0) {
+ ConstantInt *Idx =
+ ConstantInt::getSigned(VO.second->getType(), -(Offset * 8) / ESize);
+ V = Builder.CreateGEP(Ety, V, Idx, "scevgep");
+ } else {
+ ConstantInt *Idx =
+ ConstantInt::getSigned(VO.second->getType(), -Offset);
+ unsigned AS = Vty->getAddressSpace();
+ V = Builder.CreateBitCast(V, Type::getInt8PtrTy(SE.getContext(), AS));
+ V = Builder.CreateGEP(Type::getInt8Ty(SE.getContext()), V, Idx,
+ "uglygep");
+ V = Builder.CreateBitCast(V, Vty);
+ }
+ } else {
+ V = Builder.CreateSub(V, VO.second);
+ }
+ }
// Remember the expanded value for this SCEV at this location.
//
// This is independent of PostIncLoops. The mapped value simply materializes
@@ -1887,8 +1910,18 @@ unsigned SCEVExpander::replaceCongruentI
return NumElim;
}
-Value *SCEVExpander::findExistingExpansion(const SCEV *S,
- const Instruction *At, Loop *L) {
+Value *SCEVExpander::getExactExistingExpansion(const SCEV *S,
+ const Instruction *At, Loop *L) {
+ Optional<ScalarEvolution::ValueOffsetPair> VO =
+ getRelatedExistingExpansion(S, At, L);
+ if (VO && VO.getValue().second == nullptr)
+ return VO.getValue().first;
+ return nullptr;
+}
+
+Optional<ScalarEvolution::ValueOffsetPair>
+SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
+ Loop *L) {
using namespace llvm::PatternMatch;
SmallVector<BasicBlock *, 4> ExitingBlocks;
@@ -1906,22 +1939,23 @@ Value *SCEVExpander::findExistingExpansi
continue;
if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
- return LHS;
+ return ScalarEvolution::ValueOffsetPair(LHS, nullptr);
if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
- return RHS;
+ return ScalarEvolution::ValueOffsetPair(RHS, nullptr);
}
// Use expand's logic which is used for reusing a previous Value in
// ExprValueMap.
- if (Value *Val = FindValueInExprValueMap(S, At))
- return Val;
+ ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At);
+ if (VO.first)
+ return VO;
// There is potential to make this significantly smarter, but this simple
// heuristic already gets some interesting cases.
// Can not find suitable value.
- return nullptr;
+ return None;
}
bool SCEVExpander::isHighCostExpansionHelper(
@@ -1930,7 +1964,7 @@ bool SCEVExpander::isHighCostExpansionHe
// If we can find an existing value for this scev avaliable at the point "At"
// then consider the expression cheap.
- if (At && findExistingExpansion(S, At, L) != nullptr)
+ if (At && getRelatedExistingExpansion(S, At, L))
return false;
// Zero/One operand expressions
@@ -1978,7 +2012,7 @@ bool SCEVExpander::isHighCostExpansionHe
// involving division. This is just a simple search heuristic.
if (!At)
At = &ExitingBB->back();
- if (!findExistingExpansion(
+ if (!getRelatedExistingExpansion(
SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
return true;
}
Modified: head/contrib/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
==============================================================================
--- head/contrib/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp Thu Jan 26 20:18:28 2017 (r312831)
+++ head/contrib/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp Thu Jan 26 20:39:43 2017 (r312832)
@@ -481,7 +481,7 @@ Value *IndVarSimplify::expandSCEVIfNeede
Type *ResultTy) {
// Before expanding S into an expensive LLVM expression, see if we can use an
// already existing value as the expansion for S.
- if (Value *ExistingValue = Rewriter.findExistingExpansion(S, InsertPt, L))
+ if (Value *ExistingValue = Rewriter.getExactExistingExpansion(S, InsertPt, L))
if (ExistingValue->getType() == ResultTy)
return ExistingValue;
More information about the svn-src-all
mailing list