This is an archive of the discontinued LLVM Phabricator instance.

Differential D13378

[SCEV] Recognize simple br-phi patterns
ClosedPublic

Authored by sanjoy on Oct 2 2015, 1:34 AM.

Details

Reviewers
atrick
mehdi_amini
• joker-eph-DISABLED
Commits
rG55015d210f2b: [SCEV] Recognize simple br-phi patterns
rL249211: [SCEV] Recognize simple br-phi patterns
Summary

Teach SCEV to match patterns like

 br %cond, label %left, label %right
left:
 br label %merge
right:
 br label %merge
merge:
 V = phi [ %x, %left ], [ %y, %right ]

as "select %cond, %x, %y". Before this SCEV would match PHI nodes
exclusively to add recurrences.

This addresses PR25005.

Diff Detail

Repository
rL LLVM

Event Timeline

sanjoy updated this revision to Diff 36335.Oct 2 2015, 1:34 AM
sanjoy retitled this revision from to [SCEV] Recognize simple br-phi patterns.
sanjoy updated this object.
sanjoy added reviewers: atrick, mehdi_amini, • joker-eph-DISABLED.
sanjoy added a subscriber: llvm-commits.
atrick accepted this revision.Oct 2 2015, 8:26 AM
atrick edited edge metadata.

Nice! Thanks Sanjoy.

This revision is now accepted and ready to land.Oct 2 2015, 8:26 AM
mehdi_amini mentioned this in D13390: SCEV: handle constant condition for select/branch.Oct 2 2015, 10:31 AM
mehdi_amini edited edge metadata.Oct 2 2015, 1:32 PM

Hi Sanjoyd,

Thanks for the clarification on the Constant Select, isn't it something that could be handled as well? Especially with D13390 coming?
See inline some other comments.

Thanks!

