Do not remove implicit defs in BranchFolder

[kparzysz]

Summary

BranchFolder removes implicit defs from blocks where they are the only instructions, potentially aside from an unconditional branch. This can lead to the liveness information becoming incorrect.

[MatzeB]

Heh, this obviously solves the problems of the broken/missing liveness updates :)

The next question of course is whether this will degrade codegen quality. Do the jumps in those empty-but-implicit-defs blocks removed so we just have a fall-through? Does MachineBlockPlacement help with that?
I think a convincing answer would require diffing assembly generated with/without this patch on a set of benchmarks. test-suite with -save-temps=obj flag maybe?.

[kparzysz]

I built test-suite with and without this patch. Out 466 .s files, there were differences in 3:

MultiSource/Benchmarks/MiBench/consumer-typeset/z23.s

[kparzysz]

Clicked the wrong button. Once again:

I built test-suite with and without this patch. Out 466 .s files, there were differences in 3:
MultiSource/Benchmarks/MiBench/consumer-typeset/z23.s
MultiSource/Benchmarks/MiBench/consumer-typeset/z37.s
MultiSource/Benchmarks/MiBench/consumer-typeset/z44.s

[kparzysz]

I looked at the actual differences:

z23.s: one small block is located in a different place. It's not on a fall-through (either in or out) path in either case.
z37.s: block numbering differences, no codegen differences
z44.s: same as z37.s, i.e. no codegen differences

[MatzeB]

In D25478#568330, @kparzysz wrote:

I looked at the actual differences:

z23.s: one small block is located in a different place. It's not on a fall-through (either in or out) path in either case.
z37.s: block numbering differences, no codegen differences
z44.s: same as z37.s, i.e. no codegen differences

Sounds good to me.

lib/CodeGen/BranchFolding.h

private:
     bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
                                    MachineBasicBlock *SuccBB,
                                    unsigned maxCommonTailLength,
                                    unsigned &commonTailIndex);
 
     bool OptimizeBranches(MachineFunction &MF);
     bool OptimizeBlock(MachineBasicBlock *MBB);
     void RemoveDeadBlock(MachineBasicBlock *MBB);
-    bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
 
     bool HoistCommonCode(MachineFunction &MF);
     bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
   };
 }
 
 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */

lib/CodeGen/BranchFolding.cpp

void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
 
   // Remove the block.
   MF->erase(MBB);
   FuncletMembership.erase(MBB);
   if (MLI)
     MLI->removeBlock(MBB);
 }
 
-/// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def
-/// followed by terminators, and if the implicitly defined registers are not
-/// used by the terminators, remove those implicit_def's. e.g.
-/// BB1:
-///   r0 = implicit_def
-///   r1 = implicit_def
-///   br
-/// This block can be optimized away later if the implicit instructions are
-/// removed.
-bool BranchFolder::OptimizeImpDefsBlock(MachineBasicBlock *MBB) {
-  SmallSet<unsigned, 4> ImpDefRegs;
-  MachineBasicBlock::iterator I = MBB->begin();
-  while (I != MBB->end()) {
-    if (!I->isImplicitDef())
-      break;
-    unsigned Reg = I->getOperand(0).getReg();
-    if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
-      for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
-           SubRegs.isValid(); ++SubRegs)
-        ImpDefRegs.insert(*SubRegs);
-    } else {
-      ImpDefRegs.insert(Reg);
-    }
-    ++I;
-  }
-  if (ImpDefRegs.empty())
-    return false;
-
-  MachineBasicBlock::iterator FirstTerm = I;
-  while (I != MBB->end()) {
-    if (!TII->isUnpredicatedTerminator(*I))
-      return false;
-    // See if it uses any of the implicitly defined registers.
-    for (const MachineOperand &MO : I->operands()) {
-      if (!MO.isReg() || !MO.isUse())
-        continue;
-      unsigned Reg = MO.getReg();
-      if (ImpDefRegs.count(Reg))
-        return false;
-    }
-    ++I;
-  }
-
-  I = MBB->begin();
-  while (I != FirstTerm) {
-    MachineInstr *ImpDefMI = &*I;
-    ++I;
-    MBB->erase(ImpDefMI);
-  }
-
-  return true;
-}
-
 /// OptimizeFunction - Perhaps branch folding, tail merging and other
 /// CFG optimizations on the given function.  Block placement changes the layout
 /// and may create new tail merging opportunities.
 bool BranchFolder::OptimizeFunction(MachineFunction &MF,
                                     const TargetInstrInfo *tii,
                                     const TargetRegisterInfo *tri,
                                     MachineModuleInfo *mmi,
                                     MachineLoopInfo *mli, bool AfterPlacement) {
bool BranchFolder::OptimizeFunction(MachineFunction &MF,
 
   // Fix CFG.  The later algorithms expect it to be right.
   bool MadeChange = false;
   for (MachineBasicBlock &MBB : MF) {
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     SmallVector<MachineOperand, 4> Cond;
     if (!TII->analyzeBranch(MBB, TBB, FBB, Cond, true))
       MadeChange |= MBB.CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
-    MadeChange |= OptimizeImpDefsBlock(&MBB);
   }
 
   // Recalculate funclet membership.
   FuncletMembership = getFuncletMembership(MF);
 
   bool MadeChangeThisIteration = true;
   while (MadeChangeThisIteration) {
     MadeChangeThisIteration    = TailMergeBlocks(MF);

test/CodeGen/Hexagon/branchfolder-keep-impdef.ll

+; RUN: llc -march=hexagon -verify-machineinstrs < %s | FileCheck %s
+;
+; Check that the testcase compiles successfully. Expect that if-conversion
+; took place.
+; CHECK-LABEL: fred:
+; CHECK: if (!p0) r1 = memw(r0 + #0)
+
+target triple = "hexagon"
+
+define void @fred(i32 %p0) local_unnamed_addr align 2 {
+b0:
+  br i1 undef, label %b1, label %b2
+
+b1:                                               ; preds = %b0
+  %t0 = load i8*, i8** undef, align 4
+  br label %b2
+
+b2:                                               ; preds = %b1, %b0
+  %t1 = phi i8* [ %t0, %b1 ], [ undef, %b0 ]
+  %t2 = getelementptr inbounds i8, i8* %t1, i32 %p0
+  tail call void @llvm.memmove.p0i8.p0i8.i32(i8* undef, i8* %t2, i32 undef, i32 1, i1 false) #1
+  unreachable
+}
+
+declare void @llvm.memmove.p0i8.p0i8.i32(i8* nocapture, i8* nocapture readonly, i32, i32, i1) #0
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { nounwind }
+

test/Transforms/LoopStrengthReduce/X86/2012-01-13-phielim.ll

 ; Test redundant phi elimination when the deleted phi's increment is
 ; itself a phi.
 ;
 ; CHECK: @test3
 ; CHECK: %for.body3.lr.ph.us.i.loopexit
 ; CHECK-NEXT: in Loop: Header
 ; CHECK-NEXT: incq
 ; CHECK-NEXT: %for.body3.us.i
+; CHECK-NEXT: Parent Loop
 ; CHECK-NEXT: Inner Loop
 ; CHECK: testb
 ; CHECK: je
 ; CHECK: jmp
 define fastcc void @test3(double* nocapture %u) nounwind uwtable ssp {
 entry:
   br i1 undef, label %meshBB1, label %meshBB5