[TargetInstrInfo] Add TargetInstrInfo interface isProfitableToBranch.

[bmakam]

Summary

Add TargetInstrInfo::isProfitableToBranch and implement for AArch64. This
implements heuristics to determine if it is profitable to branch from a
dominating head block that is terminated by the conditional branch into the compare
block that contains the compare instruction and the conditional branch.
AArch64ConditionalCompares pass uses this heuristics to decide on merging the compare
block into the head block. The heuristics are only enabled for Kryo subtarget.
NFC for subtargets other than Kryo.

[jmolloy]

Hi,

Sorry for how long it's taken - I only just saw this on my phab list.

I think this generally looks fine, but I don't see the need for isProfitableToBranch to be in TargetInstrInfo. You can simply put it in AArch64InstrInfo and query that directly in AArch64ConditionalCompares (much like is done in AArch64LdStOptimizer).

Cheers,

James

[bmakam]

Moved to a more general solution in D20030

include/llvm/Target/TargetInstrInfo.h

public:
   ///   addne  r0, r1, #1
   ///
   /// This may be profitable is conditional instructions are always executed.
   virtual bool isProfitableToUnpredicate(MachineBasicBlock &TMBB,
                                          MachineBasicBlock &FMBB) const {
     return false;
   }
 
+  /// Return true if it's profitable to branch from head block specified by MBB
+  /// that dominates the TBB.
+  ///
+  ///    e.g:          MBB
+  ///                 / |
+  ///                /  |
+  ///               |  TBB
+  ///               |  / |
+  ///               | /  |
+  ///              Tail  |
+  ///                |   |
+  ///               ... ...
+  ///
+  /// The Head block is terminated by a br.cond instruction, and the TBB block
+  /// contains compare + br.cond. Tail must be a successor of both.
+  /// @param MBB         Head block terminated by br.cond instruction.
+  /// @param TBB         Contains the compare instruction and br.cond
+  /// @param CmpMI       MI compare instruction in TBB to analyze.
+  /// @param CmpBBDepth  Instruction depths for all trace instructions above TBB
+  /// @param HeadDepth   Instruction depths for all trace instructions above MBB
+  /// @param Penalty     Branch misprediction penalty
+  /// @param Probability Probability of path taken from head block MBB to TBB.
+  virtual bool isProfitableToBranch(MachineBasicBlock *MBB,
+                                    MachineBasicBlock *TBB, MachineInstr *CmpMI,
+                                    unsigned CmpBBDepth, unsigned HeadDepth,
+                                    unsigned Penalty,
+                                    BranchProbability Probability) const {
+    return false;
+  }
+
   /// Return true if it is possible to insert a select
   /// instruction that chooses between TrueReg and FalseReg based on the
   /// condition code in Cond.
   ///
   /// When successful, also return the latency in cycles from TrueReg,
   /// FalseReg, and Cond to the destination register. In most cases, a select
   /// instruction will be 1 cycle, so CondCycles = TrueCycles = FalseCycles = 1
   ///

