This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] AAPotentialValues Interface
ClosedPublic

Authored by okura on Jul 7 2020, 1:28 AM.

Details

Summary

This is a split patch of D80991.
This patch introduces AAPotentialValues and its interface only.
For more detail of AAPotentialValues abstract attribute, see the original patch.

Diff Detail

Event Timeline

okura created this revision.Jul 7 2020, 1:28 AM
Herald added a reviewer: uenoku. · View Herald Transcript
Herald added a reviewer: homerdin. · View Herald Transcript
Herald added a reviewer: baziotis. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
okura edited the summary of this revision. (Show Details)Jul 7 2020, 1:37 AM

Nit comments, I haven't yet digested the whole patch.

llvm/include/llvm/Transforms/IPO/Attributor.h
3056

Is there an APInt constructor that takes a pointer and an int ? I think the only such constructor is a private one.

3057

I also think that this U member is private.

okura marked an inline comment as done.Jul 12 2020, 3:50 AM
okura added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
3056

Sorry for the delayed response. This struct is a friend struct of APInt. So Member functions can access the private functions of APInt. (c.f. https://llvm.org/doxygen/APInt_8h_source.html#l00099)
On the other hand, the same struct is defined in "/lib/IR/LLVMContextImpl.h" and I want to include it but I failed to do that.

A nit comment is to please start comments with caps.

In general, this is good I think.

llvm/include/llvm/Transforms/IPO/Attributor.h
3056

Yes, my bad, thank you. If you want to include that, I guess that the problem is that an #include "looks" in llvm/include. You want to go one dir back and to lib. So, ../lib/IR/.... Have you tried that?

3131

Please change this to isAtWorstState for the reasons discussed in the other review (in which though I was wrong to suggest isTop since it is ambiguous whether top is the worst or best state). And add a doc that e.g. the worst state is when the potential values are all the possible values and thus, we know nothing.

3190

Nit: "Unite" -> "Union" (it works as a verb as well). Same for other parts.

llvm/test/Transforms/Attributor/potential.ll
60

I may be missing something here but how do you see the potential values in the output IR ? (Only) through ranges ?
I mean except for e.g. simplifying (e.g. that due to potential values, we deduce that the return value is in fact a constant, like in another test case).

Btw, we have different results that the test in the other diff right (this one: https://reviews.llvm.org/differential/changeset/?ref=2038557) ?
Why is that?

(I'll have to check the tests again).

okura updated this revision to Diff 277664.Jul 13 2020, 10:16 PM
okura marked an inline comment as done.
  • Add documents (mainly AAPotentialValues struct)
  • rename isFull in PotentialValuesState struct to isAtWorstState
okura marked an inline comment as done.Jul 13 2020, 10:26 PM
okura added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
3056

Yes, I tried to do it in that way, but I got many warnings like "DEBUG_TYPE is redefined" when I built. So I gave up and redefine the struct here.

llvm/test/Transforms/Attributor/potential.ll
60

We cannot see the potential values in IR. Potential values are collected just for stronger value simplification for now.
Unlike the original patch, updateImpl has not implemented yet in this patch. So expected value simplification was not achieved and we have different results.

The code is quite good and clean. Most comments are on the doc so that we can make it good and clean too and move to the full patch.

llvm/include/llvm/Transforms/IPO/Attributor.h
177

Nit: Maximum

191

Nit: Worst.
Good comment btw. Note that there are another 2 reasons that we might go to worst state. I would change it as follows:
"If the number of ... to a full set (the worse state)" -> "The set might (only) be forced to worst state, that is, to contain
every possible value (which effectively means that practically we know nothing about this IR position) in 3 cases:

  1. We surpassed the \p MaxPotentialValues threshold.
  2. We tried to initialize on a Value that we can't handle (e.g. an operator we don't currently handle)
  3. During the iterations, this Value was affected (e.g. because of an operation) by a Value that is in

worst state.

I'm sure about the first 2, I have to think a little bit about whether the 3rd is good. What do you think for this
as a doc comment?

baziotis added inline comments.Jul 14 2020, 3:09 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
94

We need to add a clearer comment here because it is still not clear what isAtWorstState means. Add sth like: "The worst state is when the set, theoretically, contains every possible value. That never happens naturally, we only force it". With that, the doc below will make sense.

188

"will grow while iteration". That doesn't make much sense. You can change it to "will grow monotonically as we find more potential values for this position". Or sth.

3056

Yes, I tried to do it in that way, but I got many warnings like "DEBUG_TYPE is redefined" when I built. So I gave up and redefine the struct here.

Hmm, ok I don't have a way to resolve that. Maybe someone else has some idea.

llvm/test/Transforms/Attributor/potential.ll
60

You are correct, thanks for updating me. You know, we might be able to see the potential values on some tests from the ranges...
Anyway, those tests look good, we'll take a closer look to them on the other patch.

okura updated this revision to Diff 277870.Jul 14 2020, 9:30 AM
This comment was removed by okura.
okura updated this revision to Diff 277874.Jul 14 2020, 9:34 AM

replace full context diff

okura marked an inline comment as done.Jul 16 2020, 9:04 PM
okura added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
191

Thank you for the great suggestion. I think this comment explains the AA succinctly and accurately. As for case 3, we can regard that many potential values are found and we surpass the threshold. So I think the first 2 cases are sufficient.

baziotis added inline comments.Jul 17 2020, 5:15 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
191

Glad you liked it. I think that the third is important, because it lays out how different Values affect one another. For example,
if the current Value is in an operation with a Value that is in worst state, then the current also goes into worst state but not because of the threshold.

okura updated this revision to Diff 278959.Jul 17 2020, 7:06 PM
  • add document
  • eliminate an unnecessary include statement

Apologies for the long wait. Here are some more comments.

llvm/include/llvm/Transforms/IPO/Attributor.h
3434

Make the two members private please, we can access them via getters.

3460

I would prefer if we update isAtWorstState as soon as we modify the set and reach the number of allowed values. So after each (potential) increase we check and update isAtWorstState. That way it is clear that "isValid" always equals "isAtWorstState". (We can also name isAtWorstState IsValid.)

3463

This "tracks" only the worst state fixpoint but not any other one, e.g., if it is a known constant. Are you sure we don't need a separate boolean to track this. I would have assumes so to avoid calling update on the AA after we used indicateOptimisticFixpoint.

One way to handle this is to replace isAtWorstState with a BooleanState which handles the fixpoint and the valid bit. You can probably even derive from that class to minimize the code you need to type, e.g., a lot of functions provided by BooleanState might then just be good enough. Only once you need to inspect or touch the Set you have to provide functions here.

3489

We might want to add an assertion here. no point in handing out meaningless data. (I guess other types lack such an assertion as well.)

3556

We should not have a variable like this but use !Assumed.isValid() for this.

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

Would it make sense to let AAPotentialValuesCallSiteArgument derive from AAPotentialValuesFloating? We often do that.

okura updated this revision to Diff 279030.Jul 18 2020, 3:47 PM
  • change PotentialValueSet to inherit BooleanState
  • change access specifier for some members
  • add documents
okura marked 2 inline comments as done.Jul 18 2020, 4:04 PM
okura added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
3463

I do not notice that it became unable to track fixpoint in the optimistic case by eliminating Known state. I changed this to derive from BooleanState as you suggest.
By this, I feel that PotentialValuesState becomes a simple (unnecessary) wrapper for PotentialValueSet. Do you think I have to merge two structs together?

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

I will probably override both initialize and updateImpl in AAPotentialValuesCallSiteArgument. Even so, is deriving from AAPotentialValuesFloating better than from AAPotentialValuesImpl ?

okura marked 4 inline comments as done and an inline comment as not done.Jul 18 2020, 4:43 PM
jdoerfert added inline comments.Jul 18 2020, 6:19 PM
llvm/include/llvm/Transforms/IPO/Attributor.h
3463

If there is no reason (right now) to keep them separate, merge them. Keep it a template though, I think.

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

The benefit usually is that initialize and/or updateImpl are the same or we want to do something special for the call site argument case and fall back to the floating case if it didn't work. So basically, if you can/want to reuse the floating logic somehow, it makes sense to inherit from the floating AA.

Take struct AAValueSimplifyCallSiteArgument : AAValueSimplifyFloating as an example. The "value" is derived the same regardless but the floating algorithm can use the CtxI which is set for the call site argument case.

okura updated this revision to Diff 279058.Jul 18 2020, 10:36 PM
  • merge PotentialValueSet and PotentialValuesState together
  • derive AAPotentialValuesCallsiteArgument from AAPotentialValuesFloating
okura marked 2 inline comments as done.Jul 18 2020, 10:36 PM

Last set of minor comments. I think this is ready in after.

llvm/include/llvm/Transforms/IPO/Attributor.h
3354

Make this

template<>
struct DenseMapInfo<APInt> {
3388

The default state should not force the boolean state to "invalid". Just keep the default behavior which is to create an optimistic state by default.

3392

Do we need this?

3399

Make the return type const SetTy &. No need to copy the set always, if the caller wants to do that they still can.

3428

APInt should be MemberTy, right?

3475

Just check at the end once.

3489

Nit: IntersectSet

3520

Nit: TODO: Support values other than constant integers.

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

I guess something like this should be the default implementation in AbstractAttribute already. We could probably remove quite a lot of duplication. Follow up ;)

7343

We don't need this method (for now). The one in AAPotentialValuesFloating will do fine (for now).

llvm/test/Transforms/Attributor/potential.ll
386

Manually add check lines for the ranges please.

okura updated this revision to Diff 279116.Jul 19 2020, 6:14 PM
  • remove AAPotentialValuesCallSiteArgument::initialize
  • rename key info struct for APInt (and register it as friend of APInt)
  • add check lines for range

I ran whole tests and I found tools/llvm-cov/universal_bin_wrapping_archives.test failed. I investigate the cause of it now.

okura marked 10 inline comments as done.Jul 19 2020, 6:16 PM
okura added a comment.Jul 19 2020, 6:51 PM

I built latest master branch and ran test, but that test failed again.

okura added a comment.Jul 27 2020, 8:37 AM

@jdoerfert Could you give me feedback for this?

jdoerfert accepted this revision.Jul 30 2020, 5:19 PM

Don't worry about the other test, master is sometimes broken as well. I left one comment for a follow up patch and one comment for a cleanup to avoid code duplication we have now.
Assuming that can be done without problems prior to committing this, the patch looks good to me :)

llvm/include/llvm/ADT/APInt.h
102 ↗(On Diff #279116)

This is the same thing as DenseMapAPIntKeyInfo right? We should for sure avoid duplication. Let's just move the implementation into this header, call it DenseMapInfo<APInt>, and use it instead of DenseMapAPIntKeyInfo in LLVMContextImpl.h. That way everyone else can put an APInt into a DenseMap as well.

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

In a follow up we should add a flag to the state to indicate it is not empty but contains undef. That would allow us to merge such a state with for example 7 and get 7.

This revision is now accepted and ready to land.Jul 30 2020, 5:19 PM
fhahn added a subscriber: fhahn.Jul 31 2020, 2:26 AM
fhahn added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
3554

nit: unnecessary ()

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

Why not just use MaxPotentialValues directly and keep it as a global? There might be a reason for doing so that I am missing, but it seems like similar options (e.g. MaxHeapToStackSize) are also just using the global directly.

okura added inline comments.Aug 2 2020, 1:25 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
3554

These brackets are unnecessary indeed, but this function is one of the boilerplate functions of AbstactAttributes and the other AAs have the same implementation. So I think we don't need to remove them.

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

AAPotentialValues support only integer values now, and similar AA for pointer values or floating values might be introduced. To implement them, we can use the template class PotentialValuesState. I think it is better to be able to set a different threshold for each of them. That is why I keep it as a member variable of PotentialValuesState.

okura updated this revision to Diff 282434.Aug 2 2020, 2:33 AM
  • move DenseMapInfo<APInt> to APInt.h
This revision was automatically updated to reflect the committed changes.
fhahn added inline comments.Aug 2 2020, 3:16 AM
llvm/include/llvm/ADT/APInt.h
2293 ↗(On Diff #282434)

I am not sure this is the right place. Shouldn't that go into DenseMapInfo.h? Also, if this gets added there, it should probably be split off from this patch.

fhahn added inline comments.Aug 2 2020, 3:18 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
3554

FWIW, I think this is very uncommon in most parts of the llvm codebase.

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

But if you want to set them separately, you'd need separate options?

thakis added a subscriber: thakis.Aug 2 2020, 4:40 AM

This causes:

llvm/lib/Transforms/IPO/AttributorAttributes.cpp:56:49: error: explicit specialization of 'MaxPotentialValues' after instantiation
unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0;

^

../../llvm/lib/Transforms/IPO/AttributorAttributes.cpp:52:57: note: implicit instantiation first required here

cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues),
                                                    ^
okura added inline comments.Aug 2 2020, 5:30 AM
llvm/include/llvm/ADT/APInt.h
2293 ↗(On Diff #282434)

I'm sorry. I will move this into DenseMapInfo.h in a new patch.

llvm/include/llvm/Transforms/IPO/Attributor.h
3554

I think so too. I will make a new patch to remove these brackets in all AbstractAttriutes.

okura added a comment.Aug 2 2020, 5:33 AM

This causes:

llvm/lib/Transforms/IPO/AttributorAttributes.cpp:56:49: error: explicit specialization of 'MaxPotentialValues' after instantiation
unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0;

^

../../llvm/lib/Transforms/IPO/AttributorAttributes.cpp:52:57: note: implicit instantiation first required here

cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues),
                                                    ^

I confirmed that I can build successfully with g++ but fail with clang.
Should I revert the commit right away?

thakis added a comment.Aug 2 2020, 6:08 AM

If the fix is quick (< 15 min), you can fix too.

fhahn added a comment.Aug 2 2020, 6:41 AM

This causes:

llvm/lib/Transforms/IPO/AttributorAttributes.cpp:56:49: error: explicit specialization of 'MaxPotentialValues' after instantiation
unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0;

^

../../llvm/lib/Transforms/IPO/AttributorAttributes.cpp:52:57: note: implicit instantiation first required here

cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues),
                                                    ^

I confirmed that I can build successfully with g++ but fail with clang.
Should I revert the commit right away?

I'd just make the option a 'regular' global for now. This will avoid this problem. If the extra complexity is needed in the future, it can always be added back.

okura reopened this revision.Aug 2 2020, 6:58 AM

I reverted the commit.

This revision is now accepted and ready to land.Aug 2 2020, 6:58 AM
okura updated this revision to Diff 282488.Aug 2 2020, 5:38 PM
  • move DenseMapInfo<APInt> into DenseMapInfo.
  • fix MaxPotentialValues and confirmed that I could build with both clang and g++.
okura added a comment.Aug 2 2020, 5:38 PM

This causes:

llvm/lib/Transforms/IPO/AttributorAttributes.cpp:56:49: error: explicit specialization of 'MaxPotentialValues' after instantiation
unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0;

^

../../llvm/lib/Transforms/IPO/AttributorAttributes.cpp:52:57: note: implicit instantiation first required here

cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues),
                                                    ^

