Page MenuHomePhabricator

[SCEV] Introduce SCEVPtrToIntExpr (PR46786)

Authored by lebedev.ri on Oct 15 2020, 3:57 AM.



And use it to model LLVM IR's ptrtoint cast.

This is essentially an alternative to D88806, but with no chance for
all the problems it caused due to having the cast as implicit there.
(see rG7ee6c402474a2f5fd21c403e7529f97f6362fdb3)

As we've established by now, there are at least two reasons why we want this:

  • It will allow SCEV to actually model the ptrtoint casts and their operands, instead of treating them as SCEVUnknown
  • It should help with initial problem of PR46786 - this should eventually allow us to not loose pointer-ness of an expression in more cases

As discussed in PR46786, in principle,
we could just extend SCEVUnknown with a is ptrtoint cast, because ScalarEvolution::getPtrToIntExpr()
should sink the cast as far down into the expression as possible,
so in the end we should always end up with SCEVPtrToIntExpr of SCEVUnknown.

But i think that it isn't the best solution, because it doesn't really matter
from memory consumption side - there probably won't be *that* many SCEVPtrToIntExprs
for it to matter, and it allows for much better discoverability.

This probably needs some more tests.
I'm not adding any rewrites right in this patch.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
lebedev.ri added inline comments.Oct 15 2020, 11:08 AM

Yes, otherwise we end up in an endless recursion with createSCEV().


Agree, but unfortunately it is, because ScalarEvolution::getEffectiveSCEVType() is broken.

// The only other support type is pointer.
assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!");
return getDataLayout().getIndexType(Ty);

Index type can be, but is not always, the same type as the pointer-sized integer type.
There's existing test that crashes with assertion without that zextOrTrunc.


Let's see..

lebedev.ri added inline comments.Oct 15 2020, 11:16 AM
FAIL: LLVM :: Analysis/ScalarEvolution/scalable-vector.ll (851 of 943)
******************** TEST 'LLVM :: Analysis/ScalarEvolution/scalable-vector.ll' FAILED ********************
: 'RUN: at line 1';   /builddirs/llvm-project/build-Clang11-unknown/bin/opt -scalar-evolution -analyze -enable-new-pm=0 < /repositories/llvm-project/llvm/test/Analysis/ScalarEvolution/scalable-vector.ll | /builddirs/llvm-project/build-Clang11-unknown/bin/FileCheck /repositories/llvm-project/llvm/test/Analysis/ScalarEvolution/scalable-vector.ll
: 'RUN: at line 2';   /builddirs/llvm-project/build-Clang11-unknown/bin/opt "-passes=print<scalar-evolution>" -disable-output < /repositories/llvm-project/llvm/test/Analysis/ScalarEvolution/scalable-vector.ll 2>&1 | /builddirs/llvm-project/build-Clang11-unknown/bin/FileCheck /repositories/llvm-project/llvm/test/Analysis/ScalarEvolution/scalable-vector.ll
Exit Code: 1

