[SimplifyCFG] try branch-to-branch simplification sooner

[spatel]

Summary

The order that we try various folds within SimplifyCFG can affect the result as shown by this patch that only moves a block of code.

But I'm not sure if the existing code or the diff in the motivating case from PR32078 is valid. Is it safe to convert this chain of branches into bitwise logic? What if the branch conditions are poison?

If this is ok, then we should be able to turn the entire sequence into logic ops rather than select at the end. I haven't looked to see why that still happens. If this is not ok, then we already have a bug in SimplifyCFG.

[lebedev.ri]

Branching on poison is UB, while performing bitmath on poison will only result in poison, which is less bad i think.
So i think *those* folds are okay.

[efriedma]

It isn't obvious to me why the order matters? The commit message and comments in the code don't really explain.

Is it safe to convert this chain of branches into bitwise logic?

I think the way Alive2 currently defines poison, it's safe to transform a branch to a bool select, but transforming a bool select to bitwise logic requires freeze.

[efriedma]

I think the way Alive2 currently defines poison, it's safe to transform a branch to a bool select, but transforming a bool select to bitwise logic requires freeze.

Err, I meant, it's safe to transform a chain of branches to a chain of bool selects.

Branching on poison is UB, while performing bitmath on poison will only result in poison, which is less bad i think.

The question is what happens if you have a chain of conditional branches... i.e. you're potentially transforming code that uses value in dead code to code that uses that value in live code.

[aqjune]

As you concerned, in theory the transformation may introduce more undefinedness in target: http://volta.cs.utah.edu:8080/z/wygrrr
(Right now there was a slight issue with vector function input in Alive2 so I unpacked it into individual scalar inputs)
I think converting it into select rather than and/or is a safer approach. It clearly preserves which condition should be considered first.

[aqjune]

Right now, making SimplifyCFG add freeze would block many optimization because analysis for redundant freeze removal isn't mature enough.
However, we can assess its effect to backend by updating transformations that are similar with this and happening at very late pipeline.
What I've found was llvm/test/Transforms/CodeGenPrepare/X86/select.ll . it converts select into br in certain cases (fdiv_true_sink).
What do you think about making the branch condition freezed? It will be a good start for having actual freeze in IR.

[spatel]

In D76153#1922761, @aqjune wrote:

As you concerned, in theory the transformation may introduce more undefinedness in target: http://volta.cs.utah.edu:8080/z/wygrrr
(Right now there was a slight issue with vector function input in Alive2 so I unpacked it into individual scalar inputs)
I think converting it into select rather than and/or is a safer approach. It clearly preserves which condition should be considered first.

Thanks - and very grateful for the online alive2 explorer! cc @regehr
That's going to be fun. :)

So we have a chain of bugs here...

1. SimplifyCFG can directly turn branches into logic - creates more poison.
2. SimplifyCFG can turn branches into select - this is ok by itself, but...
3. InstCombine turns those selects into logic as seen in https://reviews.llvm.org/D72396#1810460

I need to review 'freeze'...and see what (if anything) can be done.

[spatel]

In D76153#1922408, @efriedma wrote:

It isn't obvious to me why the order matters? The commit message and comments in the code don't really explain.

Sorry, missed this question initially. Order matters because SimplifyCFG doesn't run to fix-point. It's a curated set of transforms gated by requestResimplify() and a 'Changed' flag. I don't think that can be changed without major surgery. For example, if we speculatively hoist instructions using the cost model, then we don't want to re-run that transform without marking the already hoisted instructions as changed by SimplifyCFG itself.

But then again, we run this pass multiple times in the normal opt pipeline, so we must be layering cost-based speculations on top of one another...unless I'm missing something that prevents that.

[regehr]

so this works but seems heavy-handed:
http://volta.cs.utah.edu:8080/z/w-L7Jw

[aqjune]

Freezing arguments will work if whole expressions are purely relying on function arguments. This can be done by a cascade of transformations like freeze(icmp p, q) -> icmp (freeze p), (freeze q) and freeze (bop x y) -> bop (freeze x) (freeze y) (where bop is guaranteed to return non-undef/poison if both operands are non-undef/poison).
If a value x is never undef or poison, freeze x can be optimized to x. I have a few patches which is under reviewed for this direction: D76010 and D75808.

