Page MenuHomePhabricator

[SCEV] Model ptrtoint(SCEVUnknown) cast not as unknown, but as zext/trunc/self of SCEVUnknown
ClosedPublic

Authored by lebedev.ri on Oct 4 2020, 2:18 PM.

Details

Summary

While we indeed can't treat them as no-ops, i think we can/should do better than just modelling them as unknown.
inttoptr story is complicated, but for ptrtoint, it seems straight-forward to model it just as a zext-or-trunc of unknown.

This may be important now that we track towards making inttoptr/ptrtoint casts not no-op,
and towards preventing folding them into loads/etc (see D88979/D88789/D88788)

Diff Detail

Event Timeline

lebedev.ri created this revision.Oct 4 2020, 2:18 PM
lebedev.ri requested review of this revision.Oct 4 2020, 2:18 PM
lebedev.ri edited the summary of this revision. (Show Details)Oct 4 2020, 2:20 PM

Using getUnknown on a value that SCEV would normally be able to reason about has weird side-effects: unrelated uses of the value will also pick up the Unknown. Not sure what all the implications of that are off the top of my head, but it's hard to reason about.

Also, treating two distinct inttoptr instructions with the same operand as if they're equivalent is a known source of unsoundness; I don't want to expand that.

Given that, I don't think this is the right way to approach the issue. I prefer the approach from https://bugs.llvm.org/show_bug.cgi?id=46786#c20 . That would allow optimizing the given examples, I think: in contexts where we don't care about the derivation of a pointer, we can look through ptrtoint/inttoptr operations. (I don't think I'll have time to implement that in the near future, though.)

lebedev.ri added a comment.EditedOct 5 2020, 12:54 AM

Using getUnknown on a value that SCEV would normally be able to reason about has weird side-effects:
unrelated uses of the value will also pick up the Unknown.

Oh, that is a very good point..

Not sure what all the implications of that are off the top of my head, but it's hard to reason about.

Also, treating two distinct inttoptr instructions with the same operand as if they're equivalent is a known source of unsoundness; I don't want to expand that.

Hm, that sounds weird. Any chance for an example?
Then i'm guessing we can't allow this in any form even if unknown-to-be is a load?
(well, or more generally, even if getSCEV(operand) == unknown?)

Given that, I don't think this is the right way to approach the issue.
I prefer the approach from https://bugs.llvm.org/show_bug.cgi?id=46786#c20 .
That would allow optimizing the given examples,
I think: in contexts where we don't care about the derivation of a pointer,
we can look through ptrtoint/inttoptr operations.
(I don't think I'll have time to implement that in the near future, though.)

See https://bugs.llvm.org/show_bug.cgi?id=34548 for the inttoptr semantic hole.

Also, treating two distinct inttoptr instructions with the same operand as if they're equivalent is a known source of unsoundness; I don't want to expand that.

Hm, that sounds weird. Any chance for an example?
Then i'm guessing we can't allow this in any form even if unknown-to-be is a load?

... and if we can't even model inttoptr(load) as no-op cast(unknown) (can we?),
i'm getting increasingly more worried that we can't fix this in instcombine, either.

nlopes added a comment.Oct 6 2020, 3:24 AM

ptrtoint and inttoptr are different beasts.
Supporting ptrtoint is much simpler. It's inttoptr that makes me uncomfortable. I don't known enough about SCEV to know how it handles these unknown nodes.
To me, the patch makes sense for ptrtoint (as you say, it's just a zext/sext of some unknown value; worst case it's poison if we want to be strict about OOB). Though I can't comment on the inttoptr case (some SCEV expert needs to chime in).

It is now always clear how this patch lead to all these changes in different tests. I can't say if all of them are correct. To make it more reviewable and get progress here, I'd ask for the following:

  • Whever you see test updates adding things like , align 1, please run it without your patch and commit these changes as NFC. This will reduce the scope of changes greatly.
  • A dedicated test file with -analyze -scalar-evolution with single inttoptr, single ptrtoint, their combinations with each other, geps and arithmetics. It should include corner cases (nullptr, negative addresses etc). That would show how this works in isolation;
  • Introduce inttoptr and ptrtoint in two different patches. I share @nlopes 's concern about inttoptr and not really sure how it should work;

