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

[aqjune]

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

[aqjune]

Add a test

[jdoerfert]

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]

In D75859#1913094, @jdoerfert wrote:

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]

clang-format

[reames]

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]

Reflect comments

[reames]

LGTM w/comments applied.

llvm/lib/CodeGen/CodeGenPrepare.cpp

7202

style: auto *F

7202

Use takeName instead of getName to avoid additional name mangling.

[reames]

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

llvm/lib/CodeGen/CodeGenPrepare.cpp

if (GEPI->hasAllZeroIndices()) {
       return true;
     }
     if (tryUnmergingGEPsAcrossIndirectBr(GEPI, TTI)) {
       return true;
     }
     return false;
   }
 
+  if (FreezeInst *FI = dyn_cast<FreezeInst>(I)) {
+    // br(freeze(icmp a, const)) -> br(icmp (freeze a), const)
+    // This helps generate efficient conditional jumps.
+    bool AllUsesAreBr = llvm::all_of(
+        FI->users(), [](const User *U) { return isa<BranchInst>(U); });
+    auto II = dyn_cast<ICmpInst>(FI->getOperand(0));
+    if (AllUsesAreBr && II && II->hasOneUse()) {
+      auto Op0 = II->getOperand(0), Op1 = II->getOperand(1);
+      bool Const0 = isa<ConstantInt>(Op0), Const1 = isa<ConstantInt>(Op1);
+      if (Const0 || Const1) {
+        FI->replaceAllUsesWith(II);
+        FI->eraseFromParent();
+        if (!Const0 || !Const1) {
+          Instruction *F = new FreezeInst(Const0 ? Op1 : Op0, "fr", II);
+          II->setOperand(Const0 ? 1 : 0, F);
+        }
+        return true;
+      }
+    }
+    return false;
+  }
+
   if (tryToSinkFreeOperands(I))
     return true;
 
   switch (I->getOpcode()) {
   case Instruction::Shl:
   case Instruction::LShr:
   case Instruction::AShr:
     return optimizeShiftInst(cast<BinaryOperator>(I));

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -codegenprepare < %s | FileCheck %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @f(i32 %a) {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:    [[FR:%.*]] = freeze i32 [[A:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[FR]], 0
+; CHECK-NEXT:    br i1 [[C]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    call void @g1()
+; CHECK-NEXT:    ret void
+; CHECK:       B:
+; CHECK-NEXT:    call void @g2()
+; CHECK-NEXT:    ret void
+;
+  %c = icmp eq i32 %a, 0
+  %fr = freeze i1 %c
+  br i1 %fr, label %A, label %B
+A:
+  call void @g1()
+  ret void
+B:
+  call void @g2()
+  ret void
+}
+
+declare void @g1()
+declare void @g2()