Add Branch Hints for Highly Biased Branches on PPC

[tjablin]

Summary

This branch adds hints for highly biased branches on the PPC architecture. Even in absence of profiling information, LLVM will mark code reaching unreachable terminators and other exceptional control flow constructs as highly unlikely to be reached.

[hfinkel]

Looks like PPCInstrInfo::SubsumesPredicate also needs to be updated, as does PPCInstrInfo::optimizeCompareInstr (to ignore the hinting bits).

lib/Target/PowerPC/MCTargetDesc/PPCPredicates.h

60

Use an enum for these.

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

59

These appear in a command-line -help-hidden list, and this description is uncharacteristically long. Shorten this. "Enable static hinting of branches on ppc" is fine, for example.

Feel free to include a more-verbose description in a comment.

2453

PCC |= (TWeight > FWeight) ? PPC::PRED_TAKEN_HINT : PCC |= PPC::PRED_NOT_TAKEN_HINT;

2901–2905

Should you do something here too?

lib/Target/PowerPC/PPCInstrInfo.cpp

713 ↗

(On Diff #40721)

This might be good for POWER cores, but not for the A2. At least, don't do this when targeting the A2.

[hfinkel]

Please remember to upload your patches with full context (http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface).

A few minor comments, otherwise LGTM.

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

39

Please don't make unrelated white-space changes along with functional changes.

58

Is there further testing you wish to do before enabling this by default? If not, then let's enable it.

[tjablin]

Enable by default. Remove accidental whitespace additions.

[hfinkel]

r255398

lib/Target/PowerPC/MCTargetDesc/PPCPredicates.h

enum Predicate {
     PRED_NU_PLUS  = (3 << 5) |  7,
 
     // When dealing with individual condition-register bits, we have simple set
     // and unset predicates.
     PRED_BIT_SET =   1024,
     PRED_BIT_UNSET = 1025
   };
   
+  // Bit for branch taken (plus) or not-taken (minus) hint
+  enum BranchHintBit {
+    BR_NO_HINT       = 0x0,
+    BR_NONTAKEN_HINT = 0x2,
+    BR_TAKEN_HINT    = 0x3,
+    BR_HINT_MASK     = 0X3
+  };
+
   /// Invert the specified predicate.  != -> ==, < -> >=.
   Predicate InvertPredicate(Predicate Opcode);
 
   /// Assume the condition register is set by MI(a,b), return the predicate if
   /// we modify the instructions such that condition register is set by MI(b,a).
   Predicate getSwappedPredicate(Predicate Opcode);
 }
 }
 
 #endif

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

 // converting from a legalized dag to a PPC dag.
 //
 //===----------------------------------------------------------------------===//
 
 #include "PPC.h"
 #include "MCTargetDesc/PPCPredicates.h"
 #include "PPCMachineFunctionInfo.h"
 #include "PPCTargetMachine.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/CodeGen/FunctionLoweringInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SelectionDAGISel.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetOptions.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "ppc-codegen"
 
 // FIXME: Remove this once the bug has been fixed!
 cl::opt<bool> ANDIGlueBug("expose-ppc-andi-glue-bug",
 cl::desc("expose the ANDI glue bug on PPC"), cl::Hidden);
 
 static cl::opt<bool>
     UseBitPermRewriter("ppc-use-bit-perm-rewriter", cl::init(true),
                        cl::desc("use aggressive ppc isel for bit permutations"),
                        cl::Hidden);
 static cl::opt<bool> BPermRewriterNoMasking(
     "ppc-bit-perm-rewriter-stress-rotates",
     cl::desc("stress rotate selection in aggressive ppc isel for "
              "bit permutations"),
     cl::Hidden);
 
+static cl::opt<bool> EnableBranchHint(
+  "ppc-use-branch-hint", cl::init(true),
+    cl::desc("Enable static hinting of branches on ppc"),
+    cl::Hidden);
+
 namespace llvm {
   void initializePPCDAGToDAGISelPass(PassRegistry&);
 }
 
 namespace {
   //===--------------------------------------------------------------------===//
   /// PPCDAGToDAGISel - PPC specific code to select PPC machine
   /// instructions for SelectionDAG operations.

 }
 
 // isInt32Immediate - This method tests to see if a constant operand.
 // If so Imm will receive the 32 bit value.
 static bool isInt32Immediate(SDValue N, unsigned &Imm) {
   return isInt32Immediate(N.getNode(), Imm);
 }
 
