LLVM API Documentation

ScheduleDAGInstrs.cpp

Go to the documentation of this file.
00001 //===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This implements the ScheduleDAGInstrs class, which implements re-scheduling
00011 // of MachineInstrs.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "sched-instrs"
00016 #include "ScheduleDAGInstrs.h"
00017 #include "llvm/Operator.h"
00018 #include "llvm/Analysis/AliasAnalysis.h"
00019 #include "llvm/CodeGen/MachineFunctionPass.h"
00020 #include "llvm/CodeGen/MachineRegisterInfo.h"
00021 #include "llvm/CodeGen/PseudoSourceValue.h"
00022 #include "llvm/Target/TargetMachine.h"
00023 #include "llvm/Target/TargetInstrInfo.h"
00024 #include "llvm/Target/TargetRegisterInfo.h"
00025 #include "llvm/Target/TargetSubtarget.h"
00026 #include "llvm/Support/Debug.h"
00027 #include "llvm/Support/raw_ostream.h"
00028 #include "llvm/ADT/SmallSet.h"
00029 using namespace llvm;
00030 
00031 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
00032                                      const MachineLoopInfo &mli,
00033                                      const MachineDominatorTree &mdt)
00034   : ScheduleDAG(mf), MLI(mli), MDT(mdt), LoopRegs(MLI, MDT) {}
00035 
00036 /// Run - perform scheduling.
00037 ///
00038 void ScheduleDAGInstrs::Run(MachineBasicBlock *bb,
00039                             MachineBasicBlock::iterator begin,
00040                             MachineBasicBlock::iterator end,
00041                             unsigned endcount) {
00042   BB = bb;
00043   Begin = begin;
00044   InsertPosIndex = endcount;
00045 
00046   ScheduleDAG::Run(bb, end);
00047 }
00048 
00049 /// getUnderlyingObjectFromInt - This is the function that does the work of
00050 /// looking through basic ptrtoint+arithmetic+inttoptr sequences.
00051 static const Value *getUnderlyingObjectFromInt(const Value *V) {
00052   do {
00053     if (const Operator *U = dyn_cast<Operator>(V)) {
00054       // If we find a ptrtoint, we can transfer control back to the
00055       // regular getUnderlyingObjectFromInt.
00056       if (U->getOpcode() == Instruction::PtrToInt)
00057         return U->getOperand(0);
00058       // If we find an add of a constant or a multiplied value, it's
00059       // likely that the other operand will lead us to the base
00060       // object. We don't have to worry about the case where the
00061       // object address is somehow being computed by the multiply,
00062       // because our callers only care when the result is an
00063       // identifibale object.
00064       if (U->getOpcode() != Instruction::Add ||
00065           (!isa<ConstantInt>(U->getOperand(1)) &&
00066            Operator::getOpcode(U->getOperand(1)) != Instruction::Mul))
00067         return V;
00068       V = U->getOperand(0);
00069     } else {
00070       return V;
00071     }
00072     assert(isa<IntegerType>(V->getType()) && "Unexpected operand type!");
00073   } while (1);
00074 }
00075 
00076 /// getUnderlyingObject - This is a wrapper around Value::getUnderlyingObject
00077 /// and adds support for basic ptrtoint+arithmetic+inttoptr sequences.
00078 static const Value *getUnderlyingObject(const Value *V) {
00079   // First just call Value::getUnderlyingObject to let it do what it does.
00080   do {
00081     V = V->getUnderlyingObject();
00082     // If it found an inttoptr, use special code to continue climing.
00083     if (Operator::getOpcode(V) != Instruction::IntToPtr)
00084       break;
00085     const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0));
00086     // If that succeeded in finding a pointer, continue the search.
00087     if (!isa<PointerType>(O->getType()))
00088       break;
00089     V = O;
00090   } while (1);
00091   return V;
00092 }
00093 
00094 /// getUnderlyingObjectForInstr - If this machine instr has memory reference
00095 /// information and it can be tracked to a normal reference to a known
00096 /// object, return the Value for that object. Otherwise return null.
00097 static const Value *getUnderlyingObjectForInstr(const MachineInstr *MI) {
00098   if (!MI->hasOneMemOperand() ||
00099       !MI->memoperands_begin()->getValue() ||
00100       MI->memoperands_begin()->isVolatile())
00101     return 0;
00102 
00103   const Value *V = MI->memoperands_begin()->getValue();
00104   if (!V)
00105     return 0;
00106 
00107   V = getUnderlyingObject(V);
00108   if (!isa<PseudoSourceValue>(V) && !isIdentifiedObject(V))
00109     return 0;
00110 
00111   return V;
00112 }
00113 
00114 void ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) {
00115   if (MachineLoop *ML = MLI.getLoopFor(BB))
00116     if (BB == ML->getLoopLatch()) {
00117       MachineBasicBlock *Header = ML->getHeader();
00118       for (MachineBasicBlock::livein_iterator I = Header->livein_begin(),
00119            E = Header->livein_end(); I != E; ++I)
00120         LoopLiveInRegs.insert(*I);
00121       LoopRegs.VisitLoop(ML);
00122     }
00123 }
00124 
00125 void ScheduleDAGInstrs::BuildSchedGraph() {
00126   // We'll be allocating one SUnit for each instruction, plus one for
00127   // the region exit node.
00128   SUnits.reserve(BB->size());
00129 
00130   // We build scheduling units by walking a block's instruction list from bottom
00131   // to top.
00132 
00133   // Remember where a generic side-effecting instruction is as we procede. If
00134   // ChainMMO is null, this is assumed to have arbitrary side-effects. If
00135   // ChainMMO is non-null, then Chain makes only a single memory reference.
00136   SUnit *Chain = 0;
00137   MachineMemOperand *ChainMMO = 0;
00138 
00139   // Memory references to specific known memory locations are tracked so that
00140   // they can be given more precise dependencies.
00141   std::map<const Value *, SUnit *> MemDefs;
00142   std::map<const Value *, std::vector<SUnit *> > MemUses;
00143 
00144   // Check to see if the scheduler cares about latencies.
00145   bool UnitLatencies = ForceUnitLatencies();
00146 
00147   // Ask the target if address-backscheduling is desirable, and if so how much.
00148   const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>();
00149   unsigned SpecialAddressLatency = ST.getSpecialAddressLatency();
00150 
00151   // Walk the list of instructions, from bottom moving up.
00152   for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin;
00153        MII != MIE; --MII) {
00154     MachineInstr *MI = prior(MII);
00155     const TargetInstrDesc &TID = MI->getDesc();
00156     assert(!TID.isTerminator() && !MI->isLabel() &&
00157            "Cannot schedule terminators or labels!");
00158     // Create the SUnit for this MI.
00159     SUnit *SU = NewSUnit(MI);
00160 
00161     // Assign the Latency field of SU using target-provided information.
00162     if (UnitLatencies)
00163       SU->Latency = 1;
00164     else
00165       ComputeLatency(SU);
00166 
00167     // Add register-based dependencies (data, anti, and output).
00168     for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
00169       const MachineOperand &MO = MI->getOperand(j);
00170       if (!MO.isReg()) continue;
00171       unsigned Reg = MO.getReg();
00172       if (Reg == 0) continue;
00173 
00174       assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
00175       std::vector<SUnit *> &UseList = Uses[Reg];
00176       std::vector<SUnit *> &DefList = Defs[Reg];
00177       // Optionally add output and anti dependencies. For anti
00178       // dependencies we use a latency of 0 because for a multi-issue
00179       // target we want to allow the defining instruction to issue
00180       // in the same cycle as the using instruction.
00181       // TODO: Using a latency of 1 here for output dependencies assumes
00182       //       there's no cost for reusing registers.
00183       SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
00184       unsigned AOLatency = (Kind == SDep::Anti) ? 0 : 1;
00185       for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
00186         SUnit *DefSU = DefList[i];
00187         if (DefSU != SU &&
00188             (Kind != SDep::Output || !MO.isDead() ||
00189              !DefSU->getInstr()->registerDefIsDead(Reg)))
00190           DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/Reg));
00191       }
00192       for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
00193         std::vector<SUnit *> &DefList = Defs[*Alias];
00194         for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
00195           SUnit *DefSU = DefList[i];
00196           if (DefSU != SU &&
00197               (Kind != SDep::Output || !MO.isDead() ||
00198                !DefSU->getInstr()->registerDefIsDead(Reg)))
00199             DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/ *Alias));
00200         }
00201       }
00202 
00203       if (MO.isDef()) {
00204         // Add any data dependencies.
00205         unsigned DataLatency = SU->Latency;
00206         for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
00207           SUnit *UseSU = UseList[i];
00208           if (UseSU != SU) {
00209             unsigned LDataLatency = DataLatency;
00210             // Optionally add in a special extra latency for nodes that
00211             // feed addresses.
00212             // TODO: Do this for register aliases too.
00213             // TODO: Perhaps we should get rid of
00214             // SpecialAddressLatency and just move this into
00215             // adjustSchedDependency for the targets that care about
00216             // it.
00217             if (SpecialAddressLatency != 0 && !UnitLatencies) {
00218               MachineInstr *UseMI = UseSU->getInstr();
00219               const TargetInstrDesc &UseTID = UseMI->getDesc();
00220               int RegUseIndex = UseMI->findRegisterUseOperandIdx(Reg);
00221               assert(RegUseIndex >= 0 && "UseMI doesn's use register!");
00222               if ((UseTID.mayLoad() || UseTID.mayStore()) &&
00223                   (unsigned)RegUseIndex < UseTID.getNumOperands() &&
00224                   UseTID.OpInfo[RegUseIndex].isLookupPtrRegClass())
00225                 LDataLatency += SpecialAddressLatency;
00226             }
00227             // Adjust the dependence latency using operand def/use
00228             // information (if any), and then allow the target to
00229             // perform its own adjustments.
00230             const SDep& dep = SDep(SU, SDep::Data, LDataLatency, Reg);
00231             if (!UnitLatencies) {
00232               ComputeOperandLatency(SU, UseSU, (SDep &)dep);
00233               ST.adjustSchedDependency(SU, UseSU, (SDep &)dep);
00234             }
00235             UseSU->addPred(dep);
00236           }
00237         }
00238         for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
00239           std::vector<SUnit *> &UseList = Uses[*Alias];
00240           for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
00241             SUnit *UseSU = UseList[i];
00242             if (UseSU != SU) {
00243               const SDep& dep = SDep(SU, SDep::Data, DataLatency, *Alias);
00244               if (!UnitLatencies) {
00245                 ComputeOperandLatency(SU, UseSU, (SDep &)dep);
00246                 ST.adjustSchedDependency(SU, UseSU, (SDep &)dep);
00247               }
00248               UseSU->addPred(dep);
00249             }
00250           }
00251         }
00252 
00253         // If a def is going to wrap back around to the top of the loop,
00254         // backschedule it.
00255         if (!UnitLatencies && DefList.empty()) {
00256           LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(Reg);
00257           if (I != LoopRegs.Deps.end()) {
00258             const MachineOperand *UseMO = I->second.first;
00259             unsigned Count = I->second.second;
00260             const MachineInstr *UseMI = UseMO->getParent();
00261             unsigned UseMOIdx = UseMO - &UseMI->getOperand(0);
00262             const TargetInstrDesc &UseTID = UseMI->getDesc();
00263             // TODO: If we knew the total depth of the region here, we could
00264             // handle the case where the whole loop is inside the region but
00265             // is large enough that the isScheduleHigh trick isn't needed.
00266             if (UseMOIdx < UseTID.getNumOperands()) {
00267               // Currently, we only support scheduling regions consisting of
00268               // single basic blocks. Check to see if the instruction is in
00269               // the same region by checking to see if it has the same parent.
00270               if (UseMI->getParent() != MI->getParent()) {
00271                 unsigned Latency = SU->Latency;
00272                 if (UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass())
00273                   Latency += SpecialAddressLatency;
00274                 // This is a wild guess as to the portion of the latency which
00275                 // will be overlapped by work done outside the current
00276                 // scheduling region.
00277                 Latency -= std::min(Latency, Count);
00278                 // Add the artifical edge.
00279                 ExitSU.addPred(SDep(SU, SDep::Order, Latency,
00280                                     /*Reg=*/0, /*isNormalMemory=*/false,
00281                                     /*isMustAlias=*/false,
00282                                     /*isArtificial=*/true));
00283               } else if (SpecialAddressLatency > 0 &&
00284                          UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) {
00285                 // The entire loop body is within the current scheduling region
00286                 // and the latency of this operation is assumed to be greater
00287                 // than the latency of the loop.
00288                 // TODO: Recursively mark data-edge predecessors as
00289                 //       isScheduleHigh too.
00290                 SU->isScheduleHigh = true;
00291               }
00292             }
00293             LoopRegs.Deps.erase(I);
00294           }
00295         }
00296 
00297         UseList.clear();
00298         if (!MO.isDead())
00299           DefList.clear();
00300         DefList.push_back(SU);
00301       } else {
00302         UseList.push_back(SU);
00303       }
00304     }
00305 
00306     // Add chain dependencies.
00307     // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable
00308     // after stack slots are lowered to actual addresses.
00309     // TODO: Use an AliasAnalysis and do real alias-analysis queries, and
00310     // produce more precise dependence information.
00311     if (TID.isCall() || TID.hasUnmodeledSideEffects()) {
00312     new_chain:
00313       // This is the conservative case. Add dependencies on all memory
00314       // references.
00315       if (Chain)
00316         Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
00317       Chain = SU;
00318       for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
00319         PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency));
00320       PendingLoads.clear();
00321       for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(),
00322            E = MemDefs.end(); I != E; ++I) {
00323         I->second->addPred(SDep(SU, SDep::Order, SU->Latency));
00324         I->second = SU;
00325       }
00326       for (std::map<const Value *, std::vector<SUnit *> >::iterator I =
00327            MemUses.begin(), E = MemUses.end(); I != E; ++I) {
00328         for (unsigned i = 0, e = I->second.size(); i != e; ++i)
00329           I->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency));
00330         I->second.clear();
00331       }
00332       // See if it is known to just have a single memory reference.
00333       MachineInstr *ChainMI = Chain->getInstr();
00334       const TargetInstrDesc &ChainTID = ChainMI->getDesc();
00335       if (!ChainTID.isCall() &&
00336           !ChainTID.hasUnmodeledSideEffects() &&
00337           ChainMI->hasOneMemOperand() &&
00338           !ChainMI->memoperands_begin()->isVolatile() &&
00339           ChainMI->memoperands_begin()->getValue())
00340         // We know that the Chain accesses one specific memory location.
00341         ChainMMO = &*ChainMI->memoperands_begin();
00342       else
00343         // Unknown memory accesses. Assume the worst.
00344         ChainMMO = 0;
00345     } else if (TID.mayStore()) {
00346       if (const Value *V = getUnderlyingObjectForInstr(MI)) {
00347         // A store to a specific PseudoSourceValue. Add precise dependencies.
00348         // Handle the def in MemDefs, if there is one.
00349         std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
00350         if (I != MemDefs.end()) {
00351           I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
00352                                   /*isNormalMemory=*/true));
00353           I->second = SU;
00354         } else {
00355           MemDefs[V] = SU;
00356         }
00357         // Handle the uses in MemUses, if there are any.
00358         std::map<const Value *, std::vector<SUnit *> >::iterator J =
00359           MemUses.find(V);
00360         if (J != MemUses.end()) {
00361           for (unsigned i = 0, e = J->second.size(); i != e; ++i)
00362             J->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
00363                                        /*isNormalMemory=*/true));
00364           J->second.clear();
00365         }
00366         // Add dependencies from all the PendingLoads, since without
00367         // memoperands we must assume they alias anything.
00368         for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
00369           PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency));
00370         // Add a general dependence too, if needed.
00371         if (Chain)
00372           Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
00373       } else
00374         // Treat all other stores conservatively.
00375         goto new_chain;
00376     } else if (TID.mayLoad()) {
00377       if (TII->isInvariantLoad(MI)) {
00378         // Invariant load, no chain dependencies needed!
00379       } else if (const Value *V = getUnderlyingObjectForInstr(MI)) {
00380         // A load from a specific PseudoSourceValue. Add precise dependencies.
00381         std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
00382         if (I != MemDefs.end())
00383           I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
00384                                   /*isNormalMemory=*/true));
00385         MemUses[V].push_back(SU);
00386 
00387         // Add a general dependence too, if needed.
00388         if (Chain && (!ChainMMO ||
00389                       (ChainMMO->isStore() || ChainMMO->isVolatile())))
00390           Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
00391       } else if (MI->hasVolatileMemoryRef()) {
00392         // Treat volatile loads conservatively. Note that this includes
00393         // cases where memoperand information is unavailable.
00394         goto new_chain;
00395       } else {
00396         // A normal load. Depend on the general chain, as well as on
00397         // all stores. In the absense of MachineMemOperand information,
00398         // we can't even assume that the load doesn't alias well-behaved
00399         // memory locations.
00400         if (Chain)
00401           Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
00402         for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(),
00403              E = MemDefs.end(); I != E; ++I)
00404           I->second->addPred(SDep(SU, SDep::Order, SU->Latency));
00405         PendingLoads.push_back(SU);
00406       }
00407     }
00408   }
00409 
00410   for (int i = 0, e = TRI->getNumRegs(); i != e; ++i) {
00411     Defs[i].clear();
00412     Uses[i].clear();
00413   }
00414   PendingLoads.clear();
00415 }
00416 
00417 void ScheduleDAGInstrs::FinishBlock() {
00418   // Nothing to do.
00419 }
00420 
00421 void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) {
00422   const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
00423 
00424   // Compute the latency for the node.
00425   SU->Latency =
00426     InstrItins.getStageLatency(SU->getInstr()->getDesc().getSchedClass());
00427 
00428   // Simplistic target-independent heuristic: assume that loads take
00429   // extra time.
00430   if (InstrItins.isEmpty())
00431     if (SU->getInstr()->getDesc().mayLoad())
00432       SU->Latency += 2;
00433 }
00434 
00435 void ScheduleDAGInstrs::ComputeOperandLatency(SUnit *Def, SUnit *Use, 
00436                                               SDep& dep) const {
00437   const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
00438   if (InstrItins.isEmpty())
00439     return;
00440   
00441   // For a data dependency with a known register...
00442   if ((dep.getKind() != SDep::Data) || (dep.getReg() == 0))
00443     return;
00444 
00445   const unsigned Reg = dep.getReg();
00446 
00447   // ... find the definition of the register in the defining
00448   // instruction
00449   MachineInstr *DefMI = Def->getInstr();
00450   int DefIdx = DefMI->findRegisterDefOperandIdx(Reg);
00451   if (DefIdx != -1) {
00452     int DefCycle = InstrItins.getOperandCycle(DefMI->getDesc().getSchedClass(), DefIdx);
00453     if (DefCycle >= 0) {
00454       MachineInstr *UseMI = Use->getInstr();
00455       const unsigned UseClass = UseMI->getDesc().getSchedClass();
00456 
00457       // For all uses of the register, calculate the maxmimum latency
00458       int Latency = -1;
00459       for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) {
00460         const MachineOperand &MO = UseMI->getOperand(i);
00461         if (!MO.isReg() || !MO.isUse())
00462           continue;
00463         unsigned MOReg = MO.getReg();
00464         if (MOReg != Reg)
00465           continue;
00466 
00467         int UseCycle = InstrItins.getOperandCycle(UseClass, i);
00468         if (UseCycle >= 0)
00469           Latency = std::max(Latency, DefCycle - UseCycle + 1);
00470       }
00471 
00472       // If we found a latency, then replace the existing dependence latency.
00473       if (Latency >= 0)
00474         dep.setLatency(Latency);
00475     }
00476   }
00477 }
00478 
00479 void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
00480   SU->getInstr()->dump();
00481 }
00482 
00483 std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
00484   std::string s;
00485   raw_string_ostream oss(s);
00486   if (SU == &EntrySU)
00487     oss << "<entry>";
00488   else if (SU == &ExitSU)
00489     oss << "<exit>";
00490   else
00491     SU->getInstr()->print(oss);
00492   return oss.str();
00493 }
00494 
00495 // EmitSchedule - Emit the machine code in scheduled order.
00496 MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() {
00497   // For MachineInstr-based scheduling, we're rescheduling the instructions in
00498   // the block, so start by removing them from the block.
00499   while (Begin != InsertPos) {
00500     MachineBasicBlock::iterator I = Begin;
00501     ++Begin;
00502     BB->remove(I);
00503   }
00504 
00505   // Then re-insert them according to the given schedule.
00506   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
00507     SUnit *SU = Sequence[i];
00508     if (!SU) {
00509       // Null SUnit* is a noop.
00510       EmitNoop();
00511       continue;
00512     }
00513 
00514     BB->insert(InsertPos, SU->getInstr());
00515   }
00516 
00517   // Update the Begin iterator, as the first instruction in the block
00518   // may have been scheduled later.
00519   if (!Sequence.empty())
00520     Begin = Sequence[0]->getInstr();
00521 
00522   return BB;
00523 }