This is an archive of the discontinued LLVM Phabricator instance.

[SCCP] Use conditional info with AND/OR branch conditions.
ClosedPublic

Authored by fhahn on Apr 9 2020, 8:46 AM.

Details

Summary

Currently SCCP does not combine the information of conditions joined by
AND in the true branch or OR in the false branch.

For branches on AND, 2 copies will be inserted for the true branch, with
one being the operand of the other as in the code below. We can combine
the information using intersection. Note that for the OR case, the
copies are inserted in the false branch, where using intersection is
safe as well.

define void @foo(i32 %a) {
entry:
  %lt = icmp ult i32 %a, 100
  %gt = icmp ugt i32 %a, 20
  %and = and i1 %lt, %gt
; Has predicate info
; branch predicate info { TrueEdge: 1 Comparison:  %lt = icmp ult i32 %a, 100 Edge: [label %entry,label %true] }
  %a.0 = call i32 @llvm.ssa.copy.140247425954880(i32 %a)
; Has predicate info
; branch predicate info { TrueEdge: 1 Comparison:  %gt = icmp ugt i32 %a, 20 Edge: [label %entry,label %false] }
  %a.1 = call i32 @llvm.ssa.copy.140247425954880(i32 %a.0)
  br i1 %and, label %true, label %false

true:                                             ; preds = %entry
  call void @use(i32 %a.1)
  %true.1 = icmp ne i32 %a.1, 20
  call void @use.i1(i1 %true.1)
  ret void

false:                                            ; preds = %entry
  call void @use(i32 %a.1)
  ret void
}

Diff Detail

Event Timeline

fhahn created this revision.Apr 9 2020, 8:46 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 9 2020, 8:46 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
fhahn added a subscriber: baziotis.Apr 9 2020, 8:48 AM

With this change, the example in http://lists.llvm.org/pipermail/llvm-dev/2020-April/140641.html is optimized as expected.

efriedma added inline comments.Apr 9 2020, 12:35 PM
llvm/lib/Transforms/Scalar/SCCP.cpp
1262

I don't understand what OriginalVal is when it isn't equal to CopyOf. The example in the commit message isn't helpful here; it looks like the predicate info refers to the same value as the ssa copy.

fhahn marked an inline comment as done.Apr 9 2020, 2:06 PM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/SCCP.cpp
1262

We need 1 more renaming step to run into the issue:

entry:
  %lt = icmp ult i32 %a, 100
  %a.0 = call i32 @llvm.ssa.copy.140247425954880(i32 %a) ; OriginalOp = %a
  br i1 %lt, label %true.1, label %false

true: 
   %gt = icmp ugt i32 %a.0, 20
   %a.1 = call i32 @llvm.ssa.copy.140247425954880(i32 %a.0) ; OriginalOp = %a
   br i1 %gt, label %true.2, %label %false

The OriginalOp for the info attached to %a.1 refers to %a as OriginalOp, but the actual use in %gt has been renamed due to the first copy. For most cases, using the operand is fine (as we did before), but for ANDs the operand of the second copy will be the first copy, which is not part of the Cmp instruction.

Ideally we would have OriginalOp (or another member) refer to the name of the value in the condition. Otherwise we have to walk backwards here and try to find the right value to use. I tried just checking if we have 2 chained ssa_copies, but there were some cases where this failed. I will take a closer look to check whether this should be handled here or directly in PredicateInfo. It only means that we miss out on some cases, but are able to still cover more cases as before.

