[WIP][Attributor] AAPotentialValues Attribute

[okura]

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

[jdoerfert]

llvm/test/Transforms/Attributor/potential.ll

1

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

[okura]

Add boilerplates and some implementation (but still in progress)

[okura]

• 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]

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.

[jdoerfert]

In D80991#2079013, @fhahn wrote:

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]

• 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]

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'

[jdoerfert]

In D80991#2095399, @okura wrote:

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

1

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

[okura]

In D80991#2096230, @jdoerfert wrote:

In D80991#2095399, @okura wrote:

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]

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]

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

2960 ↗

(On Diff #271938)

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

2974 ↗

(On Diff #271938)

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

2976 ↗

(On Diff #271938)

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

3007 ↗

(On Diff #271938)

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.

3027 ↗

(On Diff #271938)

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.

3031 ↗

(On Diff #271938)

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

3049 ↗

(On Diff #271938)

7 needs to be replaced by a command line option

3124 ↗

(On Diff #271938)

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

3427 ↗

(On Diff #271938)

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

4422 ↗

(On Diff #271938)

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.

4514 ↗

(On Diff #271938)

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.

4587 ↗

(On Diff #271938)

Same comment as last.

4695 ↗

(On Diff #271938)

Same comment as last.

7171 ↗

(On Diff #271938)

not needed.

7467 ↗

(On Diff #271938)

Put these large conditionals in separate helper functions please.

llvm/test/Transforms/Attributor/potential.ll

25

YaY! :)

[okura]

• 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]

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

[jdoerfert]

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

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

3071 ↗

(On Diff #273949)

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 ↗

(On Diff #273949)

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 ↗

(On Diff #273949)

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 ↗

(On Diff #273949)

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 ↗

(On Diff #273949)

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

[okura]

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

added some comments.

[okura]

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

3185 ↗

(On Diff #273949)

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 ↗

(On Diff #273949)

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

4708 ↗

(On Diff #273949)

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]

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

[baziotis]

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 ↗

(On Diff #273949)

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 ↗

(On Diff #273949)

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]

This patch was split into D83283 and D85632.

llvm/test/Transforms/Attributor/potential.ll

+; Test for multiple potential values
+;
+; potential-test 1
+; int iszero(int c) { return c == 0; }
+; int potential_test1(int c) { return iszero(c ? 1 : -1); }
+
+define dso_local i32 @potential_test1(i32 %0) {
+  %2 = icmp eq i32 %0, 0
+  %3 = select i1 %2, i32 -1, i32 1
+  %4 = tail call i32 @iszero(i32 %3)
+  ret i32 %4
+}
+
+define internal  i32 @iszero(i32 %0) {
+  %2 = icmp eq i32 %0, 0
+  %3 = zext i1 %2 to i32
+  ret i32 %3
+}
+
+; potential-test 2
+; 
+; potential values of argument of iszero are {1,-1}
+; potential value of returned value of iszero is 0
+;
+; int call_with_two_values(int x) { return iszero(x) + iszero(-x); }
+; int potential_test2(int x) { return call_with_two_values(1) + call_with_two_values(-1); }
+
+define dso_local i32 @potential_test2(i32 %0) {
+  %2 = tail call i32 @call_with_two_values(i32 1)
+  %3 = tail call i32 @call_with_two_values(i32 -1)
+  %4 = add nsw i32 %3, %2
+  ret i32 %4
+}
+
+define internal  i32 @call_with_two_values(i32 %0) {
+  %2 = tail call i32 @iszero(i32 %0)
+  %3 = sub nsw i32 0, %0
+  %4 = tail call i32 @iszero(i32 %3)
+  %5 = add nsw i32 %4, %2
+  ret i32 %5
+}
+
+
+; potential-test 3
+;
+; potential values of returned value of f are {0,1}
+; potential values of argument of g are {0,1}
+; potential value of returned value of g is 1
+; then returned value of g can be simplified
+;
+; int zero_or_one(int c) { return c < 2; }
+; int potential_test3() { return zero_or_one(iszero(0))+zero_or_one(iszero(1)); }
+
+
+define dso_local i32 @potential_test3(i32 %0) {
+  %2 = tail call i32 @iszero(i32 0)
+  %3 = tail call i32 @zero_or_one(i32 %2)
+  %4 = tail call i32 @iszero(i32 1)
+  %5 = tail call i32 @zero_or_one(i32 %4)
+  %6 = add nsw i32 %5, %3
+  ret i32 %6
+}
+
+define internal i32 @zero_or_one(i32 %0) {
+  %2 = icmp slt i32 %0, 2
+  %3 = zext i1 %2 to i32
+  ret i32 %3
+}
+
+
+; potential-test 4,5
+; 
+; simplified
+; int potential_test4(int c) { return return1or3(c) == 2; }
+; int potential_test5(int c) { return return1or3(c) == return2or4(c); }
+;
+; not simplified
+; int potential_test6(int c) { return return1or3(c) == 3; }
+; int potential_test7(int c) { return return1or3(c) == return3or4(c); }
+
+define dso_local i32 @potential_test4(i32 %0) {
+  %2 = tail call i32 @return1or3(i32 %0)
+  %3 = icmp eq i32 %2, 2
+  %4 = zext i1 %3 to i32
+  ret i32 %4
+}
+
+define dso_local i32 @potential_test5(i32 %0) {
+  %2 = tail call i32 @return1or3(i32 %0)
+  %3 = tail call i32 @return2or4(i32 %0)
+  %4 = icmp eq i32 %2, %3
+  %5 = zext i1 %4 to i32
+  ret i32 %5
+}
+
+define dso_local i32 @potential_test6(i32 %0) {
+  %2 = tail call i32 @return1or3(i32 %0)
+  %3 = icmp eq i32 %2, 3
+  %4 = zext i1 %3 to i32
+  ret i32 %4
+}
+
+define dso_local i32 @potential_test7(i32 %0) {
+  %2 = tail call i32 @return1or3(i32 %0)
+  %3 = tail call i32 @return3or4(i32 %0)
+  %4 = icmp eq i32 %2, %3
+  %5 = zext i1 %4 to i32
+  ret i32 %5
+}
+
+define internal i32 @return1or3(i32 %0) {
+  %2 = icmp eq i32 %0, 0
+  %3 = select i1 %2, i32 1, i32 3
+  ret i32 %3
+}
+
+define internal i32 @return2or4(i32 %0) {
+  %2 = icmp eq i32 %0, 0
+  %3 = select i1 %2, i32 2, i32 4
+  ret i32 %3
+}
+
+define internal i32 @return3or4(i32 %0) {
+  %2 = icmp eq i32 %0, 0
+  %3 = select i1 %2, i32 3, i32 4
+  ret i32 %3
+}
+