Page MenuHomePhabricator

[Attributor] Look through selects in genericValueTraversal
AcceptedPublic

Authored by jdoerfert on Mon, Jun 7, 4:59 PM.

Details

Summary

If we can simplify the select condition we can avoid one value in the
traversal.

Diff Detail

Unit TestsFailed

TimeTest
200 msx64 debian > LLVM.Transforms/Attributor::potential.ll
Script: -- : 'RUN: at line 2'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/opt -enable-new-pm=0 -attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=20 -S < /var/lib/buildkite-agent/builds/llvm-project/llvm/test/Transforms/Attributor/potential.ll | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck --allow-unused-prefixes /var/lib/buildkite-agent/builds/llvm-project/llvm/test/Transforms/Attributor/potential.ll --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
320 msx64 windows > LLVM.Transforms/Attributor::potential.ll
Script: -- : 'RUN: at line 2'; c:\ws\w32-1\llvm-project\premerge-checks\build\bin\opt.exe -enable-new-pm=0 -attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=20 -S < C:\ws\w32-1\llvm-project\premerge-checks\llvm\test\Transforms\Attributor\potential.ll | c:\ws\w32-1\llvm-project\premerge-checks\build\bin\filecheck.exe --allow-unused-prefixes C:\ws\w32-1\llvm-project\premerge-checks\llvm\test\Transforms\Attributor\potential.ll --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM

Event Timeline

jdoerfert created this revision.Mon, Jun 7, 4:59 PM
jdoerfert requested review of this revision.Mon, Jun 7, 4:59 PM
Herald added a project: Restricted Project. · View Herald TranscriptMon, Jun 7, 4:59 PM
Herald added a subscriber: bbn. · View Herald Transcript
baziotis added inline comments.Mon, Jun 7, 6:18 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
310

Not important but SI->getCondition() should return either an i1 or a vector of i1. I don't know what's happening in getAssumedConstant() but I assume it doesn't deal with vectors which means that if C.hasValue() and it is not undef, then it must be a ConstantInt? So, maybe put that in an assert(). OTOH, if later you decide to deal with vectors, those asserts will fire while in this you can just add an else if. Anyway, just wanted to bring it to the foreground and you can choose what is better.

llvm/test/Transforms/Attributor/lvi-for-ashr.ll
45

Why is this not replaced by 3 now?

jdoerfert added inline comments.Thu, Jun 10, 3:12 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
310

It must not be a constantint, even if there are no vectors.

int foo(bool A) {
  B = !A;
  C = !B;
  return C ? 0: 42;
}

C here is a i1, simplified value is (potentially) A which is neither constant nor vector.

llvm/test/Transforms/Attributor/lvi-for-ashr.ll
45

Because we never ask for the simplified value but only look through it in the genericValueTraversal. I'll improve AAPotentialValues in a follow up patch. I'm also considering to ask for a simplified value as part of the genericValueTraversal but I'll need to double check if that is the best idea.

LGTM although I've missed a lot of progress in the Attributor so definitely wait for other reviewers if you want an acceptance to move it forward :)

llvm/lib/Transforms/IPO/AttributorAttributes.cpp
310

Ok, something I probably missed here, which I should've have inferred from the usage of isa_and_nonnull and dyn_cast_or_null, is that C may have a value (i.e., C.hasValue() == true) but its value may be null. Hm.., then why the Optional?

kuter added inline comments.Thu, Jun 10, 4:56 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
309

A.getAssumedConstant returns None if the value simplification wasn't possible.
If the value is simplified but not constant it returns nullptr.

Shouldn't we visit the true and false options when there is no simplification ?
I don't understand why we continue here. I think callback would receive the select instruction itself.
Which is very different from previous behavior.

baziotis added inline comments.Thu, Jun 10, 5:43 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
309

Well, it's an intricate design but now it's clear, thanks!

jdoerfert added inline comments.Thu, Jun 10, 6:26 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
309

A.getAssumedConstant returns None if the value simplification wasn't possible.

No. None means "the value is dead/undetermined so far". You can basically say "there is no value yet".
Eventually, a value other than none is returned, *iff* the value is in fact live.

310
baziotis added inline comments.Thu, Jun 10, 6:59 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
310

I get it from a dataflow framework perspective. I also think Optional is a good choice for a best/worse value (infinites etc.). It's just that it makes it tricky for me if a function returns an optional pointer, which pointer can be null. Because the optional family of structures are a lot of times used exactly to avoid a pointer acting both as a flag and an address. But that's just my perspective and it's probably not a particularly useful review to you :)

jdoerfert added inline comments.Thu, Jun 10, 8:50 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
310

But null means something. All values have a dedicated and important meaning. We "cannot" just not use an optional, nor is the optional used to avoid pointers or null.

   None -> Nothing yet (best)
    |
  Undef -> Second best
/   |  \ 
... 0   1  ...   -> values/constants or similar
\   |   /
  nullptr       -> worst

Does this make more sense?

baziotis added inline comments.Fri, Jun 11, 10:12 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
310

I don't have a misunderstanding on what None and null mean in this context (although I had initially...), but thank you. The problem is that you are using Optional and null in a way that it is not usually used.

Let me give a different and more simplified example to make my case clear. Let's say that you have a function which returns a number. But, you also want to support the concept of "infinite" in which case you return None. So, it looks something like this:

Optional<int> Number = getNumber(...);
if (!Number.hasValue())
  // Do something that has to do with infinite
else
  // .getValue() and handle int

So, what's the problem IMHO with this code ? Optional is usually used to denote "you didn't get a value", "that call failed" etc. It's usually used in a pattern to denote some kind of "failure". But in my pattern, it is actually used as just a different meaningful value. For this reason, if the code does not make an effort to make clear that I'm following a different pattern than the common one, it creates a congestion to the mind of the reader.

In the case of getAssumedConstant(), when I first read it, unconsciously I assumed None means "you didn't get a constant". And because of that, it followed nullptr had no place because its usual place is to denote failure but Optional was used for that. It turned that all these assumptions were wrong because I was thinking in terms of the common case. Now, granted, I should've thought that through. But the usage of common values for different uses than the common ones can be tricky. I hope this provided some value for you!

jdoerfert added inline comments.Fri, Jun 11, 11:14 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
310

I hope this provided some value for you!

I guess we should improve the documentation somewhere :)

kuter accepted this revision.Fri, Jun 11, 11:50 AM

Thanks @jdoerfert for the clarification. I know understand why we are not processing the true and false values there.
The use of Optional in the A.getAssumedConstant definitely seems a little counterintuitive. It is documented in the header
but we might also add some comments to the implementation of the function itself.

LGTM if @baziotis doesn't have any concerns.

This revision is now accepted and ready to land.Fri, Jun 11, 11:50 AM
baziotis accepted this revision.Fri, Jun 11, 12:16 PM

Oh, don't mind me, LGTM!
IMHO, the documentation is fine if the readier gets some hint that they should look at it :P Sth like:

bool BestPossible = !C.hasValue();
bool SecondBest = isa_and_nonnull<UndefValue>(*C);

might do the trick. Like, they will either get it, or they will see that they don't get it and they'll check the doc. But I don't know if you like the style, maybe too verbose.

jdoerfert updated this revision to Diff 352714.Thu, Jun 17, 7:23 AM

Improve according to feedback