[PowerPC] Update branch coalescing to be a PowerPC specific pass

[lei]

Summary

Implementing this pass as a PowerPC specific pass.

This branch coalescing pass utilizes the analyzeBranch method which currently does not include any implicit operands.
This is not an issue on PPC but must be handled on other targets. For this pass to be made target-independent, the analyzeBranch API need to be updated to support implicit operands and there would need to be a way to verify that any implicit operands would not be clobbered by merging blocks.

Original patch implementation: https://reviews.llvm.org/D28249
Bugzilla: https://llvm.org/bugs/show_bug.cgi?id=25219

[nemanjai]

include/llvm/Target/TargetFrameLowering.h

149

I find this an unusual place for this check. What is the relationship between this pass and frame lowering?

test/CodeGen/PowerPC/select-i1-vs-i1.ll

1029

I don't think this comment is necessary here. It should suffice to just remove the FIXME comment. The reason I say that is that the user will not know that we once had this duplicate block issue.

[lei]

include/llvm/Target/TargetFrameLowering.h

149

None. Will move.

test/CodeGen/PowerPC/select-i1-vs-i1.ll

1029

k.

[lei]

Move check to subtarget.

[kbarton]

Aside from two minor comments, this LGTM.
Please make sure to update the release notes when this gets committed.

include/llvm/Target/TargetSubtargetInfo.h

139 ↗

(On Diff #97851)

We no longer need \brief since autobrief has been turned on for doxygen.

test/CodeGen/PowerPC/branch_coalesce.ll

2

There is nothing specific to pwr8 in this patch so I think we're better to remove -mcpu=pwr8.

[echristo]

Hrm.

I can think of three ways to enable this:

a) Enable it all the time, this would take some benchmarking across platforms, but I think is the right long term direction.
b) Add it as a pass in the backend, and use something like a lambda passed into the constructor to conditionalize it if you want (see inline question below)
c) Do this for now, but do all of the work in a as well to turn it on (i.e. a above) and remove the subtarget query (caveat of the inline question below).

I guess this comes down to my (now expanded) inline question of:

why don't we just want this on all the time on all targets?

One additional followup question:

Did you see any other performance changes across spec/lnt? Any degredations? Any other benchmark runs?

Thanks!

-eric

lib/CodeGen/TargetPassConfig.cpp

722

You don't need this because of the skipFunction query in the pass.

lib/Target/PowerPC/PPCSubtarget.cpp

183 ↗

(On Diff #97851)

Is this the right choice or is this just the only place it's been tested?

[lei]

In D32776#746781, @echristo wrote:

Hrm.

I can think of three ways to enable this:

a) Enable it all the time, this would take some benchmarking across platforms, but I think is the right long term direction.
b) Add it as a pass in the backend, and use something like a lambda passed into the constructor to conditionalize it if you want (see inline question below)
c) Do this for now, but do all of the work in a as well to turn it on (i.e. a above) and remove the subtarget query (caveat of the inline question below).

I guess this comes down to my (now expanded) inline question of:

why don't we just want this on all the time on all targets?

Investigation into this is now being done.

One additional followup question:

Did you see any other performance changes across spec/lnt? Any degredations? Any other benchmark runs?

The only performance run I did so far is SPEC2006 on a power8 LE machine.
A speed up of > 1 means better performance with branch coalescing enabled. Based on the speed up below, we see a 11% improvement for lbm and 28% improvement for mcf.

Benchmark Speed Up
433.milc 0.997
444.namd 1.000
450.soplex 1.002
453.povray 0.995
470.lbm 1.112
482.sphinx3 1.006
400.perlbench 1.001
401.bzip2 1.000
403.gcc 1.067
429.mcf 1.284
445.gobmk 1.001
456.hmmer 1.000
458.sjeng 1.000
462.libquantum 1.025
464.h264ref 0.997
473.astar 0.998
483.xalancbmk 1.043

Thanks!

-eric

[lei]

Updating this to be a PPC specific pass since it does not handle implicit operands which are used by other targets.

[lei]

remove -mcpu=pwr8 from IR test case.

[kbarton]