lib/Analysis/ScalarEvolution.cpp
3601 ↗(On Diff #36335)

Update the comment

3781 ↗(On Diff #36335)

I have a question about the lambda and their size, and especially the second one with this inner structure. Usually I have seen in LLVM only very small lambda used in favor of static function for larger one. Also Structure helper are usually in an anonymous namespace. Is there any guideline on this?

3872 ↗(On Diff #36335)

What about renaming createNodeForSelect into createNodeForSelectOrPhi? And also update the comment on top of the definition for createNodeForSelect.

sanjoy added inline comments.Oct 2 2015, 1:58 PM
lib/Analysis/ScalarEvolution.cpp
3781 ↗(On Diff #36335)

First of all, I'm not opposed to moving lifting the lambda outside if you think that'll help readability. I don't remember seeing anything about this in the coding style, but I can certainly understand the sentiment. :)

My bias is towards keeping things in as restricted a scope as possible. If a structure / helper function is useful only inside a function, then it should stay within that function, and not be leaked into the file scope etc. IOW, if something is not generally useful, it should be generally available either (same reason why you'd want to put the struct in an anonymous namespace, and not inside the llvm namespace). But this is just a bias (not a strong rational reason).

mehdi_amini added a comment.Oct 2 2015, 2:02 PM

I don't have a definitive opinion on the topic, but I did the same as you do in the past, and for the same reason ;), but I was asked to change it I think.

mehdi_amini edited edge metadata.Oct 2 2015, 2:02 PM
mehdi_amini added a subscriber: dexonsmith.
sanjoy added a comment.Oct 2 2015, 2:02 PM
In D13378#258915, @joker.eph wrote:

Hi Sanjoyd,

Thanks for the clarification on the Constant Select, isn't it something that could be handled as well? Especially with D13390 coming?

I'm not sure there is much value in optimizing ConstantExprs in SCEV, because they're compile time constants anyway (though they may need to remain symbolic till link time). I'd just wait till we see a case where it matters in practice.

See inline some other comments.

Thanks!

sanjoy updated this revision to Diff 36400.Oct 2 2015, 2:59 PM
  • address review: I've split createNodeForPHI into two subroutines, and removed the misleading comment. Also renamed createNodeFromSelect.
Herald added a subscriber: sanjoy. · View Herald TranscriptOct 2 2015, 2:59 PM
sanjoy updated this revision to Diff 36401.Oct 2 2015, 3:00 PM
  • use slash (///) in header comments
Closed by commit rL249211: [SCEV] Recognize simple br-phi patterns (authored by sanjoy). · Explain WhyOct 2 2015, 4:11 PM
This revision was automatically updated to reflect the committed changes.
Diffusion mentioned this in rL249431: This patch builds on top of D13378 to handle constant condition..Oct 6 2015, 10:21 AM
dnovillo added a subscriber: dnovillo.Oct 6 2015, 10:37 AM

Sanjoy,

This commit is causing an internal compiler error with the following code:

int x0, x1, x2;
double *x3;
int fsolv() {

int x4, x5 = x4 = 0;
for (; x4 < x2; ++x4) {
  x0 = 0;
  for (; x0 < x4; ++x0)
    x1 = x3[x5++];
}
return 0;

}

Is this something you recognize? If not, do you mind if I revert your
commit while you work on the test case?

Thanks. Diego.

$ clang -c -O2 a.c
clang-3.8:
/usr/local/google/home/dnovillo/llvm/llvm/lib/Analysis/LazyValueInfo.cpp:632:
bool (anonymous namespace)::LazyValueInfoCache
::solveBlockValueNonLocal((anonymous namespace)::LVILatticeVal &,
llvm::Value *, llvm::BasicBlock *): Assertion `isa<Argument>(Val) &&
"Unknown live-in to the entry block"' failed.
0 libLLVMSupport.so.3.8 0x00007f484d2fafde
llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 46
1 libLLVMSupport.so.3.8 0x00007f484d2fc119
2 libLLVMSupport.so.3.8 0x00007f484d2fab53
llvm::sys::RunSignalHandlers() + 131
3 libLLVMSupport.so.3.8 0x00007f484d2fc35b
4 libc.so.6 0x00007f484a447d40
5 libc.so.6 0x00007f484a447cc9 gsignal + 57
6 libc.so.6 0x00007f484a44b0d8 abort + 328
7 libc.so.6 0x00007f484a440b86
8 libc.so.6 0x00007f484a440c32
9 libLLVMAnalysis.so.3.8 0x00007f48504ba546
10 libLLVMAnalysis.so.3.8 0x00007f48504b9dd6
11 libLLVMAnalysis.so.3.8 0x00007f48504b97b2
12 libLLVMAnalysis.so.3.8 0x00007f48504b776e
13 libLLVMAnalysis.so.3.8 0x00007f48504b7541
llvm::LazyValueInfo::getConstantOnEdge(llvm::Value*, llvm::BasicBlock*,
llvm::BasicBl
ock*, llvm::Instruction*) + 129
14 libLLVMScalarOpts.so.3.8 0x00007f484d60a6ea
15 libLLVMScalarOpts.so.3.8 0x00007f484d60a317
16 libLLVMCore.so.3.8 0x00007f484f4281ff
llvm::FPPassManager::runOnFunction(llvm::Function&) + 399
17 libLLVMAnalysis.so.3.8 0x00007f48503f1611
18 libLLVMAnalysis.so.3.8 0x00007f48503f107d
19 libLLVMAnalysis.so.3.8 0x00007f48503f0928
20 libLLVMCore.so.3.8 0x00007f484f428caa
21 libLLVMCore.so.3.8 0x00007f484f4287d6
llvm::legacy::PassManagerImpl::run(llvm::Module&) + 342
22 libLLVMCore.so.3.8 0x00007f484f4291c1
llvm::legacy::PassManager::run(llvm::Module&) + 33
23 libclangCodeGen.so.3.8 0x00007f484bbb6dd5
24 libclangCodeGen.so.3.8 0x00007f484bbb6502
clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::CodeGenOptions
const&, clang::TargetOptions const&, clang::LangOptions const&,
llvm::StringRef, llvm::Module*, clang::BackendAction,
llvm::raw_pwrite_stream*) + 162
25 libclangCodeGen.so.3.8 0x00007f484be89a39
26 libclangParse.so.3.8 0x00007f48463905b1
clang::ParseAST(clang::Sema&, bool, bool) + 817
27 libclangFrontend.so.3.8 0x00007f484b402d10
clang::ASTFrontendAction::ExecuteAction() + 320
28 libclangCodeGen.so.3.8 0x00007f484be875f4
clang::CodeGenAction::ExecuteAction() + 2100
29 libclangFrontend.so.3.8 0x00007f484b4027f0
clang::FrontendAction::Execute() + 112
30 libclangFrontend.so.3.8 0x00007f484b39f402
clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) + 978
31 libclangFrontendTool.so.3.8 0x00007f484affa764
clang::ExecuteCompilerInvocation(clang::CompilerInstance*) + 1172
32 clang-3.8 0x0000000000423f08
cc1_main(llvm::ArrayRef<char const*>, char const*, void*) + 920
33 clang-3.8 0x0000000000417839
34 clang-3.8 0x0000000000416715 main + 2277
35 libc.so.6 0x00007f484a432ec5 __libc_start_main + 245
36 clang-3.8 0x0000000000415ce4
Stack dump:

  1. <eof> parser at end of file
  2. Per-module optimization passes
  3. Running pass 'CallGraph Pass Manager' on module 'a.c'.
  4. Running pass 'Value Propagation' on function '@fsolv'
sanjoy added a comment.Oct 6 2015, 10:48 AM

Diego Novillo via llvm-commits wrote:

dnovillo added a subscriber: dnovillo.
dnovillo added a comment.

Sanjoy,

This commit is causing an internal compiler error with the following code:

int x0, x1, x2;
double *x3;
int fsolv() {

int x4, x5 = x4 = 0;
for (; x4<  x2; ++x4) {
  x0 = 0;
  for (; x0<  x4; ++x0)
    x1 = x3[x5++];
}
return 0;

}

Is this something you recognize? If not, do you mind if I revert your
commit while you work on the test case?

It is plausible that this is the same issue as in http://reviews.llvm.org/D13460. If it is possible, can you please try
D13460 and see if it fixes the ICE? If not or if trying out a new patch will be too much work, reverting this is okay.

Thanks!

  • Sanjoy

Thanks. Diego.

$ clang -c -O2 a.c
clang-3.8:
/usr/local/google/home/dnovillo/llvm/llvm/lib/Analysis/LazyValueInfo.cpp:632:
bool (anonymous namespace)::LazyValueInfoCache
::solveBlockValueNonLocal((anonymous namespace)::LVILatticeVal&,
llvm::Value *, llvm::BasicBlock *): Assertion `isa<Argument>(Val)&&
"Unknown live-in to the entry block"' failed.
0 libLLVMSupport.so.3.8 0x00007f484d2fafde
llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 46
1 libLLVMSupport.so.3.8 0x00007f484d2fc119
2 libLLVMSupport.so.3.8 0x00007f484d2fab53
llvm::sys::RunSignalHandlers() + 131
3 libLLVMSupport.so.3.8 0x00007f484d2fc35b
4 libc.so.6 0x00007f484a447d40
5 libc.so.6 0x00007f484a447cc9 gsignal + 57
6 libc.so.6 0x00007f484a44b0d8 abort + 328
7 libc.so.6 0x00007f484a440b86
8 libc.so.6 0x00007f484a440c32
9 libLLVMAnalysis.so.3.8 0x00007f48504ba546
10 libLLVMAnalysis.so.3.8 0x00007f48504b9dd6
11 libLLVMAnalysis.so.3.8 0x00007f48504b97b2
12 libLLVMAnalysis.so.3.8 0x00007f48504b776e
13 libLLVMAnalysis.so.3.8 0x00007f48504b7541
llvm::LazyValueInfo::getConstantOnEdge(llvm::Value*, llvm::BasicBlock*,
llvm::BasicBl
ock*, llvm::Instruction*) + 129
14 libLLVMScalarOpts.so.3.8 0x00007f484d60a6ea
15 libLLVMScalarOpts.so.3.8 0x00007f484d60a317
16 libLLVMCore.so.3.8 0x00007f484f4281ff
llvm::FPPassManager::runOnFunction(llvm::Function&) + 399
17 libLLVMAnalysis.so.3.8 0x00007f48503f1611
18 libLLVMAnalysis.so.3.8 0x00007f48503f107d
19 libLLVMAnalysis.so.3.8 0x00007f48503f0928
20 libLLVMCore.so.3.8 0x00007f484f428caa
21 libLLVMCore.so.3.8 0x00007f484f4287d6
llvm::legacy::PassManagerImpl::run(llvm::Module&) + 342
22 libLLVMCore.so.3.8 0x00007f484f4291c1
llvm::legacy::PassManager::run(llvm::Module&) + 33
23 libclangCodeGen.so.3.8 0x00007f484bbb6dd5
24 libclangCodeGen.so.3.8 0x00007f484bbb6502
clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::CodeGenOptions
const&, clang::TargetOptions const&, clang::LangOptions const&,
llvm::StringRef, llvm::Module*, clang::BackendAction,
llvm::raw_pwrite_stream*) + 162
25 libclangCodeGen.so.3.8 0x00007f484be89a39
26 libclangParse.so.3.8 0x00007f48463905b1
clang::ParseAST(clang::Sema&, bool, bool) + 817
27 libclangFrontend.so.3.8 0x00007f484b402d10
clang::ASTFrontendAction::ExecuteAction() + 320
28 libclangCodeGen.so.3.8 0x00007f484be875f4
clang::CodeGenAction::ExecuteAction() + 2100
29 libclangFrontend.so.3.8 0x00007f484b4027f0
clang::FrontendAction::Execute() + 112
30 libclangFrontend.so.3.8 0x00007f484b39f402
clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) + 978
31 libclangFrontendTool.so.3.8 0x00007f484affa764
clang::ExecuteCompilerInvocation(clang::CompilerInstance*) + 1172
32 clang-3.8 0x0000000000423f08
cc1_main(llvm::ArrayRef<char const*>, char const*, void*) + 920
33 clang-3.8 0x0000000000417839
34 clang-3.8 0x0000000000416715 main + 2277
35 libc.so.6 0x00007f484a432ec5 __libc_start_main + 245
36 clang-3.8 0x0000000000415ce4
Stack dump:

1.<eof> parser at end of file

  1. Per-module optimization passes
  2. Running pass 'CallGraph Pass Manager' on module 'a.c'.
  3. Running pass 'Value Propagation' on function '@fsolv'

Repository:

rL LLVM

http://reviews.llvm.org/D13378

llvm-commits mailing list
llvm-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

Diffusion mentioned this in rL249528: Revert "This patch builds on top of D13378 to handle constant condition.".Oct 7 2015, 2:05 AM
Diffusion mentioned this in rL249581: Revert "Revert "This patch builds on top of D13378 to handle constant….Oct 7 2015, 11:16 AM

Revision Contents

PathSize
llvm/
trunk/
include/
llvm/
Analysis/
10 lines
lib/
Analysis/
423 lines
test/
Analysis/
ScalarEvolution/
104 lines

Diff 36407

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

Show First 20 Lines • Show All 409 Lines • ▼ Show 20 Lines private:
/// We know that there is no SCEV for the specified value. Analyze the /// We know that there is no SCEV for the specified value. Analyze the
/// expression. /// expression.
const SCEV *createSCEV(Value *V); const SCEV *createSCEV(Value *V);
/// Provide the special handling we need to analyze PHI SCEVs. /// Provide the special handling we need to analyze PHI SCEVs.
const SCEV *createNodeForPHI(PHINode *PN); const SCEV *createNodeForPHI(PHINode *PN);
/// Helper function called from createNodeForPHI.
const SCEV *createAddRecFromPHI(PHINode *PN);
/// Helper function called from createNodeForPHI.
const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
/// Provide special handling for a select-like instruction (currently this /// Provide special handling for a select-like instruction (currently this
/// is either a select instruction or a phi node). \p I is the instruction /// is either a select instruction or a phi node). \p I is the instruction
/// being processed, and it is assumed equivalent to "Cond ? TrueVal : /// being processed, and it is assumed equivalent to "Cond ? TrueVal :
/// FalseVal". /// FalseVal".
const SCEV *createNodeForSelect(Instruction *I, Value *Cond, Value *TrueVal, const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond,
Value *FalseVal); Value *TrueVal, Value *FalseVal);
/// Provide the special handling we need to analyze GEP SCEVs. /// Provide the special handling we need to analyze GEP SCEVs.
const SCEV *createNodeForGEP(GEPOperator *GEP); const SCEV *createNodeForGEP(GEPOperator *GEP);
/// Implementation code for getSCEVAtScope; called at most once for each /// Implementation code for getSCEVAtScope; called at most once for each
/// SCEV+Loop pair. /// SCEV+Loop pair.
/// ///
const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
▲ Show 20 Lines • Show All 716 Lines • Show Last 20 Lines

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 3,591 Lines • ▼ Show 20 Lines if (It != ValueExprMap.end()) {
ValueExprMap.erase(It); ValueExprMap.erase(It);
} }
} }
PushDefUseChildren(I, Worklist); PushDefUseChildren(I, Worklist);
} }
} }
/// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
/// a loop header, making it a potential recurrence, or it doesn't. const Loop *L = LI.getLoopFor(PN->getParent());
/// if (!L || L->getHeader() != PN->getParent())
const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { return nullptr;
if (const Loop *L = LI.getLoopFor(PN->getParent()))
if (L->getHeader() == PN->getParent()) {
// The loop may have multiple entrances or multiple exits; we can analyze // The loop may have multiple entrances or multiple exits; we can analyze
// this phi as an addrec if it has a unique entry value and a unique // this phi as an addrec if it has a unique entry value and a unique
// backedge value. // backedge value.
Value *BEValueV = nullptr, *StartValueV = nullptr; Value *BEValueV = nullptr, *StartValueV = nullptr;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
Value *V = PN->getIncomingValue(i); Value *V = PN->getIncomingValue(i);
if (L->contains(PN->getIncomingBlock(i))) { if (L->contains(PN->getIncomingBlock(i))) {
if (!BEValueV) { if (!BEValueV) {
BEValueV = V; BEValueV = V;
} else if (BEValueV != V) { } else if (BEValueV != V) {
BEValueV = nullptr; BEValueV = nullptr;
break; break;
} }
} else if (!StartValueV) { } else if (!StartValueV) {
StartValueV = V; StartValueV = V;
} else if (StartValueV != V) { } else if (StartValueV != V) {
StartValueV = nullptr; StartValueV = nullptr;
break; break;
} }
} }
if (BEValueV && StartValueV) { if (BEValueV && StartValueV) {
// While we are analyzing this PHI node, handle its value symbolically. // While we are analyzing this PHI node, handle its value symbolically.
const SCEV *SymbolicName = getUnknown(PN); const SCEV *SymbolicName = getUnknown(PN);
assert(ValueExprMap.find_as(PN) == ValueExprMap.end() && assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
"PHI node already processed?"); "PHI node already processed?");
ValueExprMap.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName)); ValueExprMap.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName));
// Using this symbolic name for the PHI, analyze the value coming around // Using this symbolic name for the PHI, analyze the value coming around
// the back-edge. // the back-edge.
const SCEV *BEValue = getSCEV(BEValueV); const SCEV *BEValue = getSCEV(BEValueV);
// NOTE: If BEValue is loop invariant, we know that the PHI node just // NOTE: If BEValue is loop invariant, we know that the PHI node just
// has a special value for the first iteration of the loop. // has a special value for the first iteration of the loop.
// If the value coming around the backedge is an add with the symbolic // If the value coming around the backedge is an add with the symbolic
// value we just inserted, then we found a simple induction variable! // value we just inserted, then we found a simple induction variable!
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) { if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
// If there is a single occurrence of the symbolic value, replace it // If there is a single occurrence of the symbolic value, replace it
// with a recurrence. // with a recurrence.
unsigned FoundIndex = Add->getNumOperands(); unsigned FoundIndex = Add->getNumOperands();
for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
if (Add->getOperand(i) == SymbolicName) if (Add->getOperand(i) == SymbolicName)
if (FoundIndex == e) { if (FoundIndex == e) {
FoundIndex = i; FoundIndex = i;
break; break;
} }
if (FoundIndex != Add->getNumOperands()) { if (FoundIndex != Add->getNumOperands()) {
// Create an add with everything but the specified operand. // Create an add with everything but the specified operand.
SmallVector<const SCEV *, 8> Ops; SmallVector<const SCEV *, 8> Ops;
for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
if (i != FoundIndex) if (i != FoundIndex)
Ops.push_back(Add->getOperand(i)); Ops.push_back(Add->getOperand(i));
const SCEV *Accum = getAddExpr(Ops); const SCEV *Accum = getAddExpr(Ops);
// This is not a valid addrec if the step amount is varying each // This is not a valid addrec if the step amount is varying each
// loop iteration, but is not itself an addrec in this loop. // loop iteration, but is not itself an addrec in this loop.
if (isLoopInvariant(Accum, L) || if (isLoopInvariant(Accum, L) ||
(isa<SCEVAddRecExpr>(Accum) && (isa<SCEVAddRecExpr>(Accum) &&
cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) { cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
// If the increment doesn't overflow, then neither the addrec nor // If the increment doesn't overflow, then neither the addrec nor
// the post-increment will overflow. // the post-increment will overflow.
if (const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV)) { if (const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV)) {
if (OBO->getOperand(0) == PN) { if (OBO->getOperand(0) == PN) {
if (OBO->hasNoUnsignedWrap()) if (OBO->hasNoUnsignedWrap())
Flags = setFlags(Flags, SCEV::FlagNUW); Flags = setFlags(Flags, SCEV::FlagNUW);
if (OBO->hasNoSignedWrap()) if (OBO->hasNoSignedWrap())
Flags = setFlags(Flags, SCEV::FlagNSW); Flags = setFlags(Flags, SCEV::FlagNSW);
} }
} else if (GEPOperator *GEP = dyn_cast<GEPOperator>(BEValueV)) { } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(BEValueV)) {
// If the increment is an inbounds GEP, then we know the address // If the increment is an inbounds GEP, then we know the address
// space cannot be wrapped around. We cannot make any guarantee // space cannot be wrapped around. We cannot make any guarantee
// about signed or unsigned overflow because pointers are // about signed or unsigned overflow because pointers are
// unsigned but we may have a negative index from the base // unsigned but we may have a negative index from the base
// pointer. We can guarantee that no unsigned wrap occurs if the // pointer. We can guarantee that no unsigned wrap occurs if the
// indices form a positive value. // indices form a positive value.
if (GEP->isInBounds() && GEP->getOperand(0) == PN) { if (GEP->isInBounds() && GEP->getOperand(0) == PN) {
Flags = setFlags(Flags, SCEV::FlagNW); Flags = setFlags(Flags, SCEV::FlagNW);
const SCEV *Ptr = getSCEV(GEP->getPointerOperand()); const SCEV *Ptr = getSCEV(GEP->getPointerOperand());
if (isKnownPositive(getMinusSCEV(getSCEV(GEP), Ptr))) if (isKnownPositive(getMinusSCEV(getSCEV(GEP), Ptr)))
Flags = setFlags(Flags, SCEV::FlagNUW); Flags = setFlags(Flags, SCEV::FlagNUW);
} }
// We cannot transfer nuw and nsw flags from subtraction // We cannot transfer nuw and nsw flags from subtraction
// operations -- sub nuw X, Y is not the same as add nuw X, -Y // operations -- sub nuw X, Y is not the same as add nuw X, -Y
// for instance. // for instance.
} }
const SCEV *StartVal = getSCEV(StartValueV); const SCEV *StartVal = getSCEV(StartValueV);
const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
// Since the no-wrap flags are on the increment, they apply to the // Since the no-wrap flags are on the increment, they apply to the
// post-incremented value as well. // post-incremented value as well.
if (isLoopInvariant(Accum, L)) if (isLoopInvariant(Accum, L))
(void)getAddRecExpr(getAddExpr(StartVal, Accum), (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
Accum, L, Flags);
// Okay, for the entire analysis of this edge we assumed the PHI // Okay, for the entire analysis of this edge we assumed the PHI
// to be symbolic. We now need to go back and purge all of the // to be symbolic. We now need to go back and purge all of the
// entries for the scalars that use the symbolic expression. // entries for the scalars that use the symbolic expression.
ForgetSymbolicName(PN, SymbolicName); ForgetSymbolicName(PN, SymbolicName);
ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV; ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV;
return PHISCEV; return PHISCEV;
} }
} }
} else if (const SCEVAddRecExpr *AddRec = } else if (const SCEVAddRecExpr *AddRec =
dyn_cast<SCEVAddRecExpr>(BEValue)) { dyn_cast<SCEVAddRecExpr>(BEValue)) {
// Otherwise, this could be a loop like this: // Otherwise, this could be a loop like this:
// i = 0; for (j = 1; ..; ++j) { .... i = j; } // i = 0; for (j = 1; ..; ++j) { .... i = j; }
// In this case, j = {1,+,1} and BEValue is j. // In this case, j = {1,+,1} and BEValue is j.
// Because the other in-value of i (0) fits the evolution of BEValue // Because the other in-value of i (0) fits the evolution of BEValue
// i really is an addrec evolution. // i really is an addrec evolution.
if (AddRec->getLoop() == L && AddRec->isAffine()) { if (AddRec->getLoop() == L && AddRec->isAffine()) {
const SCEV *StartVal = getSCEV(StartValueV); const SCEV *StartVal = getSCEV(StartValueV);
// If StartVal = j.start - j.stride, we can use StartVal as the // If StartVal = j.start - j.stride, we can use StartVal as the
// initial step of the addrec evolution. // initial step of the addrec evolution.
if (StartVal == getMinusSCEV(AddRec->getOperand(0), if (StartVal ==
AddRec->getOperand(1))) { getMinusSCEV(AddRec->getOperand(0), AddRec->getOperand(1))) {
// FIXME: For constant StartVal, we should be able to infer // FIXME: For constant StartVal, we should be able to infer
// no-wrap flags. // no-wrap flags.
const SCEV *PHISCEV = const SCEV *PHISCEV = getAddRecExpr(StartVal, AddRec->getOperand(1),
getAddRecExpr(StartVal, AddRec->getOperand(1), L, L, SCEV::FlagAnyWrap);
SCEV::FlagAnyWrap);
// Okay, for the entire analysis of this edge we assumed the PHI // Okay, for the entire analysis of this edge we assumed the PHI
// to be symbolic. We now need to go back and purge all of the // to be symbolic. We now need to go back and purge all of the
// entries for the scalars that use the symbolic expression. // entries for the scalars that use the symbolic expression.
ForgetSymbolicName(PN, SymbolicName); ForgetSymbolicName(PN, SymbolicName);
ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV; ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV;
return PHISCEV; return PHISCEV;
} }
} }
} }
} }
return nullptr;
}
const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
const Loop *L = LI.getLoopFor(PN->getParent());
// Try to match a control flow sequence that branches out at BI and merges
// back at Merge into a "C ? LHS : RHS" select pattern. Return true on a
// successful match.
auto BrPHIToSelect = [&](BranchInst *BI, PHINode *Merge, Value *&C,
Value *&LHS, Value *&RHS) {
C = BI->getCondition();
BasicBlockEdge LeftEdge(BI->getParent(), BI->getSuccessor(0));
BasicBlockEdge RightEdge(BI->getParent(), BI->getSuccessor(1));
if (!LeftEdge.isSingleEdge())
return false;
assert(RightEdge.isSingleEdge() && "Follows from LeftEdge.isSingleEdge()");
Use &LeftUse = Merge->getOperandUse(0);
Use &RightUse = Merge->getOperandUse(1);
if (DT.dominates(LeftEdge, LeftUse) && DT.dominates(RightEdge, RightUse)) {
LHS = LeftUse;
RHS = RightUse;
return true;
} }
if (DT.dominates(LeftEdge, RightUse) && DT.dominates(RightEdge, LeftUse)) {
LHS = RightUse;
RHS = LeftUse;
return true;
}
return false;
};
// Checks if the SCEV S is available at BB. S is considered available at BB
// if S can be materialized at BB without introducing a fault.
auto IsAvailableOnEntry = [&](const SCEV *S, BasicBlock *BB) {
struct CheckAvailable {
bool TraversalDone = false;
bool Available = true;
const Loop *L = nullptr; // The loop BB is in (can be nullptr)
BasicBlock *BB = nullptr;
DominatorTree &DT;
CheckAvailable(const Loop *L, BasicBlock *BB, DominatorTree &DT)
: L(L), BB(BB), DT(DT) {}
bool setUnavailable() {
TraversalDone = true;
Available = false;
return false;
}
bool follow(const SCEV *S) {
switch (S->getSCEVType()) {
case scConstant: case scTruncate: case scZeroExtend: case scSignExtend:
case scAddExpr: case scMulExpr: case scUMaxExpr: case scSMaxExpr:
// These expressions are available if their operand(s) is/are.
return true;
case scAddRecExpr: {
// We allow add recurrences that are on the loop BB is in, or some
// outer loop. This guarantees availability because the value of the
// add recurrence at BB is simply the "current" value of the induction
// variable. We can relax this in the future; for instance an add
// recurrence on a sibling dominating loop is also available at BB.
const auto *ARLoop = cast<SCEVAddRecExpr>(S)->getLoop();
if (L && (ARLoop == L || ARLoop->contains(L)))
return true;
return setUnavailable();
}
case scUnknown: {
// For SCEVUnknown, we check for simple dominance.
const auto *SU = cast<SCEVUnknown>(S);
Value *V = SU->getValue();
if (isa<Argument>(V))
return false;
if (isa<Instruction>(V) && DT.dominates(cast<Instruction>(V), BB))
return false;
return setUnavailable();
}
case scUDivExpr:
case scCouldNotCompute:
// We do not try to smart about these at all.
return setUnavailable();
}
llvm_unreachable("switch should be fully covered!");
}
bool isDone() { return TraversalDone; }
};
CheckAvailable CA(L, BB, DT);
SCEVTraversal<CheckAvailable> ST(CA);
ST.visitAll(S);
return CA.Available;
};
if (PN->getNumIncomingValues() == 2) {
// Try to match
//
// br %cond, label %left, label %right
// left:
// br label %merge
// right:
// br label %merge
// merge:
// V = phi [ %x, %left ], [ %y, %right ]
//
// as "select %cond, %x, %y"
BasicBlock *IDom = DT[PN->getParent()]->getIDom()->getBlock();
assert(IDom && "At least the entry block should dominate PN");
auto *BI = dyn_cast<BranchInst>(IDom->getTerminator());
Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
if (BI && BI->isConditional() && BrPHIToSelect(BI, PN, Cond, LHS, RHS) &&
IsAvailableOnEntry(getSCEV(LHS), PN->getParent()) &&
IsAvailableOnEntry(getSCEV(RHS), PN->getParent()))
return createNodeForSelectOrPHI(PN, Cond, LHS, RHS);
}
return nullptr;
}
const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
if (const SCEV *S = createAddRecFromPHI(PN))
return S;
if (const SCEV *S = createNodeFromSelectLikePHI(PN))
return S;
// If the PHI has a single incoming value, follow that value, unless the // If the PHI has a single incoming value, follow that value, unless the
// PHI's incoming blocks are in a different loop, in which case doing so // PHI's incoming blocks are in a different loop, in which case doing so
// risks breaking LCSSA form. Instcombine would normally zap these, but // risks breaking LCSSA form. Instcombine would normally zap these, but
// it doesn't have DominatorTree information, so it may miss cases. // it doesn't have DominatorTree information, so it may miss cases.
if (Value *V = SimplifyInstruction(PN, F.getParent()->getDataLayout(), &TLI, if (Value *V = SimplifyInstruction(PN, F.getParent()->getDataLayout(), &TLI,
&DT, &AC)) &DT, &AC))
if (LI.replacementPreservesLCSSAForm(PN, V)) if (LI.replacementPreservesLCSSAForm(PN, V))
return getSCEV(V); return getSCEV(V);
// If it's not a loop phi, we can't handle it yet. // If it's not a loop phi, we can't handle it yet.
return getUnknown(PN); return getUnknown(PN);
} }
const SCEV *ScalarEvolution::createNodeForSelect(Instruction *I, Value *Cond, const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Instruction *I,
Value *Cond,
Value *TrueVal, Value *TrueVal,
Value *FalseVal) { Value *FalseVal) {
// Try to match some simple smax or umax patterns. // Try to match some simple smax or umax patterns.
auto *ICI = dyn_cast<ICmpInst>(Cond); auto *ICI = dyn_cast<ICmpInst>(Cond);
if (!ICI) if (!ICI)
return getUnknown(I); return getUnknown(I);
Value *LHS = ICI->getOperand(0); Value *LHS = ICI->getOperand(0);
Value *RHS = ICI->getOperand(1); Value *RHS = ICI->getOperand(1);
▲ Show 20 Lines • Show All 793 Lines • ▼ Show 20 Lines case Instruction::PHI:
return createNodeForPHI(cast<PHINode>(U)); return createNodeForPHI(cast<PHINode>(U));
case Instruction::Select: case Instruction::Select:
// U can also be a select constant expr, which let fall through. Since // U can also be a select constant expr, which let fall through. Since
// createNodeForSelect only works for a condition that is an `ICmpInst`, and // createNodeForSelect only works for a condition that is an `ICmpInst`, and
// constant expressions cannot have instructions as operands, we'd have // constant expressions cannot have instructions as operands, we'd have
// returned getUnknown for a select constant expressions anyway. // returned getUnknown for a select constant expressions anyway.
if (isa<Instruction>(U)) if (isa<Instruction>(U))
return createNodeForSelect(cast<Instruction>(U), U->getOperand(0), return createNodeForSelectOrPHI(cast<Instruction>(U), U->getOperand(0),
U->getOperand(1), U->getOperand(2)); U->getOperand(1), U->getOperand(2));
default: // We cannot analyze this expression. default: // We cannot analyze this expression.
break; break;
} }
return getUnknown(V); return getUnknown(V);
} }
▲ Show 20 Lines • Show All 4,515 Lines • Show Last 20 Lines

