ScheduleDAGRRList.cpp revision 3b66555c53eb8921b2dd50335e0b278ddf80d220
1e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----- ScheduleDAGList.cpp - Reg pressure reduction list scheduler ----===// 2e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// 3e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// The LLVM Compiler Infrastructure 4e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// 8e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 9e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// 10e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// This implements bottom-up and top-down register pressure reduction list 11e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// schedulers, using standard algorithms. The basic approach uses a priority 12e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// queue of available nodes to schedule. One at a time, nodes are taken from 13e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// the priority queue (thus in priority order), checked for legality to 14e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// schedule, and emitted if legal. 15e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// 16e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 17e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 18e7e7d0d7e39d0c7c659d26b97e8081fce0fcd749Dale Johannesen#define DEBUG_TYPE "pre-RA-sched" 19e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include "llvm/CodeGen/ScheduleDAG.h" 20eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey#include "llvm/CodeGen/SchedulerRegistry.h" 216f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 2207000c6f01d8f57170f2d4c77a86d934bdc5c696Owen Anderson#include "llvm/Target/TargetData.h" 23e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include "llvm/Target/TargetMachine.h" 24e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include "llvm/Target/TargetInstrInfo.h" 25e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include "llvm/Support/Debug.h" 26a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 27cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng#include "llvm/ADT/SmallPtrSet.h" 28a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng#include "llvm/ADT/SmallSet.h" 29e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include "llvm/ADT/Statistic.h" 30e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include <climits> 31e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include <queue> 32e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include "llvm/Support/CommandLine.h" 33e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengusing namespace llvm; 34e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 35a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan ChengSTATISTIC(NumBacktracks, "Number of times scheduler backtraced"); 36f10c973797cf79da802f9b0118543cbd50954c9cEvan ChengSTATISTIC(NumUnfolds, "Number of nodes unfolded"); 37a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan ChengSTATISTIC(NumDups, "Number of duplicated nodes"); 38a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan ChengSTATISTIC(NumCCCopies, "Number of cross class copies"); 39a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 4013ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskeystatic RegisterScheduler 4113ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey burrListDAGScheduler("list-burr", 4213ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey " Bottom-up register reduction list scheduling", 4313ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey createBURRListDAGScheduler); 4413ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskeystatic RegisterScheduler 4513ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey tdrListrDAGScheduler("list-tdrr", 4613ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey " Top-down register reduction list scheduling", 4713ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey createTDRRListDAGScheduler); 4813ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey 49e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengnamespace { 50e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 51e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ScheduleDAGRRList - The actual register reduction list scheduler 52e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// implementation. This supports both top-down and bottom-up scheduling. 53e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// 54f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattnerclass VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG { 55e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengprivate: 56e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// isBottomUp - This is true if the scheduling problem is bottom-up, false if 57e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// it is top-down. 58e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isBottomUp; 59e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 60e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// AvailableQueue - The priority queue to use for the available SUnits. 61e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SchedulingPriorityQueue *AvailableQueue; 62e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 63a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng /// LiveRegs / LiveRegDefs - A set of physical registers and their definition 64a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng /// that are "live". These nodes must be scheduled before any other nodes that 65a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng /// modifies the registers can be scheduled. 66a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SmallSet<unsigned, 4> LiveRegs; 67a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng std::vector<SUnit*> LiveRegDefs; 68a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng std::vector<unsigned> LiveRegCycles; 69a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 70e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengpublic: 71e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb, 72e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng const TargetMachine &tm, bool isbottomup, 73e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SchedulingPriorityQueue *availqueue) 74e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), 75e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue(availqueue) { 76e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 77e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 78e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng ~ScheduleDAGRRList() { 79e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng delete AvailableQueue; 80e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 81e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 82e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void Schedule(); 83e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 84e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengprivate: 8542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void ReleasePred(SUnit*, bool, unsigned); 8642d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void ReleaseSucc(SUnit*, bool isChain, unsigned); 8742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void CapturePred(SUnit*, SUnit*, bool); 8842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void ScheduleNodeBottomUp(SUnit*, unsigned); 8942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void ScheduleNodeTopDown(SUnit*, unsigned); 9042d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void UnscheduleNodeBottomUp(SUnit*); 9142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void BacktrackBottomUp(SUnit*, unsigned, unsigned&); 9242d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng SUnit *CopyAndMoveSuccessors(SUnit*); 93a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng void InsertCCCopiesAndMoveSuccs(SUnit*, unsigned, 94a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng const TargetRegisterClass*, 9542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng const TargetRegisterClass*, 96a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<SUnit*, 2>&); 97a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&); 98e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void ListScheduleTopDown(); 99e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void ListScheduleBottomUp(); 10013d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng void CommuteNodesToReducePressure(); 101e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng}; 102e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} // end anonymous namespace 103e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 104e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 105e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// Schedule - Schedule the DAG using list scheduling. 106e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengvoid ScheduleDAGRRList::Schedule() { 107832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "********** List Scheduling **********\n"; 108a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1096f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman LiveRegDefs.resize(TRI->getNumRegs(), NULL); 1106f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman LiveRegCycles.resize(TRI->getNumRegs(), 0); 111a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 112e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Build scheduling units. 113e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng BuildSchedUnits(); 114e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 115e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 116228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner SUnits[su].dumpAll(&DAG)); 117d42a5238a967c9cdfec8fe086bd18876bff5a951Evan Cheng CalculateDepths(); 118d42a5238a967c9cdfec8fe086bd18876bff5a951Evan Cheng CalculateHeights(); 119e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 12095f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng AvailableQueue->initNodes(SUnitMap, SUnits); 1218d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman 122e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate. 123e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (isBottomUp) 124e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng ListScheduleBottomUp(); 125e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng else 126e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng ListScheduleTopDown(); 127e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 128e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue->releaseState(); 1298d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman 1303b788238683396671e63cad36298d26eb4806dbeEvan Cheng CommuteNodesToReducePressure(); 131e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 132832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "*** Final schedule ***\n"; 133e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng DEBUG(dumpSchedule()); 134832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "\n"; 135e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 136e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Emit in scheduled order 137e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng EmitSchedule(); 138e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 139e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 14095f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng/// CommuteNodesToReducePressure - If a node is two-address and commutable, and 14113d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng/// it is not the last use of its first operand, add it to the CommuteSet if 14213d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng/// possible. It will be commuted when it is translated to a MI. 14313d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Chengvoid ScheduleDAGRRList::CommuteNodesToReducePressure() { 1440b2ce1fc19c5f8742051cf022ac119a3d4d9a3adEvan Cheng SmallPtrSet<SUnit*, 4> OperandSeen; 14513d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng for (unsigned i = Sequence.size()-1; i != 0; --i) { // Ignore first node. 14613d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng SUnit *SU = Sequence[i]; 14742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng if (!SU || !SU->Node) continue; 14895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng if (SU->isCommutable) { 14995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng unsigned Opc = SU->Node->getTargetOpcode(); 150749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = TII->get(Opc); 1513db805ea80eeec9084a1b86273d93804d233d938Chris Lattner unsigned NumRes = TID.getNumDefs(); 1523b66555c53eb8921b2dd50335e0b278ddf80d220Dan Gohman unsigned NumOps = TID.getNumOperands() - NumRes; 15395f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng for (unsigned j = 0; j != NumOps; ++j) { 1543db805ea80eeec9084a1b86273d93804d233d938Chris Lattner if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1) 15595f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng continue; 15695f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 15795f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng SDNode *OpN = SU->Node->getOperand(j).Val; 1587da8f399bf09e9a03fe8bdd8c8eef6e5a7d87327Evan Cheng SUnit *OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN][SU->InstanceNo]; 15995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng if (OpSU && OperandSeen.count(OpSU) == 1) { 16095f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng // Ok, so SU is not the last use of OpSU, but SU is two-address so 16195f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng // it will clobber OpSU. Try to commute SU if no other source operands 16295f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng // are live below. 16395f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng bool DoCommute = true; 16495f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng for (unsigned k = 0; k < NumOps; ++k) { 16595f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng if (k != j) { 16695f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng OpN = SU->Node->getOperand(k).Val; 1677da8f399bf09e9a03fe8bdd8c8eef6e5a7d87327Evan Cheng OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN][SU->InstanceNo]; 16895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng if (OpSU && OperandSeen.count(OpSU) == 1) { 16995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng DoCommute = false; 17095f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng break; 17195f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 17295f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 17313d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng } 17495f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng if (DoCommute) 17595f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng CommuteSet.insert(SU->Node); 17613d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng } 17795f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 17895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng // Only look at the first use&def node for now. 17995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng break; 18013d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng } 18113d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng } 18213d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng 183228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 184228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner I != E; ++I) { 185713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng if (!I->isCtrl) 186713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng OperandSeen.insert(I->Dep); 18713d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng } 18813d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng } 18913d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng} 190e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 191e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 192e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// Bottom-Up Scheduling 193e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 194e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 195e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 1968d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 197e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengvoid ScheduleDAGRRList::ReleasePred(SUnit *PredSU, bool isChain, 198e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng unsigned CurCycle) { 199e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // FIXME: the distance between two nodes is not always == the predecessor's 200e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // latency. For example, the reader can very well read the register written 201e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // by the predecessor later than the issue cycle. It also depends on the 202e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // interrupt model (drain vs. freeze). 203e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency); 204e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 20574d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng --PredSU->NumSuccsLeft; 206e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 207e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#ifndef NDEBUG 20874d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng if (PredSU->NumSuccsLeft < 0) { 209832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << "*** List scheduling failed! ***\n"; 210e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng PredSU->dump(&DAG); 211832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << " has been released too many times!\n"; 212e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng assert(0); 213e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 214e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#endif 215e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 21674d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng if (PredSU->NumSuccsLeft == 0) { 217e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // EntryToken has to go last! Special case it here. 21842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng if (!PredSU->Node || PredSU->Node->getOpcode() != ISD::EntryToken) { 219e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng PredSU->isAvailable = true; 220e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue->push(PredSU); 221e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 222e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 223e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 224e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 225e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 226e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// count of its predecessors. If a predecessor pending count is zero, add it to 227e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// the Available queue. 2286b8e5a93183ab08811b7b71887d8c7d774666210Evan Chengvoid ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 229832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "*** Scheduling [" << CurCycle << "]: "; 230e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng DEBUG(SU->dump(&DAG)); 231e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SU->Cycle = CurCycle; 232e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 233e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue->ScheduledNode(SU); 234e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 235e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Bottom up: release predecessors 236228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 237a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 238713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng ReleasePred(I->Dep, I->isCtrl, CurCycle); 239a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (I->Cost < 0) { 240a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // This is a physical register dependency and it's impossible or 241a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // expensive to copy the register. Make sure nothing that can 242a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // clobber the register is scheduled between the predecessor and 243a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // this node. 244a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (LiveRegs.insert(I->Reg)) { 245a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng LiveRegDefs[I->Reg] = I->Dep; 246a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng LiveRegCycles[I->Reg] = CurCycle; 247a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 248a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 249a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 250a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 251a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // Release all the implicit physical register defs that are live. 252a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 253a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 254a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (I->Cost < 0) { 255a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (LiveRegCycles[I->Reg] == I->Dep->Cycle) { 256a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng LiveRegs.erase(I->Reg); 257a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng assert(LiveRegDefs[I->Reg] == SU && 258a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng "Physical register dependency violated?"); 259a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng LiveRegDefs[I->Reg] = NULL; 260a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng LiveRegCycles[I->Reg] = 0; 261a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 262a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 263a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 264a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 265e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SU->isScheduled = true; 266e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 267e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 268a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// CapturePred - This does the opposite of ReleasePred. Since SU is being 269a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// unscheduled, incrcease the succ left count of its predecessors. Remove 270a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// them from AvailableQueue if necessary. 271a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Chengvoid ScheduleDAGRRList::CapturePred(SUnit *PredSU, SUnit *SU, bool isChain) { 272a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng PredSU->CycleBound = 0; 273a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::succ_iterator I = PredSU->Succs.begin(), E = PredSU->Succs.end(); 274a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 275a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (I->Dep == SU) 276a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng continue; 277a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng PredSU->CycleBound = std::max(PredSU->CycleBound, 278a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I->Dep->Cycle + PredSU->Latency); 279a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 280a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 281a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (PredSU->isAvailable) { 282a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng PredSU->isAvailable = false; 283a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (!PredSU->isPending) 284a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->remove(PredSU); 285a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 286a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 28774d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng ++PredSU->NumSuccsLeft; 288a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng} 289a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 290a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and 291a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// its predecessor states to reflect the change. 292a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Chengvoid ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) { 293a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng DOUT << "*** Unscheduling [" << SU->Cycle << "]: "; 294a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng DEBUG(SU->dump(&DAG)); 295a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 296a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->UnscheduledNode(SU); 297a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 298a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 299a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 300a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng CapturePred(I->Dep, SU, I->isCtrl); 301a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (I->Cost < 0 && SU->Cycle == LiveRegCycles[I->Reg]) { 302a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng LiveRegs.erase(I->Reg); 303a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng assert(LiveRegDefs[I->Reg] == I->Dep && 304a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng "Physical register dependency violated?"); 305a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng LiveRegDefs[I->Reg] = NULL; 306a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng LiveRegCycles[I->Reg] = 0; 307a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 308a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 309a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 310a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 311a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 312a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (I->Cost < 0) { 313a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (LiveRegs.insert(I->Reg)) { 314a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng assert(!LiveRegDefs[I->Reg] && 315a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng "Physical register dependency violated?"); 316a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng LiveRegDefs[I->Reg] = SU; 317a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 318a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (I->Dep->Cycle < LiveRegCycles[I->Reg]) 319a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng LiveRegCycles[I->Reg] = I->Dep->Cycle; 320a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 321a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 322a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 323a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SU->Cycle = 0; 324a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SU->isScheduled = false; 325a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SU->isAvailable = true; 326a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->push(SU); 327a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng} 328a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 3296e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng// FIXME: This is probably too slow! 3306e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Chengstatic void isReachable(SUnit *SU, SUnit *TargetSU, 3316e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng SmallPtrSet<SUnit*, 32> &Visited, bool &Reached) { 3326e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng if (Reached) return; 3336e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng if (SU == TargetSU) { 3346e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng Reached = true; 3356e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng return; 3366e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng } 3376e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng if (!Visited.insert(SU)) return; 3386e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng 3396e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E; 3406e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng ++I) 3416e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng isReachable(I->Dep, TargetSU, Visited, Reached); 3426e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng} 3436e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng 3446e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Chengstatic bool isReachable(SUnit *SU, SUnit *TargetSU) { 3456e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng SmallPtrSet<SUnit*, 32> Visited; 3466e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng bool Reached = false; 3476e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng isReachable(SU, TargetSU, Visited, Reached); 3486e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng return Reached; 3496e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng} 3506e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng 3516e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng/// willCreateCycle - Returns true if adding an edge from SU to TargetSU will 3526e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng/// create a cycle. 353a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Chengstatic bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) { 3546e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng if (isReachable(TargetSU, SU)) 3556e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng return true; 3566e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 3576e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng I != E; ++I) 3586e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng if (I->Cost < 0 && isReachable(TargetSU, I->Dep)) 3596e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng return true; 3606e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng return false; 3616e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng} 3626e4c46cea5daef8bc807a36ce2ab9bb7f9855b67Evan Cheng 36342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng/// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in 364a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// BTCycle in order to schedule a specific node. Returns the last unscheduled 365a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// SUnit. Also returns if a successor is unscheduled in the process. 36642d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Chengvoid ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle, 36742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng unsigned &CurCycle) { 368a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SUnit *OldSU = NULL; 36942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng while (CurCycle > BtCycle) { 370a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng OldSU = Sequence.back(); 371a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Sequence.pop_back(); 372a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (SU->isSucc(OldSU)) 37342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng // Don't try to remove SU from AvailableQueue. 37442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng SU->isAvailable = false; 375a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng UnscheduleNodeBottomUp(OldSU); 376a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng --CurCycle; 377a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 378a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 379a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 380a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (SU->isSucc(OldSU)) { 381a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng assert(false && "Something is wrong!"); 382a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng abort(); 383a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 384a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 385a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng ++NumBacktracks; 386a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng} 387a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 388f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled 389f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng/// successors to the newly created node. 390f10c973797cf79da802f9b0118543cbd50954c9cEvan ChengSUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) { 391f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (SU->FlaggedNodes.size()) 392f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng return NULL; 393f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 394f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SDNode *N = SU->Node; 39542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng if (!N) 396f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng return NULL; 39742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 398f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SUnit *NewSU; 399f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng bool TryUnfold = false; 400d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 401d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng MVT::ValueType VT = N->getValueType(i); 402d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng if (VT == MVT::Flag) 403d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng return NULL; 404d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng else if (VT == MVT::Other) 405d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng TryUnfold = true; 406d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng } 407a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 408a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng const SDOperand &Op = N->getOperand(i); 409a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng MVT::ValueType VT = Op.Val->getValueType(Op.ResNo); 410f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (VT == MVT::Flag) 411f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng return NULL; 412a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 413a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 414f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (TryUnfold) { 415f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SmallVector<SDNode*, 4> NewNodes; 4166425f8be7263e625c2d7484eb2fb8f6643824f49Owen Anderson if (!TII->unfoldMemoryOperand(DAG, N, NewNodes)) 417f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng return NULL; 418f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 419f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng DOUT << "Unfolding SU # " << SU->NodeNum << "\n"; 420f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng assert(NewNodes.size() == 2 && "Expected a load folding node!"); 421f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 422f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng N = NewNodes[1]; 423f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SDNode *LoadNode = NewNodes[0]; 424f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng unsigned NumVals = N->getNumValues(); 425f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng unsigned OldNumVals = SU->Node->getNumValues(); 426f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (unsigned i = 0; i != NumVals; ++i) 42701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner DAG.ReplaceAllUsesOfValueWith(SDOperand(SU->Node, i), SDOperand(N, i)); 428f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng DAG.ReplaceAllUsesOfValueWith(SDOperand(SU->Node, OldNumVals-1), 42901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner SDOperand(LoadNode, 1)); 430f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 431f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SUnit *NewSU = NewSUnit(N); 432f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SUnitMap[N].push_back(NewSU); 433749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = TII->get(N->getTargetOpcode()); 4343db805ea80eeec9084a1b86273d93804d233d938Chris Lattner for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 4353db805ea80eeec9084a1b86273d93804d233d938Chris Lattner if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 436f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng NewSU->isTwoAddress = true; 437f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng break; 438f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 439f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 4403db805ea80eeec9084a1b86273d93804d233d938Chris Lattner if (TID.isCommutable()) 441f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng NewSU->isCommutable = true; 442f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng // FIXME: Calculate height / depth and propagate the changes? 443beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng NewSU->Depth = SU->Depth; 444beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng NewSU->Height = SU->Height; 445f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng ComputeLatency(NewSU); 446f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 447beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng // LoadNode may already exist. This can happen when there is another 448beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng // load from the same location and producing the same type of value 449beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng // but it has different alignment or volatileness. 450beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng bool isNewLoad = true; 451beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng SUnit *LoadSU; 452beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng DenseMap<SDNode*, std::vector<SUnit*> >::iterator SMI = 453beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng SUnitMap.find(LoadNode); 454beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng if (SMI != SUnitMap.end()) { 455beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng LoadSU = SMI->second.front(); 456beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng isNewLoad = false; 457beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng } else { 458beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng LoadSU = NewSUnit(LoadNode); 459beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng SUnitMap[LoadNode].push_back(LoadSU); 460beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng 461beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng LoadSU->Depth = SU->Depth; 462beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng LoadSU->Height = SU->Height; 463beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng ComputeLatency(LoadSU); 464beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng } 465beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng 466f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SUnit *ChainPred = NULL; 467f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SmallVector<SDep, 4> ChainSuccs; 468f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SmallVector<SDep, 4> LoadPreds; 469f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SmallVector<SDep, 4> NodePreds; 470f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SmallVector<SDep, 4> NodeSuccs; 471f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 472f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng I != E; ++I) { 473f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (I->isCtrl) 474f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng ChainPred = I->Dep; 475f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng else if (I->Dep->Node && I->Dep->Node->isOperand(LoadNode)) 476f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng LoadPreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false)); 477f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng else 478f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng NodePreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false)); 479f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 480f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 481f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng I != E; ++I) { 482f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (I->isCtrl) 483f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng ChainSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost, 484f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng I->isCtrl, I->isSpecial)); 485f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng else 486f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng NodeSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost, 487f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng I->isCtrl, I->isSpecial)); 488f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 48942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 490f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SU->removePred(ChainPred, true, false); 491beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng if (isNewLoad) 492beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng LoadSU->addPred(ChainPred, true, false); 493f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { 494f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SDep *Pred = &LoadPreds[i]; 495f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SU->removePred(Pred->Dep, Pred->isCtrl, Pred->isSpecial); 496beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng if (isNewLoad) 497beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng LoadSU->addPred(Pred->Dep, Pred->isCtrl, Pred->isSpecial, 498beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng Pred->Reg, Pred->Cost); 499f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 500f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { 501f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SDep *Pred = &NodePreds[i]; 502f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SU->removePred(Pred->Dep, Pred->isCtrl, Pred->isSpecial); 503f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng NewSU->addPred(Pred->Dep, Pred->isCtrl, Pred->isSpecial, 504f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng Pred->Reg, Pred->Cost); 505f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 506f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { 507f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SDep *Succ = &NodeSuccs[i]; 508f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng Succ->Dep->removePred(SU, Succ->isCtrl, Succ->isSpecial); 509f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng Succ->Dep->addPred(NewSU, Succ->isCtrl, Succ->isSpecial, 510f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng Succ->Reg, Succ->Cost); 511f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 512f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { 513f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SDep *Succ = &ChainSuccs[i]; 514f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng Succ->Dep->removePred(SU, Succ->isCtrl, Succ->isSpecial); 515beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng if (isNewLoad) 516beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng Succ->Dep->addPred(LoadSU, Succ->isCtrl, Succ->isSpecial, 517beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng Succ->Reg, Succ->Cost); 518f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 519beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng if (isNewLoad) 520beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng NewSU->addPred(LoadSU, false, false); 521f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 522beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng if (isNewLoad) 523beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng AvailableQueue->addNode(LoadSU); 524f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng AvailableQueue->addNode(NewSU); 525f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 526f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng ++NumUnfolds; 527f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 528f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (NewSU->NumSuccsLeft == 0) { 529f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng NewSU->isAvailable = true; 530f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng return NewSU; 531beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng } 532beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng SU = NewSU; 533f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 534f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 535f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng DOUT << "Duplicating SU # " << SU->NodeNum << "\n"; 536f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng NewSU = Clone(SU); 537a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 538a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // New SUnit has the exact same predecessors. 539a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 540a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) 541a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (!I->isSpecial) { 542a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng NewSU->addPred(I->Dep, I->isCtrl, false, I->Reg, I->Cost); 543a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1); 544a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 545a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 546a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // Only copy scheduled successors. Cut them from old node's successor 547a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // list and move them over. 5482dc7a0e075f619ecd657acdb19c4be8af051e35cEvan Cheng SmallVector<std::pair<SUnit*, bool>, 4> DelDeps; 549a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 550a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 551a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (I->isSpecial) 552a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng continue; 553a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (I->Dep->isScheduled) { 5542dc7a0e075f619ecd657acdb19c4be8af051e35cEvan Cheng NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1); 555a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I->Dep->addPred(NewSU, I->isCtrl, false, I->Reg, I->Cost); 5562dc7a0e075f619ecd657acdb19c4be8af051e35cEvan Cheng DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl)); 557a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 558a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 559a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 5602dc7a0e075f619ecd657acdb19c4be8af051e35cEvan Cheng SUnit *Succ = DelDeps[i].first; 5612dc7a0e075f619ecd657acdb19c4be8af051e35cEvan Cheng bool isCtrl = DelDeps[i].second; 562a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Succ->removePred(SU, isCtrl, false); 563a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 564a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 565a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->updateNode(SU); 566a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->addNode(NewSU); 567a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 568a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng ++NumDups; 569a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return NewSU; 570a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng} 571a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 572a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng/// InsertCCCopiesAndMoveSuccs - Insert expensive cross register class copies 573a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng/// and move all scheduled successors of the given SUnit to the last copy. 574a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Chengvoid ScheduleDAGRRList::InsertCCCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, 575a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng const TargetRegisterClass *DestRC, 576a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng const TargetRegisterClass *SrcRC, 577a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<SUnit*, 2> &Copies) { 57842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng SUnit *CopyFromSU = NewSUnit(NULL); 57942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyFromSU->CopySrcRC = SrcRC; 58042d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyFromSU->CopyDstRC = DestRC; 58142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyFromSU->Depth = SU->Depth; 58242d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyFromSU->Height = SU->Height; 58342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 58442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng SUnit *CopyToSU = NewSUnit(NULL); 58542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyToSU->CopySrcRC = DestRC; 58642d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyToSU->CopyDstRC = SrcRC; 58742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 58842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng // Only copy scheduled successors. Cut them from old node's successor 58942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng // list and move them over. 5902dc7a0e075f619ecd657acdb19c4be8af051e35cEvan Cheng SmallVector<std::pair<SUnit*, bool>, 4> DelDeps; 59142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 59242d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng I != E; ++I) { 59342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng if (I->isSpecial) 59442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng continue; 59542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng if (I->Dep->isScheduled) { 5962dc7a0e075f619ecd657acdb19c4be8af051e35cEvan Cheng CopyToSU->Height = std::max(CopyToSU->Height, I->Dep->Height+1); 59742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng I->Dep->addPred(CopyToSU, I->isCtrl, false, I->Reg, I->Cost); 5982dc7a0e075f619ecd657acdb19c4be8af051e35cEvan Cheng DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl)); 59942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng } 60042d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng } 60142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 6022dc7a0e075f619ecd657acdb19c4be8af051e35cEvan Cheng SUnit *Succ = DelDeps[i].first; 6032dc7a0e075f619ecd657acdb19c4be8af051e35cEvan Cheng bool isCtrl = DelDeps[i].second; 60442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng Succ->removePred(SU, isCtrl, false); 60542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng } 60642d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 60742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyFromSU->addPred(SU, false, false, Reg, -1); 60842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyToSU->addPred(CopyFromSU, false, false, Reg, 1); 60942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 61042d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng AvailableQueue->updateNode(SU); 61142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng AvailableQueue->addNode(CopyFromSU); 61242d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng AvailableQueue->addNode(CopyToSU); 613a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng Copies.push_back(CopyFromSU); 614a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng Copies.push_back(CopyToSU); 61542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 616a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng ++NumCCCopies; 61742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng} 61842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 61942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng/// getPhysicalRegisterVT - Returns the ValueType of the physical register 62042d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng/// definition of the specified node. 62142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng/// FIXME: Move to SelectionDAG? 62242d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Chengstatic MVT::ValueType getPhysicalRegisterVT(SDNode *N, unsigned Reg, 62342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng const TargetInstrInfo *TII) { 624749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = TII->get(N->getTargetOpcode()); 62542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!"); 626349c4952009525b27383e2120a6b3c998f39bd09Chris Lattner unsigned NumRes = TID.getNumDefs(); 627349c4952009525b27383e2120a6b3c998f39bd09Chris Lattner for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) { 62842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng if (Reg == *ImpDef) 62942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng break; 63042d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng ++NumRes; 63142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng } 63242d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng return N->getValueType(NumRes); 63342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng} 63442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 635a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay 636a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// scheduling of the given node to satisfy live physical register dependencies. 637a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// If the specific node is the last one that's available to schedule, do 638a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// whatever is necessary (i.e. backtracking or cloning) to make it possible. 639a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Chengbool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, 640a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<unsigned, 4> &LRegs){ 641a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (LiveRegs.empty()) 642a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return false; 643a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 644cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng SmallSet<unsigned, 4> RegAdded; 645a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // If this node would clobber any "live" register, then it's not ready. 646a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 647a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 648a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (I->Cost < 0) { 649a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng unsigned Reg = I->Reg; 650cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (LiveRegs.count(Reg) && LiveRegDefs[Reg] != I->Dep) { 651cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (RegAdded.insert(Reg)) 652cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng LRegs.push_back(Reg); 653cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng } 6546f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned *Alias = TRI->getAliasSet(Reg); 655a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng *Alias; ++Alias) 656cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != I->Dep) { 657cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (RegAdded.insert(*Alias)) 658cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng LRegs.push_back(*Alias); 659cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng } 660a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 661a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 662a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 663a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (unsigned i = 0, e = SU->FlaggedNodes.size()+1; i != e; ++i) { 664a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SDNode *Node = (i == 0) ? SU->Node : SU->FlaggedNodes[i-1]; 66542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng if (!Node || !Node->isTargetOpcode()) 666a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng continue; 667749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = TII->get(Node->getTargetOpcode()); 668a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (!TID.ImplicitDefs) 669a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng continue; 670a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) { 671cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (LiveRegs.count(*Reg) && LiveRegDefs[*Reg] != SU) { 672cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (RegAdded.insert(*Reg)) 673cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng LRegs.push_back(*Reg); 674cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng } 6756f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned *Alias = TRI->getAliasSet(*Reg); 676a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng *Alias; ++Alias) 677cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != SU) { 678cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (RegAdded.insert(*Alias)) 679cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng LRegs.push_back(*Alias); 680cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng } 681a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 682a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 683a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return !LRegs.empty(); 684e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 685e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 686a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 687e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 688e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// schedulers. 689e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengvoid ScheduleDAGRRList::ListScheduleBottomUp() { 690e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng unsigned CurCycle = 0; 691e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Add root to Available queue. 692a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SUnit *RootSU = SUnitMap[DAG.getRoot().Val].front(); 693a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng RootSU->isAvailable = true; 694a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->push(RootSU); 695e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 696e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // While Available queue is not empty, grab the node with the highest 6978d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman // priority. If it is not ready put it back. Schedule the node. 698a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SmallVector<SUnit*, 4> NotReady; 699e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng while (!AvailableQueue->empty()) { 700a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng bool Delayed = false; 701a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap; 702a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SUnit *CurSU = AvailableQueue->pop(); 703a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng while (CurSU) { 704a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (CurSU->CycleBound <= CurCycle) { 705a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<unsigned, 4> LRegs; 706a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!DelayForLiveRegsBottomUp(CurSU, LRegs)) 707a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng break; 708a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng Delayed = true; 709a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng LRegsMap.insert(std::make_pair(CurSU, LRegs)); 710a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 711a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 712a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng CurSU->isPending = true; // This SU is not in AvailableQueue right now. 713a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng NotReady.push_back(CurSU); 714a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng CurSU = AvailableQueue->pop(); 715e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 716a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 717a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // All candidates are delayed due to live physical reg dependencies. 718a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // Try backtracking, code duplication, or inserting cross class copies 719a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // to resolve it. 720a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (Delayed && !CurSU) { 721a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 722a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SUnit *TrySU = NotReady[i]; 723a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 724a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 725a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // Try unscheduling up to the point where it's safe to schedule 726a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // this node. 727a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng unsigned LiveCycle = CurCycle; 728a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) { 729a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng unsigned Reg = LRegs[j]; 730a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng unsigned LCycle = LiveRegCycles[Reg]; 731a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng LiveCycle = std::min(LiveCycle, LCycle); 732a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 733a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SUnit *OldSU = Sequence[LiveCycle]; 734a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!WillCreateCycle(TrySU, OldSU)) { 735a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng BacktrackBottomUp(TrySU, LiveCycle, CurCycle); 736a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // Force the current node to be scheduled before the node that 737a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // requires the physical reg dep. 738a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (OldSU->isAvailable) { 739a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng OldSU->isAvailable = false; 740a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng AvailableQueue->remove(OldSU); 741a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 742a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng TrySU->addPred(OldSU, true, true); 743a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // If one or more successors has been unscheduled, then the current 744a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // node is no longer avaialable. Schedule a successor that's now 745a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // available instead. 746a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!TrySU->isAvailable) 747a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng CurSU = AvailableQueue->pop(); 748a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng else { 749a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng CurSU = TrySU; 750a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng TrySU->isPending = false; 751a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng NotReady.erase(NotReady.begin()+i); 752a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 753a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng break; 754a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 755a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 756a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 757a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!CurSU) { 758a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // Can't backtrace. Try duplicating the nodes that produces these 759a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // "expensive to copy" values to break the dependency. In case even 760a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // that doesn't work, insert cross class copies. 761a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SUnit *TrySU = NotReady[0]; 762a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 763a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng assert(LRegs.size() == 1 && "Can't handle this yet!"); 764a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng unsigned Reg = LRegs[0]; 765a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SUnit *LRDef = LiveRegDefs[Reg]; 766f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SUnit *NewDef = CopyAndMoveSuccessors(LRDef); 767f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (!NewDef) { 768a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // Issue expensive cross register class copies. 769a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng MVT::ValueType VT = getPhysicalRegisterVT(LRDef->Node, Reg, TII); 770a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng const TargetRegisterClass *RC = 7716f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman TRI->getPhysicalRegisterRegClass(VT, Reg); 7726f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); 773a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!DestRC) { 774a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng assert(false && "Don't know how to copy this physical register!"); 775a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng abort(); 776a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 777a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<SUnit*, 2> Copies; 778a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng InsertCCCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); 779a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng DOUT << "Adding an edge from SU # " << TrySU->NodeNum 780a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng << " to SU #" << Copies.front()->NodeNum << "\n"; 781a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng TrySU->addPred(Copies.front(), true, true); 782a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng NewDef = Copies.back(); 783a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 784a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 785a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng DOUT << "Adding an edge from SU # " << NewDef->NodeNum 786a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng << " to SU #" << TrySU->NodeNum << "\n"; 787a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng LiveRegDefs[Reg] = NewDef; 788a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng NewDef->addPred(TrySU, true, true); 789a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng TrySU->isAvailable = false; 790a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng CurSU = NewDef; 791a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 792a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 793a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!CurSU) { 794a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng assert(false && "Unable to resolve live physical register dependencies!"); 795a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng abort(); 796a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 797a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 798a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 799e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Add the nodes that aren't ready back onto the available list. 800a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 801a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng NotReady[i]->isPending = false; 802a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // May no longer be available due to backtracking. 803a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (NotReady[i]->isAvailable) 804a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->push(NotReady[i]); 805a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 806e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng NotReady.clear(); 807e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 808a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (!CurSU) 809a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Sequence.push_back(0); 810a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng else { 811a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng ScheduleNodeBottomUp(CurSU, CurCycle); 812a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Sequence.push_back(CurSU); 813a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 814a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng ++CurCycle; 815e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 816e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 817e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Add entry node last 818e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (DAG.getEntryNode().Val != DAG.getRoot().Val) { 819a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front(); 820e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng Sequence.push_back(Entry); 821e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 822e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 823e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Reverse the order if it is bottom up. 824e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng std::reverse(Sequence.begin(), Sequence.end()); 825e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 826e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 827e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#ifndef NDEBUG 828e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Verify that all SUnits were scheduled. 829e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool AnyNotSched = false; 830e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 83174d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng if (SUnits[i].NumSuccsLeft != 0) { 832e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (!AnyNotSched) 833832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << "*** List scheduling failed! ***\n"; 834e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnits[i].dump(&DAG); 835832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << "has not been scheduled!\n"; 836e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AnyNotSched = true; 837e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 838e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 839e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng assert(!AnyNotSched); 840e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#endif 841e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 842e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 843e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 844e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// Top-Down Scheduling 845e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 846e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 847e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 8488d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 849e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengvoid ScheduleDAGRRList::ReleaseSucc(SUnit *SuccSU, bool isChain, 850e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng unsigned CurCycle) { 851e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // FIXME: the distance between two nodes is not always == the predecessor's 852e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // latency. For example, the reader can very well read the register written 853e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // by the predecessor later than the issue cycle. It also depends on the 854e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // interrupt model (drain vs. freeze). 855e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency); 856e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 85774d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng --SuccSU->NumPredsLeft; 858e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 859e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#ifndef NDEBUG 86074d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng if (SuccSU->NumPredsLeft < 0) { 861832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << "*** List scheduling failed! ***\n"; 862e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SuccSU->dump(&DAG); 863832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << " has been released too many times!\n"; 864e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng assert(0); 865e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 866e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#endif 867e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 86874d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng if (SuccSU->NumPredsLeft == 0) { 869e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SuccSU->isAvailable = true; 870e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue->push(SuccSU); 871e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 872e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 873e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 874e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 875e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 876e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// count of its successors. If a successor pending count is zero, add it to 877e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// the Available queue. 8786b8e5a93183ab08811b7b71887d8c7d774666210Evan Chengvoid ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 879832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "*** Scheduling [" << CurCycle << "]: "; 880e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng DEBUG(SU->dump(&DAG)); 881e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SU->Cycle = CurCycle; 882e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 883e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue->ScheduledNode(SU); 884e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 885e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Top down: release successors 886228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 887228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner I != E; ++I) 888713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng ReleaseSucc(I->Dep, I->isCtrl, CurCycle); 889e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SU->isScheduled = true; 890e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 891e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 8928d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman/// ListScheduleTopDown - The main loop of list scheduling for top-down 8938d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman/// schedulers. 894e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengvoid ScheduleDAGRRList::ListScheduleTopDown() { 895e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng unsigned CurCycle = 0; 896a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front(); 897e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 898e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // All leaves to Available queue. 899e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 900e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // It is available if it has no predecessors. 901303595942502f17c087fa28874c2b89117148c45Dan Gohman if (SUnits[i].Preds.empty() && &SUnits[i] != Entry) { 902e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue->push(&SUnits[i]); 903e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnits[i].isAvailable = true; 904e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 905e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 906e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 907e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Emit the entry node first. 908e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng ScheduleNodeTopDown(Entry, CurCycle); 909a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Sequence.push_back(Entry); 910a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng ++CurCycle; 911e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 912e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // While Available queue is not empty, grab the node with the highest 9138d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman // priority. If it is not ready put it back. Schedule the node. 914e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng std::vector<SUnit*> NotReady; 915e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng while (!AvailableQueue->empty()) { 916a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SUnit *CurSU = AvailableQueue->pop(); 917a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng while (CurSU && CurSU->CycleBound > CurCycle) { 918a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng NotReady.push_back(CurSU); 919a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng CurSU = AvailableQueue->pop(); 920e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 921e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 922e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Add the nodes that aren't ready back onto the available list. 923e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue->push_all(NotReady); 924e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng NotReady.clear(); 925e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 926a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (!CurSU) 927a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Sequence.push_back(0); 928a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng else { 929a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng ScheduleNodeTopDown(CurSU, CurCycle); 930a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Sequence.push_back(CurSU); 931a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 9326b8e5a93183ab08811b7b71887d8c7d774666210Evan Cheng CurCycle++; 933e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 934e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 935e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 936e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#ifndef NDEBUG 937e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Verify that all SUnits were scheduled. 938e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool AnyNotSched = false; 939e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 940e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (!SUnits[i].isScheduled) { 941e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (!AnyNotSched) 942832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << "*** List scheduling failed! ***\n"; 943e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnits[i].dump(&DAG); 944832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << "has not been scheduled!\n"; 945e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AnyNotSched = true; 946e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 947e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 948e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng assert(!AnyNotSched); 949e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#endif 950e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 951e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 952e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 953e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 954e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 955e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// RegReductionPriorityQueue Implementation 956e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 957e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// 958e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers 959e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// to reduce register pressure. 960e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// 961e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengnamespace { 962e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng template<class SF> 963e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng class RegReductionPriorityQueue; 964e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 965e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// Sorting functions for the Available queue. 966e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 967e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ; 968e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {} 969e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 970e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 971e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool operator()(const SUnit* left, const SUnit* right) const; 972e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 973e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 974e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 975e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng RegReductionPriorityQueue<td_ls_rr_sort> *SPQ; 976e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {} 977e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 978e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 979e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool operator()(const SUnit* left, const SUnit* right) const; 980e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 981e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} // end anonymous namespace 982e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 983c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Chengstatic inline bool isCopyFromLiveIn(const SUnit *SU) { 984c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng SDNode *N = SU->Node; 98542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng return N && N->getOpcode() == ISD::CopyFromReg && 986c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag; 987c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng} 988c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng 989e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengnamespace { 990e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng template<class SF> 9919525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner class VISIBILITY_HIDDEN RegReductionPriorityQueue 9929525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner : public SchedulingPriorityQueue { 993e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng std::priority_queue<SUnit*, std::vector<SUnit*>, SF> Queue; 994e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 995e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng public: 996e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng RegReductionPriorityQueue() : 997e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng Queue(SF(this)) {} 998e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 999a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap, 100095f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng std::vector<SUnit> &sunits) {} 1001a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1002a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void addNode(const SUnit *SU) {} 1003a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1004a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void updateNode(const SUnit *SU) {} 1005a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1006e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual void releaseState() {} 1007e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1008c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng virtual unsigned getNodePriority(const SUnit *SU) const { 1009e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return 0; 1010e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1011e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1012a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng unsigned size() const { return Queue.size(); } 1013a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1014e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool empty() const { return Queue.empty(); } 1015e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1016e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void push(SUnit *U) { 1017e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng Queue.push(U); 1018e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1019e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void push_all(const std::vector<SUnit *> &Nodes) { 1020e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng for (unsigned i = 0, e = Nodes.size(); i != e; ++i) 1021e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng Queue.push(Nodes[i]); 1022e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1023e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1024e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnit *pop() { 10256b8e5a93183ab08811b7b71887d8c7d774666210Evan Cheng if (empty()) return NULL; 1026e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnit *V = Queue.top(); 1027e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng Queue.pop(); 1028e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return V; 1029e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 103095f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 1031a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng /// remove - This is a really inefficient way to remove a node from a 1032a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng /// priority queue. We should roll our own heap to make this better or 1033a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng /// something. 1034a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng void remove(SUnit *SU) { 1035a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng std::vector<SUnit*> Temp; 1036a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1037a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng assert(!Queue.empty() && "Not in queue!"); 1038a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng while (Queue.top() != SU) { 1039a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Temp.push_back(Queue.top()); 1040a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Queue.pop(); 1041a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng assert(!Queue.empty() && "Not in queue!"); 1042a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 1043a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1044a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // Remove the node from the PQ. 1045a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Queue.pop(); 1046a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1047a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // Add all the other nodes back. 1048a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (unsigned i = 0, e = Temp.size(); i != e; ++i) 1049a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Queue.push(Temp[i]); 105095f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 1051e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 1052e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1053e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng template<class SF> 10549525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner class VISIBILITY_HIDDEN BURegReductionPriorityQueue 10559525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner : public RegReductionPriorityQueue<SF> { 1056a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // SUnitMap SDNode to SUnit mapping (n -> n). 1057a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap; 105895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 1059e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // SUnits - The SUnits for the current graph. 1060e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng const std::vector<SUnit> *SUnits; 1061e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1062e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // SethiUllmanNumbers - The SethiUllman number for each node. 1063c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng std::vector<unsigned> SethiUllmanNumbers; 1064e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 106595f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng const TargetInstrInfo *TII; 10666f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI; 1067e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng public: 1068180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng explicit BURegReductionPriorityQueue(const TargetInstrInfo *tii, 10696f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *tri) 10706f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman : TII(tii), TRI(tri) {} 1071e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1072a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap, 107395f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng std::vector<SUnit> &sunits) { 107495f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng SUnitMap = &sumap; 1075e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnits = &sunits; 1076e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Add pseudo dependency edges for two-address nodes. 107713d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng AddPseudoTwoAddrDeps(); 1078e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Calculate node priorities. 1079c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng CalculateSethiUllmanNumbers(); 1080e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1081e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1082a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng void addNode(const SUnit *SU) { 1083a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SethiUllmanNumbers.resize(SUnits->size(), 0); 1084a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng CalcNodeSethiUllmanNumber(SU); 1085a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 1086a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1087a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng void updateNode(const SUnit *SU) { 1088a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SethiUllmanNumbers[SU->NodeNum] = 0; 1089a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng CalcNodeSethiUllmanNumber(SU); 1090a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 1091a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1092e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void releaseState() { 1093e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnits = 0; 1094e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SethiUllmanNumbers.clear(); 1095e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1096e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1097c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned getNodePriority(const SUnit *SU) const { 1098c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng assert(SU->NodeNum < SethiUllmanNumbers.size()); 109942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng unsigned Opc = SU->Node ? SU->Node->getOpcode() : 0; 1100c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng if (Opc == ISD::CopyFromReg && !isCopyFromLiveIn(SU)) 1101c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // CopyFromReg should be close to its def because it restricts 1102c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // allocation choices. But if it is a livein then perhaps we want it 1103c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // closer to its uses so it can be coalesced. 1104c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return 0xffff; 1105c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng else if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 1106c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // CopyToReg should be close to its uses to facilitate coalescing and 1107c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // avoid spilling. 1108c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return 0; 110932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng else if (Opc == TargetInstrInfo::EXTRACT_SUBREG || 111032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng Opc == TargetInstrInfo::INSERT_SUBREG) 111132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // EXTRACT_SUBREG / INSERT_SUBREG should be close to its use to 111232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // facilitate coalescing. 111332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng return 0; 1114c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng else if (SU->NumSuccs == 0) 1115c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // If SU does not have a use, i.e. it doesn't produce a value that would 1116c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // be consumed (e.g. store), then it terminates a chain of computation. 1117c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // Give it a large SethiUllman number so it will be scheduled right 1118c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // before its predecessors that it doesn't lengthen their live ranges. 1119c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return 0xffff; 1120c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng else if (SU->NumPreds == 0) 1121c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // If SU does not have a def, schedule it close to its uses because it 1122c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // does not lengthen any live ranges. 1123c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return 0; 1124c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng else 1125c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return SethiUllmanNumbers[SU->NodeNum]; 1126e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1127e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1128e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng private: 112995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng bool canClobber(SUnit *SU, SUnit *Op); 1130e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void AddPseudoTwoAddrDeps(); 1131c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng void CalculateSethiUllmanNumbers(); 1132c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned CalcNodeSethiUllmanNumber(const SUnit *SU); 1133e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 1134e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1135e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1136e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng template<class SF> 11378d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman class VISIBILITY_HIDDEN TDRegReductionPriorityQueue 11388d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman : public RegReductionPriorityQueue<SF> { 1139a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // SUnitMap SDNode to SUnit mapping (n -> n). 1140a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap; 114195f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 1142e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // SUnits - The SUnits for the current graph. 1143e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng const std::vector<SUnit> *SUnits; 1144e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1145e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // SethiUllmanNumbers - The SethiUllman number for each node. 1146c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng std::vector<unsigned> SethiUllmanNumbers; 1147e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1148e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng public: 1149e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng TDRegReductionPriorityQueue() {} 1150e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1151a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap, 115295f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng std::vector<SUnit> &sunits) { 115395f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng SUnitMap = &sumap; 1154e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnits = &sunits; 1155e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Calculate node priorities. 1156c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng CalculateSethiUllmanNumbers(); 1157e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1158e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1159a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng void addNode(const SUnit *SU) { 1160a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SethiUllmanNumbers.resize(SUnits->size(), 0); 1161a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng CalcNodeSethiUllmanNumber(SU); 1162a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 1163a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1164a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng void updateNode(const SUnit *SU) { 1165a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SethiUllmanNumbers[SU->NodeNum] = 0; 1166a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng CalcNodeSethiUllmanNumber(SU); 1167a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 1168a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1169e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void releaseState() { 1170e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnits = 0; 1171e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SethiUllmanNumbers.clear(); 1172e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1173e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1174c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned getNodePriority(const SUnit *SU) const { 1175c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng assert(SU->NodeNum < SethiUllmanNumbers.size()); 1176c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return SethiUllmanNumbers[SU->NodeNum]; 1177e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1178e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1179e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng private: 1180c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng void CalculateSethiUllmanNumbers(); 1181c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned CalcNodeSethiUllmanNumber(const SUnit *SU); 1182e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 1183e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1184e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1185c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng/// closestSucc - Returns the scheduled cycle of the successor which is 1186c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng/// closet to the current cycle. 118761230d18d21a5dca1378e994f43934e4b314e595Evan Chengstatic unsigned closestSucc(const SUnit *SU) { 118861230d18d21a5dca1378e994f43934e4b314e595Evan Cheng unsigned MaxCycle = 0; 118961230d18d21a5dca1378e994f43934e4b314e595Evan Cheng for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1190c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng I != E; ++I) { 1191713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng unsigned Cycle = I->Dep->Cycle; 1192c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng // If there are bunch of CopyToRegs stacked up, they should be considered 1193c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng // to be at the same position. 119442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng if (I->Dep->Node && I->Dep->Node->getOpcode() == ISD::CopyToReg) 1195713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng Cycle = closestSucc(I->Dep)+1; 1196c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng if (Cycle > MaxCycle) 1197c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng MaxCycle = Cycle; 1198c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng } 119961230d18d21a5dca1378e994f43934e4b314e595Evan Cheng return MaxCycle; 120061230d18d21a5dca1378e994f43934e4b314e595Evan Cheng} 120161230d18d21a5dca1378e994f43934e4b314e595Evan Cheng 1202d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng/// calcMaxScratches - Returns an cost estimate of the worse case requirement 1203d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng/// for scratch registers. Live-in operands and live-out results don't count 1204d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng/// since they are "fixed". 1205d6c0758944b31bb5316b36cad37f4610a77f784dEvan Chengstatic unsigned calcMaxScratches(const SUnit *SU) { 1206d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng unsigned Scratches = 0; 1207d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1208d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng I != E; ++I) { 1209d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng if (I->isCtrl) continue; // ignore chain preds 121019107563af7568713193c60be24503446556bff2Evan Cheng if (!I->Dep->Node || I->Dep->Node->getOpcode() != ISD::CopyFromReg) 1211d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng Scratches++; 1212d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng } 1213d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1214d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng I != E; ++I) { 1215d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng if (I->isCtrl) continue; // ignore chain succs 121619107563af7568713193c60be24503446556bff2Evan Cheng if (!I->Dep->Node || I->Dep->Node->getOpcode() != ISD::CopyToReg) 1217d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng Scratches += 10; 1218d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng } 1219d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng return Scratches; 1220d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng} 1221d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng 1222e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// Bottom up 1223e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengbool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 1224a2a488594df335efa17bc253436465c2ae984f91David Greene // There used to be a special tie breaker here that looked for 1225a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // two-address instructions and preferred the instruction with a 1226a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // def&use operand. The special case triggered diagnostics when 1227a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // _GLIBCXX_DEBUG was enabled because it broke the strict weak 1228a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // ordering that priority_queue requires. It didn't help much anyway 1229a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // because AddPseudoTwoAddrDeps already covers many of the cases 1230a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // where it would have applied. In addition, it's counter-intuitive 1231a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // that a tie breaker would be the first thing attempted. There's a 1232a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // "real" tie breaker below that is the operation of last resort. 1233a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // The fact that the "special tie breaker" would trigger when there 1234a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // wasn't otherwise a tie is what broke the strict weak ordering 1235a4ab2e8c726e1702d74eb207536bf953bd3d5c81David Greene // constraint. 12368820ad5154eae194a685a8735bd5999221fdffd0Evan Cheng 1237c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned LPriority = SPQ->getNodePriority(left); 1238c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned RPriority = SPQ->getNodePriority(right); 1239c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng if (LPriority > RPriority) 1240e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return true; 124161230d18d21a5dca1378e994f43934e4b314e595Evan Cheng else if (LPriority == RPriority) { 1242edc1d159841fd279d58177bfd6ac4bc1f616d91aDan Gohman // Try schedule def + use closer when Sethi-Ullman numbers are the same. 124361230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // e.g. 124461230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // t1 = op t2, c1 124561230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // t3 = op t4, c2 124661230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // 124761230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // and the following instructions are both ready. 124861230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // t2 = op c3 124961230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // t4 = op c4 125061230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // 125161230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // Then schedule t2 = op first. 125261230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // i.e. 125361230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // t4 = op c4 125461230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // t2 = op c3 125561230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // t1 = op t2, c1 125661230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // t3 = op t4, c2 125761230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // 125861230d18d21a5dca1378e994f43934e4b314e595Evan Cheng // This creates more short live intervals. 125961230d18d21a5dca1378e994f43934e4b314e595Evan Cheng unsigned LDist = closestSucc(left); 126061230d18d21a5dca1378e994f43934e4b314e595Evan Cheng unsigned RDist = closestSucc(right); 126161230d18d21a5dca1378e994f43934e4b314e595Evan Cheng if (LDist < RDist) 1262e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return true; 1263c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng else if (LDist == RDist) { 1264d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng // Intuitively, it's good to push down instructions whose results are 1265d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng // liveout so their long live ranges won't conflict with other values 1266d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng // which are needed inside the BB. Further prioritize liveout instructions 1267d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng // by the number of operands which are calculated within the BB. 1268d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng unsigned LScratch = calcMaxScratches(left); 1269d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng unsigned RScratch = calcMaxScratches(right); 1270d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng if (LScratch > RScratch) 1271e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return true; 1272d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng else if (LScratch == RScratch) 1273d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng if (left->Height > right->Height) 12748820ad5154eae194a685a8735bd5999221fdffd0Evan Cheng return true; 1275d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng else if (left->Height == right->Height) 1276d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng if (left->Depth < right->Depth) 127761230d18d21a5dca1378e994f43934e4b314e595Evan Cheng return true; 1278d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng else if (left->Depth == right->Depth) 1279d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng if (left->CycleBound > right->CycleBound) 1280d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng return true; 1281c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng } 128261230d18d21a5dca1378e994f43934e4b314e595Evan Cheng } 1283e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return false; 1284e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1285e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 128695f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Chengtemplate<class SF> 128795f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Chengbool BURegReductionPriorityQueue<SF>::canClobber(SUnit *SU, SUnit *Op) { 128895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng if (SU->isTwoAddress) { 128995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng unsigned Opc = SU->Node->getTargetOpcode(); 1290749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = TII->get(Opc); 12913db805ea80eeec9084a1b86273d93804d233d938Chris Lattner unsigned NumRes = TID.getNumDefs(); 12923b66555c53eb8921b2dd50335e0b278ddf80d220Dan Gohman unsigned NumOps = TID.getNumOperands() - NumRes; 129395f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng for (unsigned i = 0; i != NumOps; ++i) { 12943db805ea80eeec9084a1b86273d93804d233d938Chris Lattner if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) { 129595f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng SDNode *DU = SU->Node->getOperand(i).Val; 12967da8f399bf09e9a03fe8bdd8c8eef6e5a7d87327Evan Cheng if ((*SUnitMap).find(DU) != (*SUnitMap).end() && 12977da8f399bf09e9a03fe8bdd8c8eef6e5a7d87327Evan Cheng Op == (*SUnitMap)[DU][SU->InstanceNo]) 129895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng return true; 129995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 130095f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 1301e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1302e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return false; 1303e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1304e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 130595f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 130622a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// hasCopyToRegUse - Return true if SU has a value successor that is a 130722a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// CopyToReg node. 130822a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Chengstatic bool hasCopyToRegUse(SUnit *SU) { 130922a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 131022a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng I != E; ++I) { 131122a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng if (I->isCtrl) continue; 131222a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng SUnit *SuccSU = I->Dep; 131322a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng if (SuccSU->Node && SuccSU->Node->getOpcode() == ISD::CopyToReg) 131422a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng return true; 131522a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng } 131622a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng return false; 131722a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng} 131822a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng 1319180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng/// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's 1320180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng/// physical register def. 1321180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Chengstatic bool canClobberPhysRegDefs(SUnit *SuccSU, SUnit *SU, 1322180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng const TargetInstrInfo *TII, 13236f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI) { 1324180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng SDNode *N = SuccSU->Node; 1325349c4952009525b27383e2120a6b3c998f39bd09Chris Lattner unsigned NumDefs = TII->get(N->getTargetOpcode()).getNumDefs(); 1326349c4952009525b27383e2120a6b3c998f39bd09Chris Lattner const unsigned *ImpDefs = TII->get(N->getTargetOpcode()).getImplicitDefs(); 1327180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng if (!ImpDefs) 1328180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng return false; 1329349c4952009525b27383e2120a6b3c998f39bd09Chris Lattner const unsigned *SUImpDefs = 1330349c4952009525b27383e2120a6b3c998f39bd09Chris Lattner TII->get(SU->Node->getTargetOpcode()).getImplicitDefs(); 1331180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng if (!SUImpDefs) 1332180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng return false; 1333180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) { 1334180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng MVT::ValueType VT = N->getValueType(i); 1335180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng if (VT == MVT::Flag || VT == MVT::Other) 1336180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng continue; 1337180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng unsigned Reg = ImpDefs[i - NumDefs]; 1338180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng for (;*SUImpDefs; ++SUImpDefs) { 1339180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng unsigned SUReg = *SUImpDefs; 13406f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TRI->regsOverlap(Reg, SUReg)) 1341180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng return true; 1342180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng } 1343180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng } 1344180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng return false; 1345180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng} 1346180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng 1347e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses 1348e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// it as a def&use operand. Add a pseudo control edge from it to the other 1349e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// node (if it won't create a cycle) so the two-address one will be scheduled 135022a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// first (lower in the schedule). If both nodes are two-address, favor the 135122a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// one that has a CopyToReg use (more likely to be a loop induction update). 135222a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// If both are two-address, but one is commutable while the other is not 135322a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// commutable, favor the one that's not commutable. 1354e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengtemplate<class SF> 1355e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengvoid BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() { 135695f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 135795f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng SUnit *SU = (SUnit *)&((*SUnits)[i]); 135895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng if (!SU->isTwoAddress) 135995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng continue; 136095f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 136195f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng SDNode *Node = SU->Node; 136222a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng if (!Node || !Node->isTargetOpcode() || SU->FlaggedNodes.size() > 0) 136395f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng continue; 136495f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 136595f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng unsigned Opc = Node->getTargetOpcode(); 1366749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = TII->get(Opc); 13673db805ea80eeec9084a1b86273d93804d233d938Chris Lattner unsigned NumRes = TID.getNumDefs(); 13683b66555c53eb8921b2dd50335e0b278ddf80d220Dan Gohman unsigned NumOps = TID.getNumOperands() - NumRes; 136995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng for (unsigned j = 0; j != NumOps; ++j) { 13703db805ea80eeec9084a1b86273d93804d233d938Chris Lattner if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) != -1) { 137195f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng SDNode *DU = SU->Node->getOperand(j).Val; 13727da8f399bf09e9a03fe8bdd8c8eef6e5a7d87327Evan Cheng if ((*SUnitMap).find(DU) == (*SUnitMap).end()) 13737da8f399bf09e9a03fe8bdd8c8eef6e5a7d87327Evan Cheng continue; 1374a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SUnit *DUSU = (*SUnitMap)[DU][SU->InstanceNo]; 1375d5ad440f4371448e2c926b4f6613cc7107dd5c5cEvan Cheng if (!DUSU) continue; 137695f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end(); 137795f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng I != E; ++I) { 1378713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng if (I->isCtrl) continue; 1379713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SUnit *SuccSU = I->Dep; 1380180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng if (SuccSU == SU) 1381a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng continue; 13821fd15ba9614e81a3b9cc5cd9631ca76c845159b2Evan Cheng // Be conservative. Ignore if nodes aren't at roughly the same 13831fd15ba9614e81a3b9cc5cd9631ca76c845159b2Evan Cheng // depth and height. 13841fd15ba9614e81a3b9cc5cd9631ca76c845159b2Evan Cheng if (SuccSU->Height < SU->Height && (SU->Height - SuccSU->Height) > 1) 13851fd15ba9614e81a3b9cc5cd9631ca76c845159b2Evan Cheng continue; 138632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (!SuccSU->Node || !SuccSU->Node->isTargetOpcode()) 138732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng continue; 1388180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng // Don't constrain nodes with physical register defs if the 13899f65c39f806186e1bbe1c9e4b670d198c69a81c1Dan Gohman // predecessor can clobber them. 1390180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng if (SuccSU->hasPhysRegDefs) { 13916f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI)) 1392180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng continue; 1393180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng } 139432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Don't constraint extract_subreg / insert_subreg these may be 139532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // coalesced away. We don't them close to their uses. 139632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng unsigned SuccOpc = SuccSU->Node->getTargetOpcode(); 139732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG || 139832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng SuccOpc == TargetInstrInfo::INSERT_SUBREG) 139932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng continue; 1400a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if ((!canClobber(SuccSU, DUSU) || 140122a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) || 1402a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng (!SU->isCommutable && SuccSU->isCommutable)) && 1403a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng !isReachable(SuccSU, SU)) { 1404a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng DOUT << "Adding an edge from SU # " << SU->NodeNum 1405a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng << " to SU #" << SuccSU->NodeNum << "\n"; 1406a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SU->addPred(SuccSU, true, true); 140795f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 140895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 140995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 141095f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 141195f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 1412e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1413e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1414c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng/// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number. 1415e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// Smaller number is the higher priority. 1416e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengtemplate<class SF> 1417fea997aac5773e936754de5436029c2a4fa1e930Chris Lattnerunsigned BURegReductionPriorityQueue<SF>:: 1418fea997aac5773e936754de5436029c2a4fa1e930Chris LattnerCalcNodeSethiUllmanNumber(const SUnit *SU) { 1419c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; 1420e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (SethiUllmanNumber != 0) 1421e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return SethiUllmanNumber; 1422e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1423c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng unsigned Extra = 0; 1424c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1425c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng I != E; ++I) { 1426713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng if (I->isCtrl) continue; // ignore chain preds 1427713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SUnit *PredSU = I->Dep; 1428c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU); 1429c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng if (PredSethiUllman > SethiUllmanNumber) { 1430c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng SethiUllmanNumber = PredSethiUllman; 1431c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng Extra = 0; 1432713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl) 1433a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng ++Extra; 1434e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1435c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng 1436c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng SethiUllmanNumber += Extra; 1437c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng 1438c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng if (SethiUllmanNumber == 0) 1439c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng SethiUllmanNumber = 1; 1440e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1441e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return SethiUllmanNumber; 1442e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1443e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1444c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all 1445c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng/// scheduling units. 1446e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengtemplate<class SF> 1447c8edc64188399437f5476d7fa45f714a92f2cb93Evan Chengvoid BURegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() { 1448e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SethiUllmanNumbers.assign(SUnits->size(), 0); 1449e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1450e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 1451c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng CalcNodeSethiUllmanNumber(&(*SUnits)[i]); 1452e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1453e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1454e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengstatic unsigned SumOfUnscheduledPredsOfSuccs(const SUnit *SU) { 1455e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng unsigned Sum = 0; 1456228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1457228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner I != E; ++I) { 1458713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SUnit *SuccSU = I->Dep; 1459228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(), 1460228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner EE = SuccSU->Preds.end(); II != EE; ++II) { 1461713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SUnit *PredSU = II->Dep; 1462e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (!PredSU->isScheduled) 1463a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng ++Sum; 1464e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1465e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1466e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1467e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return Sum; 1468e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1469e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1470e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1471e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// Top down 1472e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengbool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 1473c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned LPriority = SPQ->getNodePriority(left); 1474c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned RPriority = SPQ->getNodePriority(right); 147542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng bool LIsTarget = left->Node && left->Node->isTargetOpcode(); 147642d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng bool RIsTarget = right->Node && right->Node->isTargetOpcode(); 1477e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool LIsFloater = LIsTarget && left->NumPreds == 0; 1478e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool RIsFloater = RIsTarget && right->NumPreds == 0; 1479e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng unsigned LBonus = (SumOfUnscheduledPredsOfSuccs(left) == 1) ? 2 : 0; 1480e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng unsigned RBonus = (SumOfUnscheduledPredsOfSuccs(right) == 1) ? 2 : 0; 1481e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1482e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (left->NumSuccs == 0 && right->NumSuccs != 0) 1483e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return false; 1484e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng else if (left->NumSuccs != 0 && right->NumSuccs == 0) 1485e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return true; 1486e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1487e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Special tie breaker: if two nodes share a operand, the one that use it 1488e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // as a def&use operand is preferred. 1489e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (LIsTarget && RIsTarget) { 1490e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (left->isTwoAddress && !right->isTwoAddress) { 1491e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SDNode *DUNode = left->Node->getOperand(0).Val; 1492e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (DUNode->isOperand(right->Node)) 1493e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng RBonus += 2; 1494e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1495e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (!left->isTwoAddress && right->isTwoAddress) { 1496e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SDNode *DUNode = right->Node->getOperand(0).Val; 1497e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (DUNode->isOperand(left->Node)) 1498e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng LBonus += 2; 1499e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1500e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1501e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (LIsFloater) 1502e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng LBonus -= 2; 1503e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (RIsFloater) 1504e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng RBonus -= 2; 1505e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (left->NumSuccs == 1) 1506e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng LBonus += 2; 1507e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (right->NumSuccs == 1) 1508e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng RBonus += 2; 1509e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1510e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (LPriority+LBonus < RPriority+RBonus) 1511e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return true; 1512e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng else if (LPriority == RPriority) 1513e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (left->Depth < right->Depth) 1514e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return true; 1515e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng else if (left->Depth == right->Depth) 1516e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (left->NumSuccsLeft > right->NumSuccsLeft) 1517e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return true; 1518e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng else if (left->NumSuccsLeft == right->NumSuccsLeft) 1519e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (left->CycleBound > right->CycleBound) 1520e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return true; 1521e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return false; 1522e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1523e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1524c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng/// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number. 1525e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// Smaller number is the higher priority. 1526e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengtemplate<class SF> 1527fea997aac5773e936754de5436029c2a4fa1e930Chris Lattnerunsigned TDRegReductionPriorityQueue<SF>:: 1528fea997aac5773e936754de5436029c2a4fa1e930Chris LattnerCalcNodeSethiUllmanNumber(const SUnit *SU) { 1529c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; 1530e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (SethiUllmanNumber != 0) 1531e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return SethiUllmanNumber; 1532e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 153342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng unsigned Opc = SU->Node ? SU->Node->getOpcode() : 0; 1534e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 1535c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng SethiUllmanNumber = 0xffff; 1536e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng else if (SU->NumSuccsLeft == 0) 1537e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // If SU does not have a use, i.e. it doesn't produce a value that would 1538e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // be consumed (e.g. store), then it terminates a chain of computation. 1539fea997aac5773e936754de5436029c2a4fa1e930Chris Lattner // Give it a small SethiUllman number so it will be scheduled right before 1540fea997aac5773e936754de5436029c2a4fa1e930Chris Lattner // its predecessors that it doesn't lengthen their live ranges. 1541c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng SethiUllmanNumber = 0; 1542e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng else if (SU->NumPredsLeft == 0 && 1543e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU))) 1544c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng SethiUllmanNumber = 0xffff; 1545e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng else { 1546e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng int Extra = 0; 1547228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1548228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner I != E; ++I) { 1549713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng if (I->isCtrl) continue; // ignore chain preds 1550713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SUnit *PredSU = I->Dep; 1551c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU); 1552e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (PredSethiUllman > SethiUllmanNumber) { 1553e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SethiUllmanNumber = PredSethiUllman; 1554e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng Extra = 0; 1555713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl) 1556a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng ++Extra; 1557e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1558e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1559e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SethiUllmanNumber += Extra; 1560e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1561e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1562e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return SethiUllmanNumber; 1563e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1564e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1565c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all 1566c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng/// scheduling units. 1567e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengtemplate<class SF> 1568c8edc64188399437f5476d7fa45f714a92f2cb93Evan Chengvoid TDRegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() { 1569e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SethiUllmanNumbers.assign(SUnits->size(), 0); 1570e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1571e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 1572c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng CalcNodeSethiUllmanNumber(&(*SUnits)[i]); 1573e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1574e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1575e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 1576e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// Public Constructor Functions 1577e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 1578e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 15799ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskeyllvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, 15809ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey SelectionDAG *DAG, 1581e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng MachineBasicBlock *BB) { 158295f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo(); 15836f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI = DAG->getTarget().getRegisterInfo(); 158413ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true, 15856f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman new BURegReductionPriorityQueue<bu_ls_rr_sort>(TII, TRI)); 1586e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1587e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 15889ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskeyllvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, 15899ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey SelectionDAG *DAG, 1590e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng MachineBasicBlock *BB) { 159113ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false, 1592fea997aac5773e936754de5436029c2a4fa1e930Chris Lattner new TDRegReductionPriorityQueue<td_ls_rr_sort>()); 1593e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1594e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1595