ScheduleDAGRRList.cpp revision ce0d4b7a77da716f234d42edd0472e97b3ba5f57
104f4f4f447806cd92a2fb6f4b66d11f6d5003a82Dan Gohman//===----- ScheduleDAGRRList.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" 19343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/ScheduleDAGSDNodes.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" 273627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman#include "llvm/ADT/PriorityQueue.h" 28a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng#include "llvm/ADT/SmallSet.h" 29e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include "llvm/ADT/Statistic.h" 30a0201d52049be8dcefffe4304a49690a831bcb34Roman Levenstein#include "llvm/ADT/STLExtras.h" 31e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include <climits> 32e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#include "llvm/Support/CommandLine.h" 33e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengusing namespace llvm; 34e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 35cffbd2562a5e3ba435dd2b622710ec272c634da5Dan GohmanSTATISTIC(NumBacktracks, "Number of times scheduler backtracked"); 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", 42b8cab9227a0f6ffbdaae33e3c64268e265008a6aDan Gohman "Bottom-up register reduction list scheduling", 4313ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey createBURRListDAGScheduler); 4413ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskeystatic RegisterScheduler 4513ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey tdrListrDAGScheduler("list-tdrr", 46b8cab9227a0f6ffbdaae33e3c64268e265008a6aDan Gohman "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/// 54343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanclass VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAGSDNodes { 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; 594576f6d7a9c0f2c6a3b6c5d4d8a3063bbf763ae5Evan Cheng 60e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// AvailableQueue - The priority queue to use for the available SUnits. 61e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SchedulingPriorityQueue *AvailableQueue; 62e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 63086ec9976ff6cee083de618429c78473491d5713Dan Gohman /// 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. 66086ec9976ff6cee083de618429c78473491d5713Dan Gohman unsigned NumLiveRegs; 67a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng std::vector<SUnit*> LiveRegDefs; 68a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng std::vector<unsigned> LiveRegCycles; 69a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 7021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Topo - A topological ordering for SUnits which permits fast IsReachable 7121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// and similar queries. 7221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman ScheduleDAGTopologicalSort Topo; 7321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 74e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengpublic: 75a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman ScheduleDAGRRList(SelectionDAG *dag, MachineBasicBlock *bb, 769e76fea3abd4229749e6ead46a0016cabff4a056Dan Gohman const TargetMachine &tm, bool isbottomup, 774576f6d7a9c0f2c6a3b6c5d4d8a3063bbf763ae5Evan Cheng SchedulingPriorityQueue *availqueue) 789e76fea3abd4229749e6ead46a0016cabff4a056Dan Gohman : ScheduleDAGSDNodes(dag, bb, tm), isBottomUp(isbottomup), 7921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman AvailableQueue(availqueue), Topo(SUnits) { 80e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 81e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 82e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng ~ScheduleDAGRRList() { 83e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng delete AvailableQueue; 84e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 85e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 86e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void Schedule(); 87e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 888dba9afd086f72db920db81a3d73c7297390cda7Roman Levenstein /// IsReachable - Checks if SU is reachable from TargetSU. 8921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool IsReachable(const SUnit *SU, const SUnit *TargetSU) { 9021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return Topo.IsReachable(SU, TargetSU); 9121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 92e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein 93e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein /// willCreateCycle - Returns true if adding an edge from SU to TargetSU will 94e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein /// create a cycle. 9521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) { 9621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return Topo.WillCreateCycle(SU, TargetSU); 9721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 98e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein 9954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// AddPred - adds a predecessor edge to SUnit SU. 1008dba9afd086f72db920db81a3d73c7297390cda7Roman Levenstein /// This returns true if this is a new predecessor. 1018dba9afd086f72db920db81a3d73c7297390cda7Roman Levenstein /// Updates the topological ordering if required. 102ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman void AddPred(SUnit *SU, const SDep &D) { 10354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Topo.AddPred(SU, D.getSUnit()); 104ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman SU->addPred(D); 10521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 106e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein 10754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// RemovePred - removes a predecessor edge from SUnit SU. 10854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// This returns true if an edge was removed. 10954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Updates the topological ordering if required. 110ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman void RemovePred(SUnit *SU, const SDep &D) { 11154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Topo.RemovePred(SU, D.getSUnit()); 112ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman SU->removePred(D); 11321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 114e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein 115e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengprivate: 11654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman void ReleasePred(SUnit *SU, SDep *PredEdge); 11754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman void ReleaseSucc(SUnit *SU, SDep *SuccEdge); 11854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman void CapturePred(SDep *PredEdge); 11942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void ScheduleNodeBottomUp(SUnit*, unsigned); 12042d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void ScheduleNodeTopDown(SUnit*, unsigned); 12142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void UnscheduleNodeBottomUp(SUnit*); 12242d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng void BacktrackBottomUp(SUnit*, unsigned, unsigned&); 12342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng SUnit *CopyAndMoveSuccessors(SUnit*); 124a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng void InsertCCCopiesAndMoveSuccs(SUnit*, unsigned, 125a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng const TargetRegisterClass*, 12642d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng const TargetRegisterClass*, 127a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<SUnit*, 2>&); 128a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&); 129e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void ListScheduleTopDown(); 130e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void ListScheduleBottomUp(); 131e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein 132e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein 133e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it. 1348dba9afd086f72db920db81a3d73c7297390cda7Roman Levenstein /// Updates the topological ordering if required. 135e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein SUnit *CreateNewSUnit(SDNode *N) { 13621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned NumSUnits = SUnits.size(); 137e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein SUnit *NewNode = NewSUnit(N); 1388dba9afd086f72db920db81a3d73c7297390cda7Roman Levenstein // Update the topological ordering. 13921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (NewNode->NodeNum >= NumSUnits) 14021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Topo.InitDAGTopologicalSorting(); 141e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein return NewNode; 142e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein } 143e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein 1448dba9afd086f72db920db81a3d73c7297390cda7Roman Levenstein /// CreateClone - Creates a new SUnit from an existing one. 1458dba9afd086f72db920db81a3d73c7297390cda7Roman Levenstein /// Updates the topological ordering if required. 146e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein SUnit *CreateClone(SUnit *N) { 14721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned NumSUnits = SUnits.size(); 148e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein SUnit *NewNode = Clone(N); 1498dba9afd086f72db920db81a3d73c7297390cda7Roman Levenstein // Update the topological ordering. 15021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (NewNode->NodeNum >= NumSUnits) 15121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Topo.InitDAGTopologicalSorting(); 152e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein return NewNode; 153e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein } 1543f23744df4809eba94284e601e81489212c974d4Dan Gohman 1553f23744df4809eba94284e601e81489212c974d4Dan Gohman /// ForceUnitLatencies - Return true, since register-pressure-reducing 1563f23744df4809eba94284e601e81489212c974d4Dan Gohman /// scheduling doesn't need actual latency information. 1573f23744df4809eba94284e601e81489212c974d4Dan Gohman bool ForceUnitLatencies() const { return true; } 158e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng}; 159e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} // end anonymous namespace 160e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 161e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 162e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// Schedule - Schedule the DAG using list scheduling. 163e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengvoid ScheduleDAGRRList::Schedule() { 164832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "********** List Scheduling **********\n"; 165a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 166086ec9976ff6cee083de618429c78473491d5713Dan Gohman NumLiveRegs = 0; 1676f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman LiveRegDefs.resize(TRI->getNumRegs(), NULL); 1686f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman LiveRegCycles.resize(TRI->getNumRegs(), 0); 169a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 170c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Build the scheduling graph. 171c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman BuildSchedGraph(); 172e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 173e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 1743cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman SUnits[su].dumpAll(this)); 17521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Topo.InitDAGTopologicalSorting(); 176e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 17794d7a5f8156e62532870fbaf197377b34e52ff2aDan Gohman AvailableQueue->initNodes(SUnits); 1788d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman 179e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate. 180e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (isBottomUp) 181e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng ListScheduleBottomUp(); 182e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng else 183e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng ListScheduleTopDown(); 184e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 185e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue->releaseState(); 18613d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng} 187e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 188e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 189e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// Bottom-Up Scheduling 190e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 191e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 192e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 1938d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 19454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohmanvoid ScheduleDAGRRList::ReleasePred(SUnit *SU, SDep *PredEdge) { 19554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *PredSU = PredEdge->getSUnit(); 19674d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng --PredSU->NumSuccsLeft; 197e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 198e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#ifndef NDEBUG 19974d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng if (PredSU->NumSuccsLeft < 0) { 2002d093f356007979e2e071725a98894a36c3625e0Dan Gohman cerr << "*** Scheduling failed! ***\n"; 2013cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman PredSU->dump(this); 202832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << " has been released too many times!\n"; 203e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng assert(0); 204e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 205e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#endif 206e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 20774d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng if (PredSU->NumSuccsLeft == 0) { 20880792f3ddec43aff7f0758c9096f8cb53dcc1e40Dan Gohman PredSU->isAvailable = true; 20980792f3ddec43aff7f0758c9096f8cb53dcc1e40Dan Gohman AvailableQueue->push(PredSU); 210e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 211e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 212e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 213e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 214e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// count of its predecessors. If a predecessor pending count is zero, add it to 215e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// the Available queue. 2166b8e5a93183ab08811b7b71887d8c7d774666210Evan Chengvoid ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 217832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "*** Scheduling [" << CurCycle << "]: "; 2183cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman DEBUG(SU->dump(this)); 219e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 2203f23744df4809eba94284e601e81489212c974d4Dan Gohman assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); 2213f23744df4809eba94284e601e81489212c974d4Dan Gohman SU->setHeightToAtLeast(CurCycle); 2221256f5fe769ab2cced36abf2cbf9e1f63f22282dDan Gohman Sequence.push_back(SU); 223e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 224e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Bottom up: release predecessors 225228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 226a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 22754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman ReleasePred(SU, &*I); 22854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep()) { 229a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // This is a physical register dependency and it's impossible or 230a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // expensive to copy the register. Make sure nothing that can 231a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // clobber the register is scheduled between the predecessor and 232a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // this node. 23354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (!LiveRegDefs[I->getReg()]) { 234086ec9976ff6cee083de618429c78473491d5713Dan Gohman ++NumLiveRegs; 23554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegDefs[I->getReg()] = I->getSUnit(); 23654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegCycles[I->getReg()] = CurCycle; 237a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 238a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 239a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 240a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 241a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // Release all the implicit physical register defs that are live. 242a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 243a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 24454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep()) { 2453f23744df4809eba94284e601e81489212c974d4Dan Gohman if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) { 246086ec9976ff6cee083de618429c78473491d5713Dan Gohman assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); 24754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert(LiveRegDefs[I->getReg()] == SU && 248a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng "Physical register dependency violated?"); 249086ec9976ff6cee083de618429c78473491d5713Dan Gohman --NumLiveRegs; 25054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegDefs[I->getReg()] = NULL; 25154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegCycles[I->getReg()] = 0; 252a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 253a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 254a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 255a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 256e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SU->isScheduled = true; 2571256f5fe769ab2cced36abf2cbf9e1f63f22282dDan Gohman AvailableQueue->ScheduledNode(SU); 258e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 259e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 260a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// CapturePred - This does the opposite of ReleasePred. Since SU is being 261a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// unscheduled, incrcease the succ left count of its predecessors. Remove 262a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// them from AvailableQueue if necessary. 26354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohmanvoid ScheduleDAGRRList::CapturePred(SDep *PredEdge) { 26454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *PredSU = PredEdge->getSUnit(); 265a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (PredSU->isAvailable) { 266a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng PredSU->isAvailable = false; 267a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (!PredSU->isPending) 268a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->remove(PredSU); 269a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 270a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 27174d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng ++PredSU->NumSuccsLeft; 272a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng} 273a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 274a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and 275a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// its predecessor states to reflect the change. 276a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Chengvoid ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) { 2773f23744df4809eba94284e601e81489212c974d4Dan Gohman DOUT << "*** Unscheduling [" << SU->getHeight() << "]: "; 2783cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman DEBUG(SU->dump(this)); 279a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 280a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->UnscheduledNode(SU); 281a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 282a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 283a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 28454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman CapturePred(&*I); 2853f23744df4809eba94284e601e81489212c974d4Dan Gohman if (I->isAssignedRegDep() && SU->getHeight() == LiveRegCycles[I->getReg()]) { 286086ec9976ff6cee083de618429c78473491d5713Dan Gohman assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); 28754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert(LiveRegDefs[I->getReg()] == I->getSUnit() && 288a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng "Physical register dependency violated?"); 289086ec9976ff6cee083de618429c78473491d5713Dan Gohman --NumLiveRegs; 29054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegDefs[I->getReg()] = NULL; 29154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegCycles[I->getReg()] = 0; 292a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 293a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 294a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 295a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 296a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 29754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep()) { 29854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (!LiveRegDefs[I->getReg()]) { 29954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegDefs[I->getReg()] = SU; 300086ec9976ff6cee083de618429c78473491d5713Dan Gohman ++NumLiveRegs; 301a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 3023f23744df4809eba94284e601e81489212c974d4Dan Gohman if (I->getSUnit()->getHeight() < LiveRegCycles[I->getReg()]) 3033f23744df4809eba94284e601e81489212c974d4Dan Gohman LiveRegCycles[I->getReg()] = I->getSUnit()->getHeight(); 304a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 305a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 306a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 3073f23744df4809eba94284e601e81489212c974d4Dan Gohman SU->setHeightDirty(); 308a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SU->isScheduled = false; 309a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SU->isAvailable = true; 310a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->push(SU); 311a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng} 312a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 31342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng/// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in 314a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// BTCycle in order to schedule a specific node. Returns the last unscheduled 315a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// SUnit. Also returns if a successor is unscheduled in the process. 31642d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Chengvoid ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle, 31742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng unsigned &CurCycle) { 318a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SUnit *OldSU = NULL; 31942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng while (CurCycle > BtCycle) { 320a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng OldSU = Sequence.back(); 321a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng Sequence.pop_back(); 322a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (SU->isSucc(OldSU)) 32342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng // Don't try to remove SU from AvailableQueue. 32442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng SU->isAvailable = false; 325a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng UnscheduleNodeBottomUp(OldSU); 326a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng --CurCycle; 327a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 328a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 329a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 330a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (SU->isSucc(OldSU)) { 331a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng assert(false && "Something is wrong!"); 332a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng abort(); 333a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 334a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 335a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng ++NumBacktracks; 336a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng} 337a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 338f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled 339f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng/// successors to the newly created node. 340f10c973797cf79da802f9b0118543cbd50954c9cEvan ChengSUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) { 341d23e0f81bc76902052e9198cad3a0d87a412a632Dan Gohman if (SU->getNode()->getFlaggedNode()) 342f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng return NULL; 343f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 344550f5afb68ce8f034991863cac65bef22a6554daDan Gohman SDNode *N = SU->getNode(); 34542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng if (!N) 346f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng return NULL; 34742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 348f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SUnit *NewSU; 349f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng bool TryUnfold = false; 350d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 35183ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands MVT VT = N->getValueType(i); 352d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng if (VT == MVT::Flag) 353d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng return NULL; 354d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng else if (VT == MVT::Other) 355d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng TryUnfold = true; 356d5cb5a462b6fd91bf54116c3eefc3b046489c414Evan Cheng } 357a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 358475871a144eb604ddaf37503397ba0941442e5fbDan Gohman const SDValue &Op = N->getOperand(i); 359ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif MVT VT = Op.getNode()->getValueType(Op.getResNo()); 360f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (VT == MVT::Flag) 361f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng return NULL; 362a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 363a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 364f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (TryUnfold) { 3654c8c83022b501759d8559e224c84ae2a9921ba41Dan Gohman SmallVector<SDNode*, 2> NewNodes; 366a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) 367f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng return NULL; 368f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 369f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng DOUT << "Unfolding SU # " << SU->NodeNum << "\n"; 370f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng assert(NewNodes.size() == 2 && "Expected a load folding node!"); 371f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 372f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng N = NewNodes[1]; 373f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SDNode *LoadNode = NewNodes[0]; 374f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng unsigned NumVals = N->getNumValues(); 375550f5afb68ce8f034991863cac65bef22a6554daDan Gohman unsigned OldNumVals = SU->getNode()->getNumValues(); 376f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (unsigned i = 0; i != NumVals; ++i) 377550f5afb68ce8f034991863cac65bef22a6554daDan Gohman DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i)); 378550f5afb68ce8f034991863cac65bef22a6554daDan Gohman DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1), 379a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman SDValue(LoadNode, 1)); 380f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 381b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman // LoadNode may already exist. This can happen when there is another 382b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman // load from the same location and producing the same type of value 383b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman // but it has different alignment or volatileness. 384b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman bool isNewLoad = true; 385b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman SUnit *LoadSU; 386b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman if (LoadNode->getNodeId() != -1) { 387b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman LoadSU = &SUnits[LoadNode->getNodeId()]; 388b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman isNewLoad = false; 389b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman } else { 390b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman LoadSU = CreateNewSUnit(LoadNode); 391b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman LoadNode->setNodeId(LoadSU->NodeNum); 392b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman ComputeLatency(LoadSU); 393b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman } 394b13af2f2ec2fd8dc215136cf8783d70225b59f66Dan Gohman 395e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein SUnit *NewSU = CreateNewSUnit(N); 39694d7a5f8156e62532870fbaf197377b34e52ff2aDan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 39794d7a5f8156e62532870fbaf197377b34e52ff2aDan Gohman N->setNodeId(NewSU->NodeNum); 3984c8c83022b501759d8559e224c84ae2a9921ba41Dan Gohman 399e8be6c63915e0389f1eef6b53c64300d13b2ce99Dan Gohman const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); 40094ebde1d45dcd7e209663c49a1cf1a4589191df1Dan Gohman for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 4013db805ea80eeec9084a1b86273d93804d233d938Chris Lattner if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 402f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng NewSU->isTwoAddress = true; 403f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng break; 404f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 405f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 4063db805ea80eeec9084a1b86273d93804d233d938Chris Lattner if (TID.isCommutable()) 407f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng NewSU->isCommutable = true; 408f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng ComputeLatency(NewSU); 409f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 41054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep ChainPred; 411f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SmallVector<SDep, 4> ChainSuccs; 412f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SmallVector<SDep, 4> LoadPreds; 413f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SmallVector<SDep, 4> NodePreds; 414f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SmallVector<SDep, 4> NodeSuccs; 415f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 416f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng I != E; ++I) { 41754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isCtrl()) 41854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman ChainPred = *I; 41954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman else if (I->getSUnit()->getNode() && 42054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman I->getSUnit()->getNode()->isOperandOf(LoadNode)) 42154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LoadPreds.push_back(*I); 422f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng else 42354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman NodePreds.push_back(*I); 424f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 425f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 426f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng I != E; ++I) { 42754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isCtrl()) 42854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman ChainSuccs.push_back(*I); 429f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng else 43054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman NodeSuccs.push_back(*I); 431f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 43242d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 43354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (ChainPred.getSUnit()) { 43454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(SU, ChainPred); 43580792f3ddec43aff7f0758c9096f8cb53dcc1e40Dan Gohman if (isNewLoad) 43654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(LoadSU, ChainPred); 437e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein } 438f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { 43954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman const SDep &Pred = LoadPreds[i]; 44054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(SU, Pred); 441e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein if (isNewLoad) { 44254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(LoadSU, Pred); 443e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein } 444f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 445f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { 44654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman const SDep &Pred = NodePreds[i]; 44754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(SU, Pred); 44854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(NewSU, Pred); 449f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 450f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { 45154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep D = NodeSuccs[i]; 45254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SuccDep = D.getSUnit(); 45354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(SU); 45454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(SuccDep, D); 45554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(NewSU); 45654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(SuccDep, D); 457f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 458f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { 45954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep D = ChainSuccs[i]; 46054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SuccDep = D.getSUnit(); 46154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(SU); 46254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(SuccDep, D); 463e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein if (isNewLoad) { 46454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(LoadSU); 46554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(SuccDep, D); 466e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein } 467f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 468e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein if (isNewLoad) { 46954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(NewSU, SDep(LoadSU, SDep::Order, LoadSU->Latency)); 470e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein } 471f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 472beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng if (isNewLoad) 473beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng AvailableQueue->addNode(LoadSU); 474f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng AvailableQueue->addNode(NewSU); 475f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 476f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng ++NumUnfolds; 477f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 478f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (NewSU->NumSuccsLeft == 0) { 479f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng NewSU->isAvailable = true; 480f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng return NewSU; 481beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng } 482beec823d4bba22b1c0c6658d2b3e71cd64a70e2eEvan Cheng SU = NewSU; 483f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng } 484f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng 485f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng DOUT << "Duplicating SU # " << SU->NodeNum << "\n"; 486e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein NewSU = CreateClone(SU); 487a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 488a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // New SUnit has the exact same predecessors. 489a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 490a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) 4913f23744df4809eba94284e601e81489212c974d4Dan Gohman if (!I->isArtificial()) 49254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(NewSU, *I); 493a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 494a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // Only copy scheduled successors. Cut them from old node's successor 495a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // list and move them over. 49654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 497a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 498a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 49954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 500a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng continue; 50154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SuccSU = I->getSUnit(); 50254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (SuccSU->isScheduled) { 50354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep D = *I; 50454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(NewSU); 50554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(SuccSU, D); 50654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(SU); 50754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman DelDeps.push_back(std::make_pair(SuccSU, D)); 508a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 509a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 5103f23744df4809eba94284e601e81489212c974d4Dan Gohman for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) 51154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(DelDeps[i].first, DelDeps[i].second); 512a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 513a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->updateNode(SU); 514a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->addNode(NewSU); 515a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 516a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng ++NumDups; 517a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return NewSU; 518a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng} 519a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 520a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng/// InsertCCCopiesAndMoveSuccs - Insert expensive cross register class copies 521a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng/// and move all scheduled successors of the given SUnit to the last copy. 522a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Chengvoid ScheduleDAGRRList::InsertCCCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, 523a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng const TargetRegisterClass *DestRC, 524a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng const TargetRegisterClass *SrcRC, 525a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<SUnit*, 2> &Copies) { 526e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein SUnit *CopyFromSU = CreateNewSUnit(NULL); 52742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyFromSU->CopySrcRC = SrcRC; 52842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyFromSU->CopyDstRC = DestRC; 52942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 530e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein SUnit *CopyToSU = CreateNewSUnit(NULL); 53142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyToSU->CopySrcRC = DestRC; 53242d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng CopyToSU->CopyDstRC = SrcRC; 53342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 53442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng // Only copy scheduled successors. Cut them from old node's successor 53542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng // list and move them over. 53654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 53742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 53842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng I != E; ++I) { 53954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 54042d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng continue; 54154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SuccSU = I->getSUnit(); 54254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (SuccSU->isScheduled) { 54354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep D = *I; 54454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(CopyToSU); 54554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(SuccSU, D); 54654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman DelDeps.push_back(std::make_pair(SuccSU, *I)); 54742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng } 54842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng } 54942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 55054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(DelDeps[i].first, DelDeps[i].second); 55142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng } 55242d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 55354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg)); 55454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0)); 55542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 55642d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng AvailableQueue->updateNode(SU); 55742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng AvailableQueue->addNode(CopyFromSU); 55842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng AvailableQueue->addNode(CopyToSU); 559a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng Copies.push_back(CopyFromSU); 560a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng Copies.push_back(CopyToSU); 56142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 562a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng ++NumCCCopies; 56342d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng} 56442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 56542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng/// getPhysicalRegisterVT - Returns the ValueType of the physical register 56642d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng/// definition of the specified node. 56742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng/// FIXME: Move to SelectionDAG? 56883ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sandsstatic MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, 56983ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands const TargetInstrInfo *TII) { 570e8be6c63915e0389f1eef6b53c64300d13b2ce99Dan Gohman const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); 57142d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!"); 572349c4952009525b27383e2120a6b3c998f39bd09Chris Lattner unsigned NumRes = TID.getNumDefs(); 573349c4952009525b27383e2120a6b3c998f39bd09Chris Lattner for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) { 57442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng if (Reg == *ImpDef) 57542d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng break; 57642d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng ++NumRes; 57742d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng } 57842d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng return N->getValueType(NumRes); 57942d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng} 58042d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng 581a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay 582a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// scheduling of the given node to satisfy live physical register dependencies. 583a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// If the specific node is the last one that's available to schedule, do 584a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng/// whatever is necessary (i.e. backtracking or cloning) to make it possible. 585a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Chengbool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, 586a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<unsigned, 4> &LRegs){ 587086ec9976ff6cee083de618429c78473491d5713Dan Gohman if (NumLiveRegs == 0) 588a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return false; 589a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 590cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng SmallSet<unsigned, 4> RegAdded; 591a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng // If this node would clobber any "live" register, then it's not ready. 592a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 593a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng I != E; ++I) { 59454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep()) { 59554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned Reg = I->getReg(); 59654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->getSUnit()) { 597cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (RegAdded.insert(Reg)) 598cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng LRegs.push_back(Reg); 599cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng } 6006f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned *Alias = TRI->getAliasSet(Reg); 601a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng *Alias; ++Alias) 60254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->getSUnit()) { 603cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (RegAdded.insert(*Alias)) 604cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng LRegs.push_back(*Alias); 605cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng } 606a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 607a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 608a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 609d23e0f81bc76902052e9198cad3a0d87a412a632Dan Gohman for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) { 610d23e0f81bc76902052e9198cad3a0d87a412a632Dan Gohman if (!Node->isMachineOpcode()) 611a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng continue; 612e8be6c63915e0389f1eef6b53c64300d13b2ce99Dan Gohman const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode()); 613a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (!TID.ImplicitDefs) 614a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng continue; 615a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) { 616086ec9976ff6cee083de618429c78473491d5713Dan Gohman if (LiveRegDefs[*Reg] && LiveRegDefs[*Reg] != SU) { 617cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (RegAdded.insert(*Reg)) 618cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng LRegs.push_back(*Reg); 619cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng } 6206f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned *Alias = TRI->getAliasSet(*Reg); 621a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng *Alias; ++Alias) 622086ec9976ff6cee083de618429c78473491d5713Dan Gohman if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) { 623cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng if (RegAdded.insert(*Alias)) 624cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng LRegs.push_back(*Alias); 625cd1c00cc6521c265784ffc7a1b5baf4ef64d80bcEvan Cheng } 626a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 627a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 628a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return !LRegs.empty(); 629e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 630e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 631a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 632e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 633e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// schedulers. 634e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengvoid ScheduleDAGRRList::ListScheduleBottomUp() { 635e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng unsigned CurCycle = 0; 636e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Add root to Available queue. 63780792f3ddec43aff7f0758c9096f8cb53dcc1e40Dan Gohman if (!SUnits.empty()) { 638a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()]; 63980792f3ddec43aff7f0758c9096f8cb53dcc1e40Dan Gohman assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!"); 64080792f3ddec43aff7f0758c9096f8cb53dcc1e40Dan Gohman RootSU->isAvailable = true; 64180792f3ddec43aff7f0758c9096f8cb53dcc1e40Dan Gohman AvailableQueue->push(RootSU); 64280792f3ddec43aff7f0758c9096f8cb53dcc1e40Dan Gohman } 643e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 644e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // While Available queue is not empty, grab the node with the highest 6458d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman // priority. If it is not ready put it back. Schedule the node. 646a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SmallVector<SUnit*, 4> NotReady; 6478cb8245cf117fc4a4f0a6549d9a773a12895550cDan Gohman DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap; 6484c8c83022b501759d8559e224c84ae2a9921ba41Dan Gohman Sequence.reserve(SUnits.size()); 649e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng while (!AvailableQueue->empty()) { 650a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng bool Delayed = false; 6518cb8245cf117fc4a4f0a6549d9a773a12895550cDan Gohman LRegsMap.clear(); 652a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SUnit *CurSU = AvailableQueue->pop(); 653a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng while (CurSU) { 654f209c2cc301ed762e4314536137832ee26e65be0Dan Gohman SmallVector<unsigned, 4> LRegs; 655f209c2cc301ed762e4314536137832ee26e65be0Dan Gohman if (!DelayForLiveRegsBottomUp(CurSU, LRegs)) 656f209c2cc301ed762e4314536137832ee26e65be0Dan Gohman break; 657f209c2cc301ed762e4314536137832ee26e65be0Dan Gohman Delayed = true; 658f209c2cc301ed762e4314536137832ee26e65be0Dan Gohman LRegsMap.insert(std::make_pair(CurSU, LRegs)); 659a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 660a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng CurSU->isPending = true; // This SU is not in AvailableQueue right now. 661a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng NotReady.push_back(CurSU); 662a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng CurSU = AvailableQueue->pop(); 663e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 664a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 665a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // All candidates are delayed due to live physical reg dependencies. 666a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // Try backtracking, code duplication, or inserting cross class copies 667a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // to resolve it. 668a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (Delayed && !CurSU) { 669a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 670a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SUnit *TrySU = NotReady[i]; 671a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 672a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 673a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // Try unscheduling up to the point where it's safe to schedule 674a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // this node. 675a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng unsigned LiveCycle = CurCycle; 676a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) { 677a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng unsigned Reg = LRegs[j]; 678a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng unsigned LCycle = LiveRegCycles[Reg]; 679a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng LiveCycle = std::min(LiveCycle, LCycle); 680a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 681a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SUnit *OldSU = Sequence[LiveCycle]; 682a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!WillCreateCycle(TrySU, OldSU)) { 683a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng BacktrackBottomUp(TrySU, LiveCycle, CurCycle); 684a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // Force the current node to be scheduled before the node that 685a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // requires the physical reg dep. 686a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (OldSU->isAvailable) { 687a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng OldSU->isAvailable = false; 688a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng AvailableQueue->remove(OldSU); 689a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 69054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1, 69154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /*Reg=*/0, /*isNormalMemory=*/false, 69254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /*isMustAlias=*/false, /*isArtificial=*/true)); 693a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // If one or more successors has been unscheduled, then the current 694a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // node is no longer avaialable. Schedule a successor that's now 695a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // available instead. 696a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!TrySU->isAvailable) 697a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng CurSU = AvailableQueue->pop(); 698a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng else { 699a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng CurSU = TrySU; 700a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng TrySU->isPending = false; 701a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng NotReady.erase(NotReady.begin()+i); 702a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 703a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng break; 704a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 705a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 706a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 707a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!CurSU) { 708cffbd2562a5e3ba435dd2b622710ec272c634da5Dan Gohman // Can't backtrack. Try duplicating the nodes that produces these 709a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // "expensive to copy" values to break the dependency. In case even 710a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // that doesn't work, insert cross class copies. 711a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SUnit *TrySU = NotReady[0]; 712a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 713a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng assert(LRegs.size() == 1 && "Can't handle this yet!"); 714a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng unsigned Reg = LRegs[0]; 715a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SUnit *LRDef = LiveRegDefs[Reg]; 716f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng SUnit *NewDef = CopyAndMoveSuccessors(LRDef); 717f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng if (!NewDef) { 718a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // Issue expensive cross register class copies. 719550f5afb68ce8f034991863cac65bef22a6554daDan Gohman MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII); 720a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng const TargetRegisterClass *RC = 721676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng TRI->getPhysicalRegisterRegClass(Reg, VT); 7226f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); 723a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!DestRC) { 724a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng assert(false && "Don't know how to copy this physical register!"); 725a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng abort(); 726a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 727a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng SmallVector<SUnit*, 2> Copies; 728a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng InsertCCCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); 729a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng DOUT << "Adding an edge from SU # " << TrySU->NodeNum 730a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng << " to SU #" << Copies.front()->NodeNum << "\n"; 73154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1, 732ce0d4b7a77da716f234d42edd0472e97b3ba5f57Dan Gohman /*Reg=*/0, /*isNormalMemory=*/false, 733ce0d4b7a77da716f234d42edd0472e97b3ba5f57Dan Gohman /*isMustAlias=*/false, 73454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /*isArtificial=*/true)); 735a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng NewDef = Copies.back(); 736a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 737a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 738a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng DOUT << "Adding an edge from SU # " << NewDef->NodeNum 739a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng << " to SU #" << TrySU->NodeNum << "\n"; 740a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng LiveRegDefs[Reg] = NewDef; 74154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1, 742ce0d4b7a77da716f234d42edd0472e97b3ba5f57Dan Gohman /*Reg=*/0, /*isNormalMemory=*/false, 743ce0d4b7a77da716f234d42edd0472e97b3ba5f57Dan Gohman /*isMustAlias=*/false, 74454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /*isArtificial=*/true)); 745a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng TrySU->isAvailable = false; 746a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng CurSU = NewDef; 747a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 748a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 749a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng if (!CurSU) { 750a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng assert(false && "Unable to resolve live physical register dependencies!"); 751a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng abort(); 752a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 753a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng } 754a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng 755e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Add the nodes that aren't ready back onto the available list. 756a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 757a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng NotReady[i]->isPending = false; 758a2ee2756f7f80d24312d6ac41b4f2ae548441cacEvan Cheng // May no longer be available due to backtracking. 759a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng if (NotReady[i]->isAvailable) 760a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng AvailableQueue->push(NotReady[i]); 761a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 762e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng NotReady.clear(); 763e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 76447d1a214a7013d12140a0c4972d7ba761150dfd4Dan Gohman if (CurSU) 765a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng ScheduleNodeBottomUp(CurSU, CurCycle); 766a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng ++CurCycle; 767e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 768e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 769e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Reverse the order if it is bottom up. 770e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng std::reverse(Sequence.begin(), Sequence.end()); 771e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 772e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#ifndef NDEBUG 773a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman VerifySchedule(isBottomUp); 774e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#endif 775e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 776e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 777e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 778e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// Top-Down Scheduling 779e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 780e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 781e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 7828d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 78354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohmanvoid ScheduleDAGRRList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { 78454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SuccSU = SuccEdge->getSUnit(); 78574d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng --SuccSU->NumPredsLeft; 786e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 787e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#ifndef NDEBUG 78874d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng if (SuccSU->NumPredsLeft < 0) { 7892d093f356007979e2e071725a98894a36c3625e0Dan Gohman cerr << "*** Scheduling failed! ***\n"; 7903cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman SuccSU->dump(this); 791832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << " has been released too many times!\n"; 792e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng assert(0); 793e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 794e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#endif 795e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 79674d2fd8dd847e0ebccef30e2c5907ff09495d518Evan Cheng if (SuccSU->NumPredsLeft == 0) { 797e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SuccSU->isAvailable = true; 798e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue->push(SuccSU); 799e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 800e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 801e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 802e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 803e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// count of its successors. If a successor pending count is zero, add it to 804e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// the Available queue. 8056b8e5a93183ab08811b7b71887d8c7d774666210Evan Chengvoid ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 806832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "*** Scheduling [" << CurCycle << "]: "; 8073cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman DEBUG(SU->dump(this)); 808e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 8093f23744df4809eba94284e601e81489212c974d4Dan Gohman assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); 8103f23744df4809eba94284e601e81489212c974d4Dan Gohman SU->setDepthToAtLeast(CurCycle); 8118123419f2be881ca77a897918f28514aa4e91765Dan Gohman Sequence.push_back(SU); 812e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 813e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Top down: release successors 814228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 815228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner I != E; ++I) 81654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman ReleaseSucc(SU, &*I); 8178123419f2be881ca77a897918f28514aa4e91765Dan Gohman 818e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SU->isScheduled = true; 8198123419f2be881ca77a897918f28514aa4e91765Dan Gohman AvailableQueue->ScheduledNode(SU); 820e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 821e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 8228d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman/// ListScheduleTopDown - The main loop of list scheduling for top-down 8238d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman/// schedulers. 824e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengvoid ScheduleDAGRRList::ListScheduleTopDown() { 825e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng unsigned CurCycle = 0; 826e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 827e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // All leaves to Available queue. 828e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 829e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // It is available if it has no predecessors. 83080792f3ddec43aff7f0758c9096f8cb53dcc1e40Dan Gohman if (SUnits[i].Preds.empty()) { 831e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng AvailableQueue->push(&SUnits[i]); 832e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnits[i].isAvailable = true; 833e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 834e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 835e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 836e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // While Available queue is not empty, grab the node with the highest 8378d1bfad00b1ebff5b140b6e1bd7e26bad697d6e1Dan Gohman // priority. If it is not ready put it back. Schedule the node. 8384c8c83022b501759d8559e224c84ae2a9921ba41Dan Gohman Sequence.reserve(SUnits.size()); 839e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng while (!AvailableQueue->empty()) { 840a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SUnit *CurSU = AvailableQueue->pop(); 841e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 84247d1a214a7013d12140a0c4972d7ba761150dfd4Dan Gohman if (CurSU) 843a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng ScheduleNodeTopDown(CurSU, CurCycle); 84480792f3ddec43aff7f0758c9096f8cb53dcc1e40Dan Gohman ++CurCycle; 845e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 846e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 847e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#ifndef NDEBUG 848a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman VerifySchedule(isBottomUp); 849e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng#endif 850e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 851e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 852e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 853e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 854e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// RegReductionPriorityQueue Implementation 855e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 856e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// 857e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers 858e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// to reduce register pressure. 859e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// 860e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengnamespace { 861e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng template<class SF> 862e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng class RegReductionPriorityQueue; 863e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 864e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// Sorting functions for the Available queue. 865e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 866e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ; 867e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {} 868e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 869e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 870e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool operator()(const SUnit* left, const SUnit* right) const; 871e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 872e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 873e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 874e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng RegReductionPriorityQueue<td_ls_rr_sort> *SPQ; 875e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {} 876e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 877e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 878e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool operator()(const SUnit* left, const SUnit* right) const; 879e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 880e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} // end anonymous namespace 881e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 882c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Chengstatic inline bool isCopyFromLiveIn(const SUnit *SU) { 883550f5afb68ce8f034991863cac65bef22a6554daDan Gohman SDNode *N = SU->getNode(); 88442d60274eaa70f8cdbed76d04d25d7a8fc1237cbEvan Cheng return N && N->getOpcode() == ISD::CopyFromReg && 885c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag; 886c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng} 887c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng 888117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman/// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number. 889117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman/// Smaller number is the higher priority. 890c6be777208f4539af400ac694d9d1dc8b992bc80Evan Chengstatic unsigned 891117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan GohmanCalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) { 892c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum]; 893c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng if (SethiUllmanNumber != 0) 894c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng return SethiUllmanNumber; 895c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng 896c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng unsigned Extra = 0; 897c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 898c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng I != E; ++I) { 89954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isCtrl()) continue; // ignore chain preds 90054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *PredSU = I->getSUnit(); 901117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers); 902c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng if (PredSethiUllman > SethiUllmanNumber) { 903c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng SethiUllmanNumber = PredSethiUllman; 904c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng Extra = 0; 90554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl()) 906c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng ++Extra; 907c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng } 908c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng 909c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng SethiUllmanNumber += Extra; 910c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng 911c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng if (SethiUllmanNumber == 0) 912c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng SethiUllmanNumber = 1; 913c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng 914c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng return SethiUllmanNumber; 915c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng} 916c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng 917e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengnamespace { 918e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng template<class SF> 9199525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner class VISIBILITY_HIDDEN RegReductionPriorityQueue 9209525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner : public SchedulingPriorityQueue { 9213627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman PriorityQueue<SUnit*, std::vector<SUnit*>, SF> Queue; 922a0201d52049be8dcefffe4304a49690a831bcb34Roman Levenstein unsigned currentQueueId; 923e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 9246be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman protected: 9256be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman // SUnits - The SUnits for the current graph. 9266be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman std::vector<SUnit> *SUnits; 9276be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman 9286be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman const TargetInstrInfo *TII; 9296be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman const TargetRegisterInfo *TRI; 9306be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman ScheduleDAGRRList *scheduleDAG; 9316be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman 932117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman // SethiUllmanNumbers - The SethiUllman number for each node. 933117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman std::vector<unsigned> SethiUllmanNumbers; 934117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman 935e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng public: 9366be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman RegReductionPriorityQueue(const TargetInstrInfo *tii, 9376be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman const TargetRegisterInfo *tri) : 9386be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman Queue(SF(this)), currentQueueId(0), 9396be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman TII(tii), TRI(tri), scheduleDAG(NULL) {} 940e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 9416be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman void initNodes(std::vector<SUnit> &sunits) { 9426be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman SUnits = &sunits; 943e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Add pseudo dependency edges for two-address nodes. 944c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng AddPseudoTwoAddrDeps(); 945e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng // Calculate node priorities. 946c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng CalculateSethiUllmanNumbers(); 947e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 948e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 949a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng void addNode(const SUnit *SU) { 950c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng unsigned SUSize = SethiUllmanNumbers.size(); 951c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng if (SUnits->size() > SUSize) 952c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng SethiUllmanNumbers.resize(SUSize*2, 0); 953117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers); 954a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 955a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 956a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng void updateNode(const SUnit *SU) { 957a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng SethiUllmanNumbers[SU->NodeNum] = 0; 958117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers); 959a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 960a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 961e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng void releaseState() { 962117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman SUnits = 0; 963e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SethiUllmanNumbers.clear(); 964e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 965e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 966c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned getNodePriority(const SUnit *SU) const { 967c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng assert(SU->NodeNum < SethiUllmanNumbers.size()); 968550f5afb68ce8f034991863cac65bef22a6554daDan Gohman unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0; 969c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng if (Opc == ISD::CopyFromReg && !isCopyFromLiveIn(SU)) 970c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // CopyFromReg should be close to its def because it restricts 971c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // allocation choices. But if it is a livein then perhaps we want it 972c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // closer to its uses so it can be coalesced. 973c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return 0xffff; 974c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng else if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 975c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // CopyToReg should be close to its uses to facilitate coalescing and 976c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // avoid spilling. 977c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return 0; 97832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng else if (Opc == TargetInstrInfo::EXTRACT_SUBREG || 97932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng Opc == TargetInstrInfo::INSERT_SUBREG) 98032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // EXTRACT_SUBREG / INSERT_SUBREG should be close to its use to 98132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // facilitate coalescing. 98232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng return 0; 983c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng else if (SU->NumSuccs == 0) 984c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // If SU does not have a use, i.e. it doesn't produce a value that would 985c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // be consumed (e.g. store), then it terminates a chain of computation. 986c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // Give it a large SethiUllman number so it will be scheduled right 987c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // before its predecessors that it doesn't lengthen their live ranges. 988c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return 0xffff; 989c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng else if (SU->NumPreds == 0) 990c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // If SU does not have a def, schedule it close to its uses because it 991c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng // does not lengthen any live ranges. 992c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return 0; 993c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng else 994c62d4bb6952a1459f10aa93579e1b881d42a33eaEvan Cheng return SethiUllmanNumbers[SU->NodeNum]; 995e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 996117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman 997117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman unsigned size() const { return Queue.size(); } 998e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 999117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman bool empty() const { return Queue.empty(); } 1000117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman 1001117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman void push(SUnit *U) { 1002117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman assert(!U->NodeQueueId && "Node in the queue already"); 1003117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman U->NodeQueueId = ++currentQueueId; 1004117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman Queue.push(U); 1005e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1006e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1007117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman void push_all(const std::vector<SUnit *> &Nodes) { 1008117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman for (unsigned i = 0, e = Nodes.size(); i != e; ++i) 1009117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman push(Nodes[i]); 1010a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 1011117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman 1012117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman SUnit *pop() { 1013117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman if (empty()) return NULL; 1014117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman SUnit *V = Queue.top(); 1015117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman Queue.pop(); 1016117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman V->NodeQueueId = 0; 1017117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman return V; 1018a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 1019a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 1020117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman void remove(SUnit *SU) { 1021117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman assert(!Queue.empty() && "Queue is empty!"); 1022117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman assert(SU->NodeQueueId != 0 && "Not in queue!"); 1023117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman Queue.erase_one(SU); 1024117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman SU->NodeQueueId = 0; 1025e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1026e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1027117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman void setScheduleDAG(ScheduleDAGRRList *scheduleDag) { 1028117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman scheduleDAG = scheduleDag; 1029e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1030e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1031117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman protected: 1032117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman bool canClobber(const SUnit *SU, const SUnit *Op); 1033117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman void AddPseudoTwoAddrDeps(); 1034c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng void CalculateSethiUllmanNumbers(); 1035e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 1036117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman 1037117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman typedef RegReductionPriorityQueue<bu_ls_rr_sort> 1038117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman BURegReductionPriorityQueue; 1039117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman 1040117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman typedef RegReductionPriorityQueue<td_ls_rr_sort> 1041117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman TDRegReductionPriorityQueue; 1042e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1043e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1044c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng/// closestSucc - Returns the scheduled cycle of the successor which is 1045c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng/// closet to the current cycle. 104661230d18d21a5dca1378e994f43934e4b314e595Evan Chengstatic unsigned closestSucc(const SUnit *SU) { 10473f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned MaxHeight = 0; 104861230d18d21a5dca1378e994f43934e4b314e595Evan Cheng for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1049c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng I != E; ++I) { 10503f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned Height = I->getSUnit()->getHeight(); 1051c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng // If there are bunch of CopyToRegs stacked up, they should be considered 1052c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng // to be at the same position. 105354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->getSUnit()->getNode() && 105454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg) 10553f23744df4809eba94284e601e81489212c974d4Dan Gohman Height = closestSucc(I->getSUnit())+1; 10563f23744df4809eba94284e601e81489212c974d4Dan Gohman if (Height > MaxHeight) 10573f23744df4809eba94284e601e81489212c974d4Dan Gohman MaxHeight = Height; 1058c6deb3d44707de57e82e16642ab845bc8b9e9e01Evan Cheng } 10593f23744df4809eba94284e601e81489212c974d4Dan Gohman return MaxHeight; 106061230d18d21a5dca1378e994f43934e4b314e595Evan Cheng} 106161230d18d21a5dca1378e994f43934e4b314e595Evan Cheng 1062d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng/// calcMaxScratches - Returns an cost estimate of the worse case requirement 1063d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng/// for scratch registers. Live-in operands and live-out results don't count 1064d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng/// since they are "fixed". 1065d6c0758944b31bb5316b36cad37f4610a77f784dEvan Chengstatic unsigned calcMaxScratches(const SUnit *SU) { 1066d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng unsigned Scratches = 0; 1067d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1068d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng I != E; ++I) { 106954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isCtrl()) continue; // ignore chain preds 107054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (!I->getSUnit()->getNode() || 107154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman I->getSUnit()->getNode()->getOpcode() != ISD::CopyFromReg) 1072d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng Scratches++; 1073d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng } 1074d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1075d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng I != E; ++I) { 107654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isCtrl()) continue; // ignore chain succs 107754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (!I->getSUnit()->getNode() || 107854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman I->getSUnit()->getNode()->getOpcode() != ISD::CopyToReg) 1079d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng Scratches += 10; 1080d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng } 1081d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng return Scratches; 1082d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng} 1083d6c0758944b31bb5316b36cad37f4610a77f784dEvan Cheng 1084e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// Bottom up 1085e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengbool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 1086c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned LPriority = SPQ->getNodePriority(left); 1087c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned RPriority = SPQ->getNodePriority(right); 108884d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng if (LPriority != RPriority) 108984d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng return LPriority > RPriority; 109084d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng 109184d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // Try schedule def + use closer when Sethi-Ullman numbers are the same. 109284d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // e.g. 109384d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // t1 = op t2, c1 109484d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // t3 = op t4, c2 109584d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // 109684d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // and the following instructions are both ready. 109784d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // t2 = op c3 109884d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // t4 = op c4 109984d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // 110084d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // Then schedule t2 = op first. 110184d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // i.e. 110284d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // t4 = op c4 110384d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // t2 = op c3 110484d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // t1 = op t2, c1 110584d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // t3 = op t4, c2 110684d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // 110784d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // This creates more short live intervals. 110884d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng unsigned LDist = closestSucc(left); 110984d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng unsigned RDist = closestSucc(right); 111084d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng if (LDist != RDist) 111184d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng return LDist < RDist; 111284d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng 111384d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // Intuitively, it's good to push down instructions whose results are 111484d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // liveout so their long live ranges won't conflict with other values 111584d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // which are needed inside the BB. Further prioritize liveout instructions 111684d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng // by the number of operands which are calculated within the BB. 111784d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng unsigned LScratch = calcMaxScratches(left); 111884d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng unsigned RScratch = calcMaxScratches(right); 111984d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng if (LScratch != RScratch) 112084d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng return LScratch > RScratch; 112184d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng 11223f23744df4809eba94284e601e81489212c974d4Dan Gohman if (left->getHeight() != right->getHeight()) 11233f23744df4809eba94284e601e81489212c974d4Dan Gohman return left->getHeight() > right->getHeight(); 112484d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng 11253f23744df4809eba94284e601e81489212c974d4Dan Gohman if (left->getDepth() != right->getDepth()) 11263f23744df4809eba94284e601e81489212c974d4Dan Gohman return left->getDepth() < right->getDepth(); 112784d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng 1128a0201d52049be8dcefffe4304a49690a831bcb34Roman Levenstein assert(left->NodeQueueId && right->NodeQueueId && 1129c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng "NodeQueueId cannot be zero"); 1130c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng return (left->NodeQueueId > right->NodeQueueId); 1131c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng} 1132c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng 11336be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohmantemplate<class SF> 1134c6be777208f4539af400ac694d9d1dc8b992bc80Evan Chengbool 11356be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan GohmanRegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) { 113695f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng if (SU->isTwoAddress) { 1137550f5afb68ce8f034991863cac65bef22a6554daDan Gohman unsigned Opc = SU->getNode()->getMachineOpcode(); 1138749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = TII->get(Opc); 11393db805ea80eeec9084a1b86273d93804d233d938Chris Lattner unsigned NumRes = TID.getNumDefs(); 11403b66555c53eb8921b2dd50335e0b278ddf80d220Dan Gohman unsigned NumOps = TID.getNumOperands() - NumRes; 114195f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng for (unsigned i = 0; i != NumOps; ++i) { 11423db805ea80eeec9084a1b86273d93804d233d938Chris Lattner if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) { 1143550f5afb68ce8f034991863cac65bef22a6554daDan Gohman SDNode *DU = SU->getNode()->getOperand(i).getNode(); 114494d7a5f8156e62532870fbaf197377b34e52ff2aDan Gohman if (DU->getNodeId() != -1 && 114594d7a5f8156e62532870fbaf197377b34e52ff2aDan Gohman Op->OrigNode == &(*SUnits)[DU->getNodeId()]) 114695f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng return true; 114795f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 114895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 1149e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng } 1150e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return false; 1151e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1152e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 115395f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 115422a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// hasCopyToRegUse - Return true if SU has a value successor that is a 115522a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// CopyToReg node. 1156430b8a22e2717d3dfb6b4f096bc23c9538fd7959Dan Gohmanstatic bool hasCopyToRegUse(const SUnit *SU) { 115722a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 115822a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng I != E; ++I) { 115954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isCtrl()) continue; 116054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman const SUnit *SuccSU = I->getSUnit(); 1161550f5afb68ce8f034991863cac65bef22a6554daDan Gohman if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg) 116222a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng return true; 116322a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng } 116422a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng return false; 116522a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng} 116622a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng 1167180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng/// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's 11682f1d3108e481758da66662f72673741da86312daDan Gohman/// physical register defs. 1169430b8a22e2717d3dfb6b4f096bc23c9538fd7959Dan Gohmanstatic bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU, 1170180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng const TargetInstrInfo *TII, 11716f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI) { 1172550f5afb68ce8f034991863cac65bef22a6554daDan Gohman SDNode *N = SuccSU->getNode(); 1173e8be6c63915e0389f1eef6b53c64300d13b2ce99Dan Gohman unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs(); 1174e8be6c63915e0389f1eef6b53c64300d13b2ce99Dan Gohman const unsigned *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs(); 11752f1d3108e481758da66662f72673741da86312daDan Gohman assert(ImpDefs && "Caller should check hasPhysRegDefs"); 1176349c4952009525b27383e2120a6b3c998f39bd09Chris Lattner const unsigned *SUImpDefs = 1177550f5afb68ce8f034991863cac65bef22a6554daDan Gohman TII->get(SU->getNode()->getMachineOpcode()).getImplicitDefs(); 1178180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng if (!SUImpDefs) 1179180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng return false; 1180180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) { 118183ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands MVT VT = N->getValueType(i); 1182180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng if (VT == MVT::Flag || VT == MVT::Other) 1183180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng continue; 118459932584a812685b16ad6a53a023b2bb3fc21819Dan Gohman if (!N->hasAnyUseOfValue(i)) 118559932584a812685b16ad6a53a023b2bb3fc21819Dan Gohman continue; 1186180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng unsigned Reg = ImpDefs[i - NumDefs]; 1187180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng for (;*SUImpDefs; ++SUImpDefs) { 1188180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng unsigned SUReg = *SUImpDefs; 11896f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TRI->regsOverlap(Reg, SUReg)) 1190180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng return true; 1191180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng } 1192180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng } 1193180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng return false; 1194180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng} 1195180c210a1d96a56ae0611d4f8de81e1ada5559ebEvan Cheng 1196e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses 1197e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// it as a def&use operand. Add a pseudo control edge from it to the other 1198e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng/// node (if it won't create a cycle) so the two-address one will be scheduled 119922a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// first (lower in the schedule). If both nodes are two-address, favor the 120022a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// one that has a CopyToReg use (more likely to be a loop induction update). 120122a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// If both are two-address, but one is commutable while the other is not 120222a529990bb4bb86bdb2ae1cfce7340320a6ca7fEvan Cheng/// commutable, favor the one that's not commutable. 12036be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohmantemplate<class SF> 12046be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohmanvoid RegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() { 120595f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 1206430b8a22e2717d3dfb6b4f096bc23c9538fd7959Dan Gohman SUnit *SU = &(*SUnits)[i]; 120795f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng if (!SU->isTwoAddress) 120895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng continue; 120995f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 1210550f5afb68ce8f034991863cac65bef22a6554daDan Gohman SDNode *Node = SU->getNode(); 1211d23e0f81bc76902052e9198cad3a0d87a412a632Dan Gohman if (!Node || !Node->isMachineOpcode() || SU->getNode()->getFlaggedNode()) 121295f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng continue; 121395f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng 1214e8be6c63915e0389f1eef6b53c64300d13b2ce99Dan Gohman unsigned Opc = Node->getMachineOpcode(); 1215749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = TII->get(Opc); 12163db805ea80eeec9084a1b86273d93804d233d938Chris Lattner unsigned NumRes = TID.getNumDefs(); 12173b66555c53eb8921b2dd50335e0b278ddf80d220Dan Gohman unsigned NumOps = TID.getNumOperands() - NumRes; 121895f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng for (unsigned j = 0; j != NumOps; ++j) { 1219c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1) 1220c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman continue; 1221c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman SDNode *DU = SU->getNode()->getOperand(j).getNode(); 1222c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman if (DU->getNodeId() == -1) 1223c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman continue; 1224c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman const SUnit *DUSU = &(*SUnits)[DU->getNodeId()]; 1225c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman if (!DUSU) continue; 1226c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman for (SUnit::const_succ_iterator I = DUSU->Succs.begin(), 1227c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman E = DUSU->Succs.end(); I != E; ++I) { 122854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isCtrl()) continue; 122954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SuccSU = I->getSUnit(); 1230c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman if (SuccSU == SU) 12317da8f399bf09e9a03fe8bdd8c8eef6e5a7d87327Evan Cheng continue; 1232c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman // Be conservative. Ignore if nodes aren't at roughly the same 1233c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman // depth and height. 12343f23744df4809eba94284e601e81489212c974d4Dan Gohman if (SuccSU->getHeight() < SU->getHeight() && 12353f23744df4809eba94284e601e81489212c974d4Dan Gohman (SU->getHeight() - SuccSU->getHeight()) > 1) 1236c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman continue; 1237c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode()) 1238c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman continue; 1239c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman // Don't constrain nodes with physical register defs if the 1240c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman // predecessor can clobber them. 1241c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman if (SuccSU->hasPhysRegDefs) { 1242c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI)) 124332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng continue; 1244c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman } 1245c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman // Don't constraint extract_subreg / insert_subreg these may be 1246c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman // coalesced away. We don't them close to their uses. 1247c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode(); 1248c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG || 1249c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman SuccOpc == TargetInstrInfo::INSERT_SUBREG) 1250c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman continue; 1251c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman if ((!canClobber(SuccSU, DUSU) || 1252c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) || 1253c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman (!SU->isCommutable && SuccSU->isCommutable)) && 1254c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman !scheduleDAG->IsReachable(SuccSU, SU)) { 1255b29ffc88701fc373c832ea2e7142ad6f72eef050Dan Gohman DOUT << "Adding a pseudo-two-addr edge from SU # " << SU->NodeNum 1256c2f9062ea4915ae034417eaeead3c5942921f24dDan Gohman << " to SU #" << SuccSU->NodeNum << "\n"; 1257fd2163bcf77df6b3e58868483c089bd3869b01d6Dan Gohman scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0, 1258ce0d4b7a77da716f234d42edd0472e97b3ba5f57Dan Gohman /*Reg=*/0, /*isNormalMemory=*/false, 1259ce0d4b7a77da716f234d42edd0472e97b3ba5f57Dan Gohman /*isMustAlias=*/false, 126054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /*isArtificial=*/true)); 126195f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 126295f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 126395f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 126495f6edeff5ab6de9cf5589f662c8e7a6ba119c2cEvan Cheng } 1265e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1266e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1267c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all 1268c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng/// scheduling units. 1269117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohmantemplate<class SF> 1270117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohmanvoid RegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() { 1271e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SethiUllmanNumbers.assign(SUnits->size(), 0); 1272e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1273e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 1274117f3e9ee426ab7eb120b5ca1b65763baae2a824Dan Gohman CalcNodeSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers); 1275c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng} 1276e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1277d7d3ea00c0a26e2545d4ba01825d8358075264e7Roman Levenstein/// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled 127895d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein/// predecessors of the successors of the SUnit SU. Stop when the provided 127995d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein/// limit is exceeded. 128095d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levensteinstatic unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU, 128195d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein unsigned Limit) { 128295d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein unsigned Sum = 0; 128395d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 128495d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein I != E; ++I) { 128554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman const SUnit *SuccSU = I->getSUnit(); 128695d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(), 128795d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein EE = SuccSU->Preds.end(); II != EE; ++II) { 128854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *PredSU = II->getSUnit(); 1289fd5da6c991ad0bb5c0b6ce797d56c49ad3f73803Evan Cheng if (!PredSU->isScheduled) 1290fd5da6c991ad0bb5c0b6ce797d56c49ad3f73803Evan Cheng if (++Sum > Limit) 1291fd5da6c991ad0bb5c0b6ce797d56c49ad3f73803Evan Cheng return Sum; 129295d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein } 129395d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein } 129495d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein return Sum; 129595d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein} 129695d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein 1297e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1298e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// Top down 1299e165a78551a91d8420cd8f074d97701e8788f8b5Evan Chengbool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 1300c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned LPriority = SPQ->getNodePriority(left); 1301c8edc64188399437f5476d7fa45f714a92f2cb93Evan Cheng unsigned RPriority = SPQ->getNodePriority(right); 1302550f5afb68ce8f034991863cac65bef22a6554daDan Gohman bool LIsTarget = left->getNode() && left->getNode()->isMachineOpcode(); 1303550f5afb68ce8f034991863cac65bef22a6554daDan Gohman bool RIsTarget = right->getNode() && right->getNode()->isMachineOpcode(); 1304e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool LIsFloater = LIsTarget && left->NumPreds == 0; 1305e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool RIsFloater = RIsTarget && right->NumPreds == 0; 130695d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0; 130795d4184e7218d7ec21b5b8d693dd3b14146eefdcRoman Levenstein unsigned RBonus = (LimitedSumOfUnscheduledPredsOfSuccs(right,1) == 1) ? 2 : 0; 1308e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1309e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (left->NumSuccs == 0 && right->NumSuccs != 0) 1310e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return false; 1311e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng else if (left->NumSuccs != 0 && right->NumSuccs == 0) 1312e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng return true; 1313e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1314e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (LIsFloater) 1315e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng LBonus -= 2; 1316e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (RIsFloater) 1317e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng RBonus -= 2; 1318e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (left->NumSuccs == 1) 1319e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng LBonus += 2; 1320e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng if (right->NumSuccs == 1) 1321e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng RBonus += 2; 1322e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 132384d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng if (LPriority+LBonus != RPriority+RBonus) 132484d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng return LPriority+LBonus < RPriority+RBonus; 132584d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng 13263f23744df4809eba94284e601e81489212c974d4Dan Gohman if (left->getDepth() != right->getDepth()) 13273f23744df4809eba94284e601e81489212c974d4Dan Gohman return left->getDepth() < right->getDepth(); 132884d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng 132984d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng if (left->NumSuccsLeft != right->NumSuccsLeft) 133084d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng return left->NumSuccsLeft > right->NumSuccsLeft; 133184d4a2b4ad0874a46642bb568b45720d55e46b64Evan Cheng 1332a0201d52049be8dcefffe4304a49690a831bcb34Roman Levenstein assert(left->NodeQueueId && right->NodeQueueId && 1333a0201d52049be8dcefffe4304a49690a831bcb34Roman Levenstein "NodeQueueId cannot be zero"); 1334a0201d52049be8dcefffe4304a49690a831bcb34Roman Levenstein return (left->NodeQueueId > right->NodeQueueId); 1335e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1336e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 1337e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 1338e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng// Public Constructor Functions 1339e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng//===----------------------------------------------------------------------===// 1340e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 13419ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskeyllvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, 13429ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey SelectionDAG *DAG, 13439b75b373756288cd39489da7994207f50b31ee40Dan Gohman const TargetMachine *TM, 13444576f6d7a9c0f2c6a3b6c5d4d8a3063bbf763ae5Evan Cheng MachineBasicBlock *BB, 13459e76fea3abd4229749e6ead46a0016cabff4a056Dan Gohman bool) { 13469b75b373756288cd39489da7994207f50b31ee40Dan Gohman const TargetInstrInfo *TII = TM->getInstrInfo(); 13479b75b373756288cd39489da7994207f50b31ee40Dan Gohman const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 1348e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein 1349c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng BURegReductionPriorityQueue *PQ = new BURegReductionPriorityQueue(TII, TRI); 1350e513ba49589bcf8fdf7dad658e20db21d6ef4758Roman Levenstein 1351c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng ScheduleDAGRRList *SD = 13529e76fea3abd4229749e6ead46a0016cabff4a056Dan Gohman new ScheduleDAGRRList(DAG, BB, *TM, true, PQ); 1353c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng PQ->setScheduleDAG(SD); 1354c6be777208f4539af400ac694d9d1dc8b992bc80Evan Cheng return SD; 1355e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1356e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 13579ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskeyllvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, 13589ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey SelectionDAG *DAG, 13599b75b373756288cd39489da7994207f50b31ee40Dan Gohman const TargetMachine *TM, 13604576f6d7a9c0f2c6a3b6c5d4d8a3063bbf763ae5Evan Cheng MachineBasicBlock *BB, 13619e76fea3abd4229749e6ead46a0016cabff4a056Dan Gohman bool) { 13626be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman const TargetInstrInfo *TII = TM->getInstrInfo(); 13636be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 13646be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman 13656be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman TDRegReductionPriorityQueue *PQ = new TDRegReductionPriorityQueue(TII, TRI); 13666be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman 13679e76fea3abd4229749e6ead46a0016cabff4a056Dan Gohman ScheduleDAGRRList *SD = new ScheduleDAGRRList(DAG, BB, *TM, false, PQ); 13686be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman PQ->setScheduleDAG(SD); 13696be2ee431f44e3eb4d87bb3779a7e97a766c7a3eDan Gohman return SD; 1370e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng} 1371