llvm/trunk/test/Analysis/ScalarEvolution/smax-br-phi-idioms.ll

; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
define i32 @f0(i32 %x, i32 %y) {
; CHECK-LABEL: Classifying expressions for: @f0
entry:
%c = icmp sgt i32 %y, 0
br i1 %c, label %add, label %merge
add:
%sum = add i32 %x, %y
br label %merge
merge:
%v = phi i32 [ %sum, %add ], [ %x, %entry ]
; CHECK: %v = phi i32 [ %sum, %add ], [ %x, %entry ]
; CHECK-NEXT: --> ((0 smax %y) + %x) U: full-set S: full-set
ret i32 %v
}
define i32 @f1(i32 %x, i32 %y) {
; CHECK-LABEL: Classifying expressions for: @f1
entry:
%c = icmp sge i32 %y, 0
br i1 %c, label %add, label %merge
add:
%sum = add i32 %x, %y
br label %merge
merge:
%v = phi i32 [ %sum, %add ], [ %x, %entry ]
; CHECK: %v = phi i32 [ %sum, %add ], [ %x, %entry ]
; CHECK-NEXT: --> ((0 smax %y) + %x) U: full-set S: full-set
ret i32 %v
}
define i32 @f2(i32 %x, i32 %y, i32* %ptr) {
; CHECK-LABEL: Classifying expressions for: @f2
entry:
%c = icmp sge i32 %y, 0
br i1 %c, label %add, label %merge
add:
%lv = load i32, i32* %ptr
br label %merge
merge:
%v = phi i32 [ %lv, %add ], [ %x, %entry ]
; CHECK: %v = phi i32 [ %lv, %add ], [ %x, %entry ]
; CHECK-NEXT: --> %v U: full-set S: full-set
ret i32 %v
}
define i32 @f3(i32 %x, i32 %init, i32 %lim) {
; CHECK-LABEL: Classifying expressions for: @f3
entry:
br label %loop
loop:
%iv = phi i32 [ %init, %entry ], [ %iv.inc, %merge ]
%iv.inc = add i32 %iv, 1
%c = icmp sge i32 %iv, 0
br i1 %c, label %add, label %merge
add:
%sum = add i32 %x, %iv
br label %merge
merge:
%v = phi i32 [ %sum, %add ], [ %x, %loop ]
; CHECK: %v = phi i32 [ %sum, %add ], [ %x, %loop ]
; CHECK-NEXT: --> ((0 smax {%init,+,1}<%loop>) + %x) U: full-set S: full-set
%be.cond = icmp eq i32 %iv.inc, %lim
br i1 %be.cond, label %loop, label %leave
leave:
ret i32 0
}
define i32 @f4(i32 %x, i32 %init, i32 %lim) {
; CHECK-LABEL: Classifying expressions for: @f4
entry:
%c = icmp sge i32 %init, 0
br i1 %c, label %add, label %merge
add:
br label %loop
loop:
%iv = phi i32 [ %init, %add ], [ %iv.inc, %loop ]
%iv.inc = add i32 %iv, 1
%be.cond = icmp eq i32 %iv.inc, %lim
br i1 %be.cond, label %loop, label %add.cont
add.cont:
%sum = add i32 %x, %iv
br label %merge
merge:
%v = phi i32 [ %sum, %add.cont ], [ %x, %entry ]
; CHECK: %v = phi i32 [ %sum, %add.cont ], [ %x, %entry ]
; CHECK-NEXT: --> %v U: full-set S: full-set
ret i32 %v
}