Also a question: how this is going to interact with non-integral pointer types (https://llvm.org/docs/LangRef.html#nointptrtype)? I never touched it, but seems that we will have such thing at some point.

Also it bugs me that the address space notion gets lost during this transform, not sure if it may have bad implications.

llvm/test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll
173

I don't quite get how we ended up with this. Do we somehow know that i8* is wider than i32? Is it coming from default data layout or?..

llvm/test/Other/constant-fold-gep.ll
184 ↗(On Diff #296077)

Did the result type change here, or old type of i8* was also i64?

316 ↗(On Diff #296077)

The old output here looks way more reasonable. Is this really what we want?

lebedev.ri abandoned this revision.Oct 8 2020, 2:09 AM

I was just in the process of updating this, hold on..

lebedev.ri reclaimed this revision.Oct 8 2020, 2:09 AM
lebedev.ri planned changes to this revision.
lebedev.ri updated this revision to Diff 296900.Oct 8 2020, 2:24 AM
lebedev.ri retitled this revision from [SCEV] Model inttoptr and ptrtoint casts not as unknown, but as zext/trunc/self of unknown to [SCEV] Model ptrtoint(SCEVUnknown) cast not as unknown, but as zext/trunc/self of SCEVUnknown.
lebedev.ri edited the summary of this revision. (Show Details)

Keep only ptrtoint part, and only when we fail to model the operand as a SCEV expression.
Still need to add standalone tests.

Also a question: how this is going to interact with non-integral pointer types (https://llvm.org/docs/LangRef.html#nointptrtype)? I never touched it, but seems that we will have such thing at some point.

int<->ptr casts are not permitted on non-integral pointers, it's a verifier error, so the best i can tell is: it isn't going to interact.

lebedev.ri updated this revision to Diff 296904.Oct 8 2020, 2:54 AM

Fix polly test, too.

lebedev.ri marked an inline comment as done.Oct 8 2020, 6:31 AM
lebedev.ri added inline comments.
llvm/test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll
173

We called getTruncateOrZeroExtend(OpSCEV, U->getType()) on %int0 = ptrtoint i8* %ptr to i32, which is:

const SCEV *ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
                                                     unsigned Depth) {
  Type *SrcTy = V->getType();
  assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
         "Cannot truncate or zero extend with non-integer arguments!");
  if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
    return V;  // No conversion
  if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty))
    return getTruncateExpr(V, Ty, Depth);
  return getZeroExtendExpr(V, Ty, Depth);
}

, where

/// Return the size in bits of the specified type, for which isSCEVable must
/// return true.
uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const {
  assert(isSCEVable(Ty) && "Type is not SCEVable!");
  if (Ty->isPointerTy())
    return getDataLayout().getIndexTypeSizeInBits(Ty);
  return getDataLayout().getTypeSizeInBits(Ty);
}

So yes, default datalayout.
Which may mean, we need to hardcode it here in the test.

Which may mean, we need to hardcode it here in the test.

Might want a test with layout where pointer size equals/less than 32 bits.

lebedev.ri marked an inline comment as done.Oct 9 2020, 2:53 AM

Which may mean, we need to hardcode it here in the test.

Might want a test with layout where pointer size equals/less than 32 bits.

Yep, will do.

lebedev.ri updated this revision to Diff 297179.Oct 9 2020, 3:51 AM

Alright, i think this should be sufficient to show the behavior here.

lebedev.ri updated this revision to Diff 297194.Oct 9 2020, 4:53 AM

Rebased, NFC.

mkazantsev accepted this revision.Oct 12 2020, 12:14 AM

Ok, let's hope it doesn't bring doom upon us. :) LGTM.

This revision is now accepted and ready to land.Oct 12 2020, 12:14 AM
lebedev.ri edited the summary of this revision. (Show Details)Oct 12 2020, 12:48 AM

Ok, let's hope it doesn't bring doom upon us. :) LGTM.

@mkazantsev @efriedma @nlopes

Thank you for the review.
I think this patch in it's current form should be reasonably safe, but we'll see.

This revision was landed with ongoing or failed builds.Oct 12 2020, 1:04 AM
This revision was automatically updated to reflect the committed changes.
hans added a subscriber: hans.Oct 12 2020, 9:39 AM

Not sure about doom, but it did trigger an assert in Chromium's builds:

llvm/lib/IR/Constants.cpp:1868: static llvm::Constant* llvm::ConstantExpr::getTrunc(llvm::Constant*, llvm::Type*, bool): Assertion `C->getType()->isIntOrIntVectorTy() && "Trunc operand must be integer"' failed.

See https://bugs.chromium.org/p/chromium/issues/detail?id=1137416#c4 for a reproducer.

I've reverted in 17cec6a11a12f815052d56a17ef738cf246a2d9a

Not sure about doom, but it did trigger an assert in Chromium's builds:

llvm/lib/IR/Constants.cpp:1868: static llvm::Constant* llvm::ConstantExpr::getTrunc(llvm::Constant*, llvm::Type*, bool): Assertion `C->getType()->isIntOrIntVectorTy() && "Trunc operand must be integer"' failed.

