1327952Sdim//===- HexagonNewValueJump.cpp - Hexagon Backend New Value Jump -----------===// 2239310Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6239310Sdim// 7239310Sdim//===----------------------------------------------------------------------===// 8239310Sdim// 9239310Sdim// This implements NewValueJump pass in Hexagon. 10239310Sdim// Ideally, we should merge this as a Peephole pass prior to register 11239310Sdim// allocation, but because we have a spill in between the feeder and new value 12239310Sdim// jump instructions, we are forced to write after register allocation. 13239310Sdim// Having said that, we should re-attempt to pull this earlier at some point 14239310Sdim// in future. 15239310Sdim 16239310Sdim// The basic approach looks for sequence of predicated jump, compare instruciton 17239310Sdim// that genereates the predicate and, the feeder to the predicate. Once it finds 18341825Sdim// all, it collapses compare and jump instruction into a new value jump 19239310Sdim// intstructions. 20239310Sdim// 21239310Sdim//===----------------------------------------------------------------------===// 22327952Sdim 23360784Sdim#include "llvm/InitializePasses.h" 24276479Sdim#include "Hexagon.h" 25276479Sdim#include "HexagonInstrInfo.h" 26276479Sdim#include "HexagonRegisterInfo.h" 27341825Sdim#include "HexagonSubtarget.h" 28239310Sdim#include "llvm/ADT/Statistic.h" 29327952Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 30327952Sdim#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 31327952Sdim#include "llvm/CodeGen/MachineFunction.h" 32276479Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 33327952Sdim#include "llvm/CodeGen/MachineInstr.h" 34276479Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 35327952Sdim#include "llvm/CodeGen/MachineOperand.h" 36276479Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 37327952Sdim#include "llvm/CodeGen/TargetOpcodes.h" 38327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 39327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 40327952Sdim#include "llvm/IR/DebugLoc.h" 41327952Sdim#include "llvm/MC/MCInstrDesc.h" 42327952Sdim#include "llvm/Pass.h" 43327952Sdim#include "llvm/Support/BranchProbability.h" 44276479Sdim#include "llvm/Support/CommandLine.h" 45276479Sdim#include "llvm/Support/Debug.h" 46327952Sdim#include "llvm/Support/ErrorHandling.h" 47327952Sdim#include "llvm/Support/MathExtras.h" 48288943Sdim#include "llvm/Support/raw_ostream.h" 49327952Sdim#include <cassert> 50327952Sdim#include <cstdint> 51327952Sdim#include <iterator> 52327952Sdim 53239310Sdimusing namespace llvm; 54239310Sdim 55276479Sdim#define DEBUG_TYPE "hexagon-nvj" 56276479Sdim 57239310SdimSTATISTIC(NumNVJGenerated, "Number of New Value Jump Instructions created"); 58239310Sdim 59327952Sdimstatic cl::opt<int> DbgNVJCount("nvj-count", cl::init(-1), cl::Hidden, 60327952Sdim cl::desc("Maximum number of predicated jumps to be converted to " 61327952Sdim "New Value Jump")); 62239310Sdim 63239310Sdimstatic cl::opt<bool> DisableNewValueJumps("disable-nvjump", cl::Hidden, 64239310Sdim cl::ZeroOrMore, cl::init(false), 65239310Sdim cl::desc("Disable New Value Jumps")); 66239310Sdim 67251662Sdimnamespace llvm { 68251662Sdim 69327952SdimFunctionPass *createHexagonNewValueJump(); 70327952Sdimvoid initializeHexagonNewValueJumpPass(PassRegistry&); 71251662Sdim 72327952Sdim} // end namespace llvm 73327952Sdim 74239310Sdimnamespace { 75327952Sdim 76239310Sdim struct HexagonNewValueJump : public MachineFunctionPass { 77239310Sdim static char ID; 78239310Sdim 79321369Sdim HexagonNewValueJump() : MachineFunctionPass(ID) {} 80239310Sdim 81276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 82251662Sdim AU.addRequired<MachineBranchProbabilityInfo>(); 83239310Sdim MachineFunctionPass::getAnalysisUsage(AU); 84239310Sdim } 85239310Sdim 86314564Sdim StringRef getPassName() const override { return "Hexagon NewValueJump"; } 87239310Sdim 88276479Sdim bool runOnMachineFunction(MachineFunction &Fn) override; 89327952Sdim 90309124Sdim MachineFunctionProperties getRequiredProperties() const override { 91309124Sdim return MachineFunctionProperties().set( 92314564Sdim MachineFunctionProperties::Property::NoVRegs); 93309124Sdim } 94239310Sdim 95239310Sdim private: 96327952Sdim const HexagonInstrInfo *QII; 97327952Sdim const HexagonRegisterInfo *QRI; 98327952Sdim 99341825Sdim /// A handle to the branch probability pass. 100251662Sdim const MachineBranchProbabilityInfo *MBPI; 101239310Sdim 102309124Sdim bool isNewValueJumpCandidate(const MachineInstr &MI) const; 103239310Sdim }; 104239310Sdim 105327952Sdim} // end anonymous namespace 106239310Sdim 107239310Sdimchar HexagonNewValueJump::ID = 0; 108239310Sdim 109251662SdimINITIALIZE_PASS_BEGIN(HexagonNewValueJump, "hexagon-nvj", 110251662Sdim "Hexagon NewValueJump", false, false) 111251662SdimINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 112251662SdimINITIALIZE_PASS_END(HexagonNewValueJump, "hexagon-nvj", 113251662Sdim "Hexagon NewValueJump", false, false) 114251662Sdim 115239310Sdim// We have identified this II could be feeder to NVJ, 116239310Sdim// verify that it can be. 117239310Sdimstatic bool canBeFeederToNewValueJump(const HexagonInstrInfo *QII, 118239310Sdim const TargetRegisterInfo *TRI, 119239310Sdim MachineBasicBlock::iterator II, 120239310Sdim MachineBasicBlock::iterator end, 121239310Sdim MachineBasicBlock::iterator skip, 122239310Sdim MachineFunction &MF) { 123239310Sdim // Predicated instruction can not be feeder to NVJ. 124309124Sdim if (QII->isPredicated(*II)) 125239310Sdim return false; 126239310Sdim 127239310Sdim // Bail out if feederReg is a paired register (double regs in 128239310Sdim // our case). One would think that we can check to see if a given 129239310Sdim // register cmpReg1 or cmpReg2 is a sub register of feederReg 130239310Sdim // using -- if (QRI->isSubRegister(feederReg, cmpReg1) logic 131239310Sdim // before the callsite of this function 132239310Sdim // But we can not as it comes in the following fashion. 133327952Sdim // %d0 = Hexagon_S2_lsr_r_p killed %d0, killed %r2 134327952Sdim // %r0 = KILL %r0, implicit killed %d0 135327952Sdim // %p0 = CMPEQri killed %r0, 0 136239310Sdim // Hence, we need to check if it's a KILL instruction. 137239310Sdim if (II->getOpcode() == TargetOpcode::KILL) 138239310Sdim return false; 139239310Sdim 140321369Sdim if (II->isImplicitDef()) 141321369Sdim return false; 142239310Sdim 143327952Sdim if (QII->isSolo(*II)) 144327952Sdim return false; 145327952Sdim 146341825Sdim if (QII->isFloat(*II)) 147341825Sdim return false; 148341825Sdim 149341825Sdim // Make sure that the (unique) def operand is a register from IntRegs. 150341825Sdim bool HadDef = false; 151341825Sdim for (const MachineOperand &Op : II->operands()) { 152341825Sdim if (!Op.isReg() || !Op.isDef()) 153341825Sdim continue; 154341825Sdim if (HadDef) 155341825Sdim return false; 156341825Sdim HadDef = true; 157341825Sdim if (!Hexagon::IntRegsRegClass.contains(Op.getReg())) 158341825Sdim return false; 159341825Sdim } 160341825Sdim assert(HadDef); 161341825Sdim 162341825Sdim // Make sure there is no 'def' or 'use' of any of the uses of 163341825Sdim // feeder insn between its definition, this MI and jump, jmpInst 164239310Sdim // skipping compare, cmpInst. 165239310Sdim // Here's the example. 166239310Sdim // r21=memub(r22+r24<<#0) 167239310Sdim // p0 = cmp.eq(r21, #0) 168239310Sdim // r4=memub(r3+r21<<#0) 169239310Sdim // if (p0.new) jump:t .LBB29_45 170239310Sdim // Without this check, it will be converted into 171239310Sdim // r4=memub(r3+r21<<#0) 172239310Sdim // r21=memub(r22+r24<<#0) 173239310Sdim // p0 = cmp.eq(r21, #0) 174239310Sdim // if (p0.new) jump:t .LBB29_45 175239310Sdim // and result WAR hazards if converted to New Value Jump. 176239310Sdim for (unsigned i = 0; i < II->getNumOperands(); ++i) { 177239310Sdim if (II->getOperand(i).isReg() && 178239310Sdim (II->getOperand(i).isUse() || II->getOperand(i).isDef())) { 179239310Sdim MachineBasicBlock::iterator localII = II; 180239310Sdim ++localII; 181360784Sdim Register Reg = II->getOperand(i).getReg(); 182327952Sdim for (MachineBasicBlock::iterator localBegin = localII; localBegin != end; 183327952Sdim ++localBegin) { 184327952Sdim if (localBegin == skip) 185327952Sdim continue; 186239310Sdim // Check for Subregisters too. 187239310Sdim if (localBegin->modifiesRegister(Reg, TRI) || 188239310Sdim localBegin->readsRegister(Reg, TRI)) 189239310Sdim return false; 190239310Sdim } 191239310Sdim } 192239310Sdim } 193239310Sdim return true; 194239310Sdim} 195239310Sdim 196239310Sdim// These are the common checks that need to performed 197239310Sdim// to determine if 198239310Sdim// 1. compare instruction can be moved before jump. 199239310Sdim// 2. feeder to the compare instruction can be moved before jump. 200239310Sdimstatic bool commonChecksToProhibitNewValueJump(bool afterRA, 201239310Sdim MachineBasicBlock::iterator MII) { 202239310Sdim // If store in path, bail out. 203327952Sdim if (MII->mayStore()) 204239310Sdim return false; 205239310Sdim 206239310Sdim // if call in path, bail out. 207314564Sdim if (MII->isCall()) 208239310Sdim return false; 209239310Sdim 210239310Sdim // if NVJ is running prior to RA, do the following checks. 211239310Sdim if (!afterRA) { 212239310Sdim // The following Target Opcode instructions are spurious 213239310Sdim // to new value jump. If they are in the path, bail out. 214239310Sdim // KILL sets kill flag on the opcode. It also sets up a 215239310Sdim // single register, out of pair. 216327952Sdim // %d0 = S2_lsr_r_p killed %d0, killed %r2 217327952Sdim // %r0 = KILL %r0, implicit killed %d0 218327952Sdim // %p0 = C2_cmpeqi killed %r0, 0 219239310Sdim // PHI can be anything after RA. 220239310Sdim // COPY can remateriaze things in between feeder, compare and nvj. 221239310Sdim if (MII->getOpcode() == TargetOpcode::KILL || 222327952Sdim MII->getOpcode() == TargetOpcode::PHI || 223239310Sdim MII->getOpcode() == TargetOpcode::COPY) 224239310Sdim return false; 225239310Sdim 226239310Sdim // The following pseudo Hexagon instructions sets "use" and "def" 227239310Sdim // of registers by individual passes in the backend. At this time, 228239310Sdim // we don't know the scope of usage and definitions of these 229239310Sdim // instructions. 230314564Sdim if (MII->getOpcode() == Hexagon::LDriw_pred || 231239310Sdim MII->getOpcode() == Hexagon::STriw_pred) 232239310Sdim return false; 233239310Sdim } 234239310Sdim 235239310Sdim return true; 236239310Sdim} 237239310Sdim 238239310Sdimstatic bool canCompareBeNewValueJump(const HexagonInstrInfo *QII, 239239310Sdim const TargetRegisterInfo *TRI, 240239310Sdim MachineBasicBlock::iterator II, 241239310Sdim unsigned pReg, 242239310Sdim bool secondReg, 243239310Sdim bool optLocation, 244239310Sdim MachineBasicBlock::iterator end, 245239310Sdim MachineFunction &MF) { 246309124Sdim MachineInstr &MI = *II; 247239310Sdim 248239310Sdim // If the second operand of the compare is an imm, make sure it's in the 249239310Sdim // range specified by the arch. 250239310Sdim if (!secondReg) { 251327952Sdim const MachineOperand &Op2 = MI.getOperand(2); 252327952Sdim if (!Op2.isImm()) 253327952Sdim return false; 254327952Sdim 255327952Sdim int64_t v = Op2.getImm(); 256314564Sdim bool Valid = false; 257239310Sdim 258314564Sdim switch (MI.getOpcode()) { 259314564Sdim case Hexagon::C2_cmpeqi: 260327952Sdim case Hexagon::C4_cmpneqi: 261314564Sdim case Hexagon::C2_cmpgti: 262327952Sdim case Hexagon::C4_cmpltei: 263314564Sdim Valid = (isUInt<5>(v) || v == -1); 264314564Sdim break; 265314564Sdim case Hexagon::C2_cmpgtui: 266327952Sdim case Hexagon::C4_cmplteui: 267314564Sdim Valid = isUInt<5>(v); 268314564Sdim break; 269314564Sdim case Hexagon::S2_tstbit_i: 270314564Sdim case Hexagon::S4_ntstbit_i: 271314564Sdim Valid = (v == 0); 272314564Sdim break; 273314564Sdim } 274314564Sdim 275314564Sdim if (!Valid) 276239310Sdim return false; 277239310Sdim } 278239310Sdim 279251662Sdim unsigned cmpReg1, cmpOp2 = 0; // cmpOp2 assignment silences compiler warning. 280309124Sdim cmpReg1 = MI.getOperand(1).getReg(); 281239310Sdim 282239310Sdim if (secondReg) { 283309124Sdim cmpOp2 = MI.getOperand(2).getReg(); 284239310Sdim 285314564Sdim // If the same register appears as both operands, we cannot generate a new 286314564Sdim // value compare. Only one operand may use the .new suffix. 287314564Sdim if (cmpReg1 == cmpOp2) 288314564Sdim return false; 289314564Sdim 290341825Sdim // Make sure that the second register is not from COPY 291341825Sdim // at machine code level, we don't need this, but if we decide 292239310Sdim // to move new value jump prior to RA, we would be needing this. 293239310Sdim MachineRegisterInfo &MRI = MF.getRegInfo(); 294360784Sdim if (secondReg && !Register::isPhysicalRegister(cmpOp2)) { 295239310Sdim MachineInstr *def = MRI.getVRegDef(cmpOp2); 296239310Sdim if (def->getOpcode() == TargetOpcode::COPY) 297239310Sdim return false; 298239310Sdim } 299239310Sdim } 300239310Sdim 301239310Sdim // Walk the instructions after the compare (predicate def) to the jump, 302239310Sdim // and satisfy the following conditions. 303327952Sdim ++II; 304327952Sdim for (MachineBasicBlock::iterator localII = II; localII != end; ++localII) { 305341825Sdim if (localII->isDebugInstr()) 306314564Sdim continue; 307239310Sdim 308239310Sdim // Check 1. 309239310Sdim // If "common" checks fail, bail out. 310239310Sdim if (!commonChecksToProhibitNewValueJump(optLocation, localII)) 311239310Sdim return false; 312239310Sdim 313239310Sdim // Check 2. 314239310Sdim // If there is a def or use of predicate (result of compare), bail out. 315239310Sdim if (localII->modifiesRegister(pReg, TRI) || 316239310Sdim localII->readsRegister(pReg, TRI)) 317239310Sdim return false; 318239310Sdim 319239310Sdim // Check 3. 320239310Sdim // If there is a def of any of the use of the compare (operands of compare), 321239310Sdim // bail out. 322239310Sdim // Eg. 323239310Sdim // p0 = cmp.eq(r2, r0) 324239310Sdim // r2 = r4 325239310Sdim // if (p0.new) jump:t .LBB28_3 326239310Sdim if (localII->modifiesRegister(cmpReg1, TRI) || 327239310Sdim (secondReg && localII->modifiesRegister(cmpOp2, TRI))) 328239310Sdim return false; 329239310Sdim } 330239310Sdim return true; 331239310Sdim} 332239310Sdim 333296417Sdim// Given a compare operator, return a matching New Value Jump compare operator. 334296417Sdim// Make sure that MI here is included in isNewValueJumpCandidate. 335251662Sdimstatic unsigned getNewValueJumpOpcode(MachineInstr *MI, int reg, 336251662Sdim bool secondRegNewified, 337251662Sdim MachineBasicBlock *jmpTarget, 338251662Sdim const MachineBranchProbabilityInfo 339251662Sdim *MBPI) { 340251662Sdim bool taken = false; 341251662Sdim MachineBasicBlock *Src = MI->getParent(); 342251662Sdim const BranchProbability Prediction = 343251662Sdim MBPI->getEdgeProbability(Src, jmpTarget); 344251662Sdim 345251662Sdim if (Prediction >= BranchProbability(1,2)) 346251662Sdim taken = true; 347251662Sdim 348239310Sdim switch (MI->getOpcode()) { 349280031Sdim case Hexagon::C2_cmpeq: 350288943Sdim return taken ? Hexagon::J4_cmpeq_t_jumpnv_t 351288943Sdim : Hexagon::J4_cmpeq_t_jumpnv_nt; 352239310Sdim 353327952Sdim case Hexagon::C2_cmpeqi: 354239310Sdim if (reg >= 0) 355288943Sdim return taken ? Hexagon::J4_cmpeqi_t_jumpnv_t 356288943Sdim : Hexagon::J4_cmpeqi_t_jumpnv_nt; 357327952Sdim return taken ? Hexagon::J4_cmpeqn1_t_jumpnv_t 358327952Sdim : Hexagon::J4_cmpeqn1_t_jumpnv_nt; 359239310Sdim 360327952Sdim case Hexagon::C4_cmpneqi: 361327952Sdim if (reg >= 0) 362327952Sdim return taken ? Hexagon::J4_cmpeqi_f_jumpnv_t 363327952Sdim : Hexagon::J4_cmpeqi_f_jumpnv_nt; 364327952Sdim return taken ? Hexagon::J4_cmpeqn1_f_jumpnv_t : 365327952Sdim Hexagon::J4_cmpeqn1_f_jumpnv_nt; 366327952Sdim 367327952Sdim case Hexagon::C2_cmpgt: 368239310Sdim if (secondRegNewified) 369288943Sdim return taken ? Hexagon::J4_cmplt_t_jumpnv_t 370288943Sdim : Hexagon::J4_cmplt_t_jumpnv_nt; 371327952Sdim return taken ? Hexagon::J4_cmpgt_t_jumpnv_t 372327952Sdim : Hexagon::J4_cmpgt_t_jumpnv_nt; 373239310Sdim 374327952Sdim case Hexagon::C2_cmpgti: 375239310Sdim if (reg >= 0) 376288943Sdim return taken ? Hexagon::J4_cmpgti_t_jumpnv_t 377288943Sdim : Hexagon::J4_cmpgti_t_jumpnv_nt; 378327952Sdim return taken ? Hexagon::J4_cmpgtn1_t_jumpnv_t 379327952Sdim : Hexagon::J4_cmpgtn1_t_jumpnv_nt; 380239310Sdim 381327952Sdim case Hexagon::C2_cmpgtu: 382239310Sdim if (secondRegNewified) 383288943Sdim return taken ? Hexagon::J4_cmpltu_t_jumpnv_t 384288943Sdim : Hexagon::J4_cmpltu_t_jumpnv_nt; 385327952Sdim return taken ? Hexagon::J4_cmpgtu_t_jumpnv_t 386327952Sdim : Hexagon::J4_cmpgtu_t_jumpnv_nt; 387239310Sdim 388280031Sdim case Hexagon::C2_cmpgtui: 389288943Sdim return taken ? Hexagon::J4_cmpgtui_t_jumpnv_t 390288943Sdim : Hexagon::J4_cmpgtui_t_jumpnv_nt; 391239310Sdim 392296417Sdim case Hexagon::C4_cmpneq: 393296417Sdim return taken ? Hexagon::J4_cmpeq_f_jumpnv_t 394296417Sdim : Hexagon::J4_cmpeq_f_jumpnv_nt; 395296417Sdim 396296417Sdim case Hexagon::C4_cmplte: 397296417Sdim if (secondRegNewified) 398296417Sdim return taken ? Hexagon::J4_cmplt_f_jumpnv_t 399296417Sdim : Hexagon::J4_cmplt_f_jumpnv_nt; 400296417Sdim return taken ? Hexagon::J4_cmpgt_f_jumpnv_t 401296417Sdim : Hexagon::J4_cmpgt_f_jumpnv_nt; 402296417Sdim 403296417Sdim case Hexagon::C4_cmplteu: 404296417Sdim if (secondRegNewified) 405296417Sdim return taken ? Hexagon::J4_cmpltu_f_jumpnv_t 406296417Sdim : Hexagon::J4_cmpltu_f_jumpnv_nt; 407296417Sdim return taken ? Hexagon::J4_cmpgtu_f_jumpnv_t 408296417Sdim : Hexagon::J4_cmpgtu_f_jumpnv_nt; 409296417Sdim 410327952Sdim case Hexagon::C4_cmpltei: 411327952Sdim if (reg >= 0) 412327952Sdim return taken ? Hexagon::J4_cmpgti_f_jumpnv_t 413327952Sdim : Hexagon::J4_cmpgti_f_jumpnv_nt; 414327952Sdim return taken ? Hexagon::J4_cmpgtn1_f_jumpnv_t 415327952Sdim : Hexagon::J4_cmpgtn1_f_jumpnv_nt; 416327952Sdim 417327952Sdim case Hexagon::C4_cmplteui: 418327952Sdim return taken ? Hexagon::J4_cmpgtui_f_jumpnv_t 419327952Sdim : Hexagon::J4_cmpgtui_f_jumpnv_nt; 420327952Sdim 421239310Sdim default: 422239310Sdim llvm_unreachable("Could not find matching New Value Jump instruction."); 423239310Sdim } 424239310Sdim // return *some value* to avoid compiler warning 425239310Sdim return 0; 426239310Sdim} 427239310Sdim 428309124Sdimbool HexagonNewValueJump::isNewValueJumpCandidate( 429309124Sdim const MachineInstr &MI) const { 430309124Sdim switch (MI.getOpcode()) { 431309124Sdim case Hexagon::C2_cmpeq: 432309124Sdim case Hexagon::C2_cmpeqi: 433309124Sdim case Hexagon::C2_cmpgt: 434309124Sdim case Hexagon::C2_cmpgti: 435309124Sdim case Hexagon::C2_cmpgtu: 436309124Sdim case Hexagon::C2_cmpgtui: 437309124Sdim case Hexagon::C4_cmpneq: 438327952Sdim case Hexagon::C4_cmpneqi: 439309124Sdim case Hexagon::C4_cmplte: 440309124Sdim case Hexagon::C4_cmplteu: 441327952Sdim case Hexagon::C4_cmpltei: 442327952Sdim case Hexagon::C4_cmplteui: 443309124Sdim return true; 444296417Sdim 445309124Sdim default: 446309124Sdim return false; 447296417Sdim } 448296417Sdim} 449296417Sdim 450239310Sdimbool HexagonNewValueJump::runOnMachineFunction(MachineFunction &MF) { 451341825Sdim LLVM_DEBUG(dbgs() << "********** Hexagon New Value Jump **********\n" 452341825Sdim << "********** Function: " << MF.getName() << "\n"); 453239310Sdim 454327952Sdim if (skipFunction(MF.getFunction())) 455309124Sdim return false; 456309124Sdim 457288943Sdim // If we move NewValueJump before register allocation we'll need live variable 458288943Sdim // analysis here too. 459239310Sdim 460280031Sdim QII = static_cast<const HexagonInstrInfo *>(MF.getSubtarget().getInstrInfo()); 461280031Sdim QRI = static_cast<const HexagonRegisterInfo *>( 462280031Sdim MF.getSubtarget().getRegisterInfo()); 463251662Sdim MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 464239310Sdim 465341825Sdim if (DisableNewValueJumps || 466341825Sdim !MF.getSubtarget<HexagonSubtarget>().useNewValueJumps()) 467239310Sdim return false; 468239310Sdim 469239310Sdim int nvjCount = DbgNVJCount; 470239310Sdim int nvjGenerated = 0; 471239310Sdim 472239310Sdim // Loop through all the bb's of the function 473239310Sdim for (MachineFunction::iterator MBBb = MF.begin(), MBBe = MF.end(); 474327952Sdim MBBb != MBBe; ++MBBb) { 475296417Sdim MachineBasicBlock *MBB = &*MBBb; 476239310Sdim 477341825Sdim LLVM_DEBUG(dbgs() << "** dumping bb ** " << MBB->getNumber() << "\n"); 478341825Sdim LLVM_DEBUG(MBB->dump()); 479341825Sdim LLVM_DEBUG(dbgs() << "\n" 480341825Sdim << "********** dumping instr bottom up **********\n"); 481239310Sdim bool foundJump = false; 482239310Sdim bool foundCompare = false; 483239310Sdim bool invertPredicate = false; 484239310Sdim unsigned predReg = 0; // predicate reg of the jump. 485239310Sdim unsigned cmpReg1 = 0; 486239310Sdim int cmpOp2 = 0; 487239310Sdim MachineBasicBlock::iterator jmpPos; 488239310Sdim MachineBasicBlock::iterator cmpPos; 489276479Sdim MachineInstr *cmpInstr = nullptr, *jmpInstr = nullptr; 490276479Sdim MachineBasicBlock *jmpTarget = nullptr; 491239310Sdim bool afterRA = false; 492239310Sdim bool isSecondOpReg = false; 493239310Sdim bool isSecondOpNewified = false; 494239310Sdim // Traverse the basic block - bottom up 495239310Sdim for (MachineBasicBlock::iterator MII = MBB->end(), E = MBB->begin(); 496327952Sdim MII != E;) { 497309124Sdim MachineInstr &MI = *--MII; 498341825Sdim if (MI.isDebugInstr()) { 499239310Sdim continue; 500239310Sdim } 501239310Sdim 502239310Sdim if ((nvjCount == 0) || (nvjCount > -1 && nvjCount <= nvjGenerated)) 503239310Sdim break; 504239310Sdim 505341825Sdim LLVM_DEBUG(dbgs() << "Instr: "; MI.dump(); dbgs() << "\n"); 506239310Sdim 507309124Sdim if (!foundJump && (MI.getOpcode() == Hexagon::J2_jumpt || 508314564Sdim MI.getOpcode() == Hexagon::J2_jumptpt || 509309124Sdim MI.getOpcode() == Hexagon::J2_jumpf || 510314564Sdim MI.getOpcode() == Hexagon::J2_jumpfpt || 511309124Sdim MI.getOpcode() == Hexagon::J2_jumptnewpt || 512309124Sdim MI.getOpcode() == Hexagon::J2_jumptnew || 513309124Sdim MI.getOpcode() == Hexagon::J2_jumpfnewpt || 514309124Sdim MI.getOpcode() == Hexagon::J2_jumpfnew)) { 515239310Sdim // This is where you would insert your compare and 516239310Sdim // instr that feeds compare 517239310Sdim jmpPos = MII; 518309124Sdim jmpInstr = &MI; 519309124Sdim predReg = MI.getOperand(0).getReg(); 520360784Sdim afterRA = Register::isPhysicalRegister(predReg); 521239310Sdim 522239310Sdim // If ifconverter had not messed up with the kill flags of the 523239310Sdim // operands, the following check on the kill flag would suffice. 524239310Sdim // if(!jmpInstr->getOperand(0).isKill()) break; 525239310Sdim 526341825Sdim // This predicate register is live out of BB 527239310Sdim // this would only work if we can actually use Live 528239310Sdim // variable analysis on phy regs - but LLVM does not 529239310Sdim // provide LV analysis on phys regs. 530239310Sdim //if(LVs.isLiveOut(predReg, *MBB)) break; 531239310Sdim 532239310Sdim // Get all the successors of this block - which will always 533314564Sdim // be 2. Check if the predicate register is live-in in those 534239310Sdim // successor. If yes, we can not delete the predicate - 535239310Sdim // I am doing this only because LLVM does not provide LiveOut 536239310Sdim // at the BB level. 537239310Sdim bool predLive = false; 538239310Sdim for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), 539327952Sdim SIE = MBB->succ_end(); 540327952Sdim SI != SIE; ++SI) { 541327952Sdim MachineBasicBlock *succMBB = *SI; 542327952Sdim if (succMBB->isLiveIn(predReg)) 543239310Sdim predLive = true; 544239310Sdim } 545239310Sdim if (predLive) 546239310Sdim break; 547239310Sdim 548309124Sdim if (!MI.getOperand(1).isMBB()) 549309124Sdim continue; 550309124Sdim jmpTarget = MI.getOperand(1).getMBB(); 551239310Sdim foundJump = true; 552309124Sdim if (MI.getOpcode() == Hexagon::J2_jumpf || 553309124Sdim MI.getOpcode() == Hexagon::J2_jumpfnewpt || 554309124Sdim MI.getOpcode() == Hexagon::J2_jumpfnew) { 555239310Sdim invertPredicate = true; 556239310Sdim } 557239310Sdim continue; 558239310Sdim } 559239310Sdim 560239310Sdim // No new value jump if there is a barrier. A barrier has to be in its 561239310Sdim // own packet. A barrier has zero operands. We conservatively bail out 562239310Sdim // here if we see any instruction with zero operands. 563309124Sdim if (foundJump && MI.getNumOperands() == 0) 564239310Sdim break; 565239310Sdim 566309124Sdim if (foundJump && !foundCompare && MI.getOperand(0).isReg() && 567309124Sdim MI.getOperand(0).getReg() == predReg) { 568239310Sdim // Not all compares can be new value compare. Arch Spec: 7.6.1.1 569296417Sdim if (isNewValueJumpCandidate(MI)) { 570309124Sdim assert( 571309124Sdim (MI.getDesc().isCompare()) && 572239310Sdim "Only compare instruction can be collapsed into New Value Jump"); 573309124Sdim isSecondOpReg = MI.getOperand(2).isReg(); 574239310Sdim 575239310Sdim if (!canCompareBeNewValueJump(QII, QRI, MII, predReg, isSecondOpReg, 576239310Sdim afterRA, jmpPos, MF)) 577239310Sdim break; 578239310Sdim 579309124Sdim cmpInstr = &MI; 580239310Sdim cmpPos = MII; 581239310Sdim foundCompare = true; 582239310Sdim 583239310Sdim // We need cmpReg1 and cmpOp2(imm or reg) while building 584239310Sdim // new value jump instruction. 585309124Sdim cmpReg1 = MI.getOperand(1).getReg(); 586239310Sdim 587321369Sdim if (isSecondOpReg) 588309124Sdim cmpOp2 = MI.getOperand(2).getReg(); 589321369Sdim else 590309124Sdim cmpOp2 = MI.getOperand(2).getImm(); 591239310Sdim continue; 592239310Sdim } 593239310Sdim } 594239310Sdim 595239310Sdim if (foundCompare && foundJump) { 596239310Sdim // If "common" checks fail, bail out on this BB. 597239310Sdim if (!commonChecksToProhibitNewValueJump(afterRA, MII)) 598239310Sdim break; 599239310Sdim 600239310Sdim bool foundFeeder = false; 601239310Sdim MachineBasicBlock::iterator feederPos = MII; 602309124Sdim if (MI.getOperand(0).isReg() && MI.getOperand(0).isDef() && 603309124Sdim (MI.getOperand(0).getReg() == cmpReg1 || 604309124Sdim (isSecondOpReg && 605309124Sdim MI.getOperand(0).getReg() == (unsigned)cmpOp2))) { 606239310Sdim 607360784Sdim Register feederReg = MI.getOperand(0).getReg(); 608239310Sdim 609239310Sdim // First try to see if we can get the feeder from the first operand 610239310Sdim // of the compare. If we can not, and if secondOpReg is true 611239310Sdim // (second operand of the compare is also register), try that one. 612239310Sdim // TODO: Try to come up with some heuristic to figure out which 613239310Sdim // feeder would benefit. 614239310Sdim 615239310Sdim if (feederReg == cmpReg1) { 616239310Sdim if (!canBeFeederToNewValueJump(QII, QRI, MII, jmpPos, cmpPos, MF)) { 617239310Sdim if (!isSecondOpReg) 618239310Sdim break; 619239310Sdim else 620239310Sdim continue; 621239310Sdim } else 622239310Sdim foundFeeder = true; 623239310Sdim } 624239310Sdim 625327952Sdim if (!foundFeeder && isSecondOpReg && feederReg == (unsigned)cmpOp2) 626239310Sdim if (!canBeFeederToNewValueJump(QII, QRI, MII, jmpPos, cmpPos, MF)) 627239310Sdim break; 628239310Sdim 629239310Sdim if (isSecondOpReg) { 630239310Sdim // In case of CMPLT, or CMPLTU, or EQ with the second register 631239310Sdim // to newify, swap the operands. 632314564Sdim unsigned COp = cmpInstr->getOpcode(); 633314564Sdim if ((COp == Hexagon::C2_cmpeq || COp == Hexagon::C4_cmpneq) && 634327952Sdim (feederReg == (unsigned)cmpOp2)) { 635239310Sdim unsigned tmp = cmpReg1; 636239310Sdim cmpReg1 = cmpOp2; 637239310Sdim cmpOp2 = tmp; 638239310Sdim } 639239310Sdim 640239310Sdim // Now we have swapped the operands, all we need to check is, 641239310Sdim // if the second operand (after swap) is the feeder. 642239310Sdim // And if it is, make a note. 643239310Sdim if (feederReg == (unsigned)cmpOp2) 644239310Sdim isSecondOpNewified = true; 645239310Sdim } 646239310Sdim 647239310Sdim // Now that we are moving feeder close the jump, 648239310Sdim // make sure we are respecting the kill values of 649239310Sdim // the operands of the feeder. 650239310Sdim 651321369Sdim auto TransferKills = [jmpPos,cmpPos] (MachineInstr &MI) { 652321369Sdim for (MachineOperand &MO : MI.operands()) { 653321369Sdim if (!MO.isReg() || !MO.isUse()) 654321369Sdim continue; 655360784Sdim Register UseR = MO.getReg(); 656321369Sdim for (auto I = std::next(MI.getIterator()); I != jmpPos; ++I) { 657321369Sdim if (I == cmpPos) 658321369Sdim continue; 659321369Sdim for (MachineOperand &Op : I->operands()) { 660321369Sdim if (!Op.isReg() || !Op.isUse() || !Op.isKill()) 661321369Sdim continue; 662321369Sdim if (Op.getReg() != UseR) 663321369Sdim continue; 664321369Sdim // We found that there is kill of a use register 665321369Sdim // Set up a kill flag on the register 666321369Sdim Op.setIsKill(false); 667321369Sdim MO.setIsKill(true); 668321369Sdim return; 669239310Sdim } 670239310Sdim } 671239310Sdim } 672321369Sdim }; 673239310Sdim 674321369Sdim TransferKills(*feederPos); 675321369Sdim TransferKills(*cmpPos); 676321369Sdim bool MO1IsKill = cmpPos->killsRegister(cmpReg1, QRI); 677321369Sdim bool MO2IsKill = isSecondOpReg && cmpPos->killsRegister(cmpOp2, QRI); 678321369Sdim 679309124Sdim MBB->splice(jmpPos, MI.getParent(), MI); 680309124Sdim MBB->splice(jmpPos, MI.getParent(), cmpInstr); 681309124Sdim DebugLoc dl = MI.getDebugLoc(); 682239310Sdim MachineInstr *NewMI; 683239310Sdim 684309124Sdim assert((isNewValueJumpCandidate(*cmpInstr)) && 685296417Sdim "This compare is not a New Value Jump candidate."); 686239310Sdim unsigned opc = getNewValueJumpOpcode(cmpInstr, cmpOp2, 687251662Sdim isSecondOpNewified, 688251662Sdim jmpTarget, MBPI); 689239310Sdim if (invertPredicate) 690239310Sdim opc = QII->getInvertedPredicatedOpcode(opc); 691239310Sdim 692251662Sdim if (isSecondOpReg) 693327952Sdim NewMI = BuildMI(*MBB, jmpPos, dl, QII->get(opc)) 694327952Sdim .addReg(cmpReg1, getKillRegState(MO1IsKill)) 695327952Sdim .addReg(cmpOp2, getKillRegState(MO2IsKill)) 696327952Sdim .addMBB(jmpTarget); 697251662Sdim 698251662Sdim else 699327952Sdim NewMI = BuildMI(*MBB, jmpPos, dl, QII->get(opc)) 700327952Sdim .addReg(cmpReg1, getKillRegState(MO1IsKill)) 701327952Sdim .addImm(cmpOp2) 702327952Sdim .addMBB(jmpTarget); 703239310Sdim 704239310Sdim assert(NewMI && "New Value Jump Instruction Not created!"); 705261991Sdim (void)NewMI; 706239310Sdim if (cmpInstr->getOperand(0).isReg() && 707239310Sdim cmpInstr->getOperand(0).isKill()) 708239310Sdim cmpInstr->getOperand(0).setIsKill(false); 709239310Sdim if (cmpInstr->getOperand(1).isReg() && 710239310Sdim cmpInstr->getOperand(1).isKill()) 711239310Sdim cmpInstr->getOperand(1).setIsKill(false); 712239310Sdim cmpInstr->eraseFromParent(); 713239310Sdim jmpInstr->eraseFromParent(); 714239310Sdim ++nvjGenerated; 715239310Sdim ++NumNVJGenerated; 716239310Sdim break; 717239310Sdim } 718239310Sdim } 719239310Sdim } 720239310Sdim } 721239310Sdim 722239310Sdim return true; 723239310Sdim} 724239310Sdim 725239310SdimFunctionPass *llvm::createHexagonNewValueJump() { 726239310Sdim return new HexagonNewValueJump(); 727239310Sdim} 728