This is an archive of the discontinued LLVM Phabricator instance.

[JumpThreading] Replace uses of Condition safely
ClosedPublic

Authored by anna on May 16 2017, 2:06 PM.

Details

Summary

This patch builds over https://reviews.llvm.org/rL303349 and replaces the use of the condition only if it is safe to do so.

We should not blindly RAUW the condition if experimental.guard or assume is a use of that
condition. This is because LVI may have used the guard/assume to identify the
value of the condition, and RUAWing will fold the guard/assume and uses before the guards/assumes.

Event Timeline

anna created this revision.May 16 2017, 2:06 PM
anna added inline comments.May 16 2017, 2:10 PM
lib/Transforms/Scalar/JumpThreading.cpp
258

This should be "We can safely RAUW Cond only if ...".
I have separated this out into a function because there are 2 places currently where we try to RAUW the condition. Tests added trigger both these source code cases: ProcessBlock and ProcessThreadableEdges.

sanjoy requested changes to this revision.May 16 2017, 2:58 PM
sanjoy added inline comments.
lib/Transforms/Scalar/JumpThreading.cpp
266

I don't think this is specific to guards. For instance, if you have:

bb:
  cond = icmp ...;
  print(cond);
  exit();
  assume(cond);
  br cond;

You can't simplify the cond in print(cond) to print(true). I think there are similar issues with isObjectDereferencedInBlock.

I'd instead phrase this problem as:

We know that at the end of a basic block, a certain condition, cond, is true. The question from what point onwards did that condition become true. To do that, I suggest walking backwards from the branch, and stopping when you find an instruction for which isGuaranteedToTransferExecutionToSuccessor returns false. All the instructions you enumerate this way can be replaceUsesOfWith(cond, true) 'ed. This approach will miss some cases though, like in:

