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