This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Implement AAPotentialValues
ClosedPublic

Authored by okura on Aug 10 2020, 1:32 AM.

Details

Summary

This patch provides an implementation of AAPotentialValues.

Diff Detail

Event Timeline

okura created this revision.Aug 10 2020, 1:32 AM
Herald added a reviewer: homerdin. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
okura requested review of this revision.Aug 10 2020, 1:32 AM
okura retitled this revision from [Attributor] Connect AAPotentialValues with AAValueSimplify to [Attributor] Implement AAPotentialValues and connect it with AAValueSimplify.Aug 10 2020, 2:59 AM
okura edited the summary of this revision. (Show Details)
okura updated this revision to Diff 284314.Aug 10 2020, 4:43 AM

add updateImpl implementation and update tests

okura updated this revision to Diff 284340.Aug 10 2020, 6:29 AM
  • fix operators in PotentialValuesState (merged from D85639)
jdoerfert added inline comments.Aug 10 2020, 9:29 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
3490 ↗(On Diff #284340)

I failed to determine why this cannot be private anymore.

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

Can you split this off into an NFC patch. Will make this one much simpler.

I think we should limit the "entry point" for this AA. It seems we can only improve AAValueSimplify when the instruction we look at is a conditional, right? So if it is, we ask AAPotentialValues, otherwise we do not. Other users of AAPotentialValues will emerge but for this use we can restrict it to the case we can actually fold the multiple values in to a single constant. Other users might be OK with multiple values, e.g., to determine a common property.

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

Add a TODO that we should look at nsw and nuw to help, e.g., to exclude certain results that cannot happen without creating undef. Similarly, division by undef should not make the result invalid but simply skip this operand pair.

7358

Why do we have the copy sometimes and sometimes not? Are the operators missing in the APInt class? If so, we should fix that in a pre-patch first.

7406

Here and below we should avoid looking at RHS if LHSAA is invalid.

7412

Please add a type here, and (or at least) make it a const reference. Also other places.

7420

We should give up once both are true.

okura added inline comments.Aug 10 2020, 10:29 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
3490 ↗(On Diff #284340)

I thought PVS.IsValidState in operators violate access specifier but that was my mistake, sorry.
I'll fix this.

okura updated this revision to Diff 284433.Aug 10 2020, 10:42 AM
okura retitled this revision from [Attributor] Implement AAPotentialValues and connect it with AAValueSimplify to [Attributor] Implement AAPotentialValues.
okura edited the summary of this revision. (Show Details)
  • fix access specifier of IsValidState
  • split patch into D85668 (Connecting part)
okura added inline comments.Aug 10 2020, 7:35 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7343

I understand you mean that we can assume the operation result is not a poison value or undef and that we can ignore such operand pair. Is that right?
I'm thinking of adding a new argument bool &Unsupported to this to distinguish the above case from the case opcode is unsupported.
In the former case we skip the operand pair, and in the latter case we give up (i.e. call indicatePessimisticFixpoint).

jdoerfert added inline comments.Aug 10 2020, 7:45 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7343

Yes and no. So there are two things.

  1. If the operation would be poison or undef, we can add undef to the set instead of something else. Undef is strictly better than any other APInt. This is the case for the nuw/nsw binary ops but I would not go there right now. A TODO makes more sense and a follow up patch.
  2. If the operation would be UB, that is it can actually not happen, we can ignore the result. Think of a division in which the RHS is {0, 1}. Since division by 0 is UB, we can ignore that result and only take the 1 result.

Have such a bool reference argument makes sense, maybe call it "SkipOperation" or something and pass it through to the caller so we can just go ahead and ignore this combination of LHS/RHS.

okura marked 3 inline comments as done.Aug 10 2020, 7:48 PM
okura added inline comments.
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7358

Are the operators missing in the APInt class?

Yes, there are only compound assignment operators for some opcodes. I'll make a new patch for this.

okura updated this revision to Diff 284567.Aug 10 2020, 7:49 PM
  • fix the places that were pointed out
jdoerfert added inline comments.Aug 10 2020, 8:05 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7358

Why do we want the assignment operators? Why not just LHS + RHS?

okura added inline comments.Aug 10 2020, 8:40 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7343

I understand. I'll rename Valid with SkipOperation and add Unsupported.

7358

Sorry, I read doxygen of APInt and mistakenly thought there is not operator+. I'll fix this.

okura updated this revision to Diff 284570.Aug 10 2020, 8:43 PM
  • fix calculateBinaryOperator
jdoerfert accepted this revision.Aug 10 2020, 9:25 PM

I think this patch is good. We should try to limit the queries to useful ones. We can do that after though. Maybe we check the instruction opcode in getAssumedConstantInt to make sure we only run this for Instructions that can fold multiple values into a single one, so far probably only compare instructions. We could also add a separate method that determines if this AAValueSimplify-like AA is good for a certain position or not. Either way, that should result in way less iterations without loosing any optimizations. Feel free to give it a try :)

LGTM.

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

You can indicate a pessimistic fixpoint here. It's an i1 which can be true and false :)

This revision is now accepted and ready to land.Aug 10 2020, 9:25 PM
okura updated this revision to Diff 284590.Aug 11 2020, 12:14 AM
okura added inline comments.Aug 11 2020, 4:22 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7426

If I indicate a pessimistic fixpoint, the state becomes invalid. If not, the state becomes {0,1}. I think this difference makes the deduction weaker. For example, the expected value simplification is not achieved in the case @potential_test3 in potential.ll.
I think I should handle known (the worst) state for values that have a very small bit width.
In the following example, the returned value's state becomes an invalid state with current implementation. But it should be {0,1}, I think.

define i32 @foo(i1 %c) {
  %ret = zext i1 %c to i32
  ret i32 %ret
}
okura added inline comments.Aug 14 2020, 3:43 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7426

I thought about this again and I noticed that this kind of analysis can (should) be done by AAValueConstantRange.
However, value simplification does not work expectedly in the current implementation as we can see with @potential_test3.
I investigated the cause of this and I found out the cause is bugs in AAConstantRange.
I will make a new patch for it.

okura updated this revision to Diff 285625.Aug 14 2020, 4:49 AM
  • fix updateWithICmpInst
  • modify test
This revision was automatically updated to reflect the committed changes.