[InstCombine] Prevent unnecessary sinks caused by the Freeze

[hyeongyukim]

Summary

The Freeze is added to Cond in fixing the miscomputation of loop unswitch(D106041).
However, more sinks are generated in Instcombine by Freeze that added in D106041.

Below is a situation where D106041 is not applied(bug exists in LU).
If D106041 is not applied, load(ptr) will not sink after InstCombine is performed.

  v = load(ptr)
  cond = icmp eq(v, 0)
  br body

body:
  br(cond, ..., ...)
=>
  v = load(ptr)
  br body

body:
  cond = icmp eq(v, 0)
  br(cond, ..., ...)

But when we add the Freeze to Cond(to fix LU), load(ptr) is sink to body block.
And this is not the intended situation.

  v = load(ptr)
  cond = icmp eq(v, 0)
  cond.fr = freeze(cond)
  br body

body:
  br(cond.fr, ..., ...)
=>
  br body

body:
  v = load(ptr)
  v.fr = freeze(v)
  cond = icmp eq(v, 0)
  br(cond, ..., ...)

Once this patch is applied, the load will not sink, but only Freeze and icmp will sink as below.

  v = load(ptr)
  cond = icmp eq(v, 0)
  cond.fr = freeze(cond)
  br body

body:
  br(cond.fr, ..., ...)
=>
  v = load(ptr)
  br body

body:
  v.fr = freeze(v)
  cond = icmp eq(v, 0)
  br(cond, ..., ...)

[lebedev.ri]

I'm sorry, but TLDR.
We already sink everything successfully: https://godbolt.org/z/df73PEPf4
Why do we not want to sink the load in @test4.freeze,
or more generally, why do we not sink it in the first case?

[nikic]

I don't understand why we want/need to prevent sinking.

[hyeongyukim]

In the original code(code without freeze), load is not sinking.
And I thought I have to sink as few instructions as possible because the body block could run more than once.

However, I noticed that instructions would not sink if the body block could run more than once.
So... I think this patch is meaningless. Can I abandon this revision?

[lebedev.ri]

Yeah, i think there's already a profitability check there, so i don't see why we'd want this.
It could be interesting to enhance the sinking to handle multiple uses (see findCommonDominator() in SimplifyIndVar.cpp),
not sure what compile-time implications that would have.

[aqjune]

As suggested, finding a common dominator and sinking the instruction to the location seems reasonable and worth trying.
It will help reduce the diff at line 3866~, I hope.
If DT is null, fallback to the old one use check?

[lebedev.ri]

In D107180#2917924, @aqjune wrote:

As suggested, finding a common dominator and sinking the instruction to the location seems reasonable and worth trying.
It will help reduce the diff at line 3866~, I hope.
If DT is null, fallback to the old one use check?

DT can not be null here

[hyeongyukim]

In D107180#2917128, @lebedev.ri wrote:

Yeah, i think there's already a profitability check there, so i don't see why we'd want this.
It could be interesting to enhance the sinking to handle multiple uses (see findCommonDominator() in SimplifyIndVar.cpp),
not sure what compile-time implications that would have.

I am writing a new patch(D107226) related to your comment.
I agree that this patch is not profitable, so I'll close it!

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

if (!I->use_empty() &&
           eraseInstFromFunction(*I);
         MadeIRChange = true;
         continue;
       }
     }
 
     // See if we can trivially sink this instruction to its user if we can
     // prove that the successor is not executed more frequently than our block.