I would change the summary of this review to reflect the fact we are moving this pass back to the PPC target.
Aside from that, this LGTM.

It would be good if @hfinkel could take a quick look and make sure he has no further comments.

[hfinkel]

In D32776#849078, @kbarton wrote:

I would change the summary of this review to reflect the fact we are moving this pass back to the PPC target.
Aside from that, this LGTM.

It would be good if @hfinkel could take a quick look and make sure he has no further comments.

Yes, please go ahead.

[lei]

Turn patch off by default.

[iteratee]

lib/CodeGen/TargetPassConfig.cpp

40–41

These seem unrelated. Can you pull them out?

[lei]

lib/CodeGen/TargetPassConfig.cpp

40–41

I do not understand why you want me to pull these out. They were not added by me and it is being used later on in this src.

[iteratee]

I don't think this should go in, even off by default as long as it's broken. You can pull the produceSameValue check or fix it, but I don't like having a known-broken pass in tree.

lib/CodeGen/TargetPassConfig.cpp

40–41

Sorry, I was trying to look at your original diff vs this one to see what changed.

[hfinkel]

lib/CodeGen/TargetPassConfig.cpp

40–41

What are you talking about? I see no changes here.

[sfertile]

lib/CodeGen/TargetPassConfig.cpp

40–41

If you compare diff 4 to diff 5 it makes it look like EnableIPRA got added in diff 5.

[lei]

Added logic to filter out physical register uses on line 347 in lib/Target/PowerPC/PPCBranchCoalescing.cpp.

@iteratee, please let me know if this fixes the issue you were seeing. Thanks!

[lei]

Pass is currently off by default. Enable pass via -enable-ppc-branch-coalesce.

[iteratee]

I'm OK with this.

[echristo]

Acking to clear the no bit.

include/llvm/Target/TargetFrameLowering.h

public:
 
   /// targetHandlesStackFrameRounding - Returns true if the target is
   /// responsible for rounding up the stack frame (probably at emitPrologue
   /// time).
   virtual bool targetHandlesStackFrameRounding() const {
     return false;
   }
 
+  /// Returns true if the target will correctly handle branch coalescing
+  virtual bool enableBranchCoalescing(const MachineFunction &MF) const {
+    return false;
+  }
+
   /// Returns true if the target will correctly handle shrink wrapping.
   virtual bool enableShrinkWrapping(const MachineFunction &MF) const {
     return false;
   }
 
   /// Returns true if the stack slot holes in the fixed and callee-save stack
   /// area should be used when allocating other stack locations to reduce stack
   /// size.

lib/CodeGen/BranchCoalescing.cpp

class BranchCoalescing : public MachineFunctionPass {
 
   void initialize(MachineFunction &F);
   bool canCoalesceBranch(CoalescingCandidateInfo &Cand);
   bool identicalOperands(ArrayRef<MachineOperand> OperandList1,
                          ArrayRef<MachineOperand> OperandList2) const;
   bool validateCandidates(CoalescingCandidateInfo &SourceRegion,
                           CoalescingCandidateInfo &TargetRegion) const;
 
-  static bool isBranchCoalescingEnabled() {
-    return EnableBranchCoalescing == cl::BOU_TRUE;
-  }
+  static bool isBranchCoalescingEnabled(const MachineFunction &MF);
 
 public:
   static char ID;
 
   BranchCoalescing() : MachineFunctionPass(ID) {
     initializeBranchCoalescingPass(*PassRegistry::getPassRegistry());
   }
 
bool BranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
 
   NumBlocksCoalesced++;
   return true;
 }
 
 bool BranchCoalescing::runOnMachineFunction(MachineFunction &MF) {
 
   if (skipFunction(*MF.getFunction()) || MF.empty() ||
-      !isBranchCoalescingEnabled())
+      !isBranchCoalescingEnabled(MF))
     return false;
 
   bool didSomething = false;
 
   DEBUG(dbgs() << "******** Branch Coalescing ********\n");
   initialize(MF);
 
   DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