(I also realized that I copied a wrong version of the example in the description. I will update it shortly.

fhahn edited the summary of this revision. (Show Details)Apr 9 2020, 2:08 PM
efriedma added inline comments.Apr 10 2020, 11:29 AM
llvm/lib/Transforms/Scalar/SCCP.cpp
1262

I'm afraid this sort of "defensive" check is hiding some real bug. I'd rather try to figure out some more consistent way to figure out the necessary information. If we're still missing some cases, that indicates to me the algorithm for converting the information in PredicateBranches into a ConstantRange is still shaky. And it's not obvious to me that the shakiness only manifests in the form of a missed optimization.

fhahn updated this revision to Diff 257454.Apr 14 2020, 12:52 PM
fhahn marked an inline comment as done.

Updated on top of D78133.

Unfortunately it seems like this change is not strictly beneficial in some cases and the additional information might destroy some useful information. For example, consider the code below

  %c.ne = icmp ne i32 %x, 0
  %c.slt = icmp slt i32 %x, 255
  %and= and i1 %c.ne, c.slt%
  br i1 %and, label %true, label %false

true:
  %c.ne.2 = icmp eq i32 %x, 0
  call void @use(i1 %c.ne.2)

With the change, we won't be able to simplify %c.ne.2 to false, because we combine the range from %x != 0 with %x < 255, which results in a range %x < 255 and we cannot represent that the range also excludes 0.

It seems like the change is overall neutral on the test-suite, but there are a few cases where fewer constants are replaced unfortunately.

fhahn added inline comments.Apr 14 2020, 12:55 PM
llvm/lib/Transforms/Scalar/SCCP.cpp
1262

Agreed! I've put up a WIP patch D78133 that updates PredicateInfo to set OriginalOp for branches to refer to the original value that is used in the condition after renaming. With that, the logic can be simplified, but I still need to double-check if that has any impact on NewGVN.

Much cleaner now.

In terms of merging information, hmm, that's a downside. No good ideas off the top of my head; I mean, you could store a vector of constant ranges instead of just one, but that gets complicated fast.

Much cleaner now.

In terms of merging information, hmm, that's a downside. No good ideas off the top of my head; I mean, you could store a vector of constant ranges instead of just one, but that gets complicated fast.

yes, I am not sure if we really want to go there. I'll try and see if there are any reasonable alternatives

fhahn updated this revision to Diff 264199.May 15 2020, 3:50 AM

Much cleaner now.

In terms of merging information, hmm, that's a downside. No good ideas off the top of my head; I mean, you could store a vector of constant ranges instead of just one, but that gets complicated fast.

yes, I am not sure if we really want to go there. I'll try and see if there are any reasonable alternatives

I've updated the patch to not use the information from chained predicates, if the original info is != constant. That gets rid of the regressions and keeps things simple. What do you think?

fhahn updated this revision to Diff 268283.Jun 3 2020, 12:45 PM

Ping :)

Rebased after latest changes. The latest version preserves ranges containing information from !=, eliminating the regressions.

fhahn updated this revision to Diff 274869.Jul 1 2020, 10:36 AM

Rebased and ping :)

nikic added a subscriber: nikic.Jul 5 2020, 1:50 PM
nikic added inline comments.
llvm/lib/Transforms/Scalar/SCCP.cpp
1309

I'd write this as:

NewCR = NewCR.intersectWith(CopyOfCR);
if (!CopyOfCR.contains(NewCR) &&
    CopyOfCR.getSingleMissingElement() &&
    CopyOf != OriginalVal)
  NewCR = CopyOfCR;

There is no need to discard the intersection if it is smaller than the original range. E.g. if you had information for ne 0 before, then intersecting it with ugt 42 will always be beneficial.

I'm also not clear on why the CopyOf != OriginalVal comparison is there. If we think that inequality information is more valuable, shouldn't that hold regardless of how we arrived at the inequality?

fhahn updated this revision to Diff 276170.Jul 7 2020, 12:09 PM

Simplify code as suggested, remove dedicated CopyOf != OriginalVal check.

fhahn marked an inline comment as done.Jul 7 2020, 12:12 PM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/SCCP.cpp
1309

Thanks, that's simpler indeed. I think the impact in practice is relatively low, but it is definitely more straight-forward:)

I'm also not clear on why the CopyOf != OriginalVal comparison is there

It was mainly there to guard against specific potential regressions caused by this patch. But it is probably not worth special casing here. I've remove the check.

nikic accepted this revision.Jul 7 2020, 12:28 PM

LGTM modulo some naming.

llvm/lib/Transforms/Scalar/SCCP.cpp
1259

The "or CopyOf" is too much now. (You might want to convert this into an assertion, to make sure there are no more surprises here.)

1287

You already fetched this above under the name of OriginalValState.

I think the naming here got a bit messed up due to the back and forth refactoring. You might want to rename OriginalValState above to CopyOfVal, to avoid confusing with OriginalVal. I'd also s/OriginalVal/OriginalOp to keep with the name from PredicateInfo, and because you're using Val to indicate lattice values rather than Value*s.

This revision is now accepted and ready to land.Jul 7 2020, 12:28 PM
fhahn updated this revision to Diff 276420.Jul 8 2020, 7:10 AM

Rebased after updating D78133. Adjust comment/naming.

This revision was automatically updated to reflect the committed changes.