See https://bugs.chromium.org/p/chromium/issues/detail?id=1137416#c4 for a reproducer.

I've reverted in 17cec6a11a12f815052d56a17ef738cf246a2d9a

Thank you, i can reproduce.

Hi,

I got my share of doom too, even after the fix.
So

opt -S -o - bbi-48445.ll -indvars

crashes with

opt: ../lib/IR/Constants.cpp:1896: static llvm::Constant *llvm::ConstantExpr::getZExt(llvm::Constant *, llvm::Type *, bool): Assertion `C->getType()->isIntOrIntVectorTy() && "ZEXt operand must be integral"' failed.

for the following input:

target datalayout = "p:16:16"

@a_i32 = external global [21 x i32], section ".bss,bss", align 1

define void @test_array_ldm_i32() {
entry:
  br label %for.body42

crit_edge:                                        ; preds = %for.body42
  %split = phi i32 [ %add58, %for.body42 ]
  %add132 = add i32 %split, undef
  unreachable

for.body42:                                       ; preds = %for.body42, %entry
  %sub.ptr.sub49 = sub i32 undef, ptrtoint ([21 x i32]* @a_i32 to i32)
  %sub.ptr.div50 = sdiv exact i32 %sub.ptr.sub49, 2
  %conv51 = sext i32 %sub.ptr.div50 to i64
  %cmp53 = icmp eq i64 %conv51, undef
  %cond55 = select i1 %cmp53, i16 0, i16 1
  %conv56 = sext i16 %cond55 to i32
  %add57 = add i32 65536, %conv56
  %add58 = add i32 undef, %add57
  br i1 false, label %for.body42, label %crit_edge
}

Hi,

I got my share of doom too, even after the fix.
So

opt -S -o - bbi-48445.ll -indvars

crashes with

opt: ../lib/IR/Constants.cpp:1896: static llvm::Constant *llvm::ConstantExpr::getZExt(llvm::Constant *, llvm::Type *, bool): Assertion `C->getType()->isIntOrIntVectorTy() && "ZEXt operand must be integral"' failed.

for the following input:

target datalayout = "p:16:16"

@a_i32 = external global [21 x i32], section ".bss,bss", align 1

define void @test_array_ldm_i32() {
entry:
  br label %for.body42

crit_edge:                                        ; preds = %for.body42
  %split = phi i32 [ %add58, %for.body42 ]
  %add132 = add i32 %split, undef
  unreachable

for.body42:                                       ; preds = %for.body42, %entry
  %sub.ptr.sub49 = sub i32 undef, ptrtoint ([21 x i32]* @a_i32 to i32)
  %sub.ptr.div50 = sdiv exact i32 %sub.ptr.sub49, 2
  %conv51 = sext i32 %sub.ptr.div50 to i64
  %cmp53 = icmp eq i64 %conv51, undef
  %cond55 = select i1 %cmp53, i16 0, i16 1
  %conv56 = sext i16 %cond55 to i32
  %add57 = add i32 65536, %conv56
  %add58 = add i32 undef, %add57
  br i1 false, label %for.body42, label %crit_edge
}

Perfect, thank you. That's the test case i was missing. Will fix in a moment.

Hi,

I got my share of doom too, even after the fix.
So

opt -S -o - bbi-48445.ll -indvars

crashes with

