contrib/llvm/lib/Target/AArch64/AArch64CondBrTuning.cpp

   1 //===-- AArch64CondBrTuning.cpp --- Conditional branch tuning for AArch64 -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 /// \file
  10 /// This file contains a pass that transforms CBZ/CBNZ/TBZ/TBNZ instructions
  11 /// into a conditional branch (B.cond), when the NZCV flags can be set for
  12 /// "free".  This is preferred on targets that have more flexibility when
  13 /// scheduling B.cond instructions as compared to CBZ/CBNZ/TBZ/TBNZ (assuming
  14 /// all other variables are equal).  This can also reduce register pressure.
  15 ///
  16 /// A few examples:
  17 ///
  18 /// 1) add w8, w0, w1  -> cmn w0, w1             ; CMN is an alias of ADDS.
  19 ///    cbz w8, .LBB_2  -> b.eq .LBB0_2
  20 ///
  21 /// 2) add w8, w0, w1  -> adds w8, w0, w1        ; w8 has multiple uses.
  22 ///    cbz w8, .LBB1_2 -> b.eq .LBB1_2
  23 ///
  24 /// 3) sub w8, w0, w1       -> subs w8, w0, w1   ; w8 has multiple uses.
  25 ///    tbz w8, #31, .LBB6_2 -> b.pl .LBB6_2
  26 ///
  27 //===----------------------------------------------------------------------===//
  28
  29 #include "AArch64.h"
  30 #include "AArch64Subtarget.h"
  31 #include "llvm/CodeGen/MachineFunction.h"
  32 #include "llvm/CodeGen/MachineFunctionPass.h"
  33 #include "llvm/CodeGen/MachineInstrBuilder.h"
  34 #include "llvm/CodeGen/MachineRegisterInfo.h"
  35 #include "llvm/CodeGen/MachineTraceMetrics.h"
  36 #include "llvm/CodeGen/Passes.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Support/raw_ostream.h"
  39 #include "llvm/Target/TargetInstrInfo.h"
  40 #include "llvm/Target/TargetRegisterInfo.h"
  41 #include "llvm/Target/TargetSubtargetInfo.h"
  42
  43 using namespace llvm;
  44
  45 #define DEBUG_TYPE "aarch64-cond-br-tuning"
  46 #define AARCH64_CONDBR_TUNING_NAME "AArch64 Conditional Branch Tuning"
  47
  48 namespace {
  49 class AArch64CondBrTuning : public MachineFunctionPass {
  50   const AArch64InstrInfo *TII;
  51   const TargetRegisterInfo *TRI;
  52
  53   MachineRegisterInfo *MRI;
  54
  55 public:
  56   static char ID;
  57   AArch64CondBrTuning() : MachineFunctionPass(ID) {
  58     initializeAArch64CondBrTuningPass(*PassRegistry::getPassRegistry());
  59   }
  60   void getAnalysisUsage(AnalysisUsage &AU) const override;
  61   bool runOnMachineFunction(MachineFunction &MF) override;
  62   StringRef getPassName() const override { return AARCH64_CONDBR_TUNING_NAME; }
  63
  64 private:
  65   MachineInstr *getOperandDef(const MachineOperand &MO);
  66   MachineInstr *convertToFlagSetting(MachineInstr &MI, bool IsFlagSetting);
  67   MachineInstr *convertToCondBr(MachineInstr &MI);
  68   bool tryToTuneBranch(MachineInstr &MI, MachineInstr &DefMI);
  69 };
  70 } // end anonymous namespace
  71
  72 char AArch64CondBrTuning::ID = 0;
  73
  74 INITIALIZE_PASS(AArch64CondBrTuning, "aarch64-cond-br-tuning",
  75                 AARCH64_CONDBR_TUNING_NAME, false, false)
  76
  77 void AArch64CondBrTuning::getAnalysisUsage(AnalysisUsage &AU) const {
  78   AU.setPreservesCFG();
  79   MachineFunctionPass::getAnalysisUsage(AU);
  80 }
  81
  82 MachineInstr *AArch64CondBrTuning::getOperandDef(const MachineOperand &MO) {
  83   if (!TargetRegisterInfo::isVirtualRegister(MO.getReg()))
  84     return nullptr;
  85   return MRI->getUniqueVRegDef(MO.getReg());
  86 }
  87
  88 MachineInstr *AArch64CondBrTuning::convertToFlagSetting(MachineInstr &MI,
  89                                                         bool IsFlagSetting) {
  90   // If this is already the flag setting version of the instruction (e.g., SUBS)
  91   // just make sure the implicit-def of NZCV isn't marked dead.
  92   if (IsFlagSetting) {
  93     for (unsigned I = MI.getNumExplicitOperands(), E = MI.getNumOperands();
  94          I != E; ++I) {
  95       MachineOperand &MO = MI.getOperand(I);
  96       if (MO.isReg() && MO.isDead() && MO.getReg() == AArch64::NZCV)
  97         MO.setIsDead(false);
  98     }
  99     return &MI;
 100   }
 101   bool Is64Bit;
 102   unsigned NewOpc = TII->convertToFlagSettingOpc(MI.getOpcode(), Is64Bit);
 103   unsigned NewDestReg = MI.getOperand(0).getReg();
 104   if (MRI->hasOneNonDBGUse(MI.getOperand(0).getReg()))
 105     NewDestReg = Is64Bit ? AArch64::XZR : AArch64::WZR;
 106
 107   MachineInstrBuilder MIB = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(),
 108                                     TII->get(NewOpc), NewDestReg);
 109   for (unsigned I = 1, E = MI.getNumOperands(); I != E; ++I)
 110     MIB.add(MI.getOperand(I));
 111
 112   return MIB;
 113 }
 114
 115 MachineInstr *AArch64CondBrTuning::convertToCondBr(MachineInstr &MI) {
 116   AArch64CC::CondCode CC;
 117   MachineBasicBlock *TargetMBB = TII->getBranchDestBlock(MI);
 118   switch (MI.getOpcode()) {
 119   default:
 120     llvm_unreachable("Unexpected opcode!");
 121
 122   case AArch64::CBZW:
 123   case AArch64::CBZX:
 124     CC = AArch64CC::EQ;
 125     break;
 126   case AArch64::CBNZW:
 127   case AArch64::CBNZX:
 128     CC = AArch64CC::NE;
 129     break;
 130   case AArch64::TBZW:
 131   case AArch64::TBZX:
 132     CC = AArch64CC::PL;
 133     break;
 134   case AArch64::TBNZW:
 135   case AArch64::TBNZX:
 136     CC = AArch64CC::MI;
 137     break;
 138   }
 139   return BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), TII->get(AArch64::Bcc))
 140       .addImm(CC)
 141       .addMBB(TargetMBB);
 142 }
 143
 144 bool AArch64CondBrTuning::tryToTuneBranch(MachineInstr &MI,
 145                                           MachineInstr &DefMI) {
 146   // We don't want NZCV bits live across blocks.
 147   if (MI.getParent() != DefMI.getParent())
 148     return false;
 149
 150   bool IsFlagSetting = true;
 151   unsigned MIOpc = MI.getOpcode();
 152   MachineInstr *NewCmp = nullptr, *NewBr = nullptr;
 153   switch (DefMI.getOpcode()) {
 154   default:
 155     return false;
 156   case AArch64::ADDWri:
 157   case AArch64::ADDWrr:
 158   case AArch64::ADDWrs:
 159   case AArch64::ADDWrx:
 160   case AArch64::ANDWri:
 161   case AArch64::ANDWrr:
 162   case AArch64::ANDWrs:
 163   case AArch64::BICWrr:
 164   case AArch64::BICWrs:
 165   case AArch64::SUBWri:
 166   case AArch64::SUBWrr:
 167   case AArch64::SUBWrs:
 168   case AArch64::SUBWrx:
 169     IsFlagSetting = false;
 170     LLVM_FALLTHROUGH;
 171   case AArch64::ADDSWri:
 172   case AArch64::ADDSWrr:
 173   case AArch64::ADDSWrs:
 174   case AArch64::ADDSWrx:
 175   case AArch64::ANDSWri:
 176   case AArch64::ANDSWrr:
 177   case AArch64::ANDSWrs:
 178   case AArch64::BICSWrr:
 179   case AArch64::BICSWrs:
 180   case AArch64::SUBSWri:
 181   case AArch64::SUBSWrr:
 182   case AArch64::SUBSWrs:
 183   case AArch64::SUBSWrx:
 184     switch (MIOpc) {
 185     default:
 186       llvm_unreachable("Unexpected opcode!");
 187
 188     case AArch64::CBZW:
 189     case AArch64::CBNZW:
 190     case AArch64::TBZW:
 191     case AArch64::TBNZW:
 192       // Check to see if the TBZ/TBNZ is checking the sign bit.
 193       if ((MIOpc == AArch64::TBZW || MIOpc == AArch64::TBNZW) &&
 194           MI.getOperand(1).getImm() != 31)
 195         return false;
 196
 197       // There must not be any instruction between DefMI and MI that clobbers or
 198       // reads NZCV.
 199       MachineBasicBlock::iterator I(DefMI), E(MI);
 200       for (I = std::next(I); I != E; ++I) {
 201         if (I->modifiesRegister(AArch64::NZCV, TRI) ||
 202             I->readsRegister(AArch64::NZCV, TRI))
 203           return false;
 204       }
 205       DEBUG(dbgs() << "  Replacing instructions:\n    ");
 206       DEBUG(DefMI.print(dbgs()));
 207       DEBUG(dbgs() << "    ");
 208       DEBUG(MI.print(dbgs()));
 209
 210       NewCmp = convertToFlagSetting(DefMI, IsFlagSetting);
 211       NewBr = convertToCondBr(MI);
 212       break;
 213     }
 214     break;
 215
 216   case AArch64::ADDXri:
 217   case AArch64::ADDXrr:
 218   case AArch64::ADDXrs:
 219   case AArch64::ADDXrx:
 220   case AArch64::ANDXri:
 221   case AArch64::ANDXrr:
 222   case AArch64::ANDXrs:
 223   case AArch64::BICXrr:
 224   case AArch64::BICXrs:
 225   case AArch64::SUBXri:
 226   case AArch64::SUBXrr:
 227   case AArch64::SUBXrs:
 228   case AArch64::SUBXrx:
 229     IsFlagSetting = false;
 230     LLVM_FALLTHROUGH;
 231   case AArch64::ADDSXri:
 232   case AArch64::ADDSXrr:
 233   case AArch64::ADDSXrs:
 234   case AArch64::ADDSXrx:
 235   case AArch64::ANDSXri:
 236   case AArch64::ANDSXrr:
 237   case AArch64::ANDSXrs:
 238   case AArch64::BICSXrr:
 239   case AArch64::BICSXrs:
 240   case AArch64::SUBSXri:
 241   case AArch64::SUBSXrr:
 242   case AArch64::SUBSXrs:
 243   case AArch64::SUBSXrx:
 244     switch (MIOpc) {
 245     default:
 246       llvm_unreachable("Unexpected opcode!");
 247
 248     case AArch64::CBZX:
 249     case AArch64::CBNZX:
 250     case AArch64::TBZX:
 251     case AArch64::TBNZX: {
 252       // Check to see if the TBZ/TBNZ is checking the sign bit.
 253       if ((MIOpc == AArch64::TBZX || MIOpc == AArch64::TBNZX) &&
 254           MI.getOperand(1).getImm() != 63)
 255         return false;
 256       // There must not be any instruction between DefMI and MI that clobbers or
 257       // reads NZCV.
 258       MachineBasicBlock::iterator I(DefMI), E(MI);
 259       for (I = std::next(I); I != E; ++I) {
 260         if (I->modifiesRegister(AArch64::NZCV, TRI) ||
 261             I->readsRegister(AArch64::NZCV, TRI))
 262           return false;
 263       }
 264       DEBUG(dbgs() << "  Replacing instructions:\n    ");
 265       DEBUG(DefMI.print(dbgs()));
 266       DEBUG(dbgs() << "    ");
 267       DEBUG(MI.print(dbgs()));
 268
 269       NewCmp = convertToFlagSetting(DefMI, IsFlagSetting);
 270       NewBr = convertToCondBr(MI);
 271       break;
 272     }
 273     }
 274     break;
 275   }
 276   (void)NewCmp; (void)NewBr;
 277   assert(NewCmp && NewBr && "Expected new instructions.");
 278
 279   DEBUG(dbgs() << "  with instruction:\n    ");
 280   DEBUG(NewCmp->print(dbgs()));
 281   DEBUG(dbgs() << "    ");
 282   DEBUG(NewBr->print(dbgs()));
 283
 284   // If this was a flag setting version of the instruction, we use the original
 285   // instruction by just clearing the dead marked on the implicit-def of NCZV.
 286   // Therefore, we should not erase this instruction.
 287   if (!IsFlagSetting)
 288     DefMI.eraseFromParent();
 289   MI.eraseFromParent();
 290   return true;
 291 }
 292
 293 bool AArch64CondBrTuning::runOnMachineFunction(MachineFunction &MF) {
 294   if (skipFunction(*MF.getFunction()))
 295     return false;
 296
 297   DEBUG(dbgs() << "********** AArch64 Conditional Branch Tuning  **********\n"
 298                << "********** Function: " << MF.getName() << '\n');
 299
 300   TII = static_cast<const AArch64InstrInfo *>(MF.getSubtarget().getInstrInfo());
 301   TRI = MF.getSubtarget().getRegisterInfo();
 302   MRI = &MF.getRegInfo();
 303
 304   bool Changed = false;
 305   for (MachineBasicBlock &MBB : MF) {
 306     bool LocalChange = false;
 307     for (MachineBasicBlock::iterator I = MBB.getFirstTerminator(),
 308                                      E = MBB.end();
 309          I != E; ++I) {
 310       MachineInstr &MI = *I;
 311       switch (MI.getOpcode()) {
 312       default:
 313         break;
 314       case AArch64::CBZW:
 315       case AArch64::CBZX:
 316       case AArch64::CBNZW:
 317       case AArch64::CBNZX:
 318       case AArch64::TBZW:
 319       case AArch64::TBZX:
 320       case AArch64::TBNZW:
 321       case AArch64::TBNZX:
 322         MachineInstr *DefMI = getOperandDef(MI.getOperand(0));
 323         LocalChange = (DefMI && tryToTuneBranch(MI, *DefMI));
 324         break;
 325       }
 326       // If the optimization was successful, we can't optimize any other
 327       // branches because doing so would clobber the NZCV flags.
 328       if (LocalChange) {
 329         Changed = true;
 330         break;
 331       }
 332     }
 333   }
 334   return Changed;
 335 }
 336
 337 FunctionPass *llvm::createAArch64CondBrTuning() {
 338   return new AArch64CondBrTuning();
 339 }