I confirmed that I can build successfully with g++ but fail with clang.
Should I revert the commit right away?

I'd just make the option a 'regular' global for now. This will avoid this problem. If the extra complexity is needed in the future, it can always be added back.

Now I'm trying to make it global.

okura added inline comments.Aug 2 2020, 7:35 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
56

Yes, but if we give a different name for each threshold (e.g. MaxPotentialConstantIntValues, MaxPotentialFloatingValues, etc.), I think it is difficult to commonize implementations into PotentialValuesState. I tried to make PotentialValuesState take threshold as a template parameter, but I failed to do that because MaxPotentialValue cannot be a const variable.
FWIW, this option is used in Attributor.h unlike the other options declared in here and we need external storage. Due to this, MaxPotentialValue cannot be const.

If you have an idea, could you tell me that?

OTOH, I confirmed that I could successfully build the current patch with both clang and g++. If we don't necessarily have to change implementation, I can land this anytime.

sstefan1 added inline comments.Aug 3 2020, 12:58 AM
llvm/include/llvm/ADT/DenseMapInfo.h
351 ↗(On Diff #282488)

As @fhahn already mentioned, I guess you can commit DenseMapInfo part separately, as a NFC.

llvm/test/Transforms/Attributor/potential.ll
2

Can you run the update script with --check-attributes to keep it in sync with other attributor tests?

okura marked an inline comment as done.Aug 3 2020, 7:15 AM
okura added inline comments.
llvm/include/llvm/ADT/DenseMapInfo.h
351 ↗(On Diff #282488)

Sorry, I misunderstood the comment. I split the part. (D85131)

okura updated this revision to Diff 282615.Aug 3 2020, 7:24 AM
  • update tests with --check-attributes
  • split patch into D85131
okura updated this revision to Diff 282630.Aug 3 2020, 8:10 AM
  • remove unnecessary change in APInt.h
okura added inline comments.Aug 6 2020, 9:23 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
56

@fhahn Could you give me your opinion?

If there is no response for a while, I will land this.

fhahn added inline comments.Aug 7 2020, 12:50 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
56

Oh right, now I see what you mean I think. I still think it would be better to only add the extra complexity once it is needed, but if it builds now I guess it's fine.

This revision was automatically updated to reflect the committed changes.