opt: ../lib/IR/Constants.cpp:1896: static llvm::Constant *llvm::ConstantExpr::getZExt(llvm::Constant *, llvm::Type *, bool): Assertion `C->getType()->isIntOrIntVectorTy() && "ZEXt operand must be integral"' failed.

for the following input:

target datalayout = "p:16:16"

@a_i32 = external global [21 x i32], section ".bss,bss", align 1

define void @test_array_ldm_i32() {
entry:
  br label %for.body42

crit_edge:                                        ; preds = %for.body42
  %split = phi i32 [ %add58, %for.body42 ]
  %add132 = add i32 %split, undef
  unreachable

for.body42:                                       ; preds = %for.body42, %entry
  %sub.ptr.sub49 = sub i32 undef, ptrtoint ([21 x i32]* @a_i32 to i32)
  %sub.ptr.div50 = sdiv exact i32 %sub.ptr.sub49, 2
  %conv51 = sext i32 %sub.ptr.div50 to i64
  %cmp53 = icmp eq i64 %conv51, undef
  %cond55 = select i1 %cmp53, i16 0, i16 1
  %conv56 = sext i16 %cond55 to i32
  %add57 = add i32 65536, %conv56
  %add58 = add i32 undef, %add57
  br i1 false, label %for.body42, label %crit_edge
}

Perfect, thank you. That's the test case i was missing. Will fix in a moment.

Fixed in rG7324616660fc0995fa8c166e3c392361222d5dbc, thank you for the reproducer!

Perfect, thank you. That's the test case i was missing. Will fix in a moment.

Fixed in rG7324616660fc0995fa8c166e3c392361222d5dbc, thank you for the reproducer!

Thanks!

Hi @lebedev.ri , it looks as if this commit is causing an assertion failure compiling the following example code.

void bar(void), baz(unsigned);

void foo(char *d, char *s, unsigned n) {
  if ((((unsigned)d | (unsigned)s) & 3) == 0) {
    bar();
  } else {
    unsigned tmp = (unsigned)d - (unsigned)s;
    while (n > tmp) {
      baz(tmp);
      n -= tmp;
    }
  }
}

Compiling this with

clang --target=arm-arm-none-eabi -Os -mthumb -march=armv6s-m -S -o - repro.c

causes an assertion failure:

clang: /data/statham/llvm-project/llvm/lib/Analysis/IVDescriptors.cpp:913: llvm::InductionDescriptor::InductionDescriptor(llvm::Value*, llvm::InductionDescriptor::InductionKind, const llvm::SCEV*, llvm::BinaryOperator*, llvm::SmallVectorImpl<llvm::Instruction*>*): Assertion `(IK == IK_FpInduction || Step->getType()->isIntegerTy()) && "StepValue is not an integer"' failed.

Bisection suggests that this commit introduced it, and reverting this commit causes that code to compile succesfully. Any thoughts?

Hi @lebedev.ri , it looks as if this commit is causing an assertion failure compiling the following example code.

Hi, thank you for the test case!

void bar(void), baz(unsigned);

void foo(char *d, char *s, unsigned n) {
  if ((((unsigned)d | (unsigned)s) & 3) == 0) {
    bar();
  } else {
    unsigned tmp = (unsigned)d - (unsigned)s;
    while (n > tmp) {
      baz(tmp);
      n -= tmp;
    }
  }
}

Compiling this with

clang --target=arm-arm-none-eabi -Os -mthumb -march=armv6s-m -S -o - repro.c

causes an assertion failure:

clang: /data/statham/llvm-project/llvm/lib/Analysis/IVDescriptors.cpp:913: llvm::InductionDescriptor::InductionDescriptor(llvm::Value*, llvm::InductionDescriptor::InductionKind, const llvm::SCEV*, llvm::BinaryOperator*, llvm::SmallVectorImpl<llvm::Instruction*>*): Assertion `(IK == IK_FpInduction || Step->getType()->isIntegerTy()) && "StepValue is not an integer"' failed.

Bisection suggests that this commit introduced it, and reverting this commit causes that code to compile succesfully. Any thoughts?

That is an yet another place that needs updating (because casts are implicit).
The more minimal test case is

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -canon-freeze -S | FileCheck %s

target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
target triple = "thumbv6m-arm-none-eabi"

declare void @widget()
declare void @wobble(i32)

define void @barney(i8* %arg, i8* %arg18, i32 %arg19) {
bb:
  %tmp = ptrtoint i8* %arg to i32
  %tmp20 = ptrtoint i8* %arg18 to i32
  %tmp21 = or i32 %tmp20, %tmp
  %tmp22 = and i32 %tmp21, 3
  %tmp23 = icmp eq i32 %tmp22, 0
  br i1 %tmp23, label %bb24, label %bb25

bb24:
  tail call void @widget()
  br label %bb34

bb25:
  %tmp26 = sub i32 %tmp, %tmp20
  %tmp27 = icmp ult i32 %tmp26, %arg19
  br i1 %tmp27, label %bb28, label %bb34

bb28:
  br label %bb29

bb29:
  %tmp30 = phi i32 [ %tmp31, %bb29 ], [ %arg19, %bb28 ]
  tail call void @wobble(i32 %tmp26)
  %tmp31 = sub i32 %tmp30, %tmp26
  %tmp32 = icmp ugt i32 %tmp31, %tmp26
  br i1 %tmp32, label %bb29, label %bb33

bb33:
  br label %bb34

bb34:
  ret void
}

Let me look a bit more..

Okay. While i could continue pushing through with fixes to this approach,
by now it is quite clear that those aren't fixes, but ad-hoc hacks
that just hide the fact that casts are implicit,
which is normally fine, but not here.

So i'll take a step back here, and re-approach this with @efriedma's
original idea from https://bugs.llvm.org/show_bug.cgi?id=46786#c20.

Thanks.

Thanks for the quick response!