Command Output (stderr):
PLEASE submit a bug report to and include the crash backtrace.
Stack dump:
0.      Program arguments: /builddirs/llvm-project/build-Clang11-unknown/bin/opt -scalar-evolution -analyze -enable-new-pm=0 
1.      Running pass 'Function Pass Manager' on module '<stdin>'.
2.      Running pass 'FunctionPass Printer: Scalar Evolution Analysis' on function '@a'
  #0 0x00007fea72fbf6b3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /repositories/llvm-project/llvm/lib/Support/Unix/
  #1 0x00007fea72fbd5d2 llvm::sys::RunSignalHandlers() /repositories/llvm-project/llvm/lib/Support/Signals.cpp:72:18
  #2 0x00007fea72fbfbb5 SignalHandler(int) /repositories/llvm-project/llvm/lib/Support/Unix/
  #3 0x00007fea75dfc140 __restore_rt (/lib/x86_64-linux-gnu/
  #4 0x00007fea73adfc2a llvm::ScalarEvolution::getSCEV(llvm::Value*) /repositories/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:3747:19
  #5 0x00007fea73aeb3c1 llvm::ScalarEvolution::createNodeForGEP(llvm::GEPOperator*) /repositories/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:0:0
  #6 0x00007fea73ae42a9 llvm::ScalarEvolution::createSCEV(llvm::Value*) /repositories/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:0:12
  #7 0x00007fea73adfc48 llvm::ScalarEvolution::getSCEV(llvm::Value*) /repositories/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:3749:7
  #8 0x00007fea73ae449c llvm::isa_impl_cl<llvm::SCEVConstant, llvm::SCEV const*>::doit(llvm::SCEV const*) /repositories/llvm-project/llvm/include/llvm/Support/Casting.h:104:5
  #9 0x00007fea73ae449c llvm::isa_impl_wrap<llvm::SCEVConstant, llvm::SCEV const*, llvm::SCEV const*>::doit(llvm::SCEV const* const&) /repositories/llvm-project/llvm/include/llvm/Support/Casting.h:131:12
 #10 0x00007fea73ae449c llvm::isa_impl_wrap<llvm::SCEVConstant, llvm::SCEV const* const, llvm::SCEV const*>::doit(llvm::SCEV const* const&) /repositories/llvm-project/llvm/include/llvm/Support/Casting.h:121:12
 #11 0x00007fea73ae449c bool llvm::isa<llvm::SCEVConstant, llvm::SCEV const*>(llvm::SCEV const* const&) /repositories/llvm-project/llvm/include/llvm/Support/Casting.h:142:10
 #12 0x00007fea73ae449c llvm::ScalarEvolution::createSCEV(llvm::Value*) /repositories/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:6373:9
 #13 0x00007fea73adfc48 llvm::ScalarEvolution::getSCEV(llvm::Value*) /repositories/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:3749:7
 #14 0x00007fea73ae01b3 llvm::ScalarEvolution::getSizeOfExpr(llvm::Type*, llvm::Type*) /repositories/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:3568:1
 #15 0x00007fea73adf970 llvm::ScalarEvolution::getGEPExpr(llvm::GEPOperator*, llvm::SmallVectorImpl<llvm::SCEV const*> const&) /repositories/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:3361:19
 #16 0x00007fea73aeb426 llvm::SmallVectorTemplateCommon<llvm::SCEV const*, void>::isSmall() const /repositories/llvm-project/llvm/include/llvm/ADT/SmallVector.h:131:39
 #17 0x00007fea73aeb426 llvm::SmallVectorImpl<llvm::SCEV const*>::~SmallVectorImpl() /repositories/llvm-project/llvm/include/llvm/ADT/SmallVector.h:388:16
 #18 0x00007fea73aeb426 llvm::SmallVector<llvm::SCEV const*, 4u>::~SmallVector() /repositories/llvm-project/llvm/include/llvm/ADT/SmallVector.h:898:3
 #19 0x00007fea73aeb426 llvm::ScalarEvolution::createNodeForGEP(llvm::GEPOperator*) /repositories/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:5297:1
 #20 0x00007fea73ae42a9 llvm::ScalarEvolution::createSCEV(llvm::Value*) /repositories/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:0:12

createSCEV(): don't model nullptr constant as zero integer, but as SCEVUnknon.

lebedev.ri marked 4 inline comments as done.Oct 15 2020, 12:17 PM
lebedev.ri added inline comments.

If you want, I can fix up the polly stuff after this patch is finished.

Yes, that would be awesome, thank you! I'm not at all familiar with polly.

lebedev.ri marked an inline comment as done.

Rebased, NFC.

efriedma added inline comments.Oct 15 2020, 1:25 PM

Oh, that makes sense. Maybe worth adding a comment to explain.


If the index width is narrower than pointer width, the range computed using zextOrTrunc is nonsense: the actual pointer value may not fit into the index type at all.

Off the top of my head, I'm not sure what the canonical IR looks like in cases like that; do we canonicalize the ptrtoint to the pointer width, or the index width?


This shouldn't be necessary with the other change for null pointers.

Oh, also, are you planning to implement the SCEV simplifications in this patch, or a followup? I can see reasons to go either way, I guess. I'd weakly lean towards implementing them here, so we can avoid churn implementing handling for cases that can't happen after simplification.

lebedev.ri marked an inline comment as done and 2 inline comments as not done.Oct 15 2020, 1:38 PM

Oh, also, are you planning to implement the SCEV simplifications in this patch, or a followup? I can see reasons to go either way, I guess. I'd weakly lean towards implementing them here, so we can avoid churn implementing handling for cases that can't happen after simplification.

I would strongly prefer to do that in a follow-up patch, since that is more in-line with incremental development / iterative improvements.


Let me take one more look at what is going on there..

lebedev.ri marked 3 inline comments as done.

@efriedma thank you for taking a look!
Addressed review notes.


Addressed by D89540.

Based on disscussion in D89540, let's just not bother with the case where index size doesn't match pointer size.

