Page MenuHomePhabricator

[ValueTracking] Let isGuaranteedNotToBeUndefOrPoison look into branch conditions of dominating blocks' terminators
ClosedPublic

Authored by aqjune on Feb 28 2020, 10:45 PM.

Details

Summary
  br i1 c, BB1, BB2:
BB1:
  use1(c)
BB2:
  use2(c)

In BB1 and BB2, c is never undef or poison because otherwise the branch would have triggered UB.

Checked with Alive2

Diff Detail

Event Timeline

aqjune created this revision.Feb 28 2020, 10:45 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 28 2020, 10:45 PM

I agree this is correct, but this seems rather pessimistic.
Don't we want to look at every br that dominates Q.CxtI?

Wouldn't we want something like this instead:

// Use a utility function defined in ValueTracking.
if (llvm::isGuaranteedNotToBeUndefOrPoison(Op0))
  return Op0;
// Use a utility function defined in ValueTracking.
if (llvm::isGuaranteedToBeUBIfUndefOrPoisonAt(Op0, Q.CtxI))
  return Op0;

And then centralized collect known UB cases?

I don't remember this code very well but can there be an exit(0) between the freeze and branch?

I don't remember this code very well but can there be an exit(0) between the freeze and branch?

Never mind, the example looks correct so I think I'm just misremembering how this works.

I don't remember this code very well but can there be an exit(0) between the freeze and branch?

Hi, I guess the condition was needed for loop unswitching:

for (..) {
  g();
  if(b) { A } else { B }
}

When unswitching if(b), g() might exit or throw an exception, so b should be freezed.

Don't we want to look at every br that dominates Q.CxtI?

And then centralized collect known UB cases?

Makes sense, I'll make isGuaranteedNotToBeUndefOrPoison take the CxtI.

aqjune updated this revision to Diff 247474.Feb 29 2020, 7:31 PM

Let ValueTracking::isGuaranteedNotToBeUndefOrPoison look into branch conditions of dominating blocks' terminators

aqjune retitled this revision from [InstSimplify] Remove freeze if its operand is used as a branch condition to [ValueTracking] Let isGuaranteedNotToBeUndefOrPoison look into branch conditions of dominating blocks' terminators.Feb 29 2020, 8:34 PM
aqjune edited the summary of this revision. (Show Details)
aqjune updated this revision to Diff 247481.Feb 29 2020, 8:35 PM

clang-format

You might need to check if the branch "must-be-executed" from the CtxI. See the example.

llvm/lib/Analysis/ValueTracking.cpp
4563

Style: early exit !CtxI.

llvm/test/Transforms/InstSimplify/freeze.ll
58

@sanjoy Did have a point (I think). What happens if you have:

declare void @use(i1 %f) willreturn nounwind
declare void @exit()
define i1 @brcond_never_reached(i1 %c, i1 %c2) {
  %f = freeze i1 %c
  call void @use(i1 %f)
  call void exit();
  call void @use(i1 %f)
  br i1 %c, label %A, label %B
A:
  br i1 %c2, label %A2, label %B
A2:
  ret i1 %f
B:
  ret i1 %f
}
reames requested changes to this revision.Mar 2 2020, 12:39 PM
reames added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
4563

This should probably be inside programUndefinedIfFullPoison

4579

This is incorrect. Consider:
b = freeze a
throw_if_a_would_be_poison()
if (a == 5) {}

You can only use branches which either a) dominate the freeze's uses, or b) are guaranteed to execute if any of those uses execute. (a) is a subcase of (b) which happens to be cheap to check. Note that phrasing in terms of "uses" here, not the freeze def.

This revision now requires changes to proceed.Mar 2 2020, 12:39 PM
aqjune updated this revision to Diff 247778.Mar 2 2020, 6:34 PM
  • Address comments
  • Update test
aqjune marked 4 inline comments as done.Mar 2 2020, 6:44 PM
aqjune added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
4563

I think the current one is more general than programUndefinedIfFullPoison(I) in that it takes only instructions as input whereas this code can take the case when V is a constant expression into account as well.

4579

You're right, so at least I should have seen idom(CxtI->getParent()), but not CxtI->getParent().
To clarify, CxtI is the location where we'd like to check whether V is poison or not, I left it as a comment at the declaration of isGuaranteedNotToBeUndefOrPoison. I used the text from isSafeToSpeculativelyExecute()

aqjune marked 3 inline comments as done.Mar 2 2020, 6:46 PM
aqjune added inline comments.
llvm/test/Transforms/InstSimplify/freeze.ll
58

The first use(f) cannot be optimized use(c). I added a test for this case.

aqjune marked an inline comment as done.Mar 2 2020, 6:50 PM

In the brcond_switch and brcond tests, freezes are moved into the block because simply InstSimplify is not recursively looking into operands of ret instructions. Even if freezes are outside the branches (as shown in the previous patch), the optimization is still correct.

jdoerfert added inline comments.Mar 2 2020, 10:09 PM
llvm/include/llvm/Analysis/ValueTracking.h
575

If CtxI and DT are specified...

llvm/lib/Analysis/ValueTracking.cpp
4585

Style: Remove hasCond (which should be HasCond btw.) and just return true in the conditionals. Remove the else to.

Nit: N -> Dominator (or similar),

aqjune updated this revision to Diff 247797.Mar 2 2020, 11:09 PM

Address comments

aqjune updated this revision to Diff 247799.Mar 2 2020, 11:14 PM

Revert whitespace diff

aqjune marked an inline comment as done.Mar 2 2020, 11:15 PM
reames accepted this revision.Mar 3 2020, 12:49 PM

LGTM

Long term, I think we'll want something more general, but for the moment, this is a lot better than nothing.

This revision is now accepted and ready to land.Mar 3 2020, 12:49 PM
This revision was automatically updated to reflect the committed changes.

Hi! Unfortunately I had to revert this patch, see my comment here: https://reviews.llvm.org/rG952ad4701cf0d8da79789f6b83ddaa386c60d535

aqjune added a comment.Mar 5 2020, 8:13 AM

Fixed ( https://github.com/llvm/llvm-project/commit/d7267ee1941668d7e985681e29d10983799811a0 )
The reason was that LoopRotate was calling SimplifyInstruction(I) where I is a cloned instruction. CtxI is set as I by SimplifyInstruction, causing getting dom node from CtxI->getParent() to crash.