[efriedma]

But then again, we run this pass multiple times in the normal opt pipeline, so we must be layering cost-based speculations on top of one another...unless I'm missing something that prevents that.

The SimplifyCFG pass (lib/Transforms/Scalar/SimplifyCFGPass.cpp) iterates until it can't make any more changes; we shouldn't be depending on any data recorded off to the side. I'm pretty sure the issue is really some sort of transform ordering issue; I'm mostly interested in knowing which specific transforms are involved.

[aqjune]

I guess in C it is UB to pass the value of uninitialized variable to a function argument:

void f(int);

int x;
f(x); // UB

Then can we say that function arguments are never undef/poison?
It may not be true in IR, then we can introduce the attribute that is discussed at nonnull thread previously, which was nonpoison (or I think frozen is good as well; nonpoison seems to imply poison only. But I don't stick to my choice)

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and one of our successors, fold the comparison into the
   // predecessor and use logical operations to pick the right destination.
   if (FoldBranchToCommonDest(BI, nullptr, Options.BonusInstThreshold))
     return requestResimplify();
 
+  // Scan predecessor blocks for conditional branches.
+  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
+    if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
+      if (PBI != BI && PBI->isConditional())
+        if (SimplifyCondBranchToCondBranch(PBI, BI, DL, TTI))
+          return requestResimplify();
+
   // We have a conditional branch to two blocks that are only reachable
   // from BI.  We know that the condbr dominates the two blocks, so see if
   // there is any identical code in the "then" and "else" blocks.  If so, we
   // can hoist it up to the branching block.
   if (BI->getSuccessor(0)->getSinglePredecessor()) {
     if (BI->getSuccessor(1)->getSinglePredecessor()) {
       if (HoistThenElseCodeToIf(BI, TTI))
         return requestResimplify();
bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
 
   // If this is a branch on a phi node in the current block, thread control
   // through this block if any PHI node entries are constants.
   if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition()))
     if (PN->getParent() == BI->getParent())
       if (FoldCondBranchOnPHI(BI, DL, Options.AC))
         return requestResimplify();
 
-  // Scan predecessor blocks for conditional branches.
-  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
-    if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
-      if (PBI != BI && PBI->isConditional())
-        if (SimplifyCondBranchToCondBranch(PBI, BI, DL, TTI))
-          return requestResimplify();
-
   // Look for diamond patterns.
   if (MergeCondStores)
     if (BasicBlock *PrevBB = allPredecessorsComeFromSameSource(BB))
       if (BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
         if (PBI != BI && PBI->isConditional())
           if (mergeConditionalStores(PBI, BI, DL, TTI))
             return requestResimplify();
 

llvm/test/Transforms/SimplifyCFG/ConditionalTrappingConstantExpr.ll

bb7:
   ret i32 927
 }
 
 ; FP ops don't trap by default, so this is safe to hoist.
 
 define i32 @tarp(i1 %c) {
 ; CHECK-LABEL: @tarp(
 ; CHECK-NEXT:  bb9:
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 fcmp oeq (float fdiv (float 3.000000e+00, float sitofp (i32 ptrtoint (i32* @G to i32) to float)), float 1.000000e+00), i32 42, i32 927
-; CHECK-NEXT:    [[MERGE:%.*]] = select i1 [[C:%.*]], i32 [[SPEC_SELECT]], i32 42
+; CHECK-NEXT:    [[C_NOT:%.*]] = xor i1 [[C:%.*]], true
+; CHECK-NEXT:    [[BRMERGE:%.*]] = or i1 [[C_NOT]], fcmp oeq (float fdiv (float 3.000000e+00, float sitofp (i32 ptrtoint (i32* @G to i32) to float)), float 1.000000e+00)
+; CHECK-NEXT:    [[MERGE:%.*]] = select i1 [[BRMERGE]], i32 42, i32 927
 ; CHECK-NEXT:    ret i32 [[MERGE]]
 ;
   br i1 %c, label %bb8, label %bb9
 bb8:
   br i1 fcmp oeq (float fdiv (float 3.0, float sitofp (i32 ptrtoint (i32* @G to i32) to float)), float 1.0), label %bb9, label %bb10
 bb9:
   ret i32 42
 bb10:
   ret i32 927
 }

llvm/test/Transforms/SimplifyCFG/PR17073.ll

exit:
   ret i32* %storemerge
 }
 
 define i32* @cannot_trap() {
 ; CHECK-LABEL: @cannot_trap(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TMP0]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL]], label [[EXIT:%.*]], label [[BLOCK1:%.*]]
