This is an archive of the discontinued LLVM Phabricator instance.

[CodeGenPrepare] Fold freeze(icmp x, const) to icmp(freeze x, const)
ClosedPublic

Authored by aqjune on Mar 9 2020, 9:41 AM.

Details

Summary

This patch helps CodeGenPrepare move freeze into the icmp.
It reenables generation of efficient conditional jumps.

This is only done when at least one of icmp's operands is constant to prevent the transformation from increasing # of freeze instructions.

Performance degradation of MultiSource/Benchmarks/Ptrdist/yacr2/yacr2.test is resolved with this patch.

Checked with Alive2

Diff Detail

Event Timeline

aqjune created this revision.Mar 9 2020, 9:41 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 9 2020, 9:41 AM
aqjune updated this revision to Diff 249138.Mar 9 2020, 9:42 AM

Add a test

I feel this is part of a bigger pattern. (I assume constants cannot cause poison and undef now)

Let op be OPERATION<value, constant> or OPERATION<constant, value>, if all uses of op, or the single use of op, are freeze, move freeze to value.

Now we can keep a list of opcodes for which we don't want to do this but it seems more generic than br + icmp.

aqjune added a comment.Mar 9 2020, 5:31 PM

I feel this is part of a bigger pattern. (I assume constants cannot cause poison and undef now)

Let op be OPERATION<value, constant> or OPERATION<constant, value>, if all uses of op, or the single use of op, are freeze, move freeze to value.

Now we can keep a list of opcodes for which we don't want to do this but it seems more generic than br + icmp.

This transformation can be generalized as you suggested (maybe instcombine would be the place?), but at this point we don't have a good inference engine for removing freeze from non-i1 values, so I think it may block further optimizations.
Currently freeze of i1 type is introduced by SimpleLoopUnswitch (https://reviews.llvm.org/D29015) (it was reverted now, but it is the place where it is likely to introduce freeze in the close future), and isGuaranteedNotToBeUndefOrPoison (I'm planning to split it, as you suggested in the other patch) can do inference better on i1 type. So, in terms of performance I'd like to put this transformation at the end of IR pipeline, which is CodeGenPrepare.

aqjune updated this revision to Diff 249271.Mar 9 2020, 9:23 PM

clang-format

aqjune edited the summary of this revision. (Show Details)Mar 10 2020, 12:05 AM

I agree that this can and should be generalized elsewhere in the optimizer, but having this local peephole in CGP is probably a reasonable starting point. The general framing would be something like "move freeze towards definition of possible poison". We could do so not just for cmps, but for any instruction according to the poison propagation rules and the may be poison analysis results.

llvm/lib/CodeGen/CodeGenPrepare.cpp
7197

I don't think you actually need the branch check here. Unless I'm missing something, moving freeze into both operands is legal, and since one of them is obviously not poison, we can only move it into one of the two. I don't think it matters which uses we have.

7199

Please structure as:

if (FreezeInst *FI = ...)

if (ICmpInst *ICI = ...)
 if (other checks...)
7207

Take the name of the original freeze?

llvm/test/Transforms/CodeGenPrepare/X86/freeze-icmp.ll
6

You need a test for the swapped operand, non-constant arg (i.e. nop), and both constants cases.

aqjune updated this revision to Diff 249645.Mar 11 2020, 8:46 AM

Reflect comments

aqjune marked 4 inline comments as done.Mar 11 2020, 8:47 AM
reames accepted this revision.Mar 11 2020, 9:49 AM

LGTM w/comments applied.

llvm/lib/CodeGen/CodeGenPrepare.cpp
7202

style: auto *F

7202

Use takeName instead of getName to avoid additional name mangling.

This revision is now accepted and ready to land.Mar 11 2020, 9:49 AM

p.s. As a follow up, you should probably generalize this to fcmp at the minimum.

aqjune marked 2 inline comments as done.Mar 11 2020, 11:20 AM
This revision was automatically updated to reflect the committed changes.
aqjune retitled this revision from [CodeGenPrepare] Fold br(freeze(icmp x, const)) to br(icmp(freeze x, const)) to [CodeGenPrepare] Fold freeze(icmp x, const) to icmp(freeze x, const).Mar 11 2020, 7:01 PM
aqjune edited the summary of this revision. (Show Details)