[InstCombine] Teach the move free before null test opti how to deal with noop casts

[qcolombet]

Summary

InstCombine features an optimization that essentially replaces:
if (a)

free(a)

into:
free(a)

Right now, this optimization is gated by the minsize attribute and therefore
we only perform it if we can prove that we are going to be able to eliminate
the branch and the destination block.

However when casts are involved the optimization would fail to apply, because
the optimization was not smart enough to realize that it is possible to also
move the casts away from the destination block and that is harmless to the
performance since they are just noops.
E.g.,
foo(int *a)
if (a)

free((char*)a)

Wouldn't be optimized by instcombine, because

• We would refuse to hoist the bitcast i32* %a to i8 in the source block
• We would fail to see that bitcast i32* %a to i8 and %a are the same value.

This patch fixes both these problems:

• It teaches the pattern matching of the comparison how to look

through casts.

• It checks that whether the additional instruction in the destination block

can be hoisted and are harmless performance-wise.

• It hoists all the code of the destination block in the source block.

[qcolombet]

Ping

[lebedev.ri]

lib/Transforms/InstCombine/InstructionCombining.cpp

2363–2367 ↗

(On Diff #169948)

if (!match(TI, m_Br(m_ICmp(Pred,
                           m_CombineOr(m_Specific(Op),
                                       m_Specific(Op->stripPointerCasts())),
                           m_Zero()), TrueBB, FalseBB)))

[spatel]

This is adding to a transform that seems out-of-place for instcombine:

1. It's a hoist transform that relies on SimplifyCFG to do the real optimization. Does the whole thing belong there (or CGP) instead?
2. It's the only transform in instcombine that is gated by 'minsize', so it's a limited optimization rather than a canonicalization?

[qcolombet]

Hi Sanjay,

This is adding to a transform that seems out-of-place for instcombine:
It's a hoist transform that relies on SimplifyCFG to do the real optimization. Does the whole thing belong there (or CGP) instead?

Interestingly I think we had the exact same conversation when it was first added back in 2013, but I cannot find any trace of this discussion... My mind must play me tricks :).
I am happy to move the whole thing in simplifyCFG. That said, strictly speaking that combine doesn't modify the CFG.
CGP seems too late to me.

It's the only transform in instcombine that is gated by 'minsize', so it's a limited optimization rather than a canonicalization?

That is correct, though, I'd argue that a lot of code in instcombine are optimizations too (as opposed to pure cannonicalization.)

How would you like to proceed?

Cheers,
-Quentin

lib/Transforms/InstCombine/InstructionCombining.cpp

2363–2367 ↗

(On Diff #169948)

Ah great! I was looking for something like m_CombineOr, but missed it.

[spatel]

In D53356#1274624, @qcolombet wrote:

Interestingly I think we had the exact same conversation when it was first added back in 2013, but I cannot find any trace of this discussion... My mind must play me tricks :).

I think the original patch was before I got here, so I probably didn't see it...but I did ask about that patch in D45343, so that might be what you are remembering. :)

I am happy to move the whole thing in simplifyCFG. That said, strictly speaking that combine doesn't modify the CFG.

If it doesn't look too hard, moving it over to SimplifyCFG would be great. That way, we can be sure that the empty block removal always happens without interference from some other pass.

CGP seems too late to me.

It's the only transform in instcombine that is gated by 'minsize', so it's a limited optimization rather than a canonicalization?

That is correct, though, I'd argue that a lot of code in instcombine are optimizations too (as opposed to pure cannonicalization.)

How would you like to proceed?

Cheers,
-Quentin

[qcolombet]

If it doesn't look too hard, moving it over to SimplifyCFG would be great. That way, we can be sure that the empty block removal always happens without interference from some other pass.

Sounds good!

[qcolombet]

Hi Sanjay,

I had a quick look and it doesn't seem to be a good fit for simplifyCFG.
In particular, simplifyCFG only inspects terminator instructions and it feels out of place to add a scan through the entire list of instructions to find a call to free.

Let me know if you want me to pursue in that direction or if you have another idea.

Cheers,
-Quentin

[qcolombet]

• Use m_CombineOr instead of repeating the pattern to match

[spatel]

In D53356#1278974, @qcolombet wrote:

I had a quick look and it doesn't seem to be a good fit for simplifyCFG.
In particular, simplifyCFG only inspects terminator instructions and it feels out of place to add a scan through the entire list of instructions to find a call to free.

Let me know if you want me to pursue in that direction or if you have another idea.

I was afraid this was going to be an odd fit no matter what we tried to do with it, so no I don't have any better ideas short of making a standalone pass, and I'm not sure if there are any other transforms like this to justify that effort.

Given that this is a small extension of the existing transform, I'll say LGTM.

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

 ///
 /// Check if this free is accessed after its argument has been test
 /// against NULL (property 0).
 /// If yes, it is legal to move this call in its predecessor block.
 ///
 /// The move is performed only if the block containing the call to free
 /// will be removed, i.e.:
 /// 1. it has only one predecessor P, and P has two successors
-/// 2. it contains the call and an unconditional branch
+/// 2. it contains the call, noops, and an unconditional branch
 /// 3. its successor is the same as its predecessor's successor
 ///
 /// The profitability is out-of concern here and this function should
 /// be called only if the caller knows this transformation would be
 /// profitable (e.g., for code size).