lib/Target/AArch64/AArch64ConditionalCompares.cpp

 //===----------------------------------------------------------------------===//
 //                       AArch64ConditionalCompares Pass
 //===----------------------------------------------------------------------===//
 
 namespace {
 class AArch64ConditionalCompares : public MachineFunctionPass {
   const TargetInstrInfo *TII;
   const TargetRegisterInfo *TRI;
+  const MachineBranchProbabilityInfo *MBPI;
   MCSchedModel SchedModel;
   // Does the proceeded function has Oz attribute.
   bool MinSize;
   MachineRegisterInfo *MRI;
   MachineDominatorTree *DomTree;
   MachineLoopInfo *Loops;
   MachineTraceMetrics *Traces;
   MachineTraceMetrics::Ensemble *MinInstr;
bool AArch64ConditionalCompares::shouldConvert() {
 
   // Instruction depths can be computed for all trace instructions above CmpBB.
   unsigned HeadDepth =
       Trace.getInstrCycles(*CmpConv.Head->getFirstTerminator()).Depth;
   unsigned CmpBBDepth =
       Trace.getInstrCycles(*CmpConv.CmpBB->getFirstTerminator()).Depth;
   DEBUG(dbgs() << "Head depth:  " << HeadDepth
                << "\nCmpBB depth: " << CmpBBDepth << '\n');
+  BranchProbability Prediction =
+      MBPI->getEdgeProbability(CmpConv.Head, CmpConv.CmpBB);
+  if (TII->isProfitableToBranch(CmpConv.Head, CmpConv.CmpBB, CmpConv.CmpMI,
+                                CmpBBDepth, HeadDepth,
+                                SchedModel.MispredictPenalty, Prediction)) {
+    DEBUG(dbgs() << "Branch is profitable than predication.\n");
+    return false;
+  }
   if (CmpBBDepth > HeadDepth + DelayLimit) {
     DEBUG(dbgs() << "Branch delay would be larger than " << DelayLimit
                  << " cycles.\n");
     return false;
   }
 
   // Check the resource depth at the bottom of CmpBB - these instructions will
   // be speculated.
bool AArch64ConditionalCompares::tryConvert(MachineBasicBlock *MBB) {
   return Changed;
 }
 
 bool AArch64ConditionalCompares::runOnMachineFunction(MachineFunction &MF) {
   DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n"
                << "********** Function: " << MF.getName() << '\n');
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
+  MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
   SchedModel = MF.getSubtarget().getSchedModel();
   MRI = &MF.getRegInfo();
   DomTree = &getAnalysis<MachineDominatorTree>();
   Loops = getAnalysisIfAvailable<MachineLoopInfo>();
   Traces = &getAnalysis<MachineTraceMetrics>();
   MinInstr = nullptr;
   MinSize = MF.getFunction()->optForMinSize();
 

lib/Target/AArch64/AArch64InstrInfo.h

void genAlternativeCodeSequence(
       SmallVectorImpl<MachineInstr *> &InsInstrs,
       SmallVectorImpl<MachineInstr *> &DelInstrs,
       DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const override;
   /// useMachineCombiner - AArch64 supports MachineCombiner
   bool useMachineCombiner() const override;
 
   bool expandPostRAPseudo(MachineBasicBlock::iterator MI) const override;
 
+  bool isProfitableToBranch(MachineBasicBlock *MBB, MachineBasicBlock *TBB,
+                            MachineInstr *CmpMI, unsigned CmpBBDepth,
+                            unsigned HeadDepth, unsigned Penalty,
+                            BranchProbability Probability) const override;
+
   std::pair<unsigned, unsigned>
   decomposeMachineOperandsTargetFlags(unsigned TF) const override;
   ArrayRef<std::pair<unsigned, const char *>>
   getSerializableDirectMachineOperandTargetFlags() const override;
   ArrayRef<std::pair<unsigned, const char *>>
   getSerializableBitmaskMachineOperandTargetFlags() const override;
 
 private:

lib/Target/AArch64/AArch64InstrInfo.cpp

 #include "AArch64Subtarget.h"
 #include "MCTargetDesc/AArch64AddressingModes.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
 #include "llvm/MC/MCInst.h"
+#include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/TargetRegistry.h"
 
 using namespace llvm;
 
 #define GET_INSTRINFO_CTOR_DTOR
 #include "AArch64GenInstrInfo.inc"
 
AArch64InstrInfo::getSerializableBitmaskMachineOperandTargetFlags() const {
   using namespace AArch64II;
   static const std::pair<unsigned, const char *> TargetFlags[] = {
       {MO_GOT, "aarch64-got"},
       {MO_NC, "aarch64-nc"},
       {MO_TLS, "aarch64-tls"},
       {MO_CONSTPOOL, "aarch64-constant-pool"}};
   return makeArrayRef(TargetFlags);
 }
+
+bool AArch64InstrInfo::isProfitableToBranch(
+    MachineBasicBlock *MBB, MachineBasicBlock *TBB, MachineInstr *CmpMI,
+    unsigned CmpBBDepth, unsigned HeadDepth, unsigned BranchMissPenalty,
+    BranchProbability Probability) const {
+  // Branching is profitable on Kryo subtarget particularly when the branch is
+  // easily predictable. Only run this for Kryo subtarget.
+  if (!Subtarget.isKryo())
+    return false;
+
+  // Heuristic: It is not profitable if the branch is hard to predict.
+  // Set a limit on the branch probability we will accept.
+  unsigned ScalingFactor = 100;
+  unsigned BranchCost = Probability.scale(ScalingFactor);
+  if (BranchCost < 75)
+    return false;
+
+  // Heuristic: If the compare instruction is a ZBranch then
+  // branching can pessimize by replacing a ccmp with cbz/nz.
+  switch (CmpMI->getOpcode()) {
+  default:
+    break;
+  case AArch64::CBZW:
+  case AArch64::CBZX:
+  case AArch64::CBNZW:
+  case AArch64::CBNZX:
+    return false;
+  }
+
+  // Heuristic: If the dominating head block contains hazardous
+  // instructions, the actual latency is variable.
+  // Instructions that read the PC such as ADRP, ADR and load-literal can affect
+  // direct branches, so it might be cheaper to speculate.
+  unsigned HazardCost = 0;
+  unsigned CondCost = 0;
+  int FI = INT_MIN;
+  for (auto &MI : *MBB) {
+    if (isLoadFromStackSlot(&MI, FI)) {
+      ++HazardCost;
+    } else {
+      switch (MI.getOpcode()) {
+      default:
+        break;
+      case AArch64::CBZW:
+      case AArch64::CBZX:
+      case AArch64::CBNZW:
+      case AArch64::CBNZX:
+      case AArch64::FDIVSrr:
+      case AArch64::FDIVDrr:
+      case AArch64::FSQRTSr:
+      case AArch64::FSQRTDr:
+      case AArch64::SDIVWr:
+      case AArch64::SDIVXr:
+      case AArch64::UDIVWr:
+      case AArch64::UDIVXr:
+      case AArch64::ADRP:
+      case AArch64::ADR:
+      case AArch64::LDRSWui:
+      case AArch64::MOVaddr:
+      case AArch64::MOVaddrJT:
+      case AArch64::MOVaddrCP:
+      case AArch64::MOVaddrBA:
+      case AArch64::MOVaddrTLS:
+      case AArch64::MOVaddrEXT:
+        ++HazardCost;
+        break;
+      case AArch64::CSINVWr:
+      case AArch64::CSINVXr:
+      case AArch64::CSINCWr:
+      case AArch64::CSINCXr:
+      case AArch64::CSELWr:
+      case AArch64::CSELXr:
+      case AArch64::CSNEGWr:
+      case AArch64::CSNEGXr:
+      case AArch64::FCSELSrrr:
+      case AArch64::FCSELDrrr:
+        ++CondCost;
+        break;
+      }
+    }
+  }
+  if (HazardCost > CondCost)
+    return false;
+
+  // Heuristic: The compare conversion delays the execution of the branch
+  // instruction because we must wait for the inputs to the second compare as
+  // well. The branch has no dependent instructions, but delaying it increases
+  // the cost of a misprediction.
+  //
+  // Using branch probability set a limit on the delay we will accept.
+  unsigned DelayLimit = Probability.scale(BranchMissPenalty) / 2;
+  if (CmpBBDepth > HeadDepth + DelayLimit)
+    return true;
+  return false;
+}

test/CodeGen/AArch64/aarch64-branch-heuristics.ll

+; RUN: llc < %s -mcpu=kryo -verify-machineinstrs -aarch64-ccmp | FileCheck %s
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnu"
+
+%struct.arc = type { i64, %struct.node*, %struct.node*, i32, %struct.arc*, %struct.arc*, i64, i64 }
+%struct.node = type { i64, i32, %struct.node*, %struct.node*, %struct.node*, %struct.node*, %struct.arc*, %struct.arc*, %struct.arc*, %struct.arc*, i64, i64, i32, i32 }
+%struct.basket = type { %struct.arc*, i64, i64 }
+
+; CHECK: primal_bea_mpp
+; CHECK: %if.then34
+; CHECK: cmp x{{[0-9]+}}, #1
+; CHECK-NEXT: b.ge
+; CHECK: %if.then34.if.else.exit
+; CHECK: cmp w{{[0-9]+}}, #2
+; CHECK-NEXT: b.ne
+; CHECK-NEXT-NOT: ccmp
+; Function Attrs: nounwind
+define void @primal_bea_mpp() #0 {
+entry:
+  br label %for.body
+
+for.body:                                       ; preds = %for.inc, %entry
+  %arc = phi %struct.arc* [ %add.ptr60, %for.inc ], [ undef, %entry ]
+  %ident32 = getelementptr inbounds %struct.arc, %struct.arc* %arc, i64 0, i32 3
+  %ident32.load = load i32, i32* %ident32, align 8
+  %cmp33 = icmp sgt i32 %ident32.load, 0
+  br i1 %cmp33, label %if.then34, label %for.inc
+
+if.then34:                                        ; preds = %for.body
+  %cost35 = getelementptr inbounds %struct.arc, %struct.arc* %arc, i64 0, i32 0
+  %0 = load i64, i64* %cost35, align 8
+  %tail36 = getelementptr inbounds %struct.arc, %struct.arc* %arc, i64 0, i32 1
+  %1 = load %struct.node*, %struct.node** %tail36, align 8
+  %potential37 = getelementptr inbounds %struct.node, %struct.node* %1, i64 0, i32 0
+  %2 = load i64, i64* %potential37, align 8
+  %sub38 = sub nsw i64 %0, %2
+  %head39 = getelementptr inbounds %struct.arc, %struct.arc* %arc, i64 0, i32 2
+  %3= load %struct.node*, %struct.node** %head39, align 8
+  %potential40 = getelementptr inbounds %struct.node, %struct.node* %3, i64 0, i32 0
+  %4 = load i64, i64* %potential40, align 8
+  %add41 = add nsw i64 %4, %sub38
+  %cmp.i = icmp sgt i64 %add41, 0
+  br i1 %cmp.i, label %land.lhs.true.i, label %if.then34.if.else.exit
+
+land.lhs.true.i:                                  ; preds = %if.then34
+  %cmp1.i = icmp eq i32 %ident32.load, 1
+  br i1 %cmp1.i, label %if.then43, label %for.inc
+
+if.then34.if.else.exit:                      ; preds = %if.then34
+  %cmp2.i = icmp sgt i64 %add41, 0
+  %cmp4.i = icmp eq i32 %ident32.load, 2
+  %cmp4.i. = and i1 %cmp4.i, %cmp2.i
+  br i1 %cmp4.i., label %if.then43, label %for.inc
+
+if.then43:                                        ; preds = %if.then34
+  %abs_cost56 = getelementptr inbounds %struct.basket, %struct.basket* undef, i64 0, i32 2
+  br label %for.inc
+
+for.inc:                                        ; preds = %if.then43, %if.then34, %for.body
+  %add.ptr60 = getelementptr inbounds %struct.arc, %struct.arc* %arc, i64 undef
+  br label %for.body
+}