This is an archive of the discontinued LLVM Phabricator instance.

[WIP][Attributor] AAPotentialValues Attribute
AbandonedPublic

Authored by okura on Jun 2 2020, 4:08 AM.

Details

Summary

As discussed in D68934, an abstract attribute which collects all potential values for each value is planned to be introduced. Ultimately, it is expected that functionalities of AAValueSimplify and AAReturnedValues are unified and replaced by this AA, and that value simplification is improved. But we implement it separately from those AAs at first.

This AA collects potential values for each IR position. Currently, only integer values are supported.
The state for this AA is a set. An assumed set is initialized with the empty set (the best state).
To save time and space, we give up collecting potential values when the number of potential values is no less than the given threshold (command line option MaxPotentialValues).

Diff Detail

Event Timeline

okura created this revision.Jun 2 2020, 4:08 AM
Herald added a reviewer: uenoku. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
okura updated this revision to Diff 267838.Jun 2 2020, 4:13 AM
jdoerfert added inline comments.Jun 2 2020, 8:28 AM
llvm/test/Transforms/Attributor/potential.ll
2

We need RUN lines and use the update test script to get check lines.

okura updated this revision to Diff 269087.Jun 7 2020, 6:47 PM

Add boilerplates and some implementation (but still in progress)

okura updated this revision to Diff 269090.Jun 7 2020, 7:29 PM
okura added a comment.Jun 7 2020, 8:04 PM
  • I didn't know what I should use to maintain potential values uniformly for integer type and floating point number type. So I consulted implementation of AAConstantRange and implemented it for integer type only at first. (by using a set of APInt)
  • We have to represent a full set (which contains arbitrary possible elements). Because we actually cannot make the set, I represented an internal state by using a pair of boolean variable, which indicates whether the corresponding set is full or not, and a set of APInt.
  • Logic in Initialize and updateImpl of each kind of IRPositions is quite incomplete and I haven't made any use of the new AA yet.
fhahn added a subscriber: fhahn.Jun 8 2020, 1:47 AM

Interesting! Do you have an idea how often this leads to further simplifications? Might be interesting to collect stats on the impact on the test-suite and compile-time/memory impact, as this potentially could be quite expensive to maintain.

Interesting! Do you have an idea how often this leads to further simplifications? Might be interesting to collect stats on the impact on the test-suite and compile-time/memory impact, as this potentially could be quite expensive to maintain.

Fair point, not trivial to do "right now" though as the real users are missing.

First, the good thing is, this can easily be opt-on, if you blacklist this AA, or not seed it initially, you will never spend any time tracking stuff.
The are two benefits of this I imagine, (1) liveness, (2) versioning. The advanced liveness + value simplification patch is pending and there is even more opportunities once this is in.
Versioning is something we are just now exploring and we will need to wait for some (deep) wrapper stuff and call site specific liveness first.

Long story short, we should do some memory and compile time tracking now but before we get more users the results might not be too interesting.

okura updated this revision to Diff 271017.Jun 16 2020, 3:48 AM
  • generate CHECK lines for tests
  • implement updateImpl and tried to make use of it from AAValueSimplify

From debug output, I think new AA collects potential values correctly, but I was not able to achieve expected simplification in some tests.
In this week, I spent most of time debugging, but I have not found the cause yet.

okura updated this revision to Diff 271048.EditedJun 16 2020, 5:00 AM

I found why it doesn't work. In 'AAValueSimplify::updateImpl' , sometimes 'askSimplifiedValueForAAPotentialValues' is not called and the dependency between them is not recorded. So I changed it to always call 'askSimplifiedValueForAAPotentialValues'.
I will add logic for binary operators to 'AAPotentialValues::updateImpl'

I found why it doesn't work. In 'AAValueSimplify::updateImpl' , sometimes 'askSimplifiedValueForAAPotentialValues' is not called and the dependency between them is not recorded. So I changed it to always call 'askSimplifiedValueForAAPotentialValues'.
I will add logic for binary operators to 'AAPotentialValues::updateImpl'

So you'll update this shortly, right?

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

^ The different RUN lines are still missing. See the other tests :)

I found why it doesn't work. In 'AAValueSimplify::updateImpl' , sometimes 'askSimplifiedValueForAAPotentialValues' is not called and the dependency between them is not recorded. So I changed it to always call 'askSimplifiedValueForAAPotentialValues'.
I will add logic for binary operators to 'AAPotentialValues::updateImpl'

So you'll update this shortly, right?

Yes, I'll update this patch soon.

okura updated this revision to Diff 271938.Jun 19 2020, 12:56 AM

I'm sorry for the delayed update. When I add logic for binary operators, I had a new problem and It took me a while to settle.

  • add logic for binary operators in AAPotentialValueFloating::updateImpl
  • fix fatal mistakes in a method of PotentialValueState
  • change whole logic in AAPotentialValuesCallSiteArgument
  • confirmed all expected value simplification were achieved by above changes

There remain some unnecessary print statements for debugging. I'll delete it.

jdoerfert added inline comments.Jun 22 2020, 6:38 PM
llvm/include/llvm/Transforms/IPO/Attributor.h
2980

What is 100 and 101 here? I think the declarations should go into the class below so they are not in global namespace.

2994