-static Instruction *
-tryToMoveFreeBeforeNullTest(CallInst &FI) {
+static Instruction *tryToMoveFreeBeforeNullTest(CallInst &FI,
+                                                const DataLayout &DL) {
   Value *Op = FI.getArgOperand(0);
   BasicBlock *FreeInstrBB = FI.getParent();
   BasicBlock *PredBB = FreeInstrBB->getSinglePredecessor();
 
   // Validate part of constraint #1: Only one predecessor
   // FIXME: We can extend the number of predecessor, but in that case, we
   //        would duplicate the call to free in each predecessor and it may
   //        not be profitable even for code size.
   if (!PredBB)
     return nullptr;
 
   // Validate constraint #2: Does this block contains only the call to
-  //                         free and an unconditional branch?
-  // FIXME: We could check if we can speculate everything in the
-  //        predecessor block
-  if (FreeInstrBB->size() != 2)
-    return nullptr;
+  //                         free, noops, and an unconditional branch?
   BasicBlock *SuccBB;
-  if (!match(FreeInstrBB->getTerminator(), m_UnconditionalBr(SuccBB)))
+  Instruction *FreeInstrBBTerminator = FreeInstrBB->getTerminator();
+  if (!match(FreeInstrBBTerminator, m_UnconditionalBr(SuccBB)))
     return nullptr;
 
+  // If there are only 2 instructions in the block, at this point,
+  // this is the call to free and unconditional.
+  // If there are more than 2 instructions, check that they are noops
+  // i.e., they won't hurt the performance of the generated code.
+  if (FreeInstrBB->size() != 2) {
+    for (const Instruction &Inst : *FreeInstrBB) {
+      if (&Inst == &FI || &Inst == FreeInstrBBTerminator)
+        continue;
+      auto *Cast = dyn_cast<CastInst>(&Inst);
+      if (!Cast || !Cast->isNoopCast(DL))
+        return nullptr;
+    }
+  }
   // Validate the rest of constraint #1 by matching on the pred branch.
   Instruction *TI = PredBB->getTerminator();
   BasicBlock *TrueBB, *FalseBB;
   ICmpInst::Predicate Pred;
-  if (!match(TI, m_Br(m_ICmp(Pred, m_Specific(Op), m_Zero()), TrueBB, FalseBB)))
+  if (!match(TI, m_Br(m_ICmp(Pred,
+                             m_CombineOr(m_Specific(Op),
+                                         m_Specific(Op->stripPointerCasts())),
+                             m_Zero()),
+                      TrueBB, FalseBB)))
     return nullptr;
   if (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE)
     return nullptr;
 
   // Validate constraint #3: Ensure the null case just falls through.
   if (SuccBB != (Pred == ICmpInst::ICMP_EQ ? TrueBB : FalseBB))
     return nullptr;
   assert(FreeInstrBB == (Pred == ICmpInst::ICMP_EQ ? FalseBB : TrueBB) &&
          "Broken CFG: missing edge from predecessor to successor");
 
-  FI.moveBefore(TI);
+  // At this point, we know that everything in FreeInstrBB can be moved
+  // before TI.
+  for (BasicBlock::iterator It = FreeInstrBB->begin(), End = FreeInstrBB->end();
+       It != End;) {
+    Instruction &Instr = *It++;
+    if (&Instr == FreeInstrBBTerminator)
+      break;
+    Instr.moveBefore(TI);
+  }
+  assert(FreeInstrBB->size() == 1 &&
+         "Only the branch instruction should remain");
   return &FI;
 }
 
 Instruction *InstCombiner::visitFree(CallInst &FI) {
   Value *Op = FI.getArgOperand(0);
 
   // free undef -> unreachable.
   if (isa<UndefValue>(Op)) {
Instruction *InstCombiner::visitFree(CallInst &FI) {
 
   // If we optimize for code size, try to move the call to free before the null
   // test so that simplify cfg can remove the empty block and dead code
   // elimination the branch. I.e., helps to turn something like:
   // if (foo) free(foo);
   // into
   // free(foo);
   if (MinimizeSize)
-    if (Instruction *I = tryToMoveFreeBeforeNullTest(FI))
+    if (Instruction *I = tryToMoveFreeBeforeNullTest(FI, DL))
       return I;
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitReturnInst(ReturnInst &RI) {
   if (RI.getNumOperands() == 0) // ret void
     return nullptr;

llvm/trunk/test/Transforms/InstCombine/malloc-free-delete.ll

 define void @test11() {
 ; CHECK-LABEL: @test11
 ; CHECK: call i8* @_Znwm
 ; CHECK: call void @_ZdlPv
   %call = call i8* @_Znwm(i64 8) builtin
   call void @_ZdlPv(i8* %call)
   ret void
 }
+
+;; Check that the optimization that moves a call to free in its predecessor
+;; block (see test6) also happens when noop casts are involved.
+; CHECK-LABEL: @test12(
+define void @test12(i32* %foo) minsize {
+; CHECK:  %tobool = icmp eq i32* %foo, null
+;; Everything before the call to free should have been moved as well.
+; CHECK-NEXT:   %bitcast = bitcast i32* %foo to i8*
+;; Call to free moved
+; CHECK-NEXT: tail call void @free(i8* %bitcast)
+; CHECK-NEXT: br i1 %tobool, label %if.end, label %if.then
+; CHECK: if.then:
+;; Block is now empty and may be simplified by simplifycfg
+; CHECK-NEXT:   br label %if.end
+; CHECK: if.end:
+; CHECK-NEXT:  ret void
+entry:
+  %tobool = icmp eq i32* %foo, null
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %bitcast = bitcast i32* %foo to i8*
+  tail call void @free(i8* %bitcast)
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  ret void
+}
+