#ifndef NDEBUG
   // Verify MF is still valid after branch coalescing
   if (didSomething)
     MF.verify(nullptr, "Error in code produced by branch coalescing");
 #endif // NDEBUG
 
   DEBUG(dbgs() << "Finished Branch Coalescing\n");
   return didSomething;
 }
+
+bool BranchCoalescing::isBranchCoalescingEnabled(const MachineFunction &MF) {
+  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
+
+  switch (EnableBranchCoalescing) {
+  case cl::BOU_UNSET:
+    return TFI->enableBranchCoalescing(MF);
+  case cl::BOU_TRUE:
+    return true;
+  case cl::BOU_FALSE:
+    return false;
+  }
+  llvm_unreachable("Invalid branch coalescing state");
+}

lib/CodeGen/TargetPassConfig.cpp

 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/SymbolRewriter.h"
 
 using namespace llvm;
 
 static cl::opt<bool> DisablePostRASched("disable-post-ra", cl::Hidden,
     cl::desc("Disable Post Regalloc Scheduler"));
 static cl::opt<bool> DisableBranchFold("disable-branch-fold", cl::Hidden,
     cl::desc("Disable branch folding"));
 static cl::opt<bool> DisableTailDuplicate("disable-tail-duplicate", cl::Hidden,
     cl::desc("Disable tail duplication"));
 static cl::opt<bool> DisableEarlyTailDup("disable-early-taildup", cl::Hidden,
     cl::desc("Disable pre-register allocation tail duplication"));
 static cl::opt<bool> DisableBlockPlacement("disable-block-placement",
void TargetPassConfig::addMachineSSAOptimization() {
   // like if-conversion. Such passes will typically need dominator trees and
   // loop info, just like LICM and CSE below.
   addILPOpts();
 
   addPass(&MachineLICMID, false);
   addPass(&MachineCSEID, false);
 
   // Coalesce basic blocks with the same branch condition
+  if (getOptLevel() != CodeGenOpt::None)
     addPass(&BranchCoalescingID);
 
   addPass(&MachineSinkingID);
 
   addPass(&PeepholeOptimizerID);
   // Clean-up the dead code that may have been generated by peephole
   // rewriting.
   addPass(&DeadMachineInstructionElimID);
 }

lib/Target/PowerPC/PPCFrameLowering.h

public:
 
   /// getLinkageSize - Return the size of the PowerPC ABI linkage area.
   ///
   unsigned getLinkageSize() const { return LinkageSize; }
 
   const SpillSlot *
   getCalleeSavedSpillSlots(unsigned &NumEntries) const override;
 
+  bool enableBranchCoalescing(const MachineFunction &MF) const override;
   bool enableShrinkWrapping(const MachineFunction &MF) const override;
 
   /// Methods used by shrink wrapping to determine if MBB can be used for the
   /// function prologue/epilogue.
   bool canUseAsPrologue(const MachineBasicBlock &MBB) const override;
   bool canUseAsEpilogue(const MachineBasicBlock &MBB) const override;
 };
 } // End llvm namespace
 
 #endif

lib/Target/PowerPC/PPCFrameLowering.cpp

if (CR2Spilled || CR3Spilled || CR4Spilled) {
     bool is31 = needsFP(*MF);
     restoreCRs(Subtarget.isPPC64(), is31, CR2Spilled, CR3Spilled, CR4Spilled,
                MBB, I, CSI, CSIIndex);
   }
 
   return true;
 }
 
+bool PPCFrameLowering::enableBranchCoalescing(const MachineFunction &MF) const {
+  return (MF.getSubtarget<PPCSubtarget>().isSVR4ABI() &&
+          MF.getSubtarget<PPCSubtarget>().isPPC64());
+}
+
 bool PPCFrameLowering::enableShrinkWrapping(const MachineFunction &MF) const {
   return (MF.getSubtarget<PPCSubtarget>().isSVR4ABI() &&
           MF.getSubtarget<PPCSubtarget>().isPPC64());
 }

test/CodeGen/PowerPC/branch_coalesce.ll