bb:
  cond = icmp ...;
  print(cond);
  cond' = or cond, something_else
  exit();
  use(cond')
  assume(cond);
  br cond;

we won't simplify cond'. If needed, we can come up with a more aggressive substitution scheme to get those cases.

This revision now requires changes to proceed.May 16 2017, 2:58 PM
reames edited edge metadata.May 16 2017, 5:23 PM

Anna, I believe this is a near duplicate of a patch I posted a while ago and never got around to getting in: https://reviews.llvm.org/D28276. I'm happy to have you take this to completion, but you might find the code and previous review comments there helpful.

In retrospect, I think I made a mistake in how I approached this. This is an active bug. We should remove the replaceAllUsesWith and update the tests as needed. Only once that's done should we come back and see if we can selectively update in some cases.

anna added a comment.May 16 2017, 6:10 PM

Anna, I believe this is a near duplicate of a patch I posted a while ago and never got around to getting in: https://reviews.llvm.org/D28276. I'm happy to have you take this to completion, but you might find the code and previous review comments there helpful.

In retrospect, I think I made a mistake in how I approached this. This is an active bug. We should remove the replaceAllUsesWith and update the tests as needed. Only once that's done should we come back and see if we can selectively update in some cases.

Philip, your patch is almost around the same issue! I was under the impression this circular logic affects guards only, but as Sanjoy pointed out it can be assumes as well (because LVI calculates values based on assumes and guards).

So, I'll remove the RAUW in the failing cases, and update the test cases asap. Next step would be following Sanjoy's idea/Philip's patch to reason about aggressively updating in cases where it is safe to do so.

mkazantsev added inline comments.May 16 2017, 10:58 PM
lib/Transforms/Scalar/JumpThreading.cpp
270

Should we check all dominating blocks as well?

anna added inline comments.May 17 2017, 5:40 AM
lib/Transforms/Scalar/JumpThreading.cpp
270

No, we don't need to check blocks dominating BB because the bug occurs when guard/assume *use* the Cond. Since defs dominate uses, we are fine.
Also, we don't need to check for uses in blocks dominated by BB because starting from the point of BB's terminator (i.e. the context instruction passed into LVI) and iterating forward, we can safely replace the uses of Cond with Val (returned by LVI).

The issue is when we try to replaces uses within the block BB where Cond is defined.

anna added inline comments.May 17 2017, 3:53 PM
lib/Transforms/Scalar/JumpThreading.cpp
266

Sanjoy's phrasing is a bit different from this phrasing: do not fold guards and assumes and uses before the guards and assumes.

Specifically these 2 examples showcase the differences:

  1. Using isGuaranteedToTransferExecutionToSuccessor, we will be folding assumes. Folding to true is okay, based on lang ref semantics of assume. Also, I think there cannot be a case of folding to assume(false), based on how LVI calculates values.
bb:
  cond = icmp ...;
  print(cond); <-- can fold this, and we do so.
  assume(cond); <-- can fold this, and we do so.
  br cond;

If there was an exit() between print and assume, we cannot fold the print.

  1. In this test case below, we unfortunately do not fold either uses because exit is a throwing call, and isGuaranteedToTransferExecutionToSuccessor won't allow to fold.
bb:
  cond = icmp ...
  assume(cond) <-- can fold this, but not able to.
  print(cond) <-- can fold this, but not able to.
  exit() <-- throws
  br cond

I think either phrasing has it's pros and cons, but both are conservatively correct. Thoughts?

mkazantsev added inline comments.May 17 2017, 10:00 PM
lib/Transforms/Scalar/JumpThreading.cpp
270

Ok, thanks for explanation!

anna updated this revision to Diff 99448.May 18 2017, 9:51 AM
anna edited edge metadata.

Replace uses of condition safely. The updated algorithm follows suggestion from Sanjoy:
starts from the end of basic block where the condition is defined and stops
when we reach a statement that may trap.
Added testcases in assumes and guards to show which cases we currently capture and which we do not.
Rebased over https://reviews.llvm.org/D33279.

anna retitled this revision from [JumpThreading] Dont RAUW condition if guards in block to [JumpThreading] Replace uses of Condition safely.May 18 2017, 9:58 AM
anna edited the summary of this revision. (Show Details)

Mostly minor stuff.

lib/Transforms/Scalar/JumpThreading.cpp
263

I'd call this replaceFoldableUses. IMHO the key transform here is that you're replacing uses, the fact that you can also sometimes remove Cond is just a "fringe benefit".

277

Perhaps this can be Instruction &I : reverse(*BB)?

283

I'd break out of the loop in both cases, and erase Cond only if it does not have uses. That way we'll remove the condition in cases like:

cond = icmp;
exit(0);
use(cond);
assume(cond);
anna updated this revision to Diff 99476.May 18 2017, 11:55 AM
anna marked 3 inline comments as done.

Addressed review comments.

sanjoy accepted this revision.May 19 2017, 5:03 PM

lgtm with nits

lib/Transforms/Scalar/JumpThreading.cpp
264

PatternMatch is unused.

268

The non-local blocks need not be strictly dominated by BB, but the uses we replace will be. The non-local blocks will not be strictly dominated in case of PHI nodes uses:

bb1:
  br label %x

bb0:
  assume(%cond)
  br i1 %cond, label %x, label %y

x:
  %v = phi i1 [ %cond, %bb0 ], [ %other_cond, %bb1 ]

I.e. the code is correct, but the comment can be more accurate.

271

This is a very subjective stylistic thing, but I think this much explanation is unnecessary. I'd just say something brief like "We only replace uses in instructions that are guaranteed to reach the end of the block, where we know Cond is ToVal." right before the check on isGuaranteedToTransferExecutionToSuccessor -- we have test cases to show why this is needed.

1379

Braces unnecessary here.

This revision is now accepted and ready to land.May 19 2017, 5:03 PM
This revision was automatically updated to reflect the committed changes.
anna marked 4 inline comments as done.May 23 2017, 6:36 AM
anna added inline comments.
lib/Transforms/Scalar/JumpThreading.cpp
268

good point!