Page MenuHomePhabricator

[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

There are a very large number of changes, so older changes are hidden. Show Older Changes
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
3156

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

3182

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.)

3185

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.

3211

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.)

3278

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

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

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
3185

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
7250

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
3185

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
7250

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
3076

Make this

template<>
struct DenseMapInfo<APInt> {
3110

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.

3114

Do we need this?

3121

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

3150

APInt should be MemberTy, right?

3197

Just check at the end once.

3211

Nit: IntersectSet

3242

Nit: TODO: Support values other than constant integers.

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

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

7244

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
7165

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
3276

nit: unnecessary ()

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

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
3276

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
53

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
3276

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

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

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

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
3276

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?

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
53

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
53

@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
53

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.