-; CHECK:       block1:
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 icmp eq (i32* bitcast (i8* @b to i32*), i32* @a), i32* select (i1 icmp eq (i64 add (i64 zext (i1 icmp eq (i32* bitcast (i8* @b to i32*), i32* @a) to i64), i64 2), i64 0), i32* null, i32* @a), i32* null
-; CHECK-NEXT:    ret i32* [[SPEC_SELECT]]
-; CHECK:       exit:
-; CHECK-NEXT:    ret i32* null
+; CHECK-NEXT:    [[BRMERGE:%.*]] = or i1 [[TOBOOL]], icmp eq (i32* bitcast (i8* @b to i32*), i32* @a)
+; CHECK-NEXT:    [[DOTMUX:%.*]] = select i1 [[TOBOOL]], i32* null, i32* select (i1 icmp eq (i64 add (i64 zext (i1 icmp eq (i32* bitcast (i8* @b to i32*), i32* @a) to i64), i64 2), i64 0), i32* null, i32* @a)
+; CHECK-NEXT:    [[STOREMERGE:%.*]] = select i1 [[BRMERGE]], i32* [[DOTMUX]], i32* null
+; CHECK-NEXT:    ret i32* [[STOREMERGE]]
 ;
 entry:
   %0 = load i32, i32* @a, align 4
   %tobool = icmp eq i32 %0, 0
   br i1 %tobool, label %exit, label %block1
 
 block1:
   br i1 icmp eq (i32* bitcast (i8* @b to i32*), i32* @a), label %exit, label %block2
 
 block2:
   br label %exit
 
 exit:
   %storemerge = phi i32* [ null, %entry ],[ null, %block2 ], [ select (i1 icmp eq (i64 add (i64 2, i64 zext (i1 icmp eq (i32* bitcast (i8* @b to i32*), i32* @a) to i64)), i64 0), i32* null, i32* @a), %block1 ]
   ret i32* %storemerge
 }

llvm/test/Transforms/SimplifyCFG/extract-cost.ll

 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[CMP0:%.*]] = extractelement <4 x i1> [[CMP]], i32 0
 ; CHECK-NEXT:    [[CMP1:%.*]] = extractelement <4 x i1> [[CMP]], i32 1
 ; CHECK-NEXT:    [[CMP2:%.*]] = extractelement <4 x i1> [[CMP]], i32 2
 ; CHECK-NEXT:    [[CMP3:%.*]] = extractelement <4 x i1> [[CMP]], i32 3
 ; CHECK-NEXT:    [[CMP0_NOT:%.*]] = xor i1 [[CMP0]], true
 ; CHECK-NEXT:    [[CMP1_NOT:%.*]] = xor i1 [[CMP1]], true
 ; CHECK-NEXT:    [[BRMERGE:%.*]] = or i1 [[CMP0_NOT]], [[CMP1_NOT]]
-; CHECK-NEXT:    br i1 [[BRMERGE]], label [[EXIT:%.*]], label [[CMP1_TRUE:%.*]]
-; CHECK:       cmp1_true:
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[CMP2]], i1 [[CMP3]], i1 false
+; CHECK-NEXT:    [[CMP2_NOT:%.*]] = xor i1 [[CMP2]], true
+; CHECK-NEXT:    [[BRMERGE1:%.*]] = or i1 [[BRMERGE]], [[CMP2_NOT]]
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[BRMERGE1]], i1 false, i1 [[CMP3]]
 ; CHECK-NEXT:    ret i1 [[SPEC_SELECT]]
-; CHECK:       exit:
-; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %cmp = icmp eq <4 x i32> %a, %b
   %cmp0 = extractelement <4 x i1> %cmp, i32 0
   %cmp1 = extractelement <4 x i1> %cmp, i32 1
   %cmp2 = extractelement <4 x i1> %cmp, i32 2
   %cmp3 = extractelement <4 x i1> %cmp, i32 3
   br i1 %cmp0, label %cmp0_true, label %exit