-    if (EnableCodeSinking)
-      if (Use *SingleUse = I->getSingleUndroppableUse()) {
+    if (EnableCodeSinking) {
+      FreezeInst* FI = nullptr;
+      Use *SingleUse = I->getSingleUndroppableUse();
+
+      // If single use of I is fr(I), try to sink I and fr(I) simultaneously.
+      if (SingleUse) {
+        User *U = SingleUse->getUser();
+        FI = dyn_cast<FreezeInst>(U);
+        if (FI)
+          SingleUse = FI->getSingleUndroppableUse();
+      }
+      if (SingleUse) {
         BasicBlock *BB = I->getParent();
         Instruction *UserInst = cast<Instruction>(SingleUse->getUser());
         BasicBlock *UserParent;
 
         // Get the block the use occurs in.
         if (PHINode *PN = dyn_cast<PHINode>(UserInst))
           UserParent = PN->getIncomingBlock(*SingleUse);
         else
if (EnableCodeSinking) {
           // So sinking I down to User is always profitable or neutral.
           if (!ShouldSink) {
             auto *Term = UserParent->getTerminator();
             ShouldSink = isa<ReturnInst>(Term) || isa<UnreachableInst>(Term);
           }
           if (ShouldSink) {
             assert(DT.dominates(BB, UserParent) &&
                    "Dominance relation broken?");
+            bool Sinked = false;
+
             // Okay, the CFG is simple enough, try to sink this instruction.
-            if (TryToSinkInstruction(I, UserParent)) {
+            if (FI) {
+              if (TryToSinkInstruction(FI, UserParent) && TryToSinkInstruction(I, UserParent)) {
+                LLVM_DEBUG(dbgs() << "IC: Sink: " << *FI << '\n');
+                LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n');
+                Sinked = true;
+              }
+            }
+            else if (TryToSinkInstruction(I, UserParent)) {
               LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n');
+              Sinked = true;
+            }
+
+            if (Sinked) {
               MadeIRChange = true;
               // We'll add uses of the sunk instruction below, but since sinking
               // can expose opportunities for it's *operands* add them to the
               // worklist
               for (Use &U : I->operands())
                 if (Instruction *OpI = dyn_cast<Instruction>(U.get()))
                   Worklist.push(OpI);
             }
           }
         }
       }
+    }
 
     // Now that we have an instruction, try combining it to simplify it.
     Builder.SetInsertPoint(I);
     Builder.CollectMetadataToCopy(
         I, {LLVMContext::MD_dbg, LLVMContext::MD_annotation});
 
 #ifndef NDEBUG
     std::string OrigI;

llvm/test/Transforms/InstCombine/sink_instruction.ll

 ; CHECK: %0 = load i32, i32* %arrayidx, align 4
   %add = add nsw i32 %0, %i
   br label %sw.epilog
 
 sw.epilog:                                        ; preds = %entry, %sw.bb
   %sum.0 = phi i32 [ %add, %sw.bb ], [ 0, %entry ]
   ret i32 %sum.0
 }
+
+declare void @f()
+
+declare void @use(i32)
+
+define void @test4(i32* %ptr, i1 %cond0) {
+entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT: %temp = load i32, i32* %ptr, align 4
+  %temp  = load i32, i32* %ptr,  align 4
+  %cond1 = icmp eq i32 %temp, 0
+  br i1 %cond0, label %split, label %end
+
+split:                                            ; preds = %entry
+; CHECK-LABEL: split:
+; CHECK-NEXT: %cond1 = icmp eq i32 %temp, 0
+  br i1 %cond1, label %body1, label %body2
+
+body1:                                            ; preds = %split
+  call void @f()
+  br label %end
+
+body2:                                            ; preds = %split
+  call void @use(i32 %temp)
+  br label %end
+
+end:                                              ; preds = %body2, %body1, %entry
+  ret void
+}
+
+define void @test4.freeze(i32* %ptr, i1 %cond0) {
+entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT: %temp = load i32, i32* %ptr, align 4
+  %temp  = load i32, i32* %ptr,  align 4
+  %cond1 = icmp eq i32 %temp, 0
+  %cond1.fr = freeze i1 %cond1
+  br i1 %cond0, label %split, label %end
+
+split:                                            ; preds = %entry
+; CHECK-LABEL: split:
+; CHECK-NEXT: %temp.fr = freeze i32 %temp
+; CHECK-NEXT: %cond1 = icmp eq i32 %temp.fr, 0
+  br i1 %cond1.fr, label %body1, label %body2
+
+body1:                                            ; preds = %split
+  call void @f()
+  br label %end
+
+body2:                                            ; preds = %split
+  call void @use(i32 %temp)
+  br label %end
+
+end:                                              ; preds = %body2, %body1, %entry
+  ret void
+}
 No newline at end of file