[SimplifyCFG] Make ValueEqaulityComparison freeze-aware.

[hyeongyukim]

Summary

  cond1.fr = freeze(%v != 0)
  cond2.fr = freeze(%v == 0)
  br i1 %cond1.fr, label %body1, label %split

split:
  br %cond2.fr, label %body2, label %body3

%cond2.fr is always true in the split block.
But currently, this analysis is not performed when conditions are frozen.
This problem can be solved by modifying isValueEqualityComparison and GetValueEqualityComparisonCases.

[hyeongyukim]

remove braces

[hyeongyukim]

This patch was discovered in the process of solving D106041. (Like D106233)
If this patch is accepted, the performance regression caused by D106041 will be reduced.

[aqjune]

Hmm.. would it make sense if SimplifyCFG also pushes freeze into icmp's arguments?

It's because it isn't clear whether isValueEqualityComparison should allow freeze(icmp eq x, y) or not..

[efriedma]

Pushing the freeze into the operand of the icmp would be a lot easier to reason about; the existing code would just work. Not sure we can really do it effectively inside SimplifyCFG; we'd probably also need some code to merge freeze operations on the same value.

Trying to analyze (freeze (icmp a, b)) directly is potentially problematic. The biggest problem is that if the freeze has multiple uses, they have to evaluate to the same value. Some specific transforms might also need to introduce freeze operations.

[nikic]

As the relevant optimizations already exist in InstCombine (D105392, D106233) is the motivation here a phase ordering problem? No InstCombine + SimplifyCFG runs at the relevant pipeline position?

[lebedev.ri]

In D106779#2905636, @nikic wrote:

As the relevant optimizations already exist in InstCombine (D105392, D106233) is the motivation here a phase ordering problem? No InstCombine + SimplifyCFG runs at the relevant pipeline position?

I'll ask a slightly different question.
Does simplifycfg itself insert said freeze that is problematic here, and thus blocks itselves forward progress?

[hyeongyukim]

In D106779#2905687, @lebedev.ri wrote:

In D106779#2905636, @nikic wrote:

As the relevant optimizations already exist in InstCombine (D105392, D106233) is the motivation here a phase ordering problem? No InstCombine + SimplifyCFG runs at the relevant pipeline position?

I'll ask a slightly different question.
Does simplifycfg itself insert said freeze that is problematic here, and thus blocks itselves forward progress?

SimplyCFG does not insert Freeze. This freeze is inserted by loop unswitch.(D106041)

In D106779#2905636, @nikic wrote:

As the relevant optimizations already exist in InstCombine (D105392, D106233) is the motivation here a phase ordering problem? No InstCombine + SimplifyCFG runs at the relevant pipeline position?

You're right. This problem can be solved by D105392.
However, this problem may remain by order of Instcombine and SimplifyCFG.
How about calling pushFreezeToPreventPoisonFromPropagating(implemented by D105392) in SimplifyCFG? It will solve more general cases of performance degradation

[lebedev.ri]

I think something along the lines of the current patch could be fine, but i'm against doing instcombine's work here.

[hyeongyukim]

There are more problems caused by a freeze that is not yet pushed.
Is it okay to send separate patches to solve those problems?

[hyeongyukim]

In D106779#2907568, @lebedev.ri wrote:

I think something along the lines of the current patch could be fine, but i'm against doing instcombine's work here.

Can you tell me the things that would be good to modify in this patch?

[aqjune]

If loop unswitch introduced the freeze, what about adding an extra InstCombine pass between the loop unswitch and SimplifyCFG?

[lebedev.ri]

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

[nikic]

This patch either needs a PhaseOrdering test, or can be abandoned.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 Value *SimplifyCFGOpt::isValueEqualityComparison(Instruction *TI) {
   Value *CV = nullptr;
   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
     // Do not permit merging of large switch instructions into their
     // predecessors unless there is only one predecessor.
     if (!SI->getParent()->hasNPredecessorsOrMore(128 / SI->getNumSuccessors()))
       CV = SI->getCondition();
   } else if (BranchInst *BI = dyn_cast<BranchInst>(TI))
-    if (BI->isConditional() && BI->getCondition()->hasOneUse())
-      if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
-        if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL))
-          CV = ICI->getOperand(0);
-      }
+    if (BI->isConditional() && BI->getCondition()->hasOneUse()) {
+      ICmpInst *ICI = nullptr;
+      if (FreezeInst *FR = dyn_cast<FreezeInst>(BI->getCondition()))
+        ICI = dyn_cast<ICmpInst>(FR->getOperand(0));
+      else
+        ICI = dyn_cast<ICmpInst>(BI->getCondition());
+
+      if (ICI && ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL))
 
   // Unwrap any lossless ptrtoint cast.
   if (CV) {
     if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) {
       Value *Ptr = PTII->getPointerOperand();
       if (PTII->getType() == DL.getIntPtrType(Ptr->getType()))
         CV = Ptr;
     }
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
     Cases.reserve(SI->getNumCases());
     for (auto Case : SI->cases())
       Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
                                                   Case.getCaseSuccessor()));
     return SI->getDefaultDest();
   }
 
   BranchInst *BI = cast<BranchInst>(TI);
-  ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
+  ICmpInst *ICI;
+  if (FreezeInst *FR = dyn_cast<FreezeInst>(BI->getCondition()))
+    ICI = dyn_cast<ICmpInst>(FR->getOperand(0));
+  else
+    ICI = dyn_cast<ICmpInst>(BI->getCondition());
   BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE);
   Cases.push_back(ValueEqualityComparisonCase(
       GetConstantInt(ICI->getOperand(1), DL), Succ));
   return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ);
 }
 
 /// Given a vector of bb/value pairs, remove any entries
 /// in the list that match the specified block.

llvm/test/Transforms/SimplifyCFG/branch-fold.ll

 ;
 entry:
   br i1 0, label %bb0, label %bb0
 
 bb0:
   call void @foo()
   ret void
 }
+
+declare void @foo1()
+declare void @foo2()
+declare void @foo3()
+; Fold even if the condition is frozen.
+define void @test4(i32 %v) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[COND1:%.*]] = icmp ne i32 [[V:%.*]], 0
+; CHECK-NEXT:    [[COND1_FR:%.*]] = freeze i1 [[COND1]]
+; CHECK-NEXT:    br i1 [[COND1_FR]], label [[BODY1:%.*]], label [[BODY2:%.*]]
+; CHECK:       body1:
+; CHECK-NEXT:    call void @foo1()
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       body2:
+; CHECK-NEXT:    call void @foo2()
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cond1 = icmp ne i32 %v, 0
+  %cond2 = icmp eq i32 %v, 0
+  %cond1.fr = freeze i1 %cond1
+  br i1 %cond1.fr, label %body1, label %split
+
+split:
+  %cond2.fr = freeze i1 %cond2
+  br i1 %cond2.fr, label %body2, label %body3
+
+body1:
+  call void @foo1()
+  br label %end
+
+body2:
+  call void @foo2()
+  br label %end
+
+body3:
+  call void @foo3()
+  br label %end
+
+end:
+  ret void
+}