+static unsigned getBranchHint(unsigned PCC, FunctionLoweringInfo *FuncInfo,
+                              const SDValue &DestMBB) {
+  assert(isa<BasicBlockSDNode>(DestMBB));
+
+  if (!FuncInfo->BPI) return PPC::BR_NO_HINT;
+
+  const BasicBlock *BB = FuncInfo->MBB->getBasicBlock();
+  const TerminatorInst *BBTerm = BB->getTerminator();
+
+  if (BBTerm->getNumSuccessors() != 2) return PPC::BR_NO_HINT;
+
+  const BasicBlock *TBB = BBTerm->getSuccessor(0);
+  const BasicBlock *FBB = BBTerm->getSuccessor(1);
+
+  uint32_t TWeight = FuncInfo->BPI->getEdgeWeight(BB, TBB);
+  uint32_t FWeight = FuncInfo->BPI->getEdgeWeight(BB, FBB);
+
+  // We only want to handle cases which are easy to predict at static time, e.g.
+  // C++ throw statement, that is very likely not taken, or calling never
+  // returned function, e.g. stdlib exit(). So we set Threshold to filter
+  // unwanted cases.
+  //
+  // Below is LLVM branch weight table, we only want to handle case 1, 2
+  //
+  // Case                  Taken:Nontaken  Example
+  // 1. Unreachable        1048575:1       C++ throw, stdlib exit(),
+  // 2. Invoke-terminating 1:1048575
+  // 3. Coldblock          4:64            __builtin_expect
+  // 4. Loop Branch        124:4           For loop
+  // 5. PH/ZH/FPH          20:12
+  const uint32_t Threshold = 10000;
+
+  // Minimal weight should be at least 1
+  if (std::max(TWeight, FWeight) /
+      std::max(1u, std::min(TWeight, FWeight)) < Threshold)
+    return PPC::BR_NO_HINT;
+
+  DEBUG(dbgs() << "Use branch hint for '" << FuncInfo->Fn->getName() << "::"
+               << BB->getName() << "'\n"
+               << " -> " << TBB->getName() << ": " << TWeight << "\n"
+               << " -> " << FBB->getName() << ": " << FWeight << "\n");
+
+  const BasicBlockSDNode *BBDN = cast<BasicBlockSDNode>(DestMBB);
+
+  // If Dest BasicBlock is False-BasicBlock (FBB), swap branch weight,
+  // because we want 'TWeight' stands for 'branch weight' to Dest BasicBlock
+  if (BBDN->getBasicBlock()->getBasicBlock() != TBB)
+    std::swap(TWeight, FWeight);
+
+  return (TWeight > FWeight) ? PPC::BR_TAKEN_HINT : PPC::BR_NONTAKEN_HINT;
+}
 
 // isOpcWithIntImmediate - This method tests to see if the node is a specific
 // opcode and that it has a immediate integer right operand.
 // If so Imm will receive the 32 bit value.
 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
   return N->getOpcode() == Opc
          && isInt32Immediate(N->getOperand(1).getNode(), Imm);
 }