Unsure if you need/want to inherit from the void* specialization.

2996

You might want to make this a template class parametrized with MemberTy. Below you can specialize it struct PotentialConstantValueSet : public PotentialValueSet<APInt> {};

3027

Style: replace auto & with const APInt & and e with C maybe. Also no braces.
Check if the set doesn't have a union member already.

3047

This doesn't actually do intersect, I think. If there is no intersect member collect all new value not the ones to be erased. That way it should work more easily. See also set comments above.

3051

Add documentation here. Also explain in the class comment or here what it means for a set to be full.

3069

7 needs to be replaced by a command line option

3144

Do you really need the known state or would a boolean suffice to track if the state is fix and valid? If it's the latter, you can use a BooleanState member for that.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp
3428–3429

Formatting changes should be moved to an [NFC] commit before the patch.

4436

Can we try to merge this function and the one above. Maybe use a template for the type for the queried AA, i mean AAPotentialValues.

4494

We should not eagerly call these but instead try value simplify first. Maybe wrap the two functions above in a wrapper that is called below (line 4539) or merge the two functions above if that makes sense.

4543

Same comment as last.

4627

Same comment as last.

7125

not needed.

7421

Put these large conditionals in separate helper functions please.

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

YaY! :)

okura updated this revision to Diff 273949.Jun 28 2020, 9:46 AM
  • change PotentialValuesSet
  • handle division by zero in calculateBinaryOperator
  • call askSimplifiedValueFor after value simplifying
  • delete unnecessary debug prints
  • add comments
  • add test for PHINode

I add the threshold as a command-line option, but I got the following error message when I run it.
I don't know the cause and I got stuck. Could you tell me where my mistake is?

: CommandLine Error: Option 'attributor-max-potential-values' registered more than once!
LLVM ERROR: inconsistency in registered CommandLine options
uenoku added a comment.EditedJun 28 2020, 11:03 AM

MaxPotentialValues is defined multiple times if you put the definition to the header.
You have to make it an external variable or declare in AttributorAttributes.cpp

Some high-level comments. I need to go over the logic later on.

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

What you can do is:

  1. Put the static value as non-const into the PotentialValueState class below.
  2. put the command line option into the cpp file.
  3. use the static location as the "location" of the command line option, that is the place the value is put. Search the code for cl::location for examples.
3185

I'm not sure if we really want/need to track the known set here. Maybe I just don't understand what we currently track in it. Feel free to explain :)
If it is "just" to match the design of other states, don't worry. Take the full set as the worst state and remove the known stuff.

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

Could you explain how we could end up with conflicting values? I was expecting we define an order here, ask the first pass, if that fails the second.

The design to put it all in the template helper is very nice!

4708

This looks like something we need to split off. If you add this stand-alone, do we see an effect in the tests, or could you create a test for this?

7118

This looks like the abstract state print code I saw before. Can we reuse it to print the state here?

okura added a comment.EditedJun 30 2020, 2:56 AM

I was able to add MaxPotentialValues as command-line option successfully. Thank you for helpful comments, Hideto and Johannes.

added some comments.

okura marked 3 inline comments as done.Jun 30 2020, 3:10 AM
okura added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
3185

Known.IsFull is always true in the current implementation, But when the bit width of an value is 1 or 2, we can initialize known set as actual full-set (isFull is false).
By this, the fixpoint state can be reached faster and we may be able to reduce the number of iterations. That's why I left known in here. Is this a bad idea?

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

I noticed that even if the current assumptions contradict, the assumption must be broken eventually. So I'll fix this.

4708

When I modified failed tests, I figured out the cause of unexpected simplification is here. The problem is not directly related to AAPotentialValues, I will split.
(actually related to AAConstantRange). I have a test in which inappropriate simplification occurs. I will make a new patch.

okura added a comment.EditedJul 7 2020, 1:34 AM

This patch is too large and hard to review. So I split off this patch. D83283

First of all, great patch. Reading the description and the referenced diff, I can't find an explanation about what this patch tries to do, it would be good if you added that. My assumption is:

You try to deduce what potential values can an IR position value get. Currently, it supports only ints (with that assumption I wrote the comments above). Correct?

(Even if you agree with that, please add some explanation about the method you're following)

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

This is something that Johannes can give more insight and also a description for the patch might help but: I guess that what you mean here by "full" is the "top" (or "bottom", depending on how you see it) of a lattice in a data-flow analysis.

Point being, "top" pretty much means "I don't know, it could be anything" and it's a common knowledge for people.

"Full" OTOH, especially without further explanation about what it means, is not that clear IMHO. e.g. can I insert stuff up to a certain point ? When does something becomes full if the set can grow infinitely large ?

3185

I agree with Johannes. OTOH, I'm sorry but I did not understand your comment. First of all, regarding the bit-width, do you mean that e.g. if I have a bit-width of 1, then I know I have only two possible values and so I know the full set ? But what is the "actual" full set ? Even in that case, if you don't know which of the values you have, you still then have pessimistic fix-point (i.e. both values, i.e. isFull = true). No?

okura edited the summary of this revision. (Show Details)Jul 13 2020, 10:37 PM
okura abandoned this revision.Aug 16 2020, 5:55 PM

This patch was split into D83283 and D85632.