I think this looks good. But I'd like a second opinion since this is a substantial change to SCEV modeling.

957 ↗(On Diff #298698)

Please reformat this to something readable.

lebedev.ri updated this revision to Diff 298748.EditedOct 16 2020, 1:52 PM

Reformat the snippet.

Looks like removal of nullptr constant special handling affected
polly tests and i didn't notice it, still need to update them.

I think this looks good. But I'd like a second opinion since this is a substantial change to SCEV modeling.

@efriedma thank you for taking a look!

But I'd like a second opinion since this is a substantial change to SCEV modeling.

@mkazantsev @fhahn thoughts? :)

lebedev.ri marked an inline comment as done.
lebedev.ri added reviewers: Meinersbur, grosser.

Mostly update polly tests.

I don't think that mixing null into AddRecs is correct and expected.


Nit: better add it last, and keep it 1 per line.

534 ↗(On Diff #298843)

What's the type of the AddRec here? Is it an integral-type AddRec with pointer base? If so, this will be a source of various bugs because the code relies on fact that AddRec's type matches Base's type in many places.

mkazantsev requested changes to this revision.Oct 18 2020, 9:50 PM

Seems that this patch leads to worse code generation in Polly in many cases. And I don't see a single case where it does something useful. I think we should have fixes for all of them if we want to merge it.

8 ↗(On Diff #298843)


7 ↗(On Diff #298843)


36 ↗(On Diff #298843)




56 ↗(On Diff #298843)


This revision now requires changes to proceed.Oct 18 2020, 9:50 PM
efriedma added inline comments.Oct 18 2020, 10:33 PM
534 ↗(On Diff #298843)

Should be a pointer-type addrec; it's treating "null" as an opaque pointer.

36 ↗(On Diff #298843)

I suspect the change to null handling is changing the way the icmp is analyzed; should be easy to fix? I'll try to find time to look in the next couple days.

56 ↗(On Diff #298843)

Is it? As far as I can tell, the llvm.gcread is actually loading from a null pointer.

I think we are conflating things here.
@efriedma while i agree that treating nullptr constant as zero seems, suboptimal?,
i'm not sure we have to do that change immediately together with the ptrtoint handling?
Can we do that later? I'll undo it for now..

Backout controversial nullptr constant handling changes - should be a separate patch.

mkazantsev added inline comments.Oct 19 2020, 3:40 AM

This code is still worse than it used to be. What boons do we expect from this patch?

lebedev.ri marked an inline comment as done.Oct 19 2020, 6:24 AM
lebedev.ri added inline comments.

E.g. see the example suggested by @efriedma - @pr46786_c26_char()/@pr46786_c26_int() in llvm/test/Analysis/ScalarEvolution/ptrtoint.ll.
If we don't model ptrtoint, we basically fail to analyze the address of the load/store there,
while it's actually quite simple after D89692.

lebedev.ri marked an inline comment as done.Oct 19 2020, 2:21 PM

Will rebase once i have proper test coverage for D89692 - still need tests for udiv/mul involving a pointer.

Rebased, addded proper test coverage.

mkazantsev added inline comments.Oct 23 2020, 3:53 AM

It doesn't look like the right way to check for loop invariance. getSCEVAtScope can potentially simplify your expression that is still invariant. Example: you have Op = A + B and loop is guarded by condition B = 0. getSCEVAtScope(Op) may return A which is still loop invariant, but not equal to Op.

What you might be looking for is isAvailableAtLoopEntry.

@mkazantsev thank you for taking a look!


Disclaimer: *i'm* not looking for loop invariance.
This chunk is a verbatum copy-paste from SCEVTruncateExpr/SCEVSignExtendExpr/SCEVZeroExtendExpr handling above.
If this isn't the right handling, then they are all wrong, and that's a preexisting problem.

mkazantsev accepted this revision.Oct 23 2020, 5:14 AM

I don't see any more problems, thanks.


Allright, maybe it's just a misleading comment then. Otherwise the code looks fine to me. I'll take a look later into these pieces.

This revision is now accepted and ready to land.Oct 23 2020, 5:14 AM
lebedev.ri marked 2 inline comments as done.Oct 23 2020, 5:19 AM

I don't see any more problems, thanks.

Thank you for the review!
I think it makes sense to land the simplifications (D89692) about at the same time,
so i'll wait until we are happy with that patch too.

Rebased, NFC.

Rebased, NFC.

This revision was landed with ongoing or failed builds.Oct 30 2020, 1:14 AM
This revision was automatically updated to reflect the committed changes.