16dc75fe5279e2c12bda13dcc4a1a13908de8596fDan Gohman//==- ScheduleDAGInstrs.h - MachineInstr Scheduling --------------*- C++ -*-==// 2343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 3343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// The LLVM Compiler Infrastructure 4343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 5343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This file is distributed under the University of Illinois Open Source 6343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// License. See LICENSE.TXT for details. 7343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 8343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 9343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 10343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This file implements the ScheduleDAGInstrs class, which implements 11343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// scheduling for a MachineInstr-based dependency graph. 12343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 13343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 14343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 15674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H 16674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H 17343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 18afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman#include "llvm/ADT/SparseMultiSet.h" 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SparseSet.h" 20343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/ScheduleDAG.h" 2134301ceca8913f3126339f332d3dc6f2d7ac0d78Andrew Trick#include "llvm/CodeGen/TargetSchedule.h" 229e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman#include "llvm/Support/Compiler.h" 2379ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman#include "llvm/Target/TargetRegisterInfo.h" 24343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 25343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmannamespace llvm { 26760fa5dc8022dcf6982969c26ef566dfbeea979cJakub Staszak class MachineFrameInfo; 273f23744df4809eba94284e601e81489212c974d4Dan Gohman class MachineLoopInfo; 283f23744df4809eba94284e601e81489212c974d4Dan Gohman class MachineDominatorTree; 29b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick class LiveIntervals; 30006e1abf76148626fb38de1b643c2d31de7f08a7Andrew Trick class RegPressureTracker; 314c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick class PressureDiffs; 323f23744df4809eba94284e601e81489212c974d4Dan Gohman 33035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// An individual mapping from virtual register number to SUnit. 34035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick struct VReg2SUnit { 35035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick unsigned VirtReg; 36035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick SUnit *SU; 37035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 38035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick VReg2SUnit(unsigned reg, SUnit *su): VirtReg(reg), SU(su) {} 39035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 40c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick unsigned getSparseSetIndex() const { 41035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick return TargetRegisterInfo::virtReg2Index(VirtReg); 42035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick } 43035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick }; 44035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 45ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// Record a physical register access. 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// For non-data-dependent uses, OpIdx == -1. 47ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick struct PhysRegSUOper { 48ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick SUnit *SU; 49ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick int OpIdx; 50afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman unsigned Reg; 51ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick 52afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {} 53035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 54afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman unsigned getSparseSetIndex() const { return Reg; } 55035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick }; 56035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 57afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman /// Use a SparseMultiSet to track physical registers. Storage is only 58afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman /// allocated once for the pass. It can be cleared in constant time and reused 59afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman /// without any frees. 6099093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick typedef SparseMultiSet<PhysRegSUOper, llvm::identity<unsigned>, uint16_t> 6199093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick Reg2SUnitsMap; 62afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 63035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// Use SparseSet as a SparseMap by relying on the fact that it never 64035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// compares ValueT's, only unsigned keys. This allows the set to be cleared 65035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// between scheduling regions in constant time as long as ValueT does not 66035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// require a destructor. 67c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick typedef SparseSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMap; 68035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 6999093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick /// Track local uses of virtual registers. These uses are gathered by the DAG 7099093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick /// builder and may be consulted by the scheduler to avoid iterating an entire 7199093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick /// vreg use list. 7299093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick typedef SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2UseMap; 7399093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick 749e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of 759e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// MachineInstrs. 76ed8a0ecaa82726c88d1962a7df060390eb6e9c22Andrew Trick class ScheduleDAGInstrs : public ScheduleDAG { 7747c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick protected: 783f23744df4809eba94284e601e81489212c974d4Dan Gohman const MachineLoopInfo &MLI; 793f23744df4809eba94284e601e81489212c974d4Dan Gohman const MachineDominatorTree &MDT; 8038bdfc69cbe370ce5f623df4449afa32cda97422Evan Cheng const MachineFrameInfo *MFI; 813f23744df4809eba94284e601e81489212c974d4Dan Gohman 82d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// Live Intervals provides reaching defs in preRA scheduling. 83d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick LiveIntervals *LIS; 84d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick 8534301ceca8913f3126339f332d3dc6f2d7ac0d78Andrew Trick /// TargetSchedModel provides an interface to the machine model. 8634301ceca8913f3126339f332d3dc6f2d7ac0d78Andrew Trick TargetSchedModel SchedModel; 8734301ceca8913f3126339f332d3dc6f2d7ac0d78Andrew Trick 885e920d7c83c20474fc3470209869978628ccf8daAndrew Trick /// isPostRA flag indicates vregs cannot be present. 895e920d7c83c20474fc3470209869978628ccf8daAndrew Trick bool IsPostRA; 905e920d7c83c20474fc3470209869978628ccf8daAndrew Trick 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// True if the DAG builder should remove kill flags (in preparation for 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// rescheduling). 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool RemoveKillFlags; 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 95007079201276368736fc893d4d5ec7aeeca00823Andrew Trick /// The standard DAG builder does not normally include terminators as DAG 96007079201276368736fc893d4d5ec7aeeca00823Andrew Trick /// nodes because it does not create the necessary dependencies to prevent 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// reordering. A specialized scheduler can override 98007079201276368736fc893d4d5ec7aeeca00823Andrew Trick /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate 99007079201276368736fc893d4d5ec7aeeca00823Andrew Trick /// it has taken responsibility for scheduling the terminator correctly. 100007079201276368736fc893d4d5ec7aeeca00823Andrew Trick bool CanHandleTerminators; 101007079201276368736fc893d4d5ec7aeeca00823Andrew Trick 10247c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// State specific to the current scheduling region. 103d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// ------------------------------------------------ 10447c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 105d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// The block in which to insert instructions 10647c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick MachineBasicBlock *BB; 10747c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 108cf46b5acfd6e0ab5d21ec3160cec195d0eb77b0bAndrew Trick /// The beginning of the range to be scheduled. 10968675c6c5b173021807e4e12cd250eeba63f6d0dAndrew Trick MachineBasicBlock::iterator RegionBegin; 11047c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 111cf46b5acfd6e0ab5d21ec3160cec195d0eb77b0bAndrew Trick /// The end of the range to be scheduled. 11268675c6c5b173021807e4e12cd250eeba63f6d0dAndrew Trick MachineBasicBlock::iterator RegionEnd; 11347c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 114d2763f6ce62eaa497e944331668414e35f3712f3Andrew Trick /// Instructions in this region (distance(RegionBegin, RegionEnd)). 115d2763f6ce62eaa497e944331668414e35f3712f3Andrew Trick unsigned NumRegionInstrs; 11647c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 117e75537a243858d8293832109e61bafc8484bb52aAndrew Trick /// After calling BuildSchedGraph, each machine instruction in the current 118e75537a243858d8293832109e61bafc8484bb52aAndrew Trick /// scheduling region is mapped to an SUnit. 119b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick DenseMap<MachineInstr*, SUnit*> MISUnitMap; 120b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick 12199093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick /// After calling BuildSchedGraph, each vreg used in the scheduling region 12299093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick /// is mapped to a set of SUnits. These include all local vreg uses, not 12399093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick /// just the uses for a singly defined vreg. 12499093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick VReg2UseMap VRegUses; 12599093638a024fc23609a323677e67bb1dc63ebe7Andrew Trick 126d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// State internal to DAG building. 127d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// ------------------------------- 1287ebcaf4cf929ef041ae6c9c07b897e4d0aa8ad06Andrew Trick 129702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick /// Defs, Uses - Remember where defs and uses of each register are as we 130702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick /// iterate upward through the instructions. This is allocated here instead 131702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick /// of inside BuildSchedGraph to avoid the need for it to be initialized and 132702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick /// destructed for each block. 133702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick Reg2SUnitsMap Defs; 134702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick Reg2SUnitsMap Uses; 1354563bbaba7fad4403acf0236cbd75805c68f2a90Andrew Trick 1363f4f420ab7acb10221ba971543a7eed5489fb626Robert Wilhelm /// Track the last instruction in this region defining each virtual register. 1378ae3ac7a8c2112ab739b4a0dc24f28b2bbb84117Andrew Trick VReg2SUnitMap VRegDefs; 1383c58ba8ea7ec097d69d7f7be5930a4a4d7405a18Andrew Trick 13979ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman /// PendingLoads - Remember where unknown loads are after the most recent 14079ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman /// unknown store, as we iterate. As with Defs and Uses, this is here 14179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman /// to minimize construction/destruction. 14279ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman std::vector<SUnit *> PendingLoads; 14379ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman 144d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer /// DbgValues - Remember instruction that precedes DBG_VALUE. 145d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// These are generated by buildSchedGraph but persist so they can be 146d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// referenced when emitting the final schedule. 1474563bbaba7fad4403acf0236cbd75805c68f2a90Andrew Trick typedef std::vector<std::pair<MachineInstr *, MachineInstr *> > 148e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel DbgValueVector; 149e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel DbgValueVector DbgValues; 150e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel MachineInstr *FirstDbgValue; 151e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel 15236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Set of live physical registers for updating kill flags. 15336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BitVector LiveRegs; 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 155343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman public: 15679ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman explicit ScheduleDAGInstrs(MachineFunction &mf, 15779ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman const MachineLoopInfo &mli, 1585e920d7c83c20474fc3470209869978628ccf8daAndrew Trick const MachineDominatorTree &mdt, 159b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick bool IsPostRAFlag, 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool RemoveKillFlags = false, 161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LiveIntervals *LIS = nullptr); 162343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 163343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual ~ScheduleDAGInstrs() {} 164343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool isPostRA() const { return IsPostRA; } 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 167e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick /// \brief Expose LiveIntervals for use in DAG mutators and such. 168e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick LiveIntervals *getLIS() const { return LIS; } 169e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick 170412cd2f81374865dfa708bef6d5b896ca10dece0Andrew Trick /// \brief Get the machine model for instruction scheduling. 171412cd2f81374865dfa708bef6d5b896ca10dece0Andrew Trick const TargetSchedModel *getSchedModel() const { return &SchedModel; } 172412cd2f81374865dfa708bef6d5b896ca10dece0Andrew Trick 1738d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick /// \brief Resolve and cache a resolved scheduling class for an SUnit. 1748d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick const MCSchedClassDesc *getSchedClass(SUnit *SU) const { 175b86a0cdb674549d8493043331cecd9cbf53b80daAndrew Trick if (!SU->SchedClass && SchedModel.hasInstrSchedModel()) 1768d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr()); 1778d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick return SU->SchedClass; 1788d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick } 1798d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick 18047c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// begin - Return an iterator to the top of the current scheduling region. 18168675c6c5b173021807e4e12cd250eeba63f6d0dAndrew Trick MachineBasicBlock::iterator begin() const { return RegionBegin; } 18247c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 18347c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// end - Return an iterator to the bottom of the current scheduling region. 18468675c6c5b173021807e4e12cd250eeba63f6d0dAndrew Trick MachineBasicBlock::iterator end() const { return RegionEnd; } 18547c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 1867afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick /// newSUnit - Creates a new SUnit and return a ptr to it. 187035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick SUnit *newSUnit(MachineInstr *MI); 188343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 1897afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick /// getSUnit - Return an existing SUnit for this MI, or NULL. 1907afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick SUnit *getSUnit(MachineInstr *MI) const; 1917afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick 192953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// startBlock - Prepare to perform scheduling in the given block. 193953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void startBlock(MachineBasicBlock *BB); 194b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick 195953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// finishBlock - Clean up after scheduling in the given block. 196953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void finishBlock(); 19747c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 19847c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// Initialize the scheduler state for the next scheduling region. 19947c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick virtual void enterRegion(MachineBasicBlock *bb, 20047c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick MachineBasicBlock::iterator begin, 20147c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick MachineBasicBlock::iterator end, 202d2763f6ce62eaa497e944331668414e35f3712f3Andrew Trick unsigned regioninstrs); 20347c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 20447c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// Notify that the scheduler has finished scheduling the current region. 20547c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick virtual void exitRegion(); 20647ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 207953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are 208343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// input. 209dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void buildSchedGraph(AliasAnalysis *AA, 210dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RegPressureTracker *RPTracker = nullptr, 211dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PressureDiffs *PDiffs = nullptr); 212343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 213953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// addSchedBarrierDeps - Add dependencies from instructions in the current 214ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// list of instructions being scheduled to scheduling barrier. We want to 215ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// make sure instructions which define registers that are either used by 216ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// the terminator or are live-out are properly scheduled. This is 217ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// especially important when the definition latency of the return value(s) 218ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// are too high to be hidden by the branch or when the liveout registers 219ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// used by instructions in the fallthrough block. 220953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick void addSchedBarrierDeps(); 221ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng 222953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// schedule - Order nodes according to selected style, filling 223343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// in the Sequence member. 224343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 225953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// Typically, a scheduling algorithm will implement schedule() without 2266fd7dd6ba57c1b5ba1f12e7e9da574b9dbd8ae09Andrew Trick /// overriding enterRegion() or exitRegion(). 227953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void schedule() = 0; 228343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 229830da405fa32ab4f2a8378a658e1429a9ffd4d65Andrew Trick /// finalizeSchedule - Allow targets to perform final scheduling actions at 230830da405fa32ab4f2a8378a658e1429a9ffd4d65Andrew Trick /// the level of the whole MachineFunction. By default does nothing. 231830da405fa32ab4f2a8378a658e1429a9ffd4d65Andrew Trick virtual void finalizeSchedule() {} 232830da405fa32ab4f2a8378a658e1429a9ffd4d65Andrew Trick 23336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void dumpNode(const SUnit *SU) const override; 234343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 2357b58ae77acb63db29116e548393ddd2127909425Andrew Trick /// Return a label for a DAG node that points to an instruction. 23636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::string getGraphNodeLabel(const SUnit *SU) const override; 2377ebcaf4cf929ef041ae6c9c07b897e4d0aa8ad06Andrew Trick 2387b58ae77acb63db29116e548393ddd2127909425Andrew Trick /// Return a label for the region of code covered by the DAG. 23936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::string getDAGName() const override; 24056b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick 24136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Fix register kill flags that scheduling has made invalid. 24236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void fixupKills(MachineBasicBlock *MBB); 2437ebcaf4cf929ef041ae6c9c07b897e4d0aa8ad06Andrew Trick protected: 244b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick void initSUnits(); 245ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx); 2467ebcaf4cf929ef041ae6c9c07b897e4d0aa8ad06Andrew Trick void addPhysRegDeps(SUnit *SU, unsigned OperIdx); 2473c58ba8ea7ec097d69d7f7be5930a4a4d7405a18Andrew Trick void addVRegDefDeps(SUnit *SU, unsigned OperIdx); 2483c58ba8ea7ec097d69d7f7be5930a4a4d7405a18Andrew Trick void addVRegUseDeps(SUnit *SU, unsigned OperIdx); 24936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief PostRA helper for rewriting kill flags. 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void startBlockForKills(MachineBasicBlock *BB); 25236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Toggle a register operand kill flag. 25436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Other adjustments may be made to the instruction if necessary. Return 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// true if the operand has been deleted, false if not. 25736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool toggleKillFlag(MachineInstr *MI, MachineOperand &MO); 258343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman }; 259035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 2607afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick /// newSUnit - Creates a new SUnit and return a ptr to it. 261035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) { 262035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick#ifndef NDEBUG 263dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0]; 264035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick#endif 265035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick SUnits.push_back(SUnit(MI, (unsigned)SUnits.size())); 266dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert((Addr == nullptr || Addr == &SUnits[0]) && 267035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick "SUnits std::vector reallocated on the fly!"); 268035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick SUnits.back().OrigNode = &SUnits.back(); 269035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick return &SUnits.back(); 270035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick } 2717afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick 2727afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick /// getSUnit - Return an existing SUnit for this MI, or NULL. 2737afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const { 2747afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI); 2757afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick if (I == MISUnitMap.end()) 276dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 2777afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick return I->second; 2787afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick } 279035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick} // namespace llvm 280343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 281343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#endif 282