ScheduleDAGInstrs.cpp revision 10343d91c52ddbfd7572032a95724f0c1ba10c7b
1d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák//===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===// 2d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák// 3d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák// The LLVM Compiler Infrastructure 4d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák// 5d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák// This file is distributed under the University of Illinois Open Source 6d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák// License. See LICENSE.TXT for details. 7d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák// 8d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák//===----------------------------------------------------------------------===// 9d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák// 10d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák// This implements the ScheduleDAGInstrs class, which implements re-scheduling 11d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák// of MachineInstrs. 12d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák// 13d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák//===----------------------------------------------------------------------===// 14d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 15d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#define DEBUG_TYPE "sched-instrs" 16d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "ScheduleDAGInstrs.h" 17d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/Operator.h" 18d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/Analysis/AliasAnalysis.h" 19d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/CodeGen/MachineFunctionPass.h" 20d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/CodeGen/MachineMemOperand.h" 21d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/CodeGen/MachineRegisterInfo.h" 22d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/CodeGen/PseudoSourceValue.h" 23d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/Target/TargetMachine.h" 24d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/Target/TargetInstrInfo.h" 25d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/Target/TargetRegisterInfo.h" 26d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/Target/TargetSubtarget.h" 27d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/Support/Debug.h" 28d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/Support/raw_ostream.h" 29d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák#include "llvm/ADT/SmallSet.h" 30d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšákusing namespace llvm; 31d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 32d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek OlšákScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, 33d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák const MachineLoopInfo &mli, 34d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák const MachineDominatorTree &mdt) 35d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie : ScheduleDAG(mf), MLI(mli), MDT(mdt), LoopRegs(MLI, MDT) { 36d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák MFI = mf.getFrameInfo(); 37d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák} 38d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 39d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák/// Run - perform scheduling. 40d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák/// 41d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšákvoid ScheduleDAGInstrs::Run(MachineBasicBlock *bb, 42d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák MachineBasicBlock::iterator begin, 43d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák MachineBasicBlock::iterator end, 44d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák unsigned endcount) { 45d0408cf55d9e8d1d376bd844386ef5c9789a3597Marek Olšák BB = bb; 46d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák Begin = begin; 47d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák InsertPosIndex = endcount; 48d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 49d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák ScheduleDAG::Run(bb, end); 50d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák} 51d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 52d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák/// getUnderlyingObjectFromInt - This is the function that does the work of 53d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák/// looking through basic ptrtoint+arithmetic+inttoptr sequences. 54d0408cf55d9e8d1d376bd844386ef5c9789a3597Marek Olšákstatic const Value *getUnderlyingObjectFromInt(const Value *V) { 55d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák do { 56d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (const Operator *U = dyn_cast<Operator>(V)) { 57d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // If we find a ptrtoint, we can transfer control back to the 58d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie // regular getUnderlyingObjectFromInt. 59d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (U->getOpcode() == Instruction::PtrToInt) 60d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák return U->getOperand(0); 61d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // If we find an add of a constant or a multiplied value, it's 62d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // likely that the other operand will lead us to the base 63d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák // object. We don't have to worry about the case where the 64d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák // object address is somehow being computed by the multiply, 65d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // because our callers only care when the result is an 66d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // identifibale object. 67d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (U->getOpcode() != Instruction::Add || 68d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák (!isa<ConstantInt>(U->getOperand(1)) && 69d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák Operator::getOpcode(U->getOperand(1)) != Instruction::Mul)) 70d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák return V; 71d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák V = U->getOperand(0); 72d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } else { 73d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák return V; 74d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 75d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák assert(V->getType()->isIntegerTy() && "Unexpected operand type!"); 76d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie } while (1); 77d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie} 78d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie 79d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie/// getUnderlyingObject - This is a wrapper around Value::getUnderlyingObject 80d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie/// and adds support for basic ptrtoint+arithmetic+inttoptr sequences. 81d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airliestatic const Value *getUnderlyingObject(const Value *V) { 82d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie // First just call Value::getUnderlyingObject to let it do what it does. 83d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie do { 84d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák V = V->getUnderlyingObject(); 85d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // If it found an inttoptr, use special code to continue climing. 86d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (Operator::getOpcode(V) != Instruction::IntToPtr) 87d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák break; 88d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0)); 89d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // If that succeeded in finding a pointer, continue the search. 90d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (!O->getType()->isPointerTy()) 9156ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák break; 92d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák V = O; 93d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } while (1); 94d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák return V; 95d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák} 96d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 97d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák/// getUnderlyingObjectForInstr - If this machine instr has memory reference 98a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák/// information and it can be tracked to a normal reference to a known 99d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák/// object, return the Value for that object. Otherwise return null. 100d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšákstatic const Value *getUnderlyingObjectForInstr(const MachineInstr *MI, 10156ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák const MachineFrameInfo *MFI, 102d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák bool &MayAlias) { 10356ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák MayAlias = true; 104d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (!MI->hasOneMemOperand() || 105d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák !(*MI->memoperands_begin())->getValue() || 106d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák (*MI->memoperands_begin())->isVolatile()) 107d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák return 0; 108d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 109d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák const Value *V = (*MI->memoperands_begin())->getValue(); 110d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (!V) 111d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák return 0; 112d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 113d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák V = getUnderlyingObject(V); 114d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 115d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // For now, ignore PseudoSourceValues which may alias LLVM IR values 116d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // because the code that uses this function has no way to cope with 117d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // such aliases. 118d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (PSV->isAliased(MFI)) 11956ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák return 0; 120d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 121d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák MayAlias = PSV->mayAlias(MFI); 122d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák return V; 123d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie } 124d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie 125d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie if (isIdentifiedObject(V)) 126d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák return V; 12756ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák 12856ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák return 0; 129d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák} 130d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 131a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšákvoid ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) { 132d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (MachineLoop *ML = MLI.getLoopFor(BB)) 133a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák if (BB == ML->getLoopLatch()) { 134d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák MachineBasicBlock *Header = ML->getHeader(); 135d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák for (MachineBasicBlock::livein_iterator I = Header->livein_begin(), 136d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák E = Header->livein_end(); I != E; ++I) 13756ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák LoopLiveInRegs.insert(*I); 138d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák LoopRegs.VisitLoop(ML); 139a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák } 140a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák} 141a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák 14256ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšákvoid ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { 14356ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // We'll be allocating one SUnit for each instruction, plus one for 144d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie // the region exit node. 145d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák SUnits.reserve(BB->size()); 146d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 147a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // We build scheduling units by walking a block's instruction list from bottom 148d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // to top. 149d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 150d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // Remember where a generic side-effecting instruction is as we procede. 151a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák SUnit *BarrierChain = 0, *AliasChain = 0; 152d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 153d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // Memory references to specific known memory locations are tracked 154d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // so that they can be given more precise dependencies. We track 15556ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // separately the known memory locations that may alias and those 156d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // that are known not to alias 157451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs; 158d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses; 159d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 160d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // Check to see if the scheduler cares about latencies. 16156ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák bool UnitLatencies = ForceUnitLatencies(); 162d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 1632d1cc27729bd1808a39b226ae3eda5663328ba74Marek Olšák // Ask the target if address-backscheduling is desirable, and if so how much. 164a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 165a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); 166a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák 167a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // Walk the list of instructions, from bottom moving up. 1682d1cc27729bd1808a39b226ae3eda5663328ba74Marek Olšák for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin; 1692d1cc27729bd1808a39b226ae3eda5663328ba74Marek Olšák MII != MIE; --MII) { 1702d1cc27729bd1808a39b226ae3eda5663328ba74Marek Olšák MachineInstr *MI = prior(MII); 171a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák const TargetInstrDesc &TID = MI->getDesc(); 172a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák assert(!TID.isTerminator() && !MI->isLabel() && 173a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák "Cannot schedule terminators or labels!"); 17456ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // Create the SUnit for this MI. 17556ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák SUnit *SU = NewSUnit(MI); 176d19b5cbd317620f3977e68fffb7a74793436b7e2Dave Airlie 177d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // Assign the Latency field of SU using target-provided information. 178d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (UnitLatencies) 179451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák SU->Latency = 1; 180451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák else 181451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák ComputeLatency(SU); 18256ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák 183451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák // Add register-based dependencies (data, anti, and output). 184451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { 185451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák const MachineOperand &MO = MI->getOperand(j); 186451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák if (!MO.isReg()) continue; 187451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák unsigned Reg = MO.getReg(); 188451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák if (Reg == 0) continue; 189451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák 190a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!"); 191a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák std::vector<SUnit *> &UseList = Uses[Reg]; 192a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák std::vector<SUnit *> &DefList = Defs[Reg]; 193a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // Optionally add output and anti dependencies. For anti 194451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák // dependencies we use a latency of 0 because for a multi-issue 195451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák // target we want to allow the defining instruction to issue 196451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák // in the same cycle as the using instruction. 197451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák // TODO: Using a latency of 1 here for output dependencies assumes 198451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák // there's no cost for reusing registers. 199451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output; 200451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák unsigned AOLatency = (Kind == SDep::Anti) ? 0 : 1; 201451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 202d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák SUnit *DefSU = DefList[i]; 203d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (DefSU != SU && 204d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák (Kind != SDep::Output || !MO.isDead() || 205a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák !DefSU->getInstr()->registerDefIsDead(Reg))) 206d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/Reg)); 207d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 208c92d232061c1aef6f5f56cbd815625778db2fd8cMarek Olšák for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 209ce9d61fec64138ebf8d0bec2511e66593297b7d5Marek Olšák std::vector<SUnit *> &DefList = Defs[*Alias]; 210ce9d61fec64138ebf8d0bec2511e66593297b7d5Marek Olšák for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 211c92d232061c1aef6f5f56cbd815625778db2fd8cMarek Olšák SUnit *DefSU = DefList[i]; 212c92d232061c1aef6f5f56cbd815625778db2fd8cMarek Olšák if (DefSU != SU && 213c92d232061c1aef6f5f56cbd815625778db2fd8cMarek Olšák (Kind != SDep::Output || !MO.isDead() || 214c92d232061c1aef6f5f56cbd815625778db2fd8cMarek Olšák !DefSU->getInstr()->registerDefIsDead(*Alias))) 215c92d232061c1aef6f5f56cbd815625778db2fd8cMarek Olšák DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/ *Alias)); 216d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 21756ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák } 218451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák 219d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (MO.isDef()) { 220a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // Add any data dependencies. 221d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák unsigned DataLatency = SU->Latency; 222311ab3d468ea5291c10bd5cada9b77a528fb7b7fMarek Olšák for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 223451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák SUnit *UseSU = UseList[i]; 224451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák if (UseSU != SU) { 22556ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák unsigned LDataLatency = DataLatency; 226d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // Optionally add in a special extra latency for nodes that 227d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // feed addresses. 228d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // TODO: Do this for register aliases too. 229d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // TODO: Perhaps we should get rid of 230d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // SpecialAddressLatency and just move this into 231d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // adjustSchedDependency for the targets that care about 232d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // it. 23356ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák if (SpecialAddressLatency != 0 && !UnitLatencies) { 234d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák MachineInstr *UseMI = UseSU->getInstr(); 23556ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák const TargetInstrDesc &UseTID = UseMI->getDesc(); 23656ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák int RegUseIndex = UseMI->findRegisterUseOperandIdx(Reg); 237d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák assert(RegUseIndex >= 0 && "UseMI doesn's use register!"); 238d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if ((UseTID.mayLoad() || UseTID.mayStore()) && 23956ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák (unsigned)RegUseIndex < UseTID.getNumOperands() && 240451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák UseTID.OpInfo[RegUseIndex].isLookupPtrRegClass()) 241451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák LDataLatency += SpecialAddressLatency; 242451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák } 243451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák // Adjust the dependence latency using operand def/use 24456ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // information (if any), and then allow the target to 24556ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // perform its own adjustments. 246451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák const SDep& dep = SDep(SU, SDep::Data, LDataLatency, Reg); 24756ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák if (!UnitLatencies) { 248451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák ComputeOperandLatency(SU, UseSU, (SDep &)dep); 249d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák ST.adjustSchedDependency(SU, UseSU, (SDep &)dep); 250d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 251d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák UseSU->addPred(dep); 252d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 253d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 254d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 255d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák std::vector<SUnit *> &UseList = Uses[*Alias]; 256d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 257d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák SUnit *UseSU = UseList[i]; 25856ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák if (UseSU != SU) { 259d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák const SDep& dep = SDep(SU, SDep::Data, DataLatency, *Alias); 26056ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák if (!UnitLatencies) { 26156ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák ComputeOperandLatency(SU, UseSU, (SDep &)dep); 26256ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák ST.adjustSchedDependency(SU, UseSU, (SDep &)dep); 26356ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák } 26456ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák UseSU->addPred(dep); 265d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 266d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 267d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 26856ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák 26956ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // If a def is going to wrap back around to the top of the loop, 27056ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // backschedule it. 271d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (!UnitLatencies && DefList.empty()) { 272d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(Reg); 273d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (I != LoopRegs.Deps.end()) { 27456ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák const MachineOperand *UseMO = I->second.first; 275d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák unsigned Count = I->second.second; 27656ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák const MachineInstr *UseMI = UseMO->getParent(); 277a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák unsigned UseMOIdx = UseMO - &UseMI->getOperand(0); 27856ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák const TargetInstrDesc &UseTID = UseMI->getDesc(); 279a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // TODO: If we knew the total depth of the region here, we could 280a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // handle the case where the whole loop is inside the region but 28156ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // is large enough that the isScheduleHigh trick isn't needed. 28256ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák if (UseMOIdx < UseTID.getNumOperands()) { 28356ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // Currently, we only support scheduling regions consisting of 284a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // single basic blocks. Check to see if the instruction is in 285a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // the same region by checking to see if it has the same parent. 286d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (UseMI->getParent() != MI->getParent()) { 287d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák unsigned Latency = SU->Latency; 288d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) 28956ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák Latency += SpecialAddressLatency; 290d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // This is a wild guess as to the portion of the latency which 291d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // will be overlapped by work done outside the current 292d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // scheduling region. 293d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák Latency -= std::min(Latency, Count); 294a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // Add the artifical edge. 295d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák ExitSU.addPred(SDep(SU, SDep::Order, Latency, 296d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák /*Reg=*/0, /*isNormalMemory=*/false, 297d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák /*isMustAlias=*/false, 298d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák /*isArtificial=*/true)); 299d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } else if (SpecialAddressLatency > 0 && 300a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) { 301d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // The entire loop body is within the current scheduling region 30256ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // and the latency of this operation is assumed to be greater 303d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // than the latency of the loop. 304ab7cc445801b99a4482ea50429ceea1d0601a221Marek Olšák // TODO: Recursively mark data-edge predecessors as 305ab7cc445801b99a4482ea50429ceea1d0601a221Marek Olšák // isScheduleHigh too. 306ab7cc445801b99a4482ea50429ceea1d0601a221Marek Olšák SU->isScheduleHigh = true; 307a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák } 30856ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák } 309d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák LoopRegs.Deps.erase(I); 310d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 311d99ec708afbb785ce05031661222b38c9447059fMarek Olšák } 312d99ec708afbb785ce05031661222b38c9447059fMarek Olšák 313d99ec708afbb785ce05031661222b38c9447059fMarek Olšák UseList.clear(); 314d99ec708afbb785ce05031661222b38c9447059fMarek Olšák if (!MO.isDead()) 315b6c9c78bffe35d0ca9af100a1595412a1e06bd33Nicolas Peninguy DefList.clear(); 316d99ec708afbb785ce05031661222b38c9447059fMarek Olšák DefList.push_back(SU); 3172050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák } else { 318d99ec708afbb785ce05031661222b38c9447059fMarek Olšák UseList.push_back(SU); 319d99ec708afbb785ce05031661222b38c9447059fMarek Olšák } 3202050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák } 321d99ec708afbb785ce05031661222b38c9447059fMarek Olšák 3222050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák // Add chain dependencies. 3232050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák // Chain dependencies used to enforce memory order should have 3242050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák // latency of 0 (except for true dependency of Store followed by 3252050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák // aliased Load... we estimate that with a single cycle of latency 3262050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák // assuming the hardware will bypass) 3272050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable 3282050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák // after stack slots are lowered to actual addresses. 3292050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák // TODO: Use an AliasAnalysis and do real alias-analysis queries, and 330d99ec708afbb785ce05031661222b38c9447059fMarek Olšák // produce more precise dependence information. 331d99ec708afbb785ce05031661222b38c9447059fMarek Olšák#define STORE_LOAD_LATENCY 1 332d99ec708afbb785ce05031661222b38c9447059fMarek Olšák unsigned TrueMemOrderLatency = 0; 333d99ec708afbb785ce05031661222b38c9447059fMarek Olšák if (TID.isCall() || TID.hasUnmodeledSideEffects() || 334d99ec708afbb785ce05031661222b38c9447059fMarek Olšák (MI->hasVolatileMemoryRef() && 335d99ec708afbb785ce05031661222b38c9447059fMarek Olšák (!TID.mayLoad() || !MI->isInvariantLoad(AA)))) { 336d99ec708afbb785ce05031661222b38c9447059fMarek Olšák // Be conservative with these and add dependencies on all memory 337d99ec708afbb785ce05031661222b38c9447059fMarek Olšák // references, even those that are known to not alias. 338d99ec708afbb785ce05031661222b38c9447059fMarek Olšák for (std::map<const Value *, SUnit *>::iterator I = 339d99ec708afbb785ce05031661222b38c9447059fMarek Olšák NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) { 340d99ec708afbb785ce05031661222b38c9447059fMarek Olšák I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 341d99ec708afbb785ce05031661222b38c9447059fMarek Olšák } 342d99ec708afbb785ce05031661222b38c9447059fMarek Olšák for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 343d99ec708afbb785ce05031661222b38c9447059fMarek Olšák NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) { 344d99ec708afbb785ce05031661222b38c9447059fMarek Olšák for (unsigned i = 0, e = I->second.size(); i != e; ++i) 345d99ec708afbb785ce05031661222b38c9447059fMarek Olšák I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 346d99ec708afbb785ce05031661222b38c9447059fMarek Olšák } 347d99ec708afbb785ce05031661222b38c9447059fMarek Olšák NonAliasMemDefs.clear(); 348d99ec708afbb785ce05031661222b38c9447059fMarek Olšák NonAliasMemUses.clear(); 349d99ec708afbb785ce05031661222b38c9447059fMarek Olšák // Add SU to the barrier chain. 350d99ec708afbb785ce05031661222b38c9447059fMarek Olšák if (BarrierChain) 351d99ec708afbb785ce05031661222b38c9447059fMarek Olšák BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 352d99ec708afbb785ce05031661222b38c9447059fMarek Olšák BarrierChain = SU; 353d99ec708afbb785ce05031661222b38c9447059fMarek Olšák 354d99ec708afbb785ce05031661222b38c9447059fMarek Olšák // fall-through 3552050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák new_alias_chain: 356a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // Chain all possibly aliasing memory references though SU. 357a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák if (AliasChain) 35856ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 3592050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák AliasChain = SU; 3602050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 3612050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 36228a336dc38c478b809544e7404c4d1fddd873333Marek Olšák for (std::map<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(), 3632050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák E = AliasMemDefs.end(); I != E; ++I) { 36428a336dc38c478b809544e7404c4d1fddd873333Marek Olšák I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 3652050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák } 3662050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 367a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) { 368d99ec708afbb785ce05031661222b38c9447059fMarek Olšák for (unsigned i = 0, e = I->second.size(); i != e; ++i) 369d99ec708afbb785ce05031661222b38c9447059fMarek Olšák I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 370a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák } 371ce9d61fec64138ebf8d0bec2511e66593297b7d5Marek Olšák PendingLoads.clear(); 372ce9d61fec64138ebf8d0bec2511e66593297b7d5Marek Olšák AliasMemDefs.clear(); 373a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák AliasMemUses.clear(); 3742050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák } else if (TID.mayStore()) { 3752050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák bool MayAlias = true; 376d99ec708afbb785ce05031661222b38c9447059fMarek Olšák TrueMemOrderLatency = STORE_LOAD_LATENCY; 37756ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák if (const Value *V = getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 378a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // A store to a specific PseudoSourceValue. Add precise dependencies. 3792050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák // Record the def in MemDefs, first adding a dep if there is 380d99ec708afbb785ce05031661222b38c9447059fMarek Olšák // an existing def. 381d99ec708afbb785ce05031661222b38c9447059fMarek Olšák std::map<const Value *, SUnit *>::iterator I = 382d99ec708afbb785ce05031661222b38c9447059fMarek Olšák ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 383d99ec708afbb785ce05031661222b38c9447059fMarek Olšák std::map<const Value *, SUnit *>::iterator IE = 3842050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 385d99ec708afbb785ce05031661222b38c9447059fMarek Olšák if (I != IE) { 386a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, 387d99ec708afbb785ce05031661222b38c9447059fMarek Olšák /*isNormalMemory=*/true)); 388d99ec708afbb785ce05031661222b38c9447059fMarek Olšák I->second = SU; 389d99ec708afbb785ce05031661222b38c9447059fMarek Olšák } else { 3902050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák if (MayAlias) 391d99ec708afbb785ce05031661222b38c9447059fMarek Olšák AliasMemDefs[V] = SU; 392b6c9c78bffe35d0ca9af100a1595412a1e06bd33Nicolas Peninguy else 3932050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák NonAliasMemDefs[V] = SU; 39456ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák } 39556ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // Handle the uses in MemUses, if there are any. 396d99ec708afbb785ce05031661222b38c9447059fMarek Olšák std::map<const Value *, std::vector<SUnit *> >::iterator J = 397d99ec708afbb785ce05031661222b38c9447059fMarek Olšák ((MayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); 398d99ec708afbb785ce05031661222b38c9447059fMarek Olšák std::map<const Value *, std::vector<SUnit *> >::iterator JE = 399d99ec708afbb785ce05031661222b38c9447059fMarek Olšák ((MayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); 400b6c9c78bffe35d0ca9af100a1595412a1e06bd33Nicolas Peninguy if (J != JE) { 401d99ec708afbb785ce05031661222b38c9447059fMarek Olšák for (unsigned i = 0, e = J->second.size(); i != e; ++i) 402d99ec708afbb785ce05031661222b38c9447059fMarek Olšák J->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency, 403d99ec708afbb785ce05031661222b38c9447059fMarek Olšák /*Reg=*/0, /*isNormalMemory=*/true)); 404d99ec708afbb785ce05031661222b38c9447059fMarek Olšák J->second.clear(); 405d99ec708afbb785ce05031661222b38c9447059fMarek Olšák } 406d99ec708afbb785ce05031661222b38c9447059fMarek Olšák if (MayAlias) { 407d99ec708afbb785ce05031661222b38c9447059fMarek Olšák // Add dependencies from all the PendingLoads, i.e. loads 408d99ec708afbb785ce05031661222b38c9447059fMarek Olšák // with no underlying object. 409d99ec708afbb785ce05031661222b38c9447059fMarek Olšák for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 410d99ec708afbb785ce05031661222b38c9447059fMarek Olšák PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 411d99ec708afbb785ce05031661222b38c9447059fMarek Olšák // Add dependence on alias chain, if needed. 412d99ec708afbb785ce05031661222b38c9447059fMarek Olšák if (AliasChain) 4132050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 4142050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák } 4152050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák // Add dependence on barrier chain, if needed. 4162050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák if (BarrierChain) 4172050f2ab96f923112d3475a655b31c8f5145a800Marek Olšák BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 418d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } else { 41956ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // Treat all other stores conservatively. 420d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák goto new_alias_chain; 421a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák } 422311ab3d468ea5291c10bd5cada9b77a528fb7b7fMarek Olšák } else if (TID.mayLoad()) { 423d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák bool MayAlias = true; 424d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák TrueMemOrderLatency = 0; 425d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (MI->isInvariantLoad(AA)) { 426d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák // Invariant load, no chain dependencies needed! 427d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák } else { 4287c24a4c6a86402be1f68d23f4d52d4d071957801Marek Olšák if (const Value *V = 429d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 430d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // A load from a specific PseudoSourceValue. Add precise dependencies. 431d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák std::map<const Value *, SUnit *>::iterator I = 432d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 433d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák std::map<const Value *, SUnit *>::iterator IE = 434a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 435d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (I != IE) 436d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, 437d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák /*isNormalMemory=*/true)); 438d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (MayAlias) 439d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák AliasMemUses[V].push_back(SU); 440d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák else 441d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák NonAliasMemUses[V].push_back(SU); 442d0408cf55d9e8d1d376bd844386ef5c9789a3597Marek Olšák } else { 443d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák // A load with no underlying object. Depend on all 444d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // potentially aliasing stores. 445d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák for (std::map<const Value *, SUnit *>::iterator I = 446d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) 447d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 448d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 449d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák PendingLoads.push_back(SU); 450d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák MayAlias = true; 451d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 452d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 453d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // Add dependencies on alias and barrier chains, if needed. 454d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (MayAlias && AliasChain) 455d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 45656ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák if (BarrierChain) 45756ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 458d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák } 459d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 460d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 461d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 46256ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák for (int i = 0, e = TRI->getNumRegs(); i != e; ++i) { 463d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák Defs[i].clear(); 464d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák Uses[i].clear(); 465d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 466d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák PendingLoads.clear(); 467d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák} 468d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 46956ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšákvoid ScheduleDAGInstrs::FinishBlock() { 47056ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // Nothing to do. 471a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák} 472a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák 473a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšákvoid ScheduleDAGInstrs::ComputeLatency(SUnit *SU) { 474a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 475d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 476d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // Compute the latency for the node. 477a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák SU->Latency = 478a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák InstrItins.getStageLatency(SU->getInstr()->getDesc().getSchedClass()); 479a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák 480d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // Simplistic target-independent heuristic: assume that loads take 481a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák // extra time. 482a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák if (InstrItins.isEmpty()) 483a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák if (SU->getInstr()->getDesc().mayLoad()) 484a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák SU->Latency += 2; 485a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák} 486a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák 487a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšákvoid ScheduleDAGInstrs::ComputeOperandLatency(SUnit *Def, SUnit *Use, 488a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák SDep& dep) const { 48956ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 49056ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák if (InstrItins.isEmpty()) 49156ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák return; 49213359e6a4b732335cdd8da48276960d0b176ffe3Marek Olšák 49356ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // For a data dependency with a known register... 49413359e6a4b732335cdd8da48276960d0b176ffe3Marek Olšák if ((dep.getKind() != SDep::Data) || (dep.getReg() == 0)) 49513359e6a4b732335cdd8da48276960d0b176ffe3Marek Olšák return; 49656ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák 49756ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák const unsigned Reg = dep.getReg(); 49856ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák 49956ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // ... find the definition of the register in the defining 50013359e6a4b732335cdd8da48276960d0b176ffe3Marek Olšák // instruction 501d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák MachineInstr *DefMI = Def->getInstr(); 50213359e6a4b732335cdd8da48276960d0b176ffe3Marek Olšák int DefIdx = DefMI->findRegisterDefOperandIdx(Reg); 503d35aeff4bb0b03450b2c3c08bd7f84db5bf43283Marek Olšák if (DefIdx != -1) { 50456ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák int DefCycle = InstrItins.getOperandCycle(DefMI->getDesc().getSchedClass(), DefIdx); 505d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (DefCycle >= 0) { 506d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák MachineInstr *UseMI = Use->getInstr(); 50756ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák const unsigned UseClass = UseMI->getDesc().getSchedClass(); 508d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 509451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák // For all uses of the register, calculate the maxmimum latency 51056ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák int Latency = -1; 5117b42ed6eb508e2f0b89f66f3f985ef1d76a0ef91Marek Olšák for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) { 512451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák const MachineOperand &MO = UseMI->getOperand(i); 5137b42ed6eb508e2f0b89f66f3f985ef1d76a0ef91Marek Olšák if (!MO.isReg() || !MO.isUse()) 51456ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák continue; 515451a0ddb190e5185372fed9ec57d24a822442eccMarek Olšák unsigned MOReg = MO.getReg(); 516d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (MOReg != Reg) 5177b42ed6eb508e2f0b89f66f3f985ef1d76a0ef91Marek Olšák continue; 518a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák 519a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák int UseCycle = InstrItins.getOperandCycle(UseClass, i); 520a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák if (UseCycle >= 0) 521a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák Latency = std::max(Latency, DefCycle - UseCycle + 1); 522a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák } 523a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák 52456ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák // If we found a latency, then replace the existing dependence latency. 525a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák if (Latency >= 0) 526a04f8c361211dda6a27c5577070492e17a2f4743Marek Olšák dep.setLatency(Latency); 527d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 528d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák } 529d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák} 5307b42ed6eb508e2f0b89f66f3f985ef1d76a0ef91Marek Olšák 5317b42ed6eb508e2f0b89f66f3f985ef1d76a0ef91Marek Olšákvoid ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { 532d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák SU->getInstr()->dump(); 53356ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák} 534d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 535d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšákstd::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { 53656ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák std::string s; 5374c7001462607e6e99e474d6271dd481d3f8f201cRoland Scheidegger raw_string_ostream oss(s); 538d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák if (SU == &EntrySU) 53956ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák oss << "<entry>"; 540d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák else if (SU == &ExitSU) 541a52b3338c6e51421e3836ae210cd98d9c1ec337bMarek Olšák oss << "<exit>"; 542d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák else 543f3021c688fc7a9c7d1eb5c207b6edebfcc9bd6fbMarek Olšák SU->getInstr()->print(oss); 54456ba7e913fef0ea2b1bead582108f9ab3ab8263dMarek Olšák return oss.str(); 545d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák} 546d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák 5474c7001462607e6e99e474d6271dd481d3f8f201cRoland Scheidegger// EmitSchedule - Emit the machine code in scheduled order. 548d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek OlšákMachineBasicBlock *ScheduleDAGInstrs:: 549d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek OlšákEmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) { 550d779a5d16ae6a17b3fc0c097f4eb477a80e54566Marek Olšák // For MachineInstr-based scheduling, we're rescheduling the instructions in 551 // the block, so start by removing them from the block. 552 while (Begin != InsertPos) { 553 MachineBasicBlock::iterator I = Begin; 554 ++Begin; 555 BB->remove(I); 556 } 557 558 // Then re-insert them according to the given schedule. 559 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 560 SUnit *SU = Sequence[i]; 561 if (!SU) { 562 // Null SUnit* is a noop. 563 EmitNoop(); 564 continue; 565 } 566 567 BB->insert(InsertPos, SU->getInstr()); 568 } 569 570 // Update the Begin iterator, as the first instruction in the block 571 // may have been scheduled later. 572 if (!Sequence.empty()) 573 Begin = Sequence[0]->getInstr(); 574 575 return BB; 576} 577