This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Simplify a known nonzero incoming value of PHI
ClosedPublic

Authored by junbuml on Jan 15 2016, 12:48 PM.

Details

Summary

When a PHI is used only to be compared with zero, it is possible to replace an
incoming value with any non-zero constant if the incoming value can be proved as
a known nonzero value. For example, in below code, we can replace the incoming value %v with
any non-zero constant based on the fact that the PHI is only used to be compared with zero
and %v is a known non-zero value:

%v = select %cond, 1, 2
%p = phi [%v, BB] ...
%c = icmp eq, %p, 0

Diff Detail

Repository
rL LLVM

Event Timeline

junbuml updated this revision to Diff 45024.Jan 15 2016, 12:48 PM
junbuml retitled this revision from to [InstCombine] Simplify a known nonzero incoming value of PHI.
junbuml updated this object.
junbuml added a reviewer: mcrosier.
junbuml added subscribers: gberry, mssimpso, bmakam and 2 others.
sanjoy added inline comments.Jan 18 2016, 11:22 AM
lib/Transforms/InstCombine/InstCombinePHI.cpp
940 ↗(On Diff #45024)

Why do you care about VA having only one use?

941 ↗(On Diff #45024)

Can't CtxI be the terminator of the i th incoming block?

junbuml added inline comments.Jan 18 2016, 12:50 PM
lib/Transforms/InstCombine/InstCombinePHI.cpp
940 ↗(On Diff #45024)

In correctness perspective, we don't have to check VA->hasOneUse(), but I expected the real impact on performance only when the incoming value become a dead code from this modification. I'm okay with removing this check (VA->hasOneUse()) if we can expect any indirect benefit.

941 ↗(On Diff #45024)

Not sure about this comment. Can you give me more detail about it ?

mssimpso added inline comments.Jan 18 2016, 1:31 PM
lib/Transforms/InstCombine/InstCombinePHI.cpp
940 ↗(On Diff #45024)

I think keeping the one-use check makes sense. If we only expect there to be a benefit if VA becomes dead, we want to avoid increasing compile-time. The only corner case that I can think of is if all of VAs users are PHIs that are compared with zero.

junbuml added inline comments.Jan 18 2016, 1:49 PM
lib/Transforms/InstCombine/InstCombinePHI.cpp
940 ↗(On Diff #45024)

The only corner case that I can think of is if all of VAs users are PHIs that are compared with zero.

This could a possible corner case, but to be simple for now, I may want to handle it as an extension if we need it.

sanjoy added inline comments.Jan 18 2016, 5:12 PM
lib/Transforms/InstCombine/InstCombinePHI.cpp
940 ↗(On Diff #45024)

I appreciate that there is a compile time tradeoff here, but reducing
the number of users of VA can help if it changes VA to have only
one user left (there are optimizations in instcombine predicated on
instructions having only one use). In general, my opinion is that if
it does not hurt performance to do this transform for VA with
more than one user, then we should not bail out.

942 ↗(On Diff #45024)

isKnownNonZero will try to prove the predicate for the location you
pass in as CtxI. You're passing in PN for CtxI, so currently
you won't optimize cases like:

  br (%x > 0), label %left, label %right

left:
  br label %merge  ;; == LOC

right:
  br label %merge

merge:
  %p = phi i32 [ %x, %left ], [ %y, %right ]
  %cmp = icmp eq i32 0, %p

The optimization won't trigger in this case because %x is not
provably non-zero at %p. However, %x is provably non-zero at
LOC, so passing in LOC for CtxI to isKnownNonZero should
return true.

My gut reaction would be to ask why we aren't trying to fold the comparison across the PHI as that would catch this case (and others) quite naturally.

lib/Transforms/InstCombine/InstCombinePHI.cpp
19–20 ↗(On Diff #45024)

Please sort these.

test/Transforms/InstCombine/phi.ll
763–764 ↗(On Diff #45024)

This is not a sufficient test. Please make the test highlight the instruction which you have altered.

junbuml updated this revision to Diff 45317.Jan 19 2016, 4:25 PM
junbuml marked 2 inline comments as done.

Addressed comments from Sanjoy and David.

My gut reaction would be to ask why we aren't trying to fold the comparison across the PHI as that would catch this case (and others) quite naturally.

The main purpose of this change is not to fold the cmp, but to replace incoming values to a nonzero constant because for a phi with multiple non constant operands, only some of its operands could be a known nonzero. By replacing some of incoming values with constants, we can expect to make the incoming value dead as well as increase chances to fold users (e.g., the cmp) of the phi.

junbuml added inline comments.Jan 19 2016, 4:25 PM
lib/Transforms/InstCombine/InstCombinePHI.cpp
940 ↗(On Diff #45024)

Looks like FoldOpIntoPhi() also continue trying to fold when a PHI has one non-constant incoming value. So, I removed VA->hasOneUse() check here.

942 ↗(On Diff #45024)

Thanks Sanjoy for the detail. Instead of PN, I pass the terminator of incoming block as CtxI.

test/Transforms/InstCombine/phi.ll
763–764 ↗(On Diff #45024)

I added check for modified PHI.
Thanks David for the comment.

Kindly ping ?

majnemer added inline comments.Jan 22 2016, 9:02 AM
lib/Transforms/InstCombine/InstCombinePHI.cpp
933 ↗(On Diff #45317)

Please use auto * here.

935 ↗(On Diff #45317)

CmpInst->isEquality() will return true if the comparison is ICMP_NE. Please add a testcase for this.

936–937 ↗(On Diff #45317)

Please add using namespace llvm::PatternMatch; to this file so that you don't need to qualify m_Zero.

936–937 ↗(On Diff #45317)

Instructions are canonicalized so that the RHS will have the constant. Please remove the code regarding the LHS.

sanjoy added inline comments.Jan 22 2016, 9:11 AM
lib/Transforms/InstCombine/InstCombinePHI.cpp
940 ↗(On Diff #45317)

I think InBB will always be non-null and have a terminator in a valid CFG. Have you seen otherwise?

junbuml updated this revision to Diff 45700.Jan 22 2016, 10:38 AM
junbuml marked 4 inline comments as done.

Addressed David's comments.

lib/Transforms/InstCombine/InstCombinePHI.cpp
940 ↗(On Diff #45317)

I haven't seen any null terminator in my environment. But, getTerminator() possibly returns nullptr. Since I cannot guarantee non-null terminator in all situations I'd rather keep the null check.

TerminatorInst *BasicBlock::getTerminator() {
  if (InstList.empty()) return nullptr;
  return dyn_cast<TerminatorInst>(&InstList.back());
}
majnemer added inline comments.Jan 22 2016, 10:40 AM
lib/Transforms/InstCombine/InstCombinePHI.cpp
941 ↗(On Diff #45700)

It will only be null for BasicBlocks which are newly created. Your basic block will not be newly created, please remove the null check.

junbuml updated this revision to Diff 45717.Jan 22 2016, 10:59 AM
junbuml marked an inline comment as done.
junbuml added inline comments.
lib/Transforms/InstCombine/InstCombinePHI.cpp
941 ↗(On Diff #45700)

Thanks David. Removed the null check.

hfinkel added a subscriber: hfinkel.Feb 2 2016, 9:04 PM
hfinkel added inline comments.
lib/Transforms/InstCombine/InstCombinePHI.cpp
941 ↗(On Diff #45717)

You skip constants, why? And if there is a constant (aside from zero), should we not reuse it instead of creating a new one (1 in this case). We might end up materializing more constants this way.

junbuml updated this revision to Diff 46828.Feb 3 2016, 1:28 PM

Addressed Hal's comments and added two more test cases to show that it reuse the existing non-zero constant.

junbuml updated this revision to Diff 47321.Feb 9 2016, 8:05 AM

Minor renaming.

sanjoy accepted this revision.Feb 10 2016, 9:22 PM
sanjoy edited edge metadata.

LGTM with minor nits inline.

lib/Transforms/InstCombine/InstCombinePHI.cpp
651 ↗(On Diff #47321)

Use for (Value *V : PN.operands()) here.

652 ↗(On Diff #47321)

Use auto *ConstVA here.

953 ↗(On Diff #47321)

I'd just pass PN by reference here (and change GetAnyNonZeroConstInt to take PHINode &).

This revision is now accepted and ready to land.Feb 10 2016, 9:22 PM
This revision was automatically updated to reflect the committed changes.