case ISD::SETCC: {
     if (SN)
       return SN;
     break;
   }
   case PPCISD::GlobalBaseReg:
     return getGlobalBaseReg();
 
   case ISD::FrameIndex:
     return getFrameIndex(N, N);
 
   case PPCISD::MFOCRF: {
     SDValue InFlag = N->getOperand(1);
     return CurDAG->getMachineNode(PPC::MFOCRF, dl, MVT::i32,
                                   N->getOperand(0), InFlag);
   }
 
   case PPCISD::READ_TIME_BASE: {
SDNode *PPCDAGToDAGISel::Select(SDNode *N) {
   }
   case PPCISD::COND_BRANCH: {
     // Op #0 is the Chain.
     // Op #1 is the PPC::PRED_* number.
     // Op #2 is the CR#
     // Op #3 is the Dest MBB
     // Op #4 is the Flag.
     // Prevent PPC::PRED_* from being selected into LI.
-    SDValue Pred =
-      getI32Imm(cast<ConstantSDNode>(N->getOperand(1))->getZExtValue(), dl);
+    unsigned PCC = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
+    if (EnableBranchHint)
+      PCC |= getBranchHint(PCC, FuncInfo, N->getOperand(3));
+
+    SDValue Pred = getI32Imm(PCC, dl);
     SDValue Ops[] = { Pred, N->getOperand(2), N->getOperand(3),
       N->getOperand(0), N->getOperand(4) };
     return CurDAG->SelectNodeTo(N, PPC::BCC, MVT::Other, Ops);
   }
   case ISD::BR_CC: {
     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
     unsigned PCC = getPredicateForSetCC(CC);
 
if (N->getOperand(2).getValueType() == MVT::i1) {
 
       SDValue BitComp(CurDAG->getMachineNode(Opc, dl, MVT::i1,
                                              N->getOperand(Swap ? 3 : 2),
                                              N->getOperand(Swap ? 2 : 3)), 0);
       return CurDAG->SelectNodeTo(N, PPC::BC, MVT::Other,
                                   BitComp, N->getOperand(4), N->getOperand(0));
     }
 
+    if (EnableBranchHint)
+      PCC |= getBranchHint(PCC, FuncInfo, N->getOperand(4));
+
     SDValue CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC, dl);
     SDValue Ops[] = { getI32Imm(PCC, dl), CondCode,
                         N->getOperand(4), N->getOperand(0) };
     return CurDAG->SelectNodeTo(N, PPC::BCC, MVT::Other, Ops);
   }
   case ISD::BRIND: {
     // FIXME: Should custom lower this.
     SDValue Chain = N->getOperand(0);

test/CodeGen/PowerPC/branch-hint.ll

+; RUN: llc < %s -O1 -verify-machineinstrs -mtriple=powerpc64-unknown-linux-gnu -ppc-use-branch-hint=false | FileCheck %s
+; RUN: llc < %s -O1 -verify-machineinstrs -mtriple=powerpc64-unknown-linux-gnu -ppc-use-branch-hint=true | FileCheck %s -check-prefix=CHECK-HINT
+define void @branch_hint_1(i32 %src) {
+entry:
+  %cmp = icmp eq i32 %src, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  tail call void @foo() #0
+  unreachable
+
+if.end:
+  call void @goo()
+  ret void
+
+; CHECK-LABEL: branch_hint_1:
+; CHECK: beq
+
+; CHECK-HINT-LABEL: branch_hint_1:
+; CHECK-HINT: beq-
+}
+
+define void @branch_hint_2(i32 %src) {
+entry:
+  %cmp = icmp eq i32 %src, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  call void @goo()
+  ret void
+
+if.end:
+  tail call void @foo() #0
+  unreachable
+
+; CHECK-LABEL: @branch_hint_2
+; CHECK: bne
+
+; CHECK-HINT-LABEL: @branch_hint_2
+; CHECK-HINT: bne-
+}
+
+declare void @foo()
+attributes #0 = { noreturn }
+
+define void @branch_hint_3(i32 %src) {
+entry:
+  %cmp = icmp eq i32 %src, 0
+  br i1 %cmp, label %if.then, label %if.end, !prof !0
+
+if.then:
+  call void @foo()
+  ret void
+
+if.end:
+  call void @goo()
+  ret void
+
+; CHECK-LABEL: @branch_hint_3
+; CHECK: bne
+
+; CHECK-HINT-LABEL: @branch_hint_3
+; CHECK-HINT: bne
+}
+
+!0 = !{!"branch_weights", i32 64, i32 4}
+
+define void @branch_hint_4(i32 %src) {
+entry:
+  %cmp = icmp eq i32 %src, 0
+  br i1 %cmp, label %if.then, label %if.end, !prof !1
+
+if.then:
+  call void @foo()
+  ret void
+
+if.end:
+  call void @goo()
+  ret void
+
+; CHECK-HINT-LABEL: branch_hint_4
+; CHECK-HINT: bne
+}
+
+!1 = !{!"branch_weights", i32 64, i32 8}
+
+define void @branch_hint_5(i32 %src) {
+entry:
+  %cmp = icmp eq i32 %src, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  ret void
+
+if.end:
+  call void @goo()
+  ret void
+
+; CHECK-HINT-LABEL: branch_hint_5:
+; CHECK-HINT: beq
+}
+
+declare void @goo()
+
+define void @branch_hint_6(i32 %src1, i32 %src2, i32 %src3) {
+entry:
+  %cmp = icmp eq i32 %src1, 0
+  br i1 %cmp, label %if.end.6, label %if.end, !prof !3
+
+if.end:
+  %cmp1 = icmp eq i32 %src2, 0
+  br i1 %cmp1, label %if.end.3, label %if.then.2
+
+if.then.2:
+  tail call void @foo() #0
+  unreachable
+
+if.end.3:
+  %cmp4 = icmp eq i32 %src3, 1
+  br i1 %cmp4, label %if.then.5, label %if.end.6
+
+if.then.5:
+  tail call void @foo() #0
+  unreachable
+
+if.end.6:
+  ret void
+
+; CHECK-HINT-LABEL: branch_hint_6:
+; CHECK-HINT: bne
+; CHECK-HINT: bne-
+; CHECK-HINT: bne+
+}
+
+!3 = !{!"branch_weights", i32 64, i32 4}