1//===----- HexagonPacketizer.cpp - vliw packetizer ---------------------===// 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// 10// This implements a simple VLIW packetizer using DFA. The packetizer works on 11// machine basic blocks. For each instruction I in BB, the packetizer consults 12// the DFA to see if machine resources are available to execute I. If so, the 13// packetizer checks if I depends on any instruction J in the current packet. 14// If no dependency is found, I is added to current packet and machine resource 15// is marked as taken. If any dependency is found, a target API call is made to 16// prune the dependence. 17// 18//===----------------------------------------------------------------------===// 19#include "llvm/CodeGen/DFAPacketizer.h" 20#include "Hexagon.h" 21#include "HexagonMachineFunctionInfo.h" 22#include "HexagonRegisterInfo.h" 23#include "HexagonSubtarget.h" 24#include "HexagonTargetMachine.h" 25#include "llvm/ADT/DenseMap.h" 26#include "llvm/ADT/Statistic.h" 27#include "llvm/CodeGen/LatencyPriorityQueue.h" 28#include "llvm/CodeGen/MachineDominators.h" 29#include "llvm/CodeGen/MachineFrameInfo.h" 30#include "llvm/CodeGen/MachineFunctionAnalysis.h" 31#include "llvm/CodeGen/MachineFunctionPass.h" 32#include "llvm/CodeGen/MachineInstrBuilder.h" 33#include "llvm/CodeGen/MachineLoopInfo.h" 34#include "llvm/CodeGen/MachineRegisterInfo.h" 35#include "llvm/CodeGen/Passes.h" 36#include "llvm/CodeGen/ScheduleDAG.h" 37#include "llvm/CodeGen/ScheduleDAGInstrs.h" 38#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 39#include "llvm/CodeGen/SchedulerRegistry.h" 40#include "llvm/MC/MCInstrItineraries.h" 41#include "llvm/Support/CommandLine.h" 42#include "llvm/Support/Compiler.h" 43#include "llvm/Support/Debug.h" 44#include "llvm/Support/MathExtras.h" 45#include "llvm/Target/TargetInstrInfo.h" 46#include "llvm/Target/TargetMachine.h" 47#include "llvm/Target/TargetRegisterInfo.h" 48#include <map> 49#include <vector> 50 51using namespace llvm; 52 53#define DEBUG_TYPE "packets" 54 55static cl::opt<bool> PacketizeVolatiles("hexagon-packetize-volatiles", 56 cl::ZeroOrMore, cl::Hidden, cl::init(true), 57 cl::desc("Allow non-solo packetization of volatile memory references")); 58 59namespace llvm { 60 void initializeHexagonPacketizerPass(PassRegistry&); 61} 62 63 64namespace { 65 class HexagonPacketizer : public MachineFunctionPass { 66 67 public: 68 static char ID; 69 HexagonPacketizer() : MachineFunctionPass(ID) { 70 initializeHexagonPacketizerPass(*PassRegistry::getPassRegistry()); 71 } 72 73 void getAnalysisUsage(AnalysisUsage &AU) const override { 74 AU.setPreservesCFG(); 75 AU.addRequired<MachineDominatorTree>(); 76 AU.addRequired<MachineBranchProbabilityInfo>(); 77 AU.addPreserved<MachineDominatorTree>(); 78 AU.addRequired<MachineLoopInfo>(); 79 AU.addPreserved<MachineLoopInfo>(); 80 MachineFunctionPass::getAnalysisUsage(AU); 81 } 82 83 const char *getPassName() const override { 84 return "Hexagon Packetizer"; 85 } 86 87 bool runOnMachineFunction(MachineFunction &Fn) override; 88 }; 89 char HexagonPacketizer::ID = 0; 90 91 class HexagonPacketizerList : public VLIWPacketizerList { 92 93 private: 94 95 // Has the instruction been promoted to a dot-new instruction. 96 bool PromotedToDotNew; 97 98 // Has the instruction been glued to allocframe. 99 bool GlueAllocframeStore; 100 101 // Has the feeder instruction been glued to new value jump. 102 bool GlueToNewValueJump; 103 104 // Check if there is a dependence between some instruction already in this 105 // packet and this instruction. 106 bool Dependence; 107 108 // Only check for dependence if there are resources available to 109 // schedule this instruction. 110 bool FoundSequentialDependence; 111 112 /// \brief A handle to the branch probability pass. 113 const MachineBranchProbabilityInfo *MBPI; 114 115 // Track MIs with ignored dependece. 116 std::vector<MachineInstr*> IgnoreDepMIs; 117 118 public: 119 // Ctor. 120 HexagonPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI, 121 const MachineBranchProbabilityInfo *MBPI); 122 123 // initPacketizerState - initialize some internal flags. 124 void initPacketizerState() override; 125 126 // ignorePseudoInstruction - Ignore bundling of pseudo instructions. 127 bool ignorePseudoInstruction(MachineInstr *MI, 128 MachineBasicBlock *MBB) override; 129 130 // isSoloInstruction - return true if instruction MI can not be packetized 131 // with any other instruction, which means that MI itself is a packet. 132 bool isSoloInstruction(MachineInstr *MI) override; 133 134 // isLegalToPacketizeTogether - Is it legal to packetize SUI and SUJ 135 // together. 136 bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) override; 137 138 // isLegalToPruneDependencies - Is it legal to prune dependece between SUI 139 // and SUJ. 140 bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) override; 141 142 MachineBasicBlock::iterator addToPacket(MachineInstr *MI) override; 143 private: 144 bool IsCallDependent(MachineInstr* MI, SDep::Kind DepType, unsigned DepReg); 145 bool PromoteToDotNew(MachineInstr* MI, SDep::Kind DepType, 146 MachineBasicBlock::iterator &MII, 147 const TargetRegisterClass* RC); 148 bool CanPromoteToDotNew(MachineInstr *MI, SUnit *PacketSU, unsigned DepReg, 149 const std::map<MachineInstr *, SUnit *> &MIToSUnit, 150 MachineBasicBlock::iterator &MII, 151 const TargetRegisterClass *RC); 152 bool 153 CanPromoteToNewValue(MachineInstr *MI, SUnit *PacketSU, unsigned DepReg, 154 const std::map<MachineInstr *, SUnit *> &MIToSUnit, 155 MachineBasicBlock::iterator &MII); 156 bool CanPromoteToNewValueStore( 157 MachineInstr *MI, MachineInstr *PacketMI, unsigned DepReg, 158 const std::map<MachineInstr *, SUnit *> &MIToSUnit); 159 bool DemoteToDotOld(MachineInstr *MI); 160 bool ArePredicatesComplements( 161 MachineInstr *MI1, MachineInstr *MI2, 162 const std::map<MachineInstr *, SUnit *> &MIToSUnit); 163 bool RestrictingDepExistInPacket(MachineInstr *, unsigned, 164 const std::map<MachineInstr *, SUnit *> &); 165 bool isNewifiable(MachineInstr* MI); 166 bool isCondInst(MachineInstr* MI); 167 bool tryAllocateResourcesForConstExt(MachineInstr* MI); 168 bool canReserveResourcesForConstExt(MachineInstr *MI); 169 void reserveResourcesForConstExt(MachineInstr* MI); 170 bool isNewValueInst(MachineInstr* MI); 171 }; 172} 173 174INITIALIZE_PASS_BEGIN(HexagonPacketizer, "packets", "Hexagon Packetizer", 175 false, false) 176INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 177INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 178INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 179INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 180INITIALIZE_PASS_END(HexagonPacketizer, "packets", "Hexagon Packetizer", 181 false, false) 182 183 184// HexagonPacketizerList Ctor. 185HexagonPacketizerList::HexagonPacketizerList( 186 MachineFunction &MF, MachineLoopInfo &MLI, 187 const MachineBranchProbabilityInfo *MBPI) 188 : VLIWPacketizerList(MF, MLI, true) { 189 this->MBPI = MBPI; 190} 191 192bool HexagonPacketizer::runOnMachineFunction(MachineFunction &Fn) { 193 const TargetInstrInfo *TII = Fn.getSubtarget().getInstrInfo(); 194 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 195 const MachineBranchProbabilityInfo *MBPI = 196 &getAnalysis<MachineBranchProbabilityInfo>(); 197 // Instantiate the packetizer. 198 HexagonPacketizerList Packetizer(Fn, MLI, MBPI); 199 200 // DFA state table should not be empty. 201 assert(Packetizer.getResourceTracker() && "Empty DFA table!"); 202 203 // 204 // Loop over all basic blocks and remove KILL pseudo-instructions 205 // These instructions confuse the dependence analysis. Consider: 206 // D0 = ... (Insn 0) 207 // R0 = KILL R0, D0 (Insn 1) 208 // R0 = ... (Insn 2) 209 // Here, Insn 1 will result in the dependence graph not emitting an output 210 // dependence between Insn 0 and Insn 2. This can lead to incorrect 211 // packetization 212 // 213 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 214 MBB != MBBe; ++MBB) { 215 MachineBasicBlock::iterator End = MBB->end(); 216 MachineBasicBlock::iterator MI = MBB->begin(); 217 while (MI != End) { 218 if (MI->isKill()) { 219 MachineBasicBlock::iterator DeleteMI = MI; 220 ++MI; 221 MBB->erase(DeleteMI); 222 End = MBB->end(); 223 continue; 224 } 225 ++MI; 226 } 227 } 228 229 // Loop over all of the basic blocks. 230 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 231 MBB != MBBe; ++MBB) { 232 // Find scheduling regions and schedule / packetize each region. 233 unsigned RemainingCount = MBB->size(); 234 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 235 RegionEnd != MBB->begin();) { 236 // The next region starts above the previous region. Look backward in the 237 // instruction stream until we find the nearest boundary. 238 MachineBasicBlock::iterator I = RegionEnd; 239 for(;I != MBB->begin(); --I, --RemainingCount) { 240 if (TII->isSchedulingBoundary(std::prev(I), MBB, Fn)) 241 break; 242 } 243 I = MBB->begin(); 244 245 // Skip empty scheduling regions. 246 if (I == RegionEnd) { 247 RegionEnd = std::prev(RegionEnd); 248 --RemainingCount; 249 continue; 250 } 251 // Skip regions with one instruction. 252 if (I == std::prev(RegionEnd)) { 253 RegionEnd = std::prev(RegionEnd); 254 continue; 255 } 256 257 Packetizer.PacketizeMIs(MBB, I, RegionEnd); 258 RegionEnd = I; 259 } 260 } 261 262 return true; 263} 264 265 266static bool IsIndirectCall(MachineInstr* MI) { 267 return MI->getOpcode() == Hexagon::J2_callr; 268} 269 270// Reserve resources for constant extender. Trigure an assertion if 271// reservation fail. 272void HexagonPacketizerList::reserveResourcesForConstExt(MachineInstr* MI) { 273 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 274 MachineFunction *MF = MI->getParent()->getParent(); 275 MachineInstr *PseudoMI = MF->CreateMachineInstr(QII->get(Hexagon::A4_ext), 276 MI->getDebugLoc()); 277 278 if (ResourceTracker->canReserveResources(PseudoMI)) { 279 ResourceTracker->reserveResources(PseudoMI); 280 MI->getParent()->getParent()->DeleteMachineInstr(PseudoMI); 281 } else { 282 MI->getParent()->getParent()->DeleteMachineInstr(PseudoMI); 283 llvm_unreachable("can not reserve resources for constant extender."); 284 } 285 return; 286} 287 288bool HexagonPacketizerList::canReserveResourcesForConstExt(MachineInstr *MI) { 289 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 290 assert((QII->isExtended(MI) || QII->isConstExtended(MI)) && 291 "Should only be called for constant extended instructions"); 292 MachineFunction *MF = MI->getParent()->getParent(); 293 MachineInstr *PseudoMI = MF->CreateMachineInstr(QII->get(Hexagon::A4_ext), 294 MI->getDebugLoc()); 295 bool CanReserve = ResourceTracker->canReserveResources(PseudoMI); 296 MF->DeleteMachineInstr(PseudoMI); 297 return CanReserve; 298} 299 300// Allocate resources (i.e. 4 bytes) for constant extender. If succeed, return 301// true, otherwise, return false. 302bool HexagonPacketizerList::tryAllocateResourcesForConstExt(MachineInstr* MI) { 303 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 304 MachineFunction *MF = MI->getParent()->getParent(); 305 MachineInstr *PseudoMI = MF->CreateMachineInstr(QII->get(Hexagon::A4_ext), 306 MI->getDebugLoc()); 307 308 if (ResourceTracker->canReserveResources(PseudoMI)) { 309 ResourceTracker->reserveResources(PseudoMI); 310 MI->getParent()->getParent()->DeleteMachineInstr(PseudoMI); 311 return true; 312 } else { 313 MI->getParent()->getParent()->DeleteMachineInstr(PseudoMI); 314 return false; 315 } 316} 317 318 319bool HexagonPacketizerList::IsCallDependent(MachineInstr* MI, 320 SDep::Kind DepType, 321 unsigned DepReg) { 322 323 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 324 const HexagonRegisterInfo *QRI = 325 (const HexagonRegisterInfo *)MF.getSubtarget().getRegisterInfo(); 326 327 // Check for lr dependence 328 if (DepReg == QRI->getRARegister()) { 329 return true; 330 } 331 332 if (QII->isDeallocRet(MI)) { 333 if (DepReg == QRI->getFrameRegister() || 334 DepReg == QRI->getStackRegister()) 335 return true; 336 } 337 338 // Check if this is a predicate dependence 339 const TargetRegisterClass* RC = QRI->getMinimalPhysRegClass(DepReg); 340 if (RC == &Hexagon::PredRegsRegClass) { 341 return true; 342 } 343 344 // 345 // Lastly check for an operand used in an indirect call 346 // If we had an attribute for checking if an instruction is an indirect call, 347 // then we could have avoided this relatively brittle implementation of 348 // IsIndirectCall() 349 // 350 // Assumes that the first operand of the CALLr is the function address 351 // 352 if (IsIndirectCall(MI) && (DepType == SDep::Data)) { 353 MachineOperand MO = MI->getOperand(0); 354 if (MO.isReg() && MO.isUse() && (MO.getReg() == DepReg)) { 355 return true; 356 } 357 } 358 359 return false; 360} 361 362static bool IsRegDependence(const SDep::Kind DepType) { 363 return (DepType == SDep::Data || DepType == SDep::Anti || 364 DepType == SDep::Output); 365} 366 367static bool IsDirectJump(MachineInstr* MI) { 368 return (MI->getOpcode() == Hexagon::J2_jump); 369} 370 371static bool IsSchedBarrier(MachineInstr* MI) { 372 switch (MI->getOpcode()) { 373 case Hexagon::Y2_barrier: 374 return true; 375 } 376 return false; 377} 378 379static bool IsControlFlow(MachineInstr* MI) { 380 return (MI->getDesc().isTerminator() || MI->getDesc().isCall()); 381} 382 383static bool IsLoopN(MachineInstr *MI) { 384 return (MI->getOpcode() == Hexagon::J2_loop0i || 385 MI->getOpcode() == Hexagon::J2_loop0r); 386} 387 388/// DoesModifyCalleeSavedReg - Returns true if the instruction modifies a 389/// callee-saved register. 390static bool DoesModifyCalleeSavedReg(MachineInstr *MI, 391 const TargetRegisterInfo *TRI) { 392 for (const MCPhysReg *CSR = 393 TRI->getCalleeSavedRegs(MI->getParent()->getParent()); 394 *CSR; ++CSR) { 395 unsigned CalleeSavedReg = *CSR; 396 if (MI->modifiesRegister(CalleeSavedReg, TRI)) 397 return true; 398 } 399 return false; 400} 401 402// Returns true if an instruction can be promoted to .new predicate 403// or new-value store. 404bool HexagonPacketizerList::isNewifiable(MachineInstr* MI) { 405 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 406 return isCondInst(MI) || QII->mayBeNewStore(MI); 407} 408 409bool HexagonPacketizerList::isCondInst (MachineInstr* MI) { 410 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 411 const MCInstrDesc& TID = MI->getDesc(); 412 // bug 5670: until that is fixed, 413 // this portion is disabled. 414 if ( TID.isConditionalBranch() // && !IsRegisterJump(MI)) || 415 || QII->isConditionalTransfer(MI) 416 || QII->isConditionalALU32(MI) 417 || QII->isConditionalLoad(MI) 418 || QII->isConditionalStore(MI)) { 419 return true; 420 } 421 return false; 422} 423 424 425// Promote an instructiont to its .new form. 426// At this time, we have already made a call to CanPromoteToDotNew 427// and made sure that it can *indeed* be promoted. 428bool HexagonPacketizerList::PromoteToDotNew(MachineInstr* MI, 429 SDep::Kind DepType, MachineBasicBlock::iterator &MII, 430 const TargetRegisterClass* RC) { 431 432 assert (DepType == SDep::Data); 433 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 434 435 int NewOpcode; 436 if (RC == &Hexagon::PredRegsRegClass) 437 NewOpcode = QII->GetDotNewPredOp(MI, MBPI); 438 else 439 NewOpcode = QII->GetDotNewOp(MI); 440 MI->setDesc(QII->get(NewOpcode)); 441 442 return true; 443} 444 445bool HexagonPacketizerList::DemoteToDotOld(MachineInstr* MI) { 446 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 447 int NewOpcode = QII->GetDotOldOp(MI->getOpcode()); 448 MI->setDesc(QII->get(NewOpcode)); 449 return true; 450} 451 452enum PredicateKind { 453 PK_False, 454 PK_True, 455 PK_Unknown 456}; 457 458/// Returns true if an instruction is predicated on p0 and false if it's 459/// predicated on !p0. 460static PredicateKind getPredicateSense(MachineInstr* MI, 461 const HexagonInstrInfo *QII) { 462 if (!QII->isPredicated(MI)) 463 return PK_Unknown; 464 465 if (QII->isPredicatedTrue(MI)) 466 return PK_True; 467 468 return PK_False; 469} 470 471static MachineOperand& GetPostIncrementOperand(MachineInstr *MI, 472 const HexagonInstrInfo *QII) { 473 assert(QII->isPostIncrement(MI) && "Not a post increment operation."); 474#ifndef NDEBUG 475 // Post Increment means duplicates. Use dense map to find duplicates in the 476 // list. Caution: Densemap initializes with the minimum of 64 buckets, 477 // whereas there are at most 5 operands in the post increment. 478 DenseMap<unsigned, unsigned> DefRegsSet; 479 for(unsigned opNum = 0; opNum < MI->getNumOperands(); opNum++) 480 if (MI->getOperand(opNum).isReg() && 481 MI->getOperand(opNum).isDef()) { 482 DefRegsSet[MI->getOperand(opNum).getReg()] = 1; 483 } 484 485 for(unsigned opNum = 0; opNum < MI->getNumOperands(); opNum++) 486 if (MI->getOperand(opNum).isReg() && 487 MI->getOperand(opNum).isUse()) { 488 if (DefRegsSet[MI->getOperand(opNum).getReg()]) { 489 return MI->getOperand(opNum); 490 } 491 } 492#else 493 if (MI->getDesc().mayLoad()) { 494 // The 2nd operand is always the post increment operand in load. 495 assert(MI->getOperand(1).isReg() && 496 "Post increment operand has be to a register."); 497 return (MI->getOperand(1)); 498 } 499 if (MI->getDesc().mayStore()) { 500 // The 1st operand is always the post increment operand in store. 501 assert(MI->getOperand(0).isReg() && 502 "Post increment operand has be to a register."); 503 return (MI->getOperand(0)); 504 } 505#endif 506 // we should never come here. 507 llvm_unreachable("mayLoad or mayStore not set for Post Increment operation"); 508} 509 510// get the value being stored 511static MachineOperand& GetStoreValueOperand(MachineInstr *MI) { 512 // value being stored is always the last operand. 513 return (MI->getOperand(MI->getNumOperands()-1)); 514} 515 516// can be new value store? 517// Following restrictions are to be respected in convert a store into 518// a new value store. 519// 1. If an instruction uses auto-increment, its address register cannot 520// be a new-value register. Arch Spec 5.4.2.1 521// 2. If an instruction uses absolute-set addressing mode, 522// its address register cannot be a new-value register. 523// Arch Spec 5.4.2.1.TODO: This is not enabled as 524// as absolute-set address mode patters are not implemented. 525// 3. If an instruction produces a 64-bit result, its registers cannot be used 526// as new-value registers. Arch Spec 5.4.2.2. 527// 4. If the instruction that sets a new-value register is conditional, then 528// the instruction that uses the new-value register must also be conditional, 529// and both must always have their predicates evaluate identically. 530// Arch Spec 5.4.2.3. 531// 5. There is an implied restriction of a packet can not have another store, 532// if there is a new value store in the packet. Corollary, if there is 533// already a store in a packet, there can not be a new value store. 534// Arch Spec: 3.4.4.2 535bool HexagonPacketizerList::CanPromoteToNewValueStore( 536 MachineInstr *MI, MachineInstr *PacketMI, unsigned DepReg, 537 const std::map<MachineInstr *, SUnit *> &MIToSUnit) { 538 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 539 // Make sure we are looking at the store, that can be promoted. 540 if (!QII->mayBeNewStore(MI)) 541 return false; 542 543 // Make sure there is dependency and can be new value'ed 544 if (GetStoreValueOperand(MI).isReg() && 545 GetStoreValueOperand(MI).getReg() != DepReg) 546 return false; 547 548 const HexagonRegisterInfo *QRI = 549 (const HexagonRegisterInfo *)MF.getSubtarget().getRegisterInfo(); 550 const MCInstrDesc& MCID = PacketMI->getDesc(); 551 // first operand is always the result 552 553 const TargetRegisterClass* PacketRC = QII->getRegClass(MCID, 0, QRI, MF); 554 555 // if there is already an store in the packet, no can do new value store 556 // Arch Spec 3.4.4.2. 557 for (std::vector<MachineInstr*>::iterator VI = CurrentPacketMIs.begin(), 558 VE = CurrentPacketMIs.end(); 559 (VI != VE); ++VI) { 560 SUnit *PacketSU = MIToSUnit.find(*VI)->second; 561 if (PacketSU->getInstr()->getDesc().mayStore() || 562 // if we have mayStore = 1 set on ALLOCFRAME and DEALLOCFRAME, 563 // then we don't need this 564 PacketSU->getInstr()->getOpcode() == Hexagon::S2_allocframe || 565 PacketSU->getInstr()->getOpcode() == Hexagon::L2_deallocframe) 566 return false; 567 } 568 569 if (PacketRC == &Hexagon::DoubleRegsRegClass) { 570 // new value store constraint: double regs can not feed into new value store 571 // arch spec section: 5.4.2.2 572 return false; 573 } 574 575 // Make sure it's NOT the post increment register that we are going to 576 // new value. 577 if (QII->isPostIncrement(MI) && 578 MI->getDesc().mayStore() && 579 GetPostIncrementOperand(MI, QII).getReg() == DepReg) { 580 return false; 581 } 582 583 if (QII->isPostIncrement(PacketMI) && 584 PacketMI->getDesc().mayLoad() && 585 GetPostIncrementOperand(PacketMI, QII).getReg() == DepReg) { 586 // if source is post_inc, or absolute-set addressing, 587 // it can not feed into new value store 588 // r3 = memw(r2++#4) 589 // memw(r30 + #-1404) = r2.new -> can not be new value store 590 // arch spec section: 5.4.2.1 591 return false; 592 } 593 594 // If the source that feeds the store is predicated, new value store must 595 // also be predicated. 596 if (QII->isPredicated(PacketMI)) { 597 if (!QII->isPredicated(MI)) 598 return false; 599 600 // Check to make sure that they both will have their predicates 601 // evaluate identically 602 unsigned predRegNumSrc = 0; 603 unsigned predRegNumDst = 0; 604 const TargetRegisterClass* predRegClass = nullptr; 605 606 // Get predicate register used in the source instruction 607 for(unsigned opNum = 0; opNum < PacketMI->getNumOperands(); opNum++) { 608 if ( PacketMI->getOperand(opNum).isReg()) 609 predRegNumSrc = PacketMI->getOperand(opNum).getReg(); 610 predRegClass = QRI->getMinimalPhysRegClass(predRegNumSrc); 611 if (predRegClass == &Hexagon::PredRegsRegClass) { 612 break; 613 } 614 } 615 assert ((predRegClass == &Hexagon::PredRegsRegClass ) && 616 ("predicate register not found in a predicated PacketMI instruction")); 617 618 // Get predicate register used in new-value store instruction 619 for(unsigned opNum = 0; opNum < MI->getNumOperands(); opNum++) { 620 if ( MI->getOperand(opNum).isReg()) 621 predRegNumDst = MI->getOperand(opNum).getReg(); 622 predRegClass = QRI->getMinimalPhysRegClass(predRegNumDst); 623 if (predRegClass == &Hexagon::PredRegsRegClass) { 624 break; 625 } 626 } 627 assert ((predRegClass == &Hexagon::PredRegsRegClass ) && 628 ("predicate register not found in a predicated MI instruction")); 629 630 // New-value register producer and user (store) need to satisfy these 631 // constraints: 632 // 1) Both instructions should be predicated on the same register. 633 // 2) If producer of the new-value register is .new predicated then store 634 // should also be .new predicated and if producer is not .new predicated 635 // then store should not be .new predicated. 636 // 3) Both new-value register producer and user should have same predicate 637 // sense, i.e, either both should be negated or both should be none negated. 638 639 if (( predRegNumDst != predRegNumSrc) || 640 QII->isDotNewInst(PacketMI) != QII->isDotNewInst(MI) || 641 getPredicateSense(MI, QII) != getPredicateSense(PacketMI, QII)) { 642 return false; 643 } 644 } 645 646 // Make sure that other than the new-value register no other store instruction 647 // register has been modified in the same packet. Predicate registers can be 648 // modified by they should not be modified between the producer and the store 649 // instruction as it will make them both conditional on different values. 650 // We already know this to be true for all the instructions before and 651 // including PacketMI. Howerver, we need to perform the check for the 652 // remaining instructions in the packet. 653 654 std::vector<MachineInstr*>::iterator VI; 655 std::vector<MachineInstr*>::iterator VE; 656 unsigned StartCheck = 0; 657 658 for (VI=CurrentPacketMIs.begin(), VE = CurrentPacketMIs.end(); 659 (VI != VE); ++VI) { 660 SUnit *TempSU = MIToSUnit.find(*VI)->second; 661 MachineInstr* TempMI = TempSU->getInstr(); 662 663 // Following condition is true for all the instructions until PacketMI is 664 // reached (StartCheck is set to 0 before the for loop). 665 // StartCheck flag is 1 for all the instructions after PacketMI. 666 if (TempMI != PacketMI && !StartCheck) // start processing only after 667 continue; // encountering PacketMI 668 669 StartCheck = 1; 670 if (TempMI == PacketMI) // We don't want to check PacketMI for dependence 671 continue; 672 673 for(unsigned opNum = 0; opNum < MI->getNumOperands(); opNum++) { 674 if (MI->getOperand(opNum).isReg() && 675 TempSU->getInstr()->modifiesRegister(MI->getOperand(opNum).getReg(), 676 QRI)) 677 return false; 678 } 679 } 680 681 // Make sure that for non-POST_INC stores: 682 // 1. The only use of reg is DepReg and no other registers. 683 // This handles V4 base+index registers. 684 // The following store can not be dot new. 685 // Eg. r0 = add(r0, #3)a 686 // memw(r1+r0<<#2) = r0 687 if (!QII->isPostIncrement(MI) && 688 GetStoreValueOperand(MI).isReg() && 689 GetStoreValueOperand(MI).getReg() == DepReg) { 690 for(unsigned opNum = 0; opNum < MI->getNumOperands()-1; opNum++) { 691 if (MI->getOperand(opNum).isReg() && 692 MI->getOperand(opNum).getReg() == DepReg) { 693 return false; 694 } 695 } 696 // 2. If data definition is because of implicit definition of the register, 697 // do not newify the store. Eg. 698 // %R9<def> = ZXTH %R12, %D6<imp-use>, %R12<imp-def> 699 // STrih_indexed %R8, 2, %R12<kill>; mem:ST2[%scevgep343] 700 for(unsigned opNum = 0; opNum < PacketMI->getNumOperands(); opNum++) { 701 if (PacketMI->getOperand(opNum).isReg() && 702 PacketMI->getOperand(opNum).getReg() == DepReg && 703 PacketMI->getOperand(opNum).isDef() && 704 PacketMI->getOperand(opNum).isImplicit()) { 705 return false; 706 } 707 } 708 } 709 710 // Can be dot new store. 711 return true; 712} 713 714// can this MI to promoted to either 715// new value store or new value jump 716bool HexagonPacketizerList::CanPromoteToNewValue( 717 MachineInstr *MI, SUnit *PacketSU, unsigned DepReg, 718 const std::map<MachineInstr *, SUnit *> &MIToSUnit, 719 MachineBasicBlock::iterator &MII) { 720 721 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 722 if (!QII->mayBeNewStore(MI)) 723 return false; 724 725 MachineInstr *PacketMI = PacketSU->getInstr(); 726 727 // Check to see the store can be new value'ed. 728 if (CanPromoteToNewValueStore(MI, PacketMI, DepReg, MIToSUnit)) 729 return true; 730 731 // Check to see the compare/jump can be new value'ed. 732 // This is done as a pass on its own. Don't need to check it here. 733 return false; 734} 735 736// Check to see if an instruction can be dot new 737// There are three kinds. 738// 1. dot new on predicate - V2/V3/V4 739// 2. dot new on stores NV/ST - V4 740// 3. dot new on jump NV/J - V4 -- This is generated in a pass. 741bool HexagonPacketizerList::CanPromoteToDotNew( 742 MachineInstr *MI, SUnit *PacketSU, unsigned DepReg, 743 const std::map<MachineInstr *, SUnit *> &MIToSUnit, 744 MachineBasicBlock::iterator &MII, const TargetRegisterClass *RC) { 745 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 746 // Already a dot new instruction. 747 if (QII->isDotNewInst(MI) && !QII->mayBeNewStore(MI)) 748 return false; 749 750 if (!isNewifiable(MI)) 751 return false; 752 753 // predicate .new 754 if (RC == &Hexagon::PredRegsRegClass && isCondInst(MI)) 755 return true; 756 else if (RC != &Hexagon::PredRegsRegClass && 757 !QII->mayBeNewStore(MI)) // MI is not a new-value store 758 return false; 759 else { 760 // Create a dot new machine instruction to see if resources can be 761 // allocated. If not, bail out now. 762 int NewOpcode = QII->GetDotNewOp(MI); 763 const MCInstrDesc &desc = QII->get(NewOpcode); 764 DebugLoc dl; 765 MachineInstr *NewMI = 766 MI->getParent()->getParent()->CreateMachineInstr(desc, dl); 767 bool ResourcesAvailable = ResourceTracker->canReserveResources(NewMI); 768 MI->getParent()->getParent()->DeleteMachineInstr(NewMI); 769 770 if (!ResourcesAvailable) 771 return false; 772 773 // new value store only 774 // new new value jump generated as a passes 775 if (!CanPromoteToNewValue(MI, PacketSU, DepReg, MIToSUnit, MII)) { 776 return false; 777 } 778 } 779 return true; 780} 781 782// Go through the packet instructions and search for anti dependency 783// between them and DepReg from MI 784// Consider this case: 785// Trying to add 786// a) %R1<def> = TFRI_cdNotPt %P3, 2 787// to this packet: 788// { 789// b) %P0<def> = OR_pp %P3<kill>, %P0<kill> 790// c) %P3<def> = TFR_PdRs %R23 791// d) %R1<def> = TFRI_cdnPt %P3, 4 792// } 793// The P3 from a) and d) will be complements after 794// a)'s P3 is converted to .new form 795// Anti Dep between c) and b) is irrelevant for this case 796bool HexagonPacketizerList::RestrictingDepExistInPacket( 797 MachineInstr *MI, unsigned DepReg, 798 const std::map<MachineInstr *, SUnit *> &MIToSUnit) { 799 800 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 801 SUnit *PacketSUDep = MIToSUnit.find(MI)->second; 802 803 for (std::vector<MachineInstr*>::iterator VIN = CurrentPacketMIs.begin(), 804 VEN = CurrentPacketMIs.end(); (VIN != VEN); ++VIN) { 805 806 // We only care for dependencies to predicated instructions 807 if(!QII->isPredicated(*VIN)) continue; 808 809 // Scheduling Unit for current insn in the packet 810 SUnit *PacketSU = MIToSUnit.find(*VIN)->second; 811 812 // Look at dependencies between current members of the packet 813 // and predicate defining instruction MI. 814 // Make sure that dependency is on the exact register 815 // we care about. 816 if (PacketSU->isSucc(PacketSUDep)) { 817 for (unsigned i = 0; i < PacketSU->Succs.size(); ++i) { 818 if ((PacketSU->Succs[i].getSUnit() == PacketSUDep) && 819 (PacketSU->Succs[i].getKind() == SDep::Anti) && 820 (PacketSU->Succs[i].getReg() == DepReg)) { 821 return true; 822 } 823 } 824 } 825 } 826 827 return false; 828} 829 830 831/// Gets the predicate register of a predicated instruction. 832static unsigned getPredicatedRegister(MachineInstr *MI, 833 const HexagonInstrInfo *QII) { 834 /// We use the following rule: The first predicate register that is a use is 835 /// the predicate register of a predicated instruction. 836 837 assert(QII->isPredicated(MI) && "Must be predicated instruction"); 838 839 for (MachineInstr::mop_iterator OI = MI->operands_begin(), 840 OE = MI->operands_end(); OI != OE; ++OI) { 841 MachineOperand &Op = *OI; 842 if (Op.isReg() && Op.getReg() && Op.isUse() && 843 Hexagon::PredRegsRegClass.contains(Op.getReg())) 844 return Op.getReg(); 845 } 846 847 llvm_unreachable("Unknown instruction operand layout"); 848 849 return 0; 850} 851 852// Given two predicated instructions, this function detects whether 853// the predicates are complements 854bool HexagonPacketizerList::ArePredicatesComplements( 855 MachineInstr *MI1, MachineInstr *MI2, 856 const std::map<MachineInstr *, SUnit *> &MIToSUnit) { 857 858 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 859 860 // If we don't know the predicate sense of the instructions bail out early, we 861 // need it later. 862 if (getPredicateSense(MI1, QII) == PK_Unknown || 863 getPredicateSense(MI2, QII) == PK_Unknown) 864 return false; 865 866 // Scheduling unit for candidate 867 SUnit *SU = MIToSUnit.find(MI1)->second; 868 869 // One corner case deals with the following scenario: 870 // Trying to add 871 // a) %R24<def> = TFR_cPt %P0, %R25 872 // to this packet: 873 // 874 // { 875 // b) %R25<def> = TFR_cNotPt %P0, %R24 876 // c) %P0<def> = CMPEQri %R26, 1 877 // } 878 // 879 // On general check a) and b) are complements, but 880 // presence of c) will convert a) to .new form, and 881 // then it is not a complement 882 // We attempt to detect it by analyzing existing 883 // dependencies in the packet 884 885 // Analyze relationships between all existing members of the packet. 886 // Look for Anti dependecy on the same predicate reg 887 // as used in the candidate 888 for (std::vector<MachineInstr*>::iterator VIN = CurrentPacketMIs.begin(), 889 VEN = CurrentPacketMIs.end(); (VIN != VEN); ++VIN) { 890 891 // Scheduling Unit for current insn in the packet 892 SUnit *PacketSU = MIToSUnit.find(*VIN)->second; 893 894 // If this instruction in the packet is succeeded by the candidate... 895 if (PacketSU->isSucc(SU)) { 896 for (unsigned i = 0; i < PacketSU->Succs.size(); ++i) { 897 // The corner case exist when there is true data 898 // dependency between candidate and one of current 899 // packet members, this dep is on predicate reg, and 900 // there already exist anti dep on the same pred in 901 // the packet. 902 if (PacketSU->Succs[i].getSUnit() == SU && 903 PacketSU->Succs[i].getKind() == SDep::Data && 904 Hexagon::PredRegsRegClass.contains( 905 PacketSU->Succs[i].getReg()) && 906 // Here I know that *VIN is predicate setting instruction 907 // with true data dep to candidate on the register 908 // we care about - c) in the above example. 909 // Now I need to see if there is an anti dependency 910 // from c) to any other instruction in the 911 // same packet on the pred reg of interest 912 RestrictingDepExistInPacket(*VIN,PacketSU->Succs[i].getReg(), 913 MIToSUnit)) { 914 return false; 915 } 916 } 917 } 918 } 919 920 // If the above case does not apply, check regular 921 // complement condition. 922 // Check that the predicate register is the same and 923 // that the predicate sense is different 924 // We also need to differentiate .old vs. .new: 925 // !p0 is not complimentary to p0.new 926 unsigned PReg1 = getPredicatedRegister(MI1, QII); 927 unsigned PReg2 = getPredicatedRegister(MI2, QII); 928 return ((PReg1 == PReg2) && 929 Hexagon::PredRegsRegClass.contains(PReg1) && 930 Hexagon::PredRegsRegClass.contains(PReg2) && 931 (getPredicateSense(MI1, QII) != getPredicateSense(MI2, QII)) && 932 (QII->isDotNewInst(MI1) == QII->isDotNewInst(MI2))); 933} 934 935// initPacketizerState - Initialize packetizer flags 936void HexagonPacketizerList::initPacketizerState() { 937 938 Dependence = false; 939 PromotedToDotNew = false; 940 GlueToNewValueJump = false; 941 GlueAllocframeStore = false; 942 FoundSequentialDependence = false; 943 944 return; 945} 946 947// ignorePseudoInstruction - Ignore bundling of pseudo instructions. 948bool HexagonPacketizerList::ignorePseudoInstruction(MachineInstr *MI, 949 MachineBasicBlock *MBB) { 950 if (MI->isDebugValue()) 951 return true; 952 953 // We must print out inline assembly 954 if (MI->isInlineAsm()) 955 return false; 956 957 // We check if MI has any functional units mapped to it. 958 // If it doesn't, we ignore the instruction. 959 const MCInstrDesc& TID = MI->getDesc(); 960 unsigned SchedClass = TID.getSchedClass(); 961 const InstrStage* IS = 962 ResourceTracker->getInstrItins()->beginStage(SchedClass); 963 unsigned FuncUnits = IS->getUnits(); 964 return !FuncUnits; 965} 966 967// isSoloInstruction: - Returns true for instructions that must be 968// scheduled in their own packet. 969bool HexagonPacketizerList::isSoloInstruction(MachineInstr *MI) { 970 971 if (MI->isInlineAsm()) 972 return true; 973 974 if (MI->isEHLabel()) 975 return true; 976 977 // From Hexagon V4 Programmer's Reference Manual 3.4.4 Grouping constraints: 978 // trap, pause, barrier, icinva, isync, and syncht are solo instructions. 979 // They must not be grouped with other instructions in a packet. 980 if (IsSchedBarrier(MI)) 981 return true; 982 983 return false; 984} 985 986// isLegalToPacketizeTogether: 987// SUI is the current instruction that is out side of the current packet. 988// SUJ is the current instruction inside the current packet against which that 989// SUI will be packetized. 990bool HexagonPacketizerList::isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) { 991 MachineInstr *I = SUI->getInstr(); 992 MachineInstr *J = SUJ->getInstr(); 993 assert(I && J && "Unable to packetize null instruction!"); 994 995 const MCInstrDesc &MCIDI = I->getDesc(); 996 const MCInstrDesc &MCIDJ = J->getDesc(); 997 998 MachineBasicBlock::iterator II = I; 999 1000 const unsigned FrameSize = MF.getFrameInfo()->getStackSize(); 1001 const HexagonRegisterInfo *QRI = 1002 (const HexagonRegisterInfo *)MF.getSubtarget().getRegisterInfo(); 1003 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 1004 1005 // Inline asm cannot go in the packet. 1006 if (I->getOpcode() == Hexagon::INLINEASM) 1007 llvm_unreachable("Should not meet inline asm here!"); 1008 1009 if (isSoloInstruction(I)) 1010 llvm_unreachable("Should not meet solo instr here!"); 1011 1012 // A save callee-save register function call can only be in a packet 1013 // with instructions that don't write to the callee-save registers. 1014 if ((QII->isSaveCalleeSavedRegsCall(I) && 1015 DoesModifyCalleeSavedReg(J, QRI)) || 1016 (QII->isSaveCalleeSavedRegsCall(J) && 1017 DoesModifyCalleeSavedReg(I, QRI))) { 1018 Dependence = true; 1019 return false; 1020 } 1021 1022 // Two control flow instructions cannot go in the same packet. 1023 if (IsControlFlow(I) && IsControlFlow(J)) { 1024 Dependence = true; 1025 return false; 1026 } 1027 1028 // A LoopN instruction cannot appear in the same packet as a jump or call. 1029 if (IsLoopN(I) && 1030 (IsDirectJump(J) || MCIDJ.isCall() || QII->isDeallocRet(J))) { 1031 Dependence = true; 1032 return false; 1033 } 1034 if (IsLoopN(J) && 1035 (IsDirectJump(I) || MCIDI.isCall() || QII->isDeallocRet(I))) { 1036 Dependence = true; 1037 return false; 1038 } 1039 1040 // dealloc_return cannot appear in the same packet as a conditional or 1041 // unconditional jump. 1042 if (QII->isDeallocRet(I) && 1043 (MCIDJ.isBranch() || MCIDJ.isCall() || MCIDJ.isBarrier())) { 1044 Dependence = true; 1045 return false; 1046 } 1047 1048 1049 // V4 allows dual store. But does not allow second store, if the 1050 // first store is not in SLOT0. New value store, new value jump, 1051 // dealloc_return and memop always take SLOT0. 1052 // Arch spec 3.4.4.2 1053 if (MCIDI.mayStore() && MCIDJ.mayStore() && 1054 (QII->isNewValueInst(J) || QII->isMemOp(J) || QII->isMemOp(I))) { 1055 Dependence = true; 1056 return false; 1057 } 1058 1059 if ((QII->isMemOp(J) && MCIDI.mayStore()) 1060 || (MCIDJ.mayStore() && QII->isMemOp(I)) 1061 || (QII->isMemOp(J) && QII->isMemOp(I))) { 1062 Dependence = true; 1063 return false; 1064 } 1065 1066 //if dealloc_return 1067 if (MCIDJ.mayStore() && QII->isDeallocRet(I)) { 1068 Dependence = true; 1069 return false; 1070 } 1071 1072 // If an instruction feeds new value jump, glue it. 1073 MachineBasicBlock::iterator NextMII = I; 1074 ++NextMII; 1075 if (NextMII != I->getParent()->end() && QII->isNewValueJump(NextMII)) { 1076 MachineInstr *NextMI = NextMII; 1077 1078 bool secondRegMatch = false; 1079 bool maintainNewValueJump = false; 1080 1081 if (NextMI->getOperand(1).isReg() && 1082 I->getOperand(0).getReg() == NextMI->getOperand(1).getReg()) { 1083 secondRegMatch = true; 1084 maintainNewValueJump = true; 1085 } 1086 1087 if (!secondRegMatch && 1088 I->getOperand(0).getReg() == NextMI->getOperand(0).getReg()) { 1089 maintainNewValueJump = true; 1090 } 1091 1092 for (std::vector<MachineInstr*>::iterator 1093 VI = CurrentPacketMIs.begin(), 1094 VE = CurrentPacketMIs.end(); 1095 (VI != VE && maintainNewValueJump); ++VI) { 1096 SUnit *PacketSU = MIToSUnit.find(*VI)->second; 1097 1098 // NVJ can not be part of the dual jump - Arch Spec: section 7.8 1099 if (PacketSU->getInstr()->getDesc().isCall()) { 1100 Dependence = true; 1101 break; 1102 } 1103 // Validate 1104 // 1. Packet does not have a store in it. 1105 // 2. If the first operand of the nvj is newified, and the second 1106 // operand is also a reg, it (second reg) is not defined in 1107 // the same packet. 1108 // 3. If the second operand of the nvj is newified, (which means 1109 // first operand is also a reg), first reg is not defined in 1110 // the same packet. 1111 if (PacketSU->getInstr()->getDesc().mayStore() || 1112 PacketSU->getInstr()->getOpcode() == Hexagon::S2_allocframe || 1113 // Check #2. 1114 (!secondRegMatch && NextMI->getOperand(1).isReg() && 1115 PacketSU->getInstr()->modifiesRegister( 1116 NextMI->getOperand(1).getReg(), QRI)) || 1117 // Check #3. 1118 (secondRegMatch && 1119 PacketSU->getInstr()->modifiesRegister( 1120 NextMI->getOperand(0).getReg(), QRI))) { 1121 Dependence = true; 1122 break; 1123 } 1124 } 1125 if (!Dependence) 1126 GlueToNewValueJump = true; 1127 else 1128 return false; 1129 } 1130 1131 if (SUJ->isSucc(SUI)) { 1132 for (unsigned i = 0; 1133 (i < SUJ->Succs.size()) && !FoundSequentialDependence; 1134 ++i) { 1135 1136 if (SUJ->Succs[i].getSUnit() != SUI) { 1137 continue; 1138 } 1139 1140 SDep::Kind DepType = SUJ->Succs[i].getKind(); 1141 1142 // For direct calls: 1143 // Ignore register dependences for call instructions for 1144 // packetization purposes except for those due to r31 and 1145 // predicate registers. 1146 // 1147 // For indirect calls: 1148 // Same as direct calls + check for true dependences to the register 1149 // used in the indirect call. 1150 // 1151 // We completely ignore Order dependences for call instructions 1152 // 1153 // For returns: 1154 // Ignore register dependences for return instructions like jumpr, 1155 // dealloc return unless we have dependencies on the explicit uses 1156 // of the registers used by jumpr (like r31) or dealloc return 1157 // (like r29 or r30). 1158 // 1159 // TODO: Currently, jumpr is handling only return of r31. So, the 1160 // following logic (specificaly IsCallDependent) is working fine. 1161 // We need to enable jumpr for register other than r31 and then, 1162 // we need to rework the last part, where it handles indirect call 1163 // of that (IsCallDependent) function. Bug 6216 is opened for this. 1164 // 1165 unsigned DepReg = 0; 1166 const TargetRegisterClass* RC = nullptr; 1167 if (DepType == SDep::Data) { 1168 DepReg = SUJ->Succs[i].getReg(); 1169 RC = QRI->getMinimalPhysRegClass(DepReg); 1170 } 1171 if ((MCIDI.isCall() || MCIDI.isReturn()) && 1172 (!IsRegDependence(DepType) || 1173 !IsCallDependent(I, DepType, SUJ->Succs[i].getReg()))) { 1174 /* do nothing */ 1175 } 1176 1177 // For instructions that can be promoted to dot-new, try to promote. 1178 else if ((DepType == SDep::Data) && 1179 CanPromoteToDotNew(I, SUJ, DepReg, MIToSUnit, II, RC) && 1180 PromoteToDotNew(I, DepType, II, RC)) { 1181 PromotedToDotNew = true; 1182 /* do nothing */ 1183 } 1184 1185 else if ((DepType == SDep::Data) && 1186 (QII->isNewValueJump(I))) { 1187 /* do nothing */ 1188 } 1189 1190 // For predicated instructions, if the predicates are complements 1191 // then there can be no dependence. 1192 else if (QII->isPredicated(I) && 1193 QII->isPredicated(J) && 1194 ArePredicatesComplements(I, J, MIToSUnit)) { 1195 /* do nothing */ 1196 1197 } 1198 else if (IsDirectJump(I) && 1199 !MCIDJ.isBranch() && 1200 !MCIDJ.isCall() && 1201 (DepType == SDep::Order)) { 1202 // Ignore Order dependences between unconditional direct branches 1203 // and non-control-flow instructions 1204 /* do nothing */ 1205 } 1206 else if (MCIDI.isConditionalBranch() && (DepType != SDep::Data) && 1207 (DepType != SDep::Output)) { 1208 // Ignore all dependences for jumps except for true and output 1209 // dependences 1210 /* do nothing */ 1211 } 1212 1213 // Ignore output dependences due to superregs. We can 1214 // write to two different subregisters of R1:0 for instance 1215 // in the same cycle 1216 // 1217 1218 // 1219 // Let the 1220 // If neither I nor J defines DepReg, then this is a 1221 // superfluous output dependence. The dependence must be of the 1222 // form: 1223 // R0 = ... 1224 // R1 = ... 1225 // and there is an output dependence between the two instructions 1226 // with 1227 // DepReg = D0 1228 // We want to ignore these dependences. 1229 // Ideally, the dependence constructor should annotate such 1230 // dependences. We can then avoid this relatively expensive check. 1231 // 1232 else if (DepType == SDep::Output) { 1233 // DepReg is the register that's responsible for the dependence. 1234 unsigned DepReg = SUJ->Succs[i].getReg(); 1235 1236 // Check if I and J really defines DepReg. 1237 if (I->definesRegister(DepReg) || 1238 J->definesRegister(DepReg)) { 1239 FoundSequentialDependence = true; 1240 break; 1241 } 1242 } 1243 1244 // We ignore Order dependences for 1245 // 1. Two loads unless they are volatile. 1246 // 2. Two stores in V4 unless they are volatile. 1247 else if ((DepType == SDep::Order) && 1248 !I->hasOrderedMemoryRef() && 1249 !J->hasOrderedMemoryRef()) { 1250 if (MCIDI.mayStore() && MCIDJ.mayStore()) { 1251 /* do nothing */ 1252 } 1253 // store followed by store-- not OK on V2 1254 // store followed by load -- not OK on all (OK if addresses 1255 // are not aliased) 1256 // load followed by store -- OK on all 1257 // load followed by load -- OK on all 1258 else if ( !MCIDJ.mayStore()) { 1259 /* do nothing */ 1260 } 1261 else { 1262 FoundSequentialDependence = true; 1263 break; 1264 } 1265 } 1266 1267 // For V4, special case ALLOCFRAME. Even though there is dependency 1268 // between ALLOCFRAME and subsequent store, allow it to be 1269 // packetized in a same packet. This implies that the store is using 1270 // caller's SP. Hence, offset needs to be updated accordingly. 1271 else if (DepType == SDep::Data 1272 && J->getOpcode() == Hexagon::S2_allocframe 1273 && (I->getOpcode() == Hexagon::S2_storerd_io 1274 || I->getOpcode() == Hexagon::S2_storeri_io 1275 || I->getOpcode() == Hexagon::S2_storerb_io) 1276 && I->getOperand(0).getReg() == QRI->getStackRegister() 1277 && QII->isValidOffset(I->getOpcode(), 1278 I->getOperand(1).getImm() - 1279 (FrameSize + HEXAGON_LRFP_SIZE))) 1280 { 1281 GlueAllocframeStore = true; 1282 // Since this store is to be glued with allocframe in the same 1283 // packet, it will use SP of the previous stack frame, i.e 1284 // caller's SP. Therefore, we need to recalculate offset according 1285 // to this change. 1286 I->getOperand(1).setImm(I->getOperand(1).getImm() - 1287 (FrameSize + HEXAGON_LRFP_SIZE)); 1288 } 1289 1290 // 1291 // Skip over anti-dependences. Two instructions that are 1292 // anti-dependent can share a packet 1293 // 1294 else if (DepType != SDep::Anti) { 1295 FoundSequentialDependence = true; 1296 break; 1297 } 1298 } 1299 1300 if (FoundSequentialDependence) { 1301 Dependence = true; 1302 return false; 1303 } 1304 } 1305 1306 return true; 1307} 1308 1309// isLegalToPruneDependencies 1310bool HexagonPacketizerList::isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) { 1311 MachineInstr *I = SUI->getInstr(); 1312 assert(I && SUJ->getInstr() && "Unable to packetize null instruction!"); 1313 1314 const unsigned FrameSize = MF.getFrameInfo()->getStackSize(); 1315 1316 if (Dependence) { 1317 1318 // Check if the instruction was promoted to a dot-new. If so, demote it 1319 // back into a dot-old. 1320 if (PromotedToDotNew) { 1321 DemoteToDotOld(I); 1322 } 1323 1324 // Check if the instruction (must be a store) was glued with an Allocframe 1325 // instruction. If so, restore its offset to its original value, i.e. use 1326 // curent SP instead of caller's SP. 1327 if (GlueAllocframeStore) { 1328 I->getOperand(1).setImm(I->getOperand(1).getImm() + 1329 FrameSize + HEXAGON_LRFP_SIZE); 1330 } 1331 1332 return false; 1333 } 1334 return true; 1335} 1336 1337MachineBasicBlock::iterator 1338HexagonPacketizerList::addToPacket(MachineInstr *MI) { 1339 1340 MachineBasicBlock::iterator MII = MI; 1341 MachineBasicBlock *MBB = MI->getParent(); 1342 1343 const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII; 1344 1345 if (GlueToNewValueJump) { 1346 1347 ++MII; 1348 MachineInstr *nvjMI = MII; 1349 assert(ResourceTracker->canReserveResources(MI)); 1350 ResourceTracker->reserveResources(MI); 1351 if ((QII->isExtended(MI) || QII->isConstExtended(MI)) && 1352 !tryAllocateResourcesForConstExt(MI)) { 1353 endPacket(MBB, MI); 1354 ResourceTracker->reserveResources(MI); 1355 assert(canReserveResourcesForConstExt(MI) && 1356 "Ensure that there is a slot"); 1357 reserveResourcesForConstExt(MI); 1358 // Reserve resources for new value jump constant extender. 1359 assert(canReserveResourcesForConstExt(MI) && 1360 "Ensure that there is a slot"); 1361 reserveResourcesForConstExt(nvjMI); 1362 assert(ResourceTracker->canReserveResources(nvjMI) && 1363 "Ensure that there is a slot"); 1364 1365 } else if ( // Extended instruction takes two slots in the packet. 1366 // Try reserve and allocate 4-byte in the current packet first. 1367 (QII->isExtended(nvjMI) 1368 && (!tryAllocateResourcesForConstExt(nvjMI) 1369 || !ResourceTracker->canReserveResources(nvjMI))) 1370 || // For non-extended instruction, no need to allocate extra 4 bytes. 1371 (!QII->isExtended(nvjMI) && 1372 !ResourceTracker->canReserveResources(nvjMI))) 1373 { 1374 endPacket(MBB, MI); 1375 // A new and empty packet starts. 1376 // We are sure that the resources requirements can be satisfied. 1377 // Therefore, do not need to call "canReserveResources" anymore. 1378 ResourceTracker->reserveResources(MI); 1379 if (QII->isExtended(nvjMI)) 1380 reserveResourcesForConstExt(nvjMI); 1381 } 1382 // Here, we are sure that "reserveResources" would succeed. 1383 ResourceTracker->reserveResources(nvjMI); 1384 CurrentPacketMIs.push_back(MI); 1385 CurrentPacketMIs.push_back(nvjMI); 1386 } else { 1387 if ( (QII->isExtended(MI) || QII->isConstExtended(MI)) 1388 && ( !tryAllocateResourcesForConstExt(MI) 1389 || !ResourceTracker->canReserveResources(MI))) 1390 { 1391 endPacket(MBB, MI); 1392 // Check if the instruction was promoted to a dot-new. If so, demote it 1393 // back into a dot-old 1394 if (PromotedToDotNew) { 1395 DemoteToDotOld(MI); 1396 } 1397 reserveResourcesForConstExt(MI); 1398 } 1399 // In case that "MI" is not an extended insn, 1400 // the resource availability has already been checked. 1401 ResourceTracker->reserveResources(MI); 1402 CurrentPacketMIs.push_back(MI); 1403 } 1404 return MII; 1405} 1406 1407//===----------------------------------------------------------------------===// 1408// Public Constructor Functions 1409//===----------------------------------------------------------------------===// 1410 1411FunctionPass *llvm::createHexagonPacketizer() { 1412 return new HexagonPacketizer(); 1413} 1414 1415