-; RUN: llc -mcpu=pwr8 -mtriple=powerpc64le-unknown-linux-gnu -verify-machineinstrs -enable-branch-coalesce=true < %s | FileCheck %s 
-; RUN: llc -mcpu=pwr8 -mtriple=powerpc64-unknown-linux-gnu -verify-machineinstrs -enable-branch-coalesce=true < %s | FileCheck %s 
+; RUN: llc -mcpu=pwr8 -mtriple=powerpc64le-unknown-linux-gnu -verify-machineinstrs < %s | FileCheck %s
+; RUN: llc -mcpu=pwr8 -mtriple=powerpc64-unknown-linux-gnu -verify-machineinstrs < %s | FileCheck %s
+; RUN: llc -enable-branch-coalesce=false -mcpu=pwr8 -mtriple=powerpc64le-unknown-linux-gnu -verify-machineinstrs < %s | FileCheck --check-prefix=CHECK-NOCOALESCE %s
+; RUN: llc -enable-branch-coalesce=false -mcpu=pwr8 -mtriple=powerpc64-unknown-linux-gnu -verify-machineinstrs < %s | FileCheck --check-prefix=CHECK-NOCOALESCE %s
 
 ; Function Attrs: nounwind
 define double @testBranchCoal(double %a, double %b, double %c, i32 %x) {
-entry:
-  %test = icmp eq i32 %x, 0
-  %tmp1 = select i1 %test, double %a, double 2.000000e-03
-  %tmp2 = select i1 %test, double %b, double 0.000000e+00
-  %tmp3 = select i1 %test, double %c, double 5.000000e-03
-
-  %res1 = fadd double %tmp1, %tmp2
-  %result = fadd double %res1, %tmp3
-  ret double %result
 
-; CHECK-LABEL: @testBranchCoal 
+; CHECK-LABEL: @testBranchCoal
 ; CHECK: cmplwi [[CMPR:[0-7]+]], 6, 0
 ; CHECK: beq [[CMPR]], .LBB[[LAB1:[0-9_]+]]
 ; CHECK-DAG: addis [[LD1REG:[0-9]+]], 2, .LCPI0_0@toc@ha
 ; CHECK-DAG: addis [[LD2REG:[0-9]+]], 2, .LCPI0_1@toc@ha
 ; CHECK-DAG: xxlxor 2, 2, 2
-; CHECK-NOT: beq 
-; CHECK-DAG: addi [[LD1BASE:[0-9]+]], [[LD1REG]] 
+; CHECK-NOT: beq
+; CHECK-DAG: addi [[LD1BASE:[0-9]+]], [[LD1REG]]
 ; CHECK-DAG: addi [[LD2BASE:[0-9]+]], [[LD2REG]]
 ; CHECK-DAG: lxsdx 1, 0, [[LD1BASE]]
 ; CHECK-DAG: lxsdx 3, 0, [[LD2BASE]]
 ; CHECK: .LBB[[LAB1]]
 ; CHECK: xsadddp 0, 1, 2
 ; CHECK: xsadddp 1, 0, 3
 ; CHECK: blr
+
+; CHECK-NOCOALESCE-LABEL: testBranchCoal:
+; CHECK-NOCOALESCE:       # BB#0: # %entry
+; CHECK-NOCOALESCE-NEXT:    cmplwi 0, 6, 0
+; CHECK-NOCOALESCE-NEXT:    bne 0, .LBB0_5
+; CHECK-NOCOALESCE-NEXT:  # BB#1: # %entry
+; CHECK-NOCOALESCE-NEXT:    bne 0, .LBB0_6
+; CHECK-NOCOALESCE-NEXT:  .LBB0_2: # %entry
+; CHECK-NOCOALESCE-NEXT:    beq 0, .LBB0_4
+; CHECK-NOCOALESCE-NEXT:  .LBB0_3: # %entry
+; CHECK-NOCOALESCE-NEXT:    addis 3, 2, .LCPI0_1@toc@ha
+; CHECK-NOCOALESCE-NEXT:    addi 3, 3, .LCPI0_1@toc@l
+; CHECK-NOCOALESCE-NEXT:    lxsdx 3, 0, 3
+; CHECK-NOCOALESCE-NEXT:  .LBB0_4: # %entry
+; CHECK-NOCOALESCE-NEXT:    xsadddp 0, 1, 2
+; CHECK-NOCOALESCE-NEXT:    xsadddp 1, 0, 3
+; CHECK-NOCOALESCE-NEXT:    blr
+; CHECK-NOCOALESCE-NEXT:  .LBB0_5: # %entry
+; CHECK-NOCOALESCE-NEXT:    addis 3, 2, .LCPI0_0@toc@ha
+; CHECK-NOCOALESCE-NEXT:    addi 3, 3, .LCPI0_0@toc@l
+; CHECK-NOCOALESCE-NEXT:    lxsdx 1, 0, 3
+; CHECK-NOCOALESCE-NEXT:    beq 0, .LBB0_2
+; CHECK-NOCOALESCE-NEXT:  .LBB0_6: # %entry
+; CHECK-NOCOALESCE-NEXT:    xxlxor 2, 2, 2
+; CHECK-NOCOALESCE-NEXT:    bne 0, .LBB0_3
+; CHECK-NOCOALESCE-NEXT:    b .LBB0_4
+  entry:
+
+  %test = icmp eq i32 %x, 0
+  %tmp1 = select i1 %test, double %a, double 2.000000e-03
+  %tmp2 = select i1 %test, double %b, double 0.000000e+00
+  %tmp3 = select i1 %test, double %c, double 5.000000e-03
+
+  %res1 = fadd double %tmp1, %tmp2
+  %result = fadd double %res1, %tmp3
+  ret double %result
 }

test/CodeGen/PowerPC/select-i1-vs-i1.ll

 define ppc_fp128 @testppc_fp128eq(ppc_fp128 %c1, ppc_fp128 %c2, ppc_fp128 %c3, ppc_fp128 %c4, ppc_fp128 %a1, ppc_fp128 %a2) #0 {
 entry:
   %cmp1 = fcmp oeq ppc_fp128 %c3, %c4
   %cmp3tmp = fcmp oeq ppc_fp128 %c1, %c2
   %cmp3 = icmp eq i1 %cmp3tmp, %cmp1
   %cond = select i1 %cmp3, ppc_fp128 %a1, ppc_fp128 %a2
   ret ppc_fp128 %cond
 
-; FIXME: Because of the way that the late SELECT_* pseudo-instruction expansion
-; works, we end up with two blocks with the same predicate. These could be
-; combined.
+; The default branchCoalescing optimization merged the two identical predicate blocks 
+; that were expanded by the late SELECT_* pseudo-instruction expansion.
 
 ; CHECK-LABEL: @testppc_fp128eq
 ; CHECK-DAG: fcmpu {{[0-9]+}}, 6, 8
 ; CHECK-DAG: fcmpu {{[0-9]+}}, 5, 7
 ; CHECK-DAG: fcmpu {{[0-9]+}}, 2, 4
 ; CHECK-DAG: fcmpu {{[0-9]+}}, 1, 3
 ; CHECK: crand [[REG1:[0-9]+]], {{[0-9]+}}, {{[0-9]+}}
 ; CHECK: crand [[REG2:[0-9]+]], {{[0-9]+}}, {{[0-9]+}}
 ; CHECK: crxor [[REG3:[0-9]+]], [[REG2]], [[REG1]]
 ; CHECK: bc 12, [[REG3]], .LBB[[BB1:[0-9_]+]]
 ; CHECK: fmr 11, 9
-; CHECK: .LBB[[BB1]]:
-; CHECK: bc 12, [[REG3]], .LBB[[BB2:[0-9_]+]]
 ; CHECK: fmr 12, 10
-; CHECK: .LBB[[BB2]]:
+; CHECK: .LBB[[BB1]]:
 ; CHECK-DAG: fmr 1, 11
 ; CHECK-DAG: fmr 2, 12
 ; CHECK: blr
 }
 
 define <2 x double> @testv2doubleslt(float %c1, float %c2, float %c3, float %c4, <2 x double> %a1, <2 x double> %a2) #0 {
 entry:
   %cmp1 = fcmp oeq float %c3, %c4