Chris Lattner | a3b8b5c | 2004-07-23 17:56:30 +0000 | [diff] [blame] | 1 | //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements the LiveInterval analysis pass which is used |
| 11 | // by the Linear Scan Register allocator. This pass linearizes the |
| 12 | // basic blocks of the function in DFS order and uses the |
| 13 | // LiveVariables pass to conservatively compute live intervals for |
| 14 | // each virtual and physical register. |
| 15 | // |
| 16 | //===----------------------------------------------------------------------===// |
| 17 | |
Jakob Stoklund Olesen | 4281e20 | 2012-01-07 07:39:47 +0000 | [diff] [blame] | 18 | #define DEBUG_TYPE "regalloc" |
Chris Lattner | 3c3fe46 | 2005-09-21 04:19:09 +0000 | [diff] [blame] | 19 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
Chris Lattner | 015959e | 2004-05-01 21:24:39 +0000 | [diff] [blame] | 20 | #include "llvm/Value.h" |
Dan Gohman | 6d69ba8 | 2008-07-25 00:02:30 +0000 | [diff] [blame] | 21 | #include "llvm/Analysis/AliasAnalysis.h" |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/LiveVariables.h" |
Jakob Stoklund Olesen | 34c6f98 | 2012-06-05 22:02:15 +0000 | [diff] [blame] | 23 | #include "llvm/CodeGen/MachineDominators.h" |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 24 | #include "llvm/CodeGen/MachineInstr.h" |
Chris Lattner | 84bc542 | 2007-12-31 04:13:23 +0000 | [diff] [blame] | 25 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 26 | #include "llvm/CodeGen/Passes.h" |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 27 | #include "llvm/Target/TargetRegisterInfo.h" |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 28 | #include "llvm/Target/TargetInstrInfo.h" |
| 29 | #include "llvm/Target/TargetMachine.h" |
Jakob Stoklund Olesen | 3dfa38a | 2012-07-27 20:58:46 +0000 | [diff] [blame] | 30 | #include "llvm/Support/CommandLine.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 31 | #include "llvm/Support/Debug.h" |
Torok Edwin | 7d696d8 | 2009-07-11 13:10:19 +0000 | [diff] [blame] | 32 | #include "llvm/Support/ErrorHandling.h" |
| 33 | #include "llvm/Support/raw_ostream.h" |
Andrew Trick | d35576b | 2012-02-13 20:44:42 +0000 | [diff] [blame] | 34 | #include "llvm/ADT/DenseSet.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 35 | #include "llvm/ADT/STLExtras.h" |
Jakob Stoklund Olesen | 34c6f98 | 2012-06-05 22:02:15 +0000 | [diff] [blame] | 36 | #include "LiveRangeCalc.h" |
Jakob Stoklund Olesen | e617ccb | 2012-09-06 18:15:18 +0000 | [diff] [blame] | 37 | #include "VirtRegMap.h" |
Alkis Evlogimenos | 20aa474 | 2004-09-03 18:19:51 +0000 | [diff] [blame] | 38 | #include <algorithm> |
Lang Hames | f41538d | 2009-06-02 16:53:25 +0000 | [diff] [blame] | 39 | #include <limits> |
Jeff Cohen | 97af751 | 2006-12-02 02:22:01 +0000 | [diff] [blame] | 40 | #include <cmath> |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 41 | using namespace llvm; |
| 42 | |
Jakob Stoklund Olesen | 3dfa38a | 2012-07-27 20:58:46 +0000 | [diff] [blame] | 43 | // Switch to the new experimental algorithm for computing live intervals. |
| 44 | static cl::opt<bool> |
| 45 | NewLiveIntervals("new-live-intervals", cl::Hidden, |
| 46 | cl::desc("Use new algorithm forcomputing live intervals")); |
| 47 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 48 | char LiveIntervals::ID = 0; |
Jakob Stoklund Olesen | dcc4436 | 2012-08-03 22:12:54 +0000 | [diff] [blame] | 49 | char &llvm::LiveIntervalsID = LiveIntervals::ID; |
Owen Anderson | 2ab36d3 | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 50 | INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", |
| 51 | "Live Interval Analysis", false, false) |
Andrew Trick | 8dd2625 | 2012-02-10 04:10:36 +0000 | [diff] [blame] | 52 | INITIALIZE_AG_DEPENDENCY(AliasAnalysis) |
Owen Anderson | 2ab36d3 | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 53 | INITIALIZE_PASS_DEPENDENCY(LiveVariables) |
Andrew Trick | 8dd2625 | 2012-02-10 04:10:36 +0000 | [diff] [blame] | 54 | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
Owen Anderson | 2ab36d3 | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 55 | INITIALIZE_PASS_DEPENDENCY(SlotIndexes) |
Owen Anderson | 2ab36d3 | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 56 | INITIALIZE_PASS_END(LiveIntervals, "liveintervals", |
Owen Anderson | ce665bd | 2010-10-07 22:25:06 +0000 | [diff] [blame] | 57 | "Live Interval Analysis", false, false) |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 58 | |
Chris Lattner | f7da2c7 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 59 | void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { |
Dan Gohman | 845012e | 2009-07-31 23:37:33 +0000 | [diff] [blame] | 60 | AU.setPreservesCFG(); |
Dan Gohman | 6d69ba8 | 2008-07-25 00:02:30 +0000 | [diff] [blame] | 61 | AU.addRequired<AliasAnalysis>(); |
| 62 | AU.addPreserved<AliasAnalysis>(); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 63 | AU.addRequired<LiveVariables>(); |
Evan Cheng | 148341c | 2010-08-17 21:00:37 +0000 | [diff] [blame] | 64 | AU.addPreserved<LiveVariables>(); |
Andrew Trick | d35576b | 2012-02-13 20:44:42 +0000 | [diff] [blame] | 65 | AU.addPreservedID(MachineLoopInfoID); |
Jakob Stoklund Olesen | c411845 | 2012-06-20 23:31:34 +0000 | [diff] [blame] | 66 | AU.addRequiredTransitiveID(MachineDominatorsID); |
Bill Wendling | 67d65bb | 2008-01-04 20:54:55 +0000 | [diff] [blame] | 67 | AU.addPreservedID(MachineDominatorsID); |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 68 | AU.addPreserved<SlotIndexes>(); |
| 69 | AU.addRequiredTransitive<SlotIndexes>(); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 70 | MachineFunctionPass::getAnalysisUsage(AU); |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 71 | } |
| 72 | |
Jakob Stoklund Olesen | 34c6f98 | 2012-06-05 22:02:15 +0000 | [diff] [blame] | 73 | LiveIntervals::LiveIntervals() : MachineFunctionPass(ID), |
| 74 | DomTree(0), LRCalc(0) { |
| 75 | initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); |
| 76 | } |
| 77 | |
| 78 | LiveIntervals::~LiveIntervals() { |
| 79 | delete LRCalc; |
| 80 | } |
| 81 | |
Chris Lattner | f7da2c7 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 82 | void LiveIntervals::releaseMemory() { |
Owen Anderson | 03857b2 | 2008-08-13 21:49:13 +0000 | [diff] [blame] | 83 | // Free the live intervals themselves. |
Jakob Stoklund Olesen | 7fa6784 | 2012-06-22 20:37:52 +0000 | [diff] [blame] | 84 | for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i) |
| 85 | delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)]; |
| 86 | VirtRegIntervals.clear(); |
Jakob Stoklund Olesen | 3fd3a84 | 2012-02-08 17:33:45 +0000 | [diff] [blame] | 87 | RegMaskSlots.clear(); |
| 88 | RegMaskBits.clear(); |
Jakob Stoklund Olesen | 34e85d0 | 2012-02-10 01:26:29 +0000 | [diff] [blame] | 89 | RegMaskBlocks.clear(); |
Lang Hames | ffd1326 | 2009-07-09 03:57:02 +0000 | [diff] [blame] | 90 | |
Jakob Stoklund Olesen | 34c6f98 | 2012-06-05 22:02:15 +0000 | [diff] [blame] | 91 | for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i) |
| 92 | delete RegUnitIntervals[i]; |
| 93 | RegUnitIntervals.clear(); |
| 94 | |
Benjamin Kramer | ce9a20b | 2010-06-26 11:30:59 +0000 | [diff] [blame] | 95 | // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. |
| 96 | VNInfoAllocator.Reset(); |
Alkis Evlogimenos | 08cec00 | 2004-01-31 19:59:32 +0000 | [diff] [blame] | 97 | } |
| 98 | |
Owen Anderson | 80b3ce6 | 2008-05-28 20:54:50 +0000 | [diff] [blame] | 99 | /// runOnMachineFunction - Register allocate the whole function |
| 100 | /// |
| 101 | bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 102 | MF = &fn; |
| 103 | MRI = &MF->getRegInfo(); |
| 104 | TM = &fn.getTarget(); |
| 105 | TRI = TM->getRegisterInfo(); |
| 106 | TII = TM->getInstrInfo(); |
| 107 | AA = &getAnalysis<AliasAnalysis>(); |
| 108 | LV = &getAnalysis<LiveVariables>(); |
| 109 | Indexes = &getAnalysis<SlotIndexes>(); |
Jakob Stoklund Olesen | c411845 | 2012-06-20 23:31:34 +0000 | [diff] [blame] | 110 | DomTree = &getAnalysis<MachineDominatorTree>(); |
| 111 | if (!LRCalc) |
Jakob Stoklund Olesen | 34c6f98 | 2012-06-05 22:02:15 +0000 | [diff] [blame] | 112 | LRCalc = new LiveRangeCalc(); |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 113 | AllocatableRegs = TRI->getAllocatableSet(fn); |
| 114 | ReservedRegs = TRI->getReservedRegs(fn); |
Owen Anderson | 80b3ce6 | 2008-05-28 20:54:50 +0000 | [diff] [blame] | 115 | |
Jakob Stoklund Olesen | 3dfa38a | 2012-07-27 20:58:46 +0000 | [diff] [blame] | 116 | // Allocate space for all virtual registers. |
| 117 | VirtRegIntervals.resize(MRI->getNumVirtRegs()); |
| 118 | |
| 119 | if (NewLiveIntervals) { |
| 120 | // This is the new way of computing live intervals. |
| 121 | // It is independent of LiveVariables, and it can run at any time. |
Jakob Stoklund Olesen | c16bf79 | 2012-07-27 21:56:39 +0000 | [diff] [blame] | 122 | computeVirtRegs(); |
| 123 | computeRegMasks(); |
Jakob Stoklund Olesen | 3dfa38a | 2012-07-27 20:58:46 +0000 | [diff] [blame] | 124 | } else { |
| 125 | // This is the old way of computing live intervals. |
| 126 | // It depends on LiveVariables. |
| 127 | computeIntervals(); |
| 128 | } |
Jakob Stoklund Olesen | c411845 | 2012-06-20 23:31:34 +0000 | [diff] [blame] | 129 | computeLiveInRegUnits(); |
Jakob Stoklund Olesen | 34c6f98 | 2012-06-05 22:02:15 +0000 | [diff] [blame] | 130 | |
Chris Lattner | 70ca358 | 2004-09-30 15:59:17 +0000 | [diff] [blame] | 131 | DEBUG(dump()); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 132 | return true; |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 133 | } |
| 134 | |
Chris Lattner | 70ca358 | 2004-09-30 15:59:17 +0000 | [diff] [blame] | 135 | /// print - Implement the dump method. |
Chris Lattner | 45cfe54 | 2009-08-23 06:03:38 +0000 | [diff] [blame] | 136 | void LiveIntervals::print(raw_ostream &OS, const Module* ) const { |
Chris Lattner | 705e07f | 2009-08-23 03:41:05 +0000 | [diff] [blame] | 137 | OS << "********** INTERVALS **********\n"; |
Jakob Stoklund Olesen | f658af5 | 2012-02-14 23:46:21 +0000 | [diff] [blame] | 138 | |
Jakob Stoklund Olesen | 34c6f98 | 2012-06-05 22:02:15 +0000 | [diff] [blame] | 139 | // Dump the regunits. |
| 140 | for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i) |
| 141 | if (LiveInterval *LI = RegUnitIntervals[i]) |
| 142 | OS << PrintRegUnit(i, TRI) << " = " << *LI << '\n'; |
| 143 | |
Jakob Stoklund Olesen | f658af5 | 2012-02-14 23:46:21 +0000 | [diff] [blame] | 144 | // Dump the virtregs. |
Jakob Stoklund Olesen | 7fa6784 | 2012-06-22 20:37:52 +0000 | [diff] [blame] | 145 | for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { |
| 146 | unsigned Reg = TargetRegisterInfo::index2VirtReg(i); |
| 147 | if (hasInterval(Reg)) |
| 148 | OS << PrintReg(Reg) << " = " << getInterval(Reg) << '\n'; |
| 149 | } |
Chris Lattner | 70ca358 | 2004-09-30 15:59:17 +0000 | [diff] [blame] | 150 | |
Evan Cheng | 752195e | 2009-09-14 21:33:42 +0000 | [diff] [blame] | 151 | printInstrs(OS); |
| 152 | } |
| 153 | |
| 154 | void LiveIntervals::printInstrs(raw_ostream &OS) const { |
Chris Lattner | 705e07f | 2009-08-23 03:41:05 +0000 | [diff] [blame] | 155 | OS << "********** MACHINEINSTRS **********\n"; |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 156 | MF->print(OS, Indexes); |
Chris Lattner | 70ca358 | 2004-09-30 15:59:17 +0000 | [diff] [blame] | 157 | } |
| 158 | |
Evan Cheng | 752195e | 2009-09-14 21:33:42 +0000 | [diff] [blame] | 159 | void LiveIntervals::dumpInstrs() const { |
David Greene | 8a34229 | 2010-01-04 22:49:02 +0000 | [diff] [blame] | 160 | printInstrs(dbgs()); |
Evan Cheng | 752195e | 2009-09-14 21:33:42 +0000 | [diff] [blame] | 161 | } |
| 162 | |
Evan Cheng | afff40a | 2010-05-04 20:26:52 +0000 | [diff] [blame] | 163 | static |
Evan Cheng | 3749943 | 2010-05-05 18:27:40 +0000 | [diff] [blame] | 164 | bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) { |
Evan Cheng | afff40a | 2010-05-04 20:26:52 +0000 | [diff] [blame] | 165 | unsigned Reg = MI.getOperand(MOIdx).getReg(); |
| 166 | for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { |
| 167 | const MachineOperand &MO = MI.getOperand(i); |
| 168 | if (!MO.isReg()) |
| 169 | continue; |
| 170 | if (MO.getReg() == Reg && MO.isDef()) { |
| 171 | assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && |
| 172 | MI.getOperand(MOIdx).getSubReg() && |
Jakob Stoklund Olesen | ed2185e | 2010-07-06 23:26:25 +0000 | [diff] [blame] | 173 | (MO.getSubReg() || MO.isImplicit())); |
Evan Cheng | afff40a | 2010-05-04 20:26:52 +0000 | [diff] [blame] | 174 | return true; |
| 175 | } |
| 176 | } |
| 177 | return false; |
| 178 | } |
| 179 | |
Evan Cheng | 3749943 | 2010-05-05 18:27:40 +0000 | [diff] [blame] | 180 | /// isPartialRedef - Return true if the specified def at the specific index is |
| 181 | /// partially re-defining the specified live interval. A common case of this is |
Jakob Stoklund Olesen | 1b29320 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 182 | /// a definition of the sub-register. |
Evan Cheng | 3749943 | 2010-05-05 18:27:40 +0000 | [diff] [blame] | 183 | bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, |
| 184 | LiveInterval &interval) { |
| 185 | if (!MO.getSubReg() || MO.isEarlyClobber()) |
| 186 | return false; |
| 187 | |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 188 | SlotIndex RedefIndex = MIIdx.getRegSlot(); |
Evan Cheng | 3749943 | 2010-05-05 18:27:40 +0000 | [diff] [blame] | 189 | const LiveRange *OldLR = |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 190 | interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); |
Lang Hames | 6e2968c | 2010-09-25 12:04:16 +0000 | [diff] [blame] | 191 | MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); |
| 192 | if (DefMI != 0) { |
Evan Cheng | 3749943 | 2010-05-05 18:27:40 +0000 | [diff] [blame] | 193 | return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; |
| 194 | } |
| 195 | return false; |
| 196 | } |
| 197 | |
Chris Lattner | be4f88a | 2006-08-22 18:19:46 +0000 | [diff] [blame] | 198 | void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 199 | MachineBasicBlock::iterator mi, |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 200 | SlotIndex MIIdx, |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 201 | MachineOperand& MO, |
Evan Cheng | ef0732d | 2008-07-10 07:35:43 +0000 | [diff] [blame] | 202 | unsigned MOIdx, |
Chris Lattner | be4f88a | 2006-08-22 18:19:46 +0000 | [diff] [blame] | 203 | LiveInterval &interval) { |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 204 | DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, TRI)); |
Evan Cheng | 419852c | 2008-04-03 16:39:43 +0000 | [diff] [blame] | 205 | |
Alkis Evlogimenos | 7065157 | 2004-08-04 09:46:56 +0000 | [diff] [blame] | 206 | // Virtual registers may be defined multiple times (due to phi |
| 207 | // elimination and 2-addr elimination). Much of what we do only has to be |
| 208 | // done once for the vreg. We use an empty interval to detect the first |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 209 | // time we see a vreg. |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 210 | LiveVariables::VarInfo& vi = LV->getVarInfo(interval.reg); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 211 | if (interval.empty()) { |
| 212 | // Get the Idx of the defining instructions. |
Jakob Stoklund Olesen | d14614e | 2011-11-13 22:05:42 +0000 | [diff] [blame] | 213 | SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); |
Jakob Stoklund Olesen | 63e6a48 | 2010-05-21 16:32:16 +0000 | [diff] [blame] | 214 | |
Jakob Stoklund Olesen | 92b7df0 | 2012-03-04 19:19:10 +0000 | [diff] [blame] | 215 | // Make sure the first definition is not a partial redefinition. |
| 216 | assert(!MO.readsReg() && "First def cannot also read virtual register " |
| 217 | "missing <undef> flag?"); |
Jakob Stoklund Olesen | 63e6a48 | 2010-05-21 16:32:16 +0000 | [diff] [blame] | 218 | |
Jakob Stoklund Olesen | 3b1088a | 2012-02-04 05:20:49 +0000 | [diff] [blame] | 219 | VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 220 | assert(ValNo->id == 0 && "First value in interval is not 0?"); |
Chris Lattner | 7ac2d31 | 2004-07-24 02:59:07 +0000 | [diff] [blame] | 221 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 222 | // Loop over all of the blocks that the vreg is defined in. There are |
| 223 | // two cases we have to handle here. The most common case is a vreg |
| 224 | // whose lifetime is contained within a basic block. In this case there |
| 225 | // will be a single kill, in MBB, which comes after the definition. |
| 226 | if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { |
| 227 | // FIXME: what about dead vars? |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 228 | SlotIndex killIdx; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 229 | if (vi.Kills[0] != mi) |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 230 | killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot(); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 231 | else |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 232 | killIdx = defIndex.getDeadSlot(); |
Chris Lattner | 6097d13 | 2004-07-19 02:15:56 +0000 | [diff] [blame] | 233 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 234 | // If the kill happens after the definition, we have an intra-block |
| 235 | // live range. |
| 236 | if (killIdx > defIndex) { |
Jeffrey Yasskin | 493a3d0 | 2009-05-26 18:27:15 +0000 | [diff] [blame] | 237 | assert(vi.AliveBlocks.empty() && |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 238 | "Shouldn't be alive across any blocks!"); |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 239 | LiveRange LR(defIndex, killIdx, ValNo); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 240 | interval.addRange(LR); |
David Greene | 8a34229 | 2010-01-04 22:49:02 +0000 | [diff] [blame] | 241 | DEBUG(dbgs() << " +" << LR << "\n"); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 242 | return; |
| 243 | } |
Alkis Evlogimenos | dd2cc65 | 2003-12-18 08:48:48 +0000 | [diff] [blame] | 244 | } |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 245 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 246 | // The other case we handle is when a virtual register lives to the end |
| 247 | // of the defining block, potentially live across some blocks, then is |
| 248 | // live into some number of blocks, but gets killed. Start by adding a |
| 249 | // range that goes from this definition to the end of the defining block. |
Lang Hames | 74ab5ee | 2009-12-22 00:11:50 +0000 | [diff] [blame] | 250 | LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); |
David Greene | 8a34229 | 2010-01-04 22:49:02 +0000 | [diff] [blame] | 251 | DEBUG(dbgs() << " +" << NewLR); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 252 | interval.addRange(NewLR); |
| 253 | |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 254 | bool PHIJoin = LV->isPHIJoin(interval.reg); |
Jakob Stoklund Olesen | dcfe5f3 | 2010-02-23 22:43:58 +0000 | [diff] [blame] | 255 | |
| 256 | if (PHIJoin) { |
Jakob Stoklund Olesen | fa8becb | 2012-06-19 22:50:53 +0000 | [diff] [blame] | 257 | // A phi join register is killed at the end of the MBB and revived as a |
| 258 | // new valno in the killing blocks. |
Jakob Stoklund Olesen | dcfe5f3 | 2010-02-23 22:43:58 +0000 | [diff] [blame] | 259 | assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); |
| 260 | DEBUG(dbgs() << " phi-join"); |
Jakob Stoklund Olesen | dcfe5f3 | 2010-02-23 22:43:58 +0000 | [diff] [blame] | 261 | } else { |
| 262 | // Iterate over all of the blocks that the variable is completely |
| 263 | // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the |
| 264 | // live interval. |
| 265 | for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), |
| 266 | E = vi.AliveBlocks.end(); I != E; ++I) { |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 267 | MachineBasicBlock *aliveBlock = MF->getBlockNumbered(*I); |
Jakob Stoklund Olesen | fa8becb | 2012-06-19 22:50:53 +0000 | [diff] [blame] | 268 | LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), |
| 269 | ValNo); |
Jakob Stoklund Olesen | dcfe5f3 | 2010-02-23 22:43:58 +0000 | [diff] [blame] | 270 | interval.addRange(LR); |
| 271 | DEBUG(dbgs() << " +" << LR); |
| 272 | } |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 273 | } |
| 274 | |
| 275 | // Finally, this virtual register is live from the start of any killing |
| 276 | // block to the 'use' slot of the killing instruction. |
| 277 | for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { |
| 278 | MachineInstr *Kill = vi.Kills[i]; |
Jakob Stoklund Olesen | dcfe5f3 | 2010-02-23 22:43:58 +0000 | [diff] [blame] | 279 | SlotIndex Start = getMBBStartIdx(Kill->getParent()); |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 280 | SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot(); |
Jakob Stoklund Olesen | dcfe5f3 | 2010-02-23 22:43:58 +0000 | [diff] [blame] | 281 | |
| 282 | // Create interval with one of a NEW value number. Note that this value |
| 283 | // number isn't actually defined by an instruction, weird huh? :) |
| 284 | if (PHIJoin) { |
Lang Hames | 6e2968c | 2010-09-25 12:04:16 +0000 | [diff] [blame] | 285 | assert(getInstructionFromIndex(Start) == 0 && |
| 286 | "PHI def index points at actual instruction."); |
Jakob Stoklund Olesen | 3b1088a | 2012-02-04 05:20:49 +0000 | [diff] [blame] | 287 | ValNo = interval.getNextValue(Start, VNInfoAllocator); |
Jakob Stoklund Olesen | dcfe5f3 | 2010-02-23 22:43:58 +0000 | [diff] [blame] | 288 | } |
| 289 | LiveRange LR(Start, killIdx, ValNo); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 290 | interval.addRange(LR); |
David Greene | 8a34229 | 2010-01-04 22:49:02 +0000 | [diff] [blame] | 291 | DEBUG(dbgs() << " +" << LR); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 292 | } |
| 293 | |
| 294 | } else { |
Evan Cheng | 3749943 | 2010-05-05 18:27:40 +0000 | [diff] [blame] | 295 | if (MultipleDefsBySameMI(*mi, MOIdx)) |
Nick Lewycky | 761fd4c | 2010-05-20 03:30:09 +0000 | [diff] [blame] | 296 | // Multiple defs of the same virtual register by the same instruction. |
| 297 | // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ... |
Evan Cheng | afff40a | 2010-05-04 20:26:52 +0000 | [diff] [blame] | 298 | // This is likely due to elimination of REG_SEQUENCE instructions. Return |
| 299 | // here since there is nothing to do. |
| 300 | return; |
| 301 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 302 | // If this is the second time we see a virtual register definition, it |
| 303 | // must be due to phi elimination or two addr elimination. If this is |
Evan Cheng | bf105c8 | 2006-11-03 03:04:46 +0000 | [diff] [blame] | 304 | // the result of two address elimination, then the vreg is one of the |
| 305 | // def-and-use register operand. |
Evan Cheng | 3749943 | 2010-05-05 18:27:40 +0000 | [diff] [blame] | 306 | |
| 307 | // It may also be partial redef like this: |
Jakob Stoklund Olesen | 1b29320 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 308 | // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0 |
| 309 | // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0 |
Evan Cheng | 3749943 | 2010-05-05 18:27:40 +0000 | [diff] [blame] | 310 | bool PartReDef = isPartialRedef(MIIdx, MO, interval); |
| 311 | if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 312 | // If this is a two-address definition, then we have already processed |
| 313 | // the live range. The only problem is that we didn't realize there |
| 314 | // are actually two values in the live interval. Because of this we |
| 315 | // need to take the LiveRegion that defines this register and split it |
| 316 | // into two values. |
Jakob Stoklund Olesen | d14614e | 2011-11-13 22:05:42 +0000 | [diff] [blame] | 317 | SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 318 | |
Lang Hames | 35f291d | 2009-09-12 03:34:03 +0000 | [diff] [blame] | 319 | const LiveRange *OldLR = |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 320 | interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 321 | VNInfo *OldValNo = OldLR->valno; |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 322 | SlotIndex DefIndex = OldValNo->def.getRegSlot(); |
Evan Cheng | 4f8ff16 | 2007-08-11 00:59:19 +0000 | [diff] [blame] | 323 | |
Jakob Stoklund Olesen | c66d0f2 | 2010-06-16 21:29:40 +0000 | [diff] [blame] | 324 | // Delete the previous value, which should be short and continuous, |
Chris Lattner | be4f88a | 2006-08-22 18:19:46 +0000 | [diff] [blame] | 325 | // because the 2-addr copy must be in the same MBB as the redef. |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 326 | interval.removeRange(DefIndex, RedefIndex); |
Alkis Evlogimenos | 7065157 | 2004-08-04 09:46:56 +0000 | [diff] [blame] | 327 | |
Chris Lattner | 91725b7 | 2006-08-31 05:54:43 +0000 | [diff] [blame] | 328 | // The new value number (#1) is defined by the instruction we claimed |
| 329 | // defined value #0. |
Lang Hames | 6e2968c | 2010-09-25 12:04:16 +0000 | [diff] [blame] | 330 | VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 331 | |
Chris Lattner | 91725b7 | 2006-08-31 05:54:43 +0000 | [diff] [blame] | 332 | // Value#0 is now defined by the 2-addr instruction. |
Jakob Stoklund Olesen | 3b1088a | 2012-02-04 05:20:49 +0000 | [diff] [blame] | 333 | OldValNo->def = RedefIndex; |
Jakob Stoklund Olesen | 1b29320 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 334 | |
Chris Lattner | be4f88a | 2006-08-22 18:19:46 +0000 | [diff] [blame] | 335 | // Add the new live interval which replaces the range for the input copy. |
| 336 | LiveRange LR(DefIndex, RedefIndex, ValNo); |
David Greene | 8a34229 | 2010-01-04 22:49:02 +0000 | [diff] [blame] | 337 | DEBUG(dbgs() << " replace range with " << LR); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 338 | interval.addRange(LR); |
| 339 | |
| 340 | // If this redefinition is dead, we need to add a dummy unit live |
| 341 | // range covering the def slot. |
Owen Anderson | 6b098de | 2008-06-25 23:39:39 +0000 | [diff] [blame] | 342 | if (MO.isDead()) |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 343 | interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(), |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 344 | OldValNo)); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 345 | |
Jakob Stoklund Olesen | b77ec7d | 2012-06-05 22:51:54 +0000 | [diff] [blame] | 346 | DEBUG(dbgs() << " RESULT: " << interval); |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 347 | } else if (LV->isPHIJoin(interval.reg)) { |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 348 | // In the case of PHI elimination, each variable definition is only |
| 349 | // live until the end of the block. We've already taken care of the |
| 350 | // rest of the live range. |
Jakob Stoklund Olesen | dcfe5f3 | 2010-02-23 22:43:58 +0000 | [diff] [blame] | 351 | |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 352 | SlotIndex defIndex = MIIdx.getRegSlot(); |
Evan Cheng | fb11288 | 2009-03-23 08:01:15 +0000 | [diff] [blame] | 353 | if (MO.isEarlyClobber()) |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 354 | defIndex = MIIdx.getRegSlot(true); |
Evan Cheng | 752195e | 2009-09-14 21:33:42 +0000 | [diff] [blame] | 355 | |
Jakob Stoklund Olesen | 3b1088a | 2012-02-04 05:20:49 +0000 | [diff] [blame] | 356 | VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); |
Jakob Stoklund Olesen | 1b29320 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 357 | |
Lang Hames | 74ab5ee | 2009-12-22 00:11:50 +0000 | [diff] [blame] | 358 | SlotIndex killIndex = getMBBEndIdx(mbb); |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 359 | LiveRange LR(defIndex, killIndex, ValNo); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 360 | interval.addRange(LR); |
Jakob Stoklund Olesen | dcfe5f3 | 2010-02-23 22:43:58 +0000 | [diff] [blame] | 361 | DEBUG(dbgs() << " phi-join +" << LR); |
Evan Cheng | 3749943 | 2010-05-05 18:27:40 +0000 | [diff] [blame] | 362 | } else { |
| 363 | llvm_unreachable("Multiply defined register"); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 364 | } |
| 365 | } |
| 366 | |
David Greene | 8a34229 | 2010-01-04 22:49:02 +0000 | [diff] [blame] | 367 | DEBUG(dbgs() << '\n'); |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 368 | } |
| 369 | |
Chris Lattner | f35fef7 | 2004-07-23 21:24:19 +0000 | [diff] [blame] | 370 | void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, |
| 371 | MachineBasicBlock::iterator MI, |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 372 | SlotIndex MIIdx, |
Evan Cheng | ef0732d | 2008-07-10 07:35:43 +0000 | [diff] [blame] | 373 | MachineOperand& MO, |
| 374 | unsigned MOIdx) { |
Owen Anderson | 6b098de | 2008-06-25 23:39:39 +0000 | [diff] [blame] | 375 | if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) |
Evan Cheng | ef0732d | 2008-07-10 07:35:43 +0000 | [diff] [blame] | 376 | handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, |
Owen Anderson | 6b098de | 2008-06-25 23:39:39 +0000 | [diff] [blame] | 377 | getOrCreateInterval(MO.getReg())); |
Evan Cheng | b371f45 | 2007-02-19 21:49:54 +0000 | [diff] [blame] | 378 | } |
| 379 | |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 380 | /// computeIntervals - computes the live intervals for virtual |
Alkis Evlogimenos | 4d46e1e | 2004-01-31 14:37:41 +0000 | [diff] [blame] | 381 | /// registers. for some ordering of the machine instructions [1,N] a |
Alkis Evlogimenos | 08cec00 | 2004-01-31 19:59:32 +0000 | [diff] [blame] | 382 | /// live interval is an interval [i, j) where 1 <= i <= j < N for |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 383 | /// which a variable is live |
Jakob Stoklund Olesen | 1b29320 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 384 | void LiveIntervals::computeIntervals() { |
David Greene | 8a34229 | 2010-01-04 22:49:02 +0000 | [diff] [blame] | 385 | DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" |
David Blaikie | 986d76d | 2012-08-22 17:18:53 +0000 | [diff] [blame] | 386 | << "********** Function: " << MF->getName() << '\n'); |
Evan Cheng | d129d73 | 2009-07-17 19:43:40 +0000 | [diff] [blame] | 387 | |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 388 | RegMaskBlocks.resize(MF->getNumBlockIDs()); |
Jakob Stoklund Olesen | 34e85d0 | 2012-02-10 01:26:29 +0000 | [diff] [blame] | 389 | |
Evan Cheng | d129d73 | 2009-07-17 19:43:40 +0000 | [diff] [blame] | 390 | SmallVector<unsigned, 8> UndefUses; |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 391 | for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end(); |
Chris Lattner | 428b92e | 2006-09-15 03:57:23 +0000 | [diff] [blame] | 392 | MBBI != E; ++MBBI) { |
| 393 | MachineBasicBlock *MBB = MBBI; |
Jakob Stoklund Olesen | 34e85d0 | 2012-02-10 01:26:29 +0000 | [diff] [blame] | 394 | RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size(); |
| 395 | |
Evan Cheng | 00a99a3 | 2010-02-06 09:07:11 +0000 | [diff] [blame] | 396 | if (MBB->empty()) |
| 397 | continue; |
| 398 | |
Owen Anderson | 134eb73 | 2008-09-21 20:43:24 +0000 | [diff] [blame] | 399 | // Track the index of the current machine instr. |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 400 | SlotIndex MIIndex = getMBBStartIdx(MBB); |
Bob Wilson | ad98f79 | 2010-05-03 21:38:11 +0000 | [diff] [blame] | 401 | DEBUG(dbgs() << "BB#" << MBB->getNumber() |
| 402 | << ":\t\t# derived from " << MBB->getName() << "\n"); |
Alkis Evlogimenos | 6b4edba | 2003-12-21 20:19:10 +0000 | [diff] [blame] | 403 | |
Owen Anderson | 99500ae | 2008-09-15 22:00:38 +0000 | [diff] [blame] | 404 | // Skip over empty initial indices. |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 405 | if (getInstructionFromIndex(MIIndex) == 0) |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 406 | MIIndex = Indexes->getNextNonNullIndex(MIIndex); |
Jakob Stoklund Olesen | 1b29320 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 407 | |
Dale Johannesen | 1caedd0 | 2010-01-22 22:38:21 +0000 | [diff] [blame] | 408 | for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); |
| 409 | MI != miEnd; ++MI) { |
David Greene | 8a34229 | 2010-01-04 22:49:02 +0000 | [diff] [blame] | 410 | DEBUG(dbgs() << MIIndex << "\t" << *MI); |
Chris Lattner | 518bb53 | 2010-02-09 19:54:29 +0000 | [diff] [blame] | 411 | if (MI->isDebugValue()) |
Dale Johannesen | 1caedd0 | 2010-01-22 22:38:21 +0000 | [diff] [blame] | 412 | continue; |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 413 | assert(Indexes->getInstructionFromIndex(MIIndex) == MI && |
Jakob Stoklund Olesen | 3fd3a84 | 2012-02-08 17:33:45 +0000 | [diff] [blame] | 414 | "Lost SlotIndex synchronization"); |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 415 | |
Evan Cheng | 438f7bc | 2006-11-10 08:43:01 +0000 | [diff] [blame] | 416 | // Handle defs. |
Chris Lattner | 428b92e | 2006-09-15 03:57:23 +0000 | [diff] [blame] | 417 | for (int i = MI->getNumOperands() - 1; i >= 0; --i) { |
| 418 | MachineOperand &MO = MI->getOperand(i); |
Jakob Stoklund Olesen | 3fd3a84 | 2012-02-08 17:33:45 +0000 | [diff] [blame] | 419 | |
| 420 | // Collect register masks. |
| 421 | if (MO.isRegMask()) { |
| 422 | RegMaskSlots.push_back(MIIndex.getRegSlot()); |
| 423 | RegMaskBits.push_back(MO.getRegMask()); |
| 424 | continue; |
| 425 | } |
| 426 | |
Jakob Stoklund Olesen | 27b7669 | 2012-06-22 18:20:50 +0000 | [diff] [blame] | 427 | if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) |
Evan Cheng | d129d73 | 2009-07-17 19:43:40 +0000 | [diff] [blame] | 428 | continue; |
| 429 | |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 430 | // handle register defs - build intervals |
Evan Cheng | d129d73 | 2009-07-17 19:43:40 +0000 | [diff] [blame] | 431 | if (MO.isDef()) |
Evan Cheng | ef0732d | 2008-07-10 07:35:43 +0000 | [diff] [blame] | 432 | handleRegisterDef(MBB, MI, MIIndex, MO, i); |
Evan Cheng | d129d73 | 2009-07-17 19:43:40 +0000 | [diff] [blame] | 433 | else if (MO.isUndef()) |
| 434 | UndefUses.push_back(MO.getReg()); |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 435 | } |
Jakob Stoklund Olesen | 1b29320 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 436 | |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 437 | // Move to the next instr slot. |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 438 | MIIndex = Indexes->getNextNonNullIndex(MIIndex); |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 439 | } |
Jakob Stoklund Olesen | 34e85d0 | 2012-02-10 01:26:29 +0000 | [diff] [blame] | 440 | |
| 441 | // Compute the number of register mask instructions in this block. |
| 442 | std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()]; |
| 443 | RMB.second = RegMaskSlots.size() - RMB.first;; |
Alkis Evlogimenos | 1a8ea01 | 2004-08-04 09:46:26 +0000 | [diff] [blame] | 444 | } |
Evan Cheng | d129d73 | 2009-07-17 19:43:40 +0000 | [diff] [blame] | 445 | |
| 446 | // Create empty intervals for registers defined by implicit_def's (except |
| 447 | // for those implicit_def that define values which are liveout of their |
| 448 | // blocks. |
| 449 | for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { |
| 450 | unsigned UndefReg = UndefUses[i]; |
| 451 | (void)getOrCreateInterval(UndefReg); |
| 452 | } |
Alkis Evlogimenos | ff0cbe1 | 2003-11-20 03:32:25 +0000 | [diff] [blame] | 453 | } |
Alkis Evlogimenos | b27ef24 | 2003-12-05 10:38:28 +0000 | [diff] [blame] | 454 | |
Owen Anderson | 03857b2 | 2008-08-13 21:49:13 +0000 | [diff] [blame] | 455 | LiveInterval* LiveIntervals::createInterval(unsigned reg) { |
Evan Cheng | 0a1fcce | 2009-02-08 11:04:35 +0000 | [diff] [blame] | 456 | float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; |
Owen Anderson | 03857b2 | 2008-08-13 21:49:13 +0000 | [diff] [blame] | 457 | return new LiveInterval(reg, Weight); |
Alkis Evlogimenos | 9a8b490 | 2004-04-09 18:07:57 +0000 | [diff] [blame] | 458 | } |
Evan Cheng | f2fbca6 | 2007-11-12 06:35:08 +0000 | [diff] [blame] | 459 | |
Jakob Stoklund Olesen | 34c6f98 | 2012-06-05 22:02:15 +0000 | [diff] [blame] | 460 | |
Jakob Stoklund Olesen | 3dfa38a | 2012-07-27 20:58:46 +0000 | [diff] [blame] | 461 | /// computeVirtRegInterval - Compute the live interval of a virtual register, |
| 462 | /// based on defs and uses. |
| 463 | void LiveIntervals::computeVirtRegInterval(LiveInterval *LI) { |
| 464 | assert(LRCalc && "LRCalc not initialized."); |
| 465 | assert(LI->empty() && "Should only compute empty intervals."); |
| 466 | LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); |
| 467 | LRCalc->createDeadDefs(LI); |
| 468 | LRCalc->extendToUses(LI); |
| 469 | } |
| 470 | |
Jakob Stoklund Olesen | c16bf79 | 2012-07-27 21:56:39 +0000 | [diff] [blame] | 471 | void LiveIntervals::computeVirtRegs() { |
| 472 | for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { |
| 473 | unsigned Reg = TargetRegisterInfo::index2VirtReg(i); |
| 474 | if (MRI->reg_nodbg_empty(Reg)) |
| 475 | continue; |
| 476 | LiveInterval *LI = createInterval(Reg); |
| 477 | VirtRegIntervals[Reg] = LI; |
| 478 | computeVirtRegInterval(LI); |
| 479 | } |
| 480 | } |
| 481 | |
| 482 | void LiveIntervals::computeRegMasks() { |
| 483 | RegMaskBlocks.resize(MF->getNumBlockIDs()); |
| 484 | |
| 485 | // Find all instructions with regmask operands. |
| 486 | for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end(); |
| 487 | MBBI != E; ++MBBI) { |
| 488 | MachineBasicBlock *MBB = MBBI; |
| 489 | std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()]; |
| 490 | RMB.first = RegMaskSlots.size(); |
| 491 | for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end(); |
| 492 | MI != ME; ++MI) |
| 493 | for (MIOperands MO(MI); MO.isValid(); ++MO) { |
| 494 | if (!MO->isRegMask()) |
| 495 | continue; |
| 496 | RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot()); |
| 497 | RegMaskBits.push_back(MO->getRegMask()); |
| 498 | } |
| 499 | // Compute the number of register mask instructions in this block. |
| 500 | RMB.second = RegMaskSlots.size() - RMB.first;; |
| 501 | } |
| 502 | } |
Jakob Stoklund Olesen | 3dfa38a | 2012-07-27 20:58:46 +0000 | [diff] [blame] | 503 | |
Jakob Stoklund Olesen | 34c6f98 | 2012-06-05 22:02:15 +0000 | [diff] [blame] | 504 | //===----------------------------------------------------------------------===// |
| 505 | // Register Unit Liveness |
| 506 | //===----------------------------------------------------------------------===// |
| 507 | // |
| 508 | // Fixed interference typically comes from ABI boundaries: Function arguments |
| 509 | // and return values are passed in fixed registers, and so are exception |
| 510 | // pointers entering landing pads. Certain instructions require values to be |
| 511 | // present in specific registers. That is also represented through fixed |
| 512 | // interference. |
| 513 | // |
| 514 | |
| 515 | /// computeRegUnitInterval - Compute the live interval of a register unit, based |
| 516 | /// on the uses and defs of aliasing registers. The interval should be empty, |
| 517 | /// or contain only dead phi-defs from ABI blocks. |
| 518 | void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) { |
| 519 | unsigned Unit = LI->reg; |
| 520 | |
| 521 | assert(LRCalc && "LRCalc not initialized."); |
| 522 | LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); |
| 523 | |
| 524 | // The physregs aliasing Unit are the roots and their super-registers. |
| 525 | // Create all values as dead defs before extending to uses. Note that roots |
| 526 | // may share super-registers. That's OK because createDeadDefs() is |
| 527 | // idempotent. It is very rare for a register unit to have multiple roots, so |
| 528 | // uniquing super-registers is probably not worthwhile. |
| 529 | for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { |
| 530 | unsigned Root = *Roots; |
| 531 | if (!MRI->reg_empty(Root)) |
| 532 | LRCalc->createDeadDefs(LI, Root); |
| 533 | for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) { |
| 534 | if (!MRI->reg_empty(*Supers)) |
| 535 | LRCalc->createDeadDefs(LI, *Supers); |
| 536 | } |
| 537 | } |
| 538 | |
| 539 | // Now extend LI to reach all uses. |
| 540 | // Ignore uses of reserved registers. We only track defs of those. |
| 541 | for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { |
| 542 | unsigned Root = *Roots; |
| 543 | if (!isReserved(Root) && !MRI->reg_empty(Root)) |
| 544 | LRCalc->extendToUses(LI, Root); |
| 545 | for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) { |
| 546 | unsigned Reg = *Supers; |
| 547 | if (!isReserved(Reg) && !MRI->reg_empty(Reg)) |
| 548 | LRCalc->extendToUses(LI, Reg); |
| 549 | } |
| 550 | } |
| 551 | } |
| 552 | |
| 553 | |
| 554 | /// computeLiveInRegUnits - Precompute the live ranges of any register units |
| 555 | /// that are live-in to an ABI block somewhere. Register values can appear |
| 556 | /// without a corresponding def when entering the entry block or a landing pad. |
| 557 | /// |
| 558 | void LiveIntervals::computeLiveInRegUnits() { |
| 559 | RegUnitIntervals.resize(TRI->getNumRegUnits()); |
| 560 | DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); |
| 561 | |
| 562 | // Keep track of the intervals allocated. |
| 563 | SmallVector<LiveInterval*, 8> NewIntvs; |
| 564 | |
| 565 | // Check all basic blocks for live-ins. |
| 566 | for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); |
| 567 | MFI != MFE; ++MFI) { |
| 568 | const MachineBasicBlock *MBB = MFI; |
| 569 | |
| 570 | // We only care about ABI blocks: Entry + landing pads. |
| 571 | if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty()) |
| 572 | continue; |
| 573 | |
| 574 | // Create phi-defs at Begin for all live-in registers. |
| 575 | SlotIndex Begin = Indexes->getMBBStartIdx(MBB); |
| 576 | DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber()); |
| 577 | for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(), |
| 578 | LIE = MBB->livein_end(); LII != LIE; ++LII) { |
| 579 | for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) { |
| 580 | unsigned Unit = *Units; |
| 581 | LiveInterval *Intv = RegUnitIntervals[Unit]; |
| 582 | if (!Intv) { |
| 583 | Intv = RegUnitIntervals[Unit] = new LiveInterval(Unit, HUGE_VALF); |
| 584 | NewIntvs.push_back(Intv); |
| 585 | } |
| 586 | VNInfo *VNI = Intv->createDeadDef(Begin, getVNInfoAllocator()); |
Matt Beaumont-Gay | 05b46f0 | 2012-06-05 23:00:03 +0000 | [diff] [blame] | 587 | (void)VNI; |
Jakob Stoklund Olesen | 34c6f98 | 2012-06-05 22:02:15 +0000 | [diff] [blame] | 588 | DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id); |
| 589 | } |
| 590 | } |
| 591 | DEBUG(dbgs() << '\n'); |
| 592 | } |
| 593 | DEBUG(dbgs() << "Created " << NewIntvs.size() << " new intervals.\n"); |
| 594 | |
| 595 | // Compute the 'normal' part of the intervals. |
| 596 | for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i) |
| 597 | computeRegUnitInterval(NewIntvs[i]); |
| 598 | } |
| 599 | |
| 600 | |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 601 | /// shrinkToUses - After removing some uses of a register, shrink its live |
| 602 | /// range to just the remaining uses. This method does not compute reaching |
| 603 | /// defs for new uses, and it doesn't remove dead defs. |
Jakob Stoklund Olesen | 6a3dbd3 | 2011-03-17 20:37:07 +0000 | [diff] [blame] | 604 | bool LiveIntervals::shrinkToUses(LiveInterval *li, |
Jakob Stoklund Olesen | 0d8ccaa | 2011-03-07 23:29:10 +0000 | [diff] [blame] | 605 | SmallVectorImpl<MachineInstr*> *dead) { |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 606 | DEBUG(dbgs() << "Shrink: " << *li << '\n'); |
| 607 | assert(TargetRegisterInfo::isVirtualRegister(li->reg) |
Lang Hames | 567cdba | 2012-01-03 20:05:57 +0000 | [diff] [blame] | 608 | && "Can only shrink virtual registers"); |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 609 | // Find all the values used, including PHI kills. |
| 610 | SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList; |
| 611 | |
Jakob Stoklund Olesen | 031432f | 2011-09-15 15:24:16 +0000 | [diff] [blame] | 612 | // Blocks that have already been added to WorkList as live-out. |
| 613 | SmallPtrSet<MachineBasicBlock*, 16> LiveOut; |
| 614 | |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 615 | // Visit all instructions reading li->reg. |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 616 | for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(li->reg); |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 617 | MachineInstr *UseMI = I.skipInstruction();) { |
| 618 | if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) |
| 619 | continue; |
Jakob Stoklund Olesen | 6c9cc21 | 2011-11-13 23:53:25 +0000 | [diff] [blame] | 620 | SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); |
Jakob Stoklund Olesen | 97769fc | 2012-05-20 02:54:52 +0000 | [diff] [blame] | 621 | LiveRangeQuery LRQ(*li, Idx); |
| 622 | VNInfo *VNI = LRQ.valueIn(); |
Jakob Stoklund Olesen | 9ef931e | 2011-03-18 03:06:04 +0000 | [diff] [blame] | 623 | if (!VNI) { |
| 624 | // This shouldn't happen: readsVirtualRegister returns true, but there is |
| 625 | // no live value. It is likely caused by a target getting <undef> flags |
| 626 | // wrong. |
| 627 | DEBUG(dbgs() << Idx << '\t' << *UseMI |
| 628 | << "Warning: Instr claims to read non-existent value in " |
| 629 | << *li << '\n'); |
| 630 | continue; |
| 631 | } |
Jakob Stoklund Olesen | f054e19 | 2011-11-14 18:45:38 +0000 | [diff] [blame] | 632 | // Special case: An early-clobber tied operand reads and writes the |
Jakob Stoklund Olesen | 97769fc | 2012-05-20 02:54:52 +0000 | [diff] [blame] | 633 | // register one slot early. |
| 634 | if (VNInfo *DefVNI = LRQ.valueDefined()) |
| 635 | Idx = DefVNI->def; |
| 636 | |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 637 | WorkList.push_back(std::make_pair(Idx, VNI)); |
| 638 | } |
| 639 | |
| 640 | // Create a new live interval with only minimal live segments per def. |
| 641 | LiveInterval NewLI(li->reg, 0); |
| 642 | for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); |
| 643 | I != E; ++I) { |
| 644 | VNInfo *VNI = *I; |
| 645 | if (VNI->isUnused()) |
| 646 | continue; |
Jakob Stoklund Olesen | 1f81e31 | 2011-11-13 22:42:13 +0000 | [diff] [blame] | 647 | NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI)); |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 648 | } |
| 649 | |
Jakob Stoklund Olesen | e0ab245 | 2011-03-02 00:33:03 +0000 | [diff] [blame] | 650 | // Keep track of the PHIs that are in use. |
| 651 | SmallPtrSet<VNInfo*, 8> UsedPHIs; |
| 652 | |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 653 | // Extend intervals to reach all uses in WorkList. |
| 654 | while (!WorkList.empty()) { |
| 655 | SlotIndex Idx = WorkList.back().first; |
| 656 | VNInfo *VNI = WorkList.back().second; |
| 657 | WorkList.pop_back(); |
Jakob Stoklund Olesen | 6c9cc21 | 2011-11-13 23:53:25 +0000 | [diff] [blame] | 658 | const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot()); |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 659 | SlotIndex BlockStart = getMBBStartIdx(MBB); |
Jakob Stoklund Olesen | e0ab245 | 2011-03-02 00:33:03 +0000 | [diff] [blame] | 660 | |
| 661 | // Extend the live range for VNI to be live at Idx. |
Jakob Stoklund Olesen | 6c9cc21 | 2011-11-13 23:53:25 +0000 | [diff] [blame] | 662 | if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) { |
Nick Lewycky | 4b11a70 | 2011-03-02 01:43:30 +0000 | [diff] [blame] | 663 | (void)ExtVNI; |
Jakob Stoklund Olesen | e0ab245 | 2011-03-02 00:33:03 +0000 | [diff] [blame] | 664 | assert(ExtVNI == VNI && "Unexpected existing value number"); |
| 665 | // Is this a PHIDef we haven't seen before? |
Jakob Stoklund Olesen | c29d9b3 | 2011-03-03 00:20:51 +0000 | [diff] [blame] | 666 | if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) |
Jakob Stoklund Olesen | e0ab245 | 2011-03-02 00:33:03 +0000 | [diff] [blame] | 667 | continue; |
| 668 | // The PHI is live, make sure the predecessors are live-out. |
| 669 | for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), |
| 670 | PE = MBB->pred_end(); PI != PE; ++PI) { |
Jakob Stoklund Olesen | 031432f | 2011-09-15 15:24:16 +0000 | [diff] [blame] | 671 | if (!LiveOut.insert(*PI)) |
| 672 | continue; |
Jakob Stoklund Olesen | 6c9cc21 | 2011-11-13 23:53:25 +0000 | [diff] [blame] | 673 | SlotIndex Stop = getMBBEndIdx(*PI); |
Jakob Stoklund Olesen | e0ab245 | 2011-03-02 00:33:03 +0000 | [diff] [blame] | 674 | // A predecessor is not required to have a live-out value for a PHI. |
Jakob Stoklund Olesen | 6c9cc21 | 2011-11-13 23:53:25 +0000 | [diff] [blame] | 675 | if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) |
Jakob Stoklund Olesen | e0ab245 | 2011-03-02 00:33:03 +0000 | [diff] [blame] | 676 | WorkList.push_back(std::make_pair(Stop, PVNI)); |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 677 | } |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 678 | continue; |
| 679 | } |
| 680 | |
| 681 | // VNI is live-in to MBB. |
| 682 | DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); |
Jakob Stoklund Olesen | 6c9cc21 | 2011-11-13 23:53:25 +0000 | [diff] [blame] | 683 | NewLI.addRange(LiveRange(BlockStart, Idx, VNI)); |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 684 | |
| 685 | // Make sure VNI is live-out from the predecessors. |
| 686 | for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), |
| 687 | PE = MBB->pred_end(); PI != PE; ++PI) { |
Jakob Stoklund Olesen | 031432f | 2011-09-15 15:24:16 +0000 | [diff] [blame] | 688 | if (!LiveOut.insert(*PI)) |
| 689 | continue; |
Jakob Stoklund Olesen | 6c9cc21 | 2011-11-13 23:53:25 +0000 | [diff] [blame] | 690 | SlotIndex Stop = getMBBEndIdx(*PI); |
| 691 | assert(li->getVNInfoBefore(Stop) == VNI && |
| 692 | "Wrong value out of predecessor"); |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 693 | WorkList.push_back(std::make_pair(Stop, VNI)); |
| 694 | } |
| 695 | } |
| 696 | |
| 697 | // Handle dead values. |
Jakob Stoklund Olesen | 6a3dbd3 | 2011-03-17 20:37:07 +0000 | [diff] [blame] | 698 | bool CanSeparate = false; |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 699 | for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); |
| 700 | I != E; ++I) { |
| 701 | VNInfo *VNI = *I; |
| 702 | if (VNI->isUnused()) |
| 703 | continue; |
| 704 | LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def); |
| 705 | assert(LII != NewLI.end() && "Missing live range for PHI"); |
Jakob Stoklund Olesen | 1f81e31 | 2011-11-13 22:42:13 +0000 | [diff] [blame] | 706 | if (LII->end != VNI->def.getDeadSlot()) |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 707 | continue; |
Jakob Stoklund Olesen | a4d3473 | 2011-03-02 00:33:01 +0000 | [diff] [blame] | 708 | if (VNI->isPHIDef()) { |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 709 | // This is a dead PHI. Remove it. |
Jakob Stoklund Olesen | b2beac2 | 2012-08-03 20:59:32 +0000 | [diff] [blame] | 710 | VNI->markUnused(); |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 711 | NewLI.removeRange(*LII); |
Jakob Stoklund Olesen | 6a3dbd3 | 2011-03-17 20:37:07 +0000 | [diff] [blame] | 712 | DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); |
| 713 | CanSeparate = true; |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 714 | } else { |
| 715 | // This is a dead def. Make sure the instruction knows. |
| 716 | MachineInstr *MI = getInstructionFromIndex(VNI->def); |
| 717 | assert(MI && "No instruction defining live value"); |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 718 | MI->addRegisterDead(li->reg, TRI); |
Jakob Stoklund Olesen | 0d8ccaa | 2011-03-07 23:29:10 +0000 | [diff] [blame] | 719 | if (dead && MI->allDefsAreDead()) { |
Jakob Stoklund Olesen | c46570d | 2011-03-16 22:56:08 +0000 | [diff] [blame] | 720 | DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); |
Jakob Stoklund Olesen | 0d8ccaa | 2011-03-07 23:29:10 +0000 | [diff] [blame] | 721 | dead->push_back(MI); |
| 722 | } |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 723 | } |
| 724 | } |
| 725 | |
| 726 | // Move the trimmed ranges back. |
| 727 | li->ranges.swap(NewLI.ranges); |
Jakob Stoklund Olesen | c46570d | 2011-03-16 22:56:08 +0000 | [diff] [blame] | 728 | DEBUG(dbgs() << "Shrunk: " << *li << '\n'); |
Jakob Stoklund Olesen | 6a3dbd3 | 2011-03-17 20:37:07 +0000 | [diff] [blame] | 729 | return CanSeparate; |
Jakob Stoklund Olesen | 11513e5 | 2011-02-08 00:03:05 +0000 | [diff] [blame] | 730 | } |
| 731 | |
| 732 | |
Evan Cheng | f2fbca6 | 2007-11-12 06:35:08 +0000 | [diff] [blame] | 733 | //===----------------------------------------------------------------------===// |
| 734 | // Register allocator hooks. |
| 735 | // |
| 736 | |
Jakob Stoklund Olesen | e617ccb | 2012-09-06 18:15:18 +0000 | [diff] [blame] | 737 | void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { |
| 738 | // Keep track of regunit ranges. |
| 739 | SmallVector<std::pair<LiveInterval*, LiveInterval::iterator>, 8> RU; |
| 740 | |
Jakob Stoklund Olesen | 12a7be9 | 2012-06-20 23:23:59 +0000 | [diff] [blame] | 741 | for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { |
| 742 | unsigned Reg = TargetRegisterInfo::index2VirtReg(i); |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 743 | if (MRI->reg_nodbg_empty(Reg)) |
Jakob Stoklund Olesen | 8a61da8 | 2011-02-08 21:13:03 +0000 | [diff] [blame] | 744 | continue; |
Jakob Stoklund Olesen | 12a7be9 | 2012-06-20 23:23:59 +0000 | [diff] [blame] | 745 | LiveInterval *LI = &getInterval(Reg); |
Jakob Stoklund Olesen | e617ccb | 2012-09-06 18:15:18 +0000 | [diff] [blame] | 746 | if (LI->empty()) |
| 747 | continue; |
| 748 | |
| 749 | // Find the regunit intervals for the assigned register. They may overlap |
| 750 | // the virtual register live range, cancelling any kills. |
| 751 | RU.clear(); |
| 752 | for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid(); |
| 753 | ++Units) { |
| 754 | LiveInterval *RUInt = &getRegUnit(*Units); |
| 755 | if (RUInt->empty()) |
| 756 | continue; |
| 757 | RU.push_back(std::make_pair(RUInt, RUInt->find(LI->begin()->end))); |
| 758 | } |
Jakob Stoklund Olesen | 8a61da8 | 2011-02-08 21:13:03 +0000 | [diff] [blame] | 759 | |
| 760 | // Every instruction that kills Reg corresponds to a live range end point. |
| 761 | for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; |
| 762 | ++RI) { |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 763 | // A block index indicates an MBB edge. |
| 764 | if (RI->end.isBlock()) |
Jakob Stoklund Olesen | 8a61da8 | 2011-02-08 21:13:03 +0000 | [diff] [blame] | 765 | continue; |
| 766 | MachineInstr *MI = getInstructionFromIndex(RI->end); |
| 767 | if (!MI) |
| 768 | continue; |
Jakob Stoklund Olesen | e617ccb | 2012-09-06 18:15:18 +0000 | [diff] [blame] | 769 | |
| 770 | // Check if any of the reguints are live beyond the end of RI. That could |
| 771 | // happen when a physreg is defined as a copy of a virtreg: |
| 772 | // |
| 773 | // %EAX = COPY %vreg5 |
| 774 | // FOO %vreg5 <--- MI, cancel kill because %EAX is live. |
| 775 | // BAR %EAX<kill> |
| 776 | // |
| 777 | // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX. |
| 778 | bool CancelKill = false; |
| 779 | for (unsigned u = 0, e = RU.size(); u != e; ++u) { |
| 780 | LiveInterval *RInt = RU[u].first; |
| 781 | LiveInterval::iterator &I = RU[u].second; |
| 782 | if (I == RInt->end()) |
| 783 | continue; |
| 784 | I = RInt->advanceTo(I, RI->end); |
| 785 | if (I == RInt->end() || I->start >= RI->end) |
| 786 | continue; |
| 787 | // I is overlapping RI. |
| 788 | CancelKill = true; |
| 789 | break; |
| 790 | } |
| 791 | if (CancelKill) |
| 792 | MI->clearRegisterKills(Reg, NULL); |
| 793 | else |
| 794 | MI->addRegisterKilled(Reg, NULL); |
Jakob Stoklund Olesen | 8a61da8 | 2011-02-08 21:13:03 +0000 | [diff] [blame] | 795 | } |
| 796 | } |
| 797 | } |
| 798 | |
Jakob Stoklund Olesen | ebf2750 | 2012-02-10 01:23:55 +0000 | [diff] [blame] | 799 | MachineBasicBlock* |
| 800 | LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { |
| 801 | // A local live range must be fully contained inside the block, meaning it is |
| 802 | // defined and killed at instructions, not at block boundaries. It is not |
| 803 | // live in or or out of any block. |
| 804 | // |
| 805 | // It is technically possible to have a PHI-defined live range identical to a |
| 806 | // single block, but we are going to return false in that case. |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 807 | |
Jakob Stoklund Olesen | ebf2750 | 2012-02-10 01:23:55 +0000 | [diff] [blame] | 808 | SlotIndex Start = LI.beginIndex(); |
| 809 | if (Start.isBlock()) |
| 810 | return NULL; |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 811 | |
Jakob Stoklund Olesen | ebf2750 | 2012-02-10 01:23:55 +0000 | [diff] [blame] | 812 | SlotIndex Stop = LI.endIndex(); |
| 813 | if (Stop.isBlock()) |
| 814 | return NULL; |
Lang Hames | 233a60e | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 815 | |
Jakob Stoklund Olesen | ebf2750 | 2012-02-10 01:23:55 +0000 | [diff] [blame] | 816 | // getMBBFromIndex doesn't need to search the MBB table when both indexes |
| 817 | // belong to proper instructions. |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 818 | MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); |
| 819 | MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); |
Jakob Stoklund Olesen | ebf2750 | 2012-02-10 01:23:55 +0000 | [diff] [blame] | 820 | return MBB1 == MBB2 ? MBB1 : NULL; |
Evan Cheng | 81a0382 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 821 | } |
| 822 | |
Jakob Stoklund Olesen | 0ab7103 | 2012-08-03 20:10:24 +0000 | [diff] [blame] | 823 | bool |
| 824 | LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { |
| 825 | for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); |
| 826 | I != E; ++I) { |
| 827 | const VNInfo *PHI = *I; |
| 828 | if (PHI->isUnused() || !PHI->isPHIDef()) |
| 829 | continue; |
| 830 | const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); |
| 831 | // Conservatively return true instead of scanning huge predecessor lists. |
| 832 | if (PHIMBB->pred_size() > 100) |
| 833 | return true; |
| 834 | for (MachineBasicBlock::const_pred_iterator |
| 835 | PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI) |
| 836 | if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI))) |
| 837 | return true; |
| 838 | } |
| 839 | return false; |
| 840 | } |
| 841 | |
Jakob Stoklund Olesen | e5d9041 | 2010-03-01 20:59:38 +0000 | [diff] [blame] | 842 | float |
| 843 | LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { |
| 844 | // Limit the loop depth ridiculousness. |
| 845 | if (loopDepth > 200) |
| 846 | loopDepth = 200; |
| 847 | |
| 848 | // The loop depth is used to roughly estimate the number of times the |
| 849 | // instruction is executed. Something like 10^d is simple, but will quickly |
| 850 | // overflow a float. This expression behaves like 10^d for small d, but is |
| 851 | // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of |
| 852 | // headroom before overflow. |
NAKAMURA Takumi | dc5198b | 2011-03-31 12:11:33 +0000 | [diff] [blame] | 853 | // By the way, powf() might be unavailable here. For consistency, |
| 854 | // We may take pow(double,double). |
| 855 | float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth); |
Jakob Stoklund Olesen | e5d9041 | 2010-03-01 20:59:38 +0000 | [diff] [blame] | 856 | |
| 857 | return (isDef + isUse) * lc; |
| 858 | } |
| 859 | |
Owen Anderson | c4dc132 | 2008-06-05 17:15:43 +0000 | [diff] [blame] | 860 | LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, |
Lang Hames | ffd1326 | 2009-07-09 03:57:02 +0000 | [diff] [blame] | 861 | MachineInstr* startInst) { |
Owen Anderson | c4dc132 | 2008-06-05 17:15:43 +0000 | [diff] [blame] | 862 | LiveInterval& Interval = getOrCreateInterval(reg); |
| 863 | VNInfo* VN = Interval.getNextValue( |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 864 | SlotIndex(getInstructionIndex(startInst).getRegSlot()), |
Jakob Stoklund Olesen | 3b1088a | 2012-02-04 05:20:49 +0000 | [diff] [blame] | 865 | getVNInfoAllocator()); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 866 | LiveRange LR( |
Jakob Stoklund Olesen | 2debd48 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 867 | SlotIndex(getInstructionIndex(startInst).getRegSlot()), |
Lang Hames | 74ab5ee | 2009-12-22 00:11:50 +0000 | [diff] [blame] | 868 | getMBBEndIdx(startInst->getParent()), VN); |
Owen Anderson | c4dc132 | 2008-06-05 17:15:43 +0000 | [diff] [blame] | 869 | Interval.addRange(LR); |
Jakob Stoklund Olesen | 1b29320 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 870 | |
Owen Anderson | c4dc132 | 2008-06-05 17:15:43 +0000 | [diff] [blame] | 871 | return LR; |
| 872 | } |
Jakob Stoklund Olesen | 3fd3a84 | 2012-02-08 17:33:45 +0000 | [diff] [blame] | 873 | |
| 874 | |
| 875 | //===----------------------------------------------------------------------===// |
| 876 | // Register mask functions |
| 877 | //===----------------------------------------------------------------------===// |
| 878 | |
| 879 | bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, |
| 880 | BitVector &UsableRegs) { |
| 881 | if (LI.empty()) |
| 882 | return false; |
Jakob Stoklund Olesen | 9f10ac6 | 2012-02-10 01:31:31 +0000 | [diff] [blame] | 883 | LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); |
| 884 | |
| 885 | // Use a smaller arrays for local live ranges. |
| 886 | ArrayRef<SlotIndex> Slots; |
| 887 | ArrayRef<const uint32_t*> Bits; |
| 888 | if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { |
| 889 | Slots = getRegMaskSlotsInBlock(MBB->getNumber()); |
| 890 | Bits = getRegMaskBitsInBlock(MBB->getNumber()); |
| 891 | } else { |
| 892 | Slots = getRegMaskSlots(); |
| 893 | Bits = getRegMaskBits(); |
| 894 | } |
Jakob Stoklund Olesen | 3fd3a84 | 2012-02-08 17:33:45 +0000 | [diff] [blame] | 895 | |
| 896 | // We are going to enumerate all the register mask slots contained in LI. |
| 897 | // Start with a binary search of RegMaskSlots to find a starting point. |
Jakob Stoklund Olesen | 3fd3a84 | 2012-02-08 17:33:45 +0000 | [diff] [blame] | 898 | ArrayRef<SlotIndex>::iterator SlotI = |
| 899 | std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); |
| 900 | ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); |
| 901 | |
| 902 | // No slots in range, LI begins after the last call. |
| 903 | if (SlotI == SlotE) |
| 904 | return false; |
| 905 | |
| 906 | bool Found = false; |
| 907 | for (;;) { |
| 908 | assert(*SlotI >= LiveI->start); |
| 909 | // Loop over all slots overlapping this segment. |
| 910 | while (*SlotI < LiveI->end) { |
| 911 | // *SlotI overlaps LI. Collect mask bits. |
| 912 | if (!Found) { |
| 913 | // This is the first overlap. Initialize UsableRegs to all ones. |
| 914 | UsableRegs.clear(); |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 915 | UsableRegs.resize(TRI->getNumRegs(), true); |
Jakob Stoklund Olesen | 3fd3a84 | 2012-02-08 17:33:45 +0000 | [diff] [blame] | 916 | Found = true; |
| 917 | } |
| 918 | // Remove usable registers clobbered by this mask. |
Jakob Stoklund Olesen | 9f10ac6 | 2012-02-10 01:31:31 +0000 | [diff] [blame] | 919 | UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); |
Jakob Stoklund Olesen | 3fd3a84 | 2012-02-08 17:33:45 +0000 | [diff] [blame] | 920 | if (++SlotI == SlotE) |
| 921 | return Found; |
| 922 | } |
| 923 | // *SlotI is beyond the current LI segment. |
| 924 | LiveI = LI.advanceTo(LiveI, *SlotI); |
| 925 | if (LiveI == LiveE) |
| 926 | return Found; |
| 927 | // Advance SlotI until it overlaps. |
| 928 | while (*SlotI < LiveI->start) |
| 929 | if (++SlotI == SlotE) |
| 930 | return Found; |
| 931 | } |
| 932 | } |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 933 | |
| 934 | //===----------------------------------------------------------------------===// |
| 935 | // IntervalUpdate class. |
| 936 | //===----------------------------------------------------------------------===// |
| 937 | |
Lang Hames | fd6d321 | 2012-02-21 00:00:36 +0000 | [diff] [blame] | 938 | // HMEditor is a toolkit used by handleMove to trim or extend live intervals. |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 939 | class LiveIntervals::HMEditor { |
| 940 | private: |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 941 | LiveIntervals& LIS; |
| 942 | const MachineRegisterInfo& MRI; |
| 943 | const TargetRegisterInfo& TRI; |
| 944 | SlotIndex NewIdx; |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 945 | |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 946 | typedef std::pair<LiveInterval*, LiveRange*> IntRangePair; |
| 947 | typedef DenseSet<IntRangePair> RangeSet; |
| 948 | |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 949 | struct RegRanges { |
| 950 | LiveRange* Use; |
| 951 | LiveRange* EC; |
| 952 | LiveRange* Dead; |
| 953 | LiveRange* Def; |
| 954 | RegRanges() : Use(0), EC(0), Dead(0), Def(0) {} |
| 955 | }; |
| 956 | typedef DenseMap<unsigned, RegRanges> BundleRanges; |
| 957 | |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 958 | public: |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 959 | HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, |
| 960 | const TargetRegisterInfo& TRI, SlotIndex NewIdx) |
| 961 | : LIS(LIS), MRI(MRI), TRI(TRI), NewIdx(NewIdx) {} |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 962 | |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 963 | // Update intervals for all operands of MI from OldIdx to NewIdx. |
| 964 | // This assumes that MI used to be at OldIdx, and now resides at |
| 965 | // NewIdx. |
Lang Hames | 4586d25 | 2012-02-21 22:29:38 +0000 | [diff] [blame] | 966 | void moveAllRangesFrom(MachineInstr* MI, SlotIndex OldIdx) { |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 967 | assert(NewIdx != OldIdx && "No-op move? That's a bit strange."); |
| 968 | |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 969 | // Collect the operands. |
| 970 | RangeSet Entering, Internal, Exiting; |
Lang Hames | ac02714 | 2012-02-19 03:09:55 +0000 | [diff] [blame] | 971 | bool hasRegMaskOp = false; |
| 972 | collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx); |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 973 | |
Andrew Trick | f70af52 | 2012-03-21 04:12:16 +0000 | [diff] [blame] | 974 | // To keep the LiveRanges valid within an interval, move the ranges closest |
| 975 | // to the destination first. This prevents ranges from overlapping, to that |
| 976 | // APIs like removeRange still work. |
| 977 | if (NewIdx < OldIdx) { |
| 978 | moveAllEnteringFrom(OldIdx, Entering); |
| 979 | moveAllInternalFrom(OldIdx, Internal); |
| 980 | moveAllExitingFrom(OldIdx, Exiting); |
| 981 | } |
| 982 | else { |
| 983 | moveAllExitingFrom(OldIdx, Exiting); |
| 984 | moveAllInternalFrom(OldIdx, Internal); |
| 985 | moveAllEnteringFrom(OldIdx, Entering); |
| 986 | } |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 987 | |
Lang Hames | ac02714 | 2012-02-19 03:09:55 +0000 | [diff] [blame] | 988 | if (hasRegMaskOp) |
| 989 | updateRegMaskSlots(OldIdx); |
| 990 | |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 991 | #ifndef NDEBUG |
| 992 | LIValidator validator; |
Pete Cooper | 722b6f1 | 2012-04-18 20:29:17 +0000 | [diff] [blame] | 993 | validator = std::for_each(Entering.begin(), Entering.end(), validator); |
| 994 | validator = std::for_each(Internal.begin(), Internal.end(), validator); |
| 995 | validator = std::for_each(Exiting.begin(), Exiting.end(), validator); |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 996 | assert(validator.rangesOk() && "moveAllOperandsFrom broke liveness."); |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 997 | #endif |
| 998 | |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 999 | } |
| 1000 | |
Lang Hames | 4586d25 | 2012-02-21 22:29:38 +0000 | [diff] [blame] | 1001 | // Update intervals for all operands of MI to refer to BundleStart's |
| 1002 | // SlotIndex. |
| 1003 | void moveAllRangesInto(MachineInstr* MI, MachineInstr* BundleStart) { |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1004 | if (MI == BundleStart) |
| 1005 | return; // Bundling instr with itself - nothing to do. |
| 1006 | |
Lang Hames | fd6d321 | 2012-02-21 00:00:36 +0000 | [diff] [blame] | 1007 | SlotIndex OldIdx = LIS.getSlotIndexes()->getInstructionIndex(MI); |
| 1008 | assert(LIS.getSlotIndexes()->getInstructionFromIndex(OldIdx) == MI && |
| 1009 | "SlotIndex <-> Instruction mapping broken for MI"); |
| 1010 | |
Lang Hames | 4586d25 | 2012-02-21 22:29:38 +0000 | [diff] [blame] | 1011 | // Collect all ranges already in the bundle. |
| 1012 | MachineBasicBlock::instr_iterator BII(BundleStart); |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1013 | RangeSet Entering, Internal, Exiting; |
| 1014 | bool hasRegMaskOp = false; |
Lang Hames | 4586d25 | 2012-02-21 22:29:38 +0000 | [diff] [blame] | 1015 | collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx); |
| 1016 | assert(!hasRegMaskOp && "Can't have RegMask operand in bundle."); |
| 1017 | for (++BII; &*BII == MI || BII->isInsideBundle(); ++BII) { |
| 1018 | if (&*BII == MI) |
| 1019 | continue; |
| 1020 | collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx); |
| 1021 | assert(!hasRegMaskOp && "Can't have RegMask operand in bundle."); |
| 1022 | } |
| 1023 | |
| 1024 | BundleRanges BR = createBundleRanges(Entering, Internal, Exiting); |
| 1025 | |
Lang Hames | f905f69 | 2012-05-29 18:19:54 +0000 | [diff] [blame] | 1026 | Entering.clear(); |
| 1027 | Internal.clear(); |
| 1028 | Exiting.clear(); |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1029 | collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx); |
Lang Hames | 4586d25 | 2012-02-21 22:29:38 +0000 | [diff] [blame] | 1030 | assert(!hasRegMaskOp && "Can't have RegMask operand in bundle."); |
| 1031 | |
| 1032 | DEBUG(dbgs() << "Entering: " << Entering.size() << "\n"); |
| 1033 | DEBUG(dbgs() << "Internal: " << Internal.size() << "\n"); |
| 1034 | DEBUG(dbgs() << "Exiting: " << Exiting.size() << "\n"); |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1035 | |
| 1036 | moveAllEnteringFromInto(OldIdx, Entering, BR); |
| 1037 | moveAllInternalFromInto(OldIdx, Internal, BR); |
| 1038 | moveAllExitingFromInto(OldIdx, Exiting, BR); |
| 1039 | |
Lang Hames | 4586d25 | 2012-02-21 22:29:38 +0000 | [diff] [blame] | 1040 | |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1041 | #ifndef NDEBUG |
| 1042 | LIValidator validator; |
Pete Cooper | 722b6f1 | 2012-04-18 20:29:17 +0000 | [diff] [blame] | 1043 | validator = std::for_each(Entering.begin(), Entering.end(), validator); |
| 1044 | validator = std::for_each(Internal.begin(), Internal.end(), validator); |
| 1045 | validator = std::for_each(Exiting.begin(), Exiting.end(), validator); |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1046 | assert(validator.rangesOk() && "moveAllOperandsInto broke liveness."); |
| 1047 | #endif |
| 1048 | } |
| 1049 | |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 1050 | private: |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1051 | |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 1052 | #ifndef NDEBUG |
| 1053 | class LIValidator { |
| 1054 | private: |
| 1055 | DenseSet<const LiveInterval*> Checked, Bogus; |
| 1056 | public: |
| 1057 | void operator()(const IntRangePair& P) { |
| 1058 | const LiveInterval* LI = P.first; |
| 1059 | if (Checked.count(LI)) |
| 1060 | return; |
| 1061 | Checked.insert(LI); |
| 1062 | if (LI->empty()) |
| 1063 | return; |
| 1064 | SlotIndex LastEnd = LI->begin()->start; |
| 1065 | for (LiveInterval::const_iterator LRI = LI->begin(), LRE = LI->end(); |
| 1066 | LRI != LRE; ++LRI) { |
| 1067 | const LiveRange& LR = *LRI; |
| 1068 | if (LastEnd > LR.start || LR.start >= LR.end) |
| 1069 | Bogus.insert(LI); |
| 1070 | LastEnd = LR.end; |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1071 | } |
| 1072 | } |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1073 | |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 1074 | bool rangesOk() const { |
| 1075 | return Bogus.empty(); |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1076 | } |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 1077 | }; |
| 1078 | #endif |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1079 | |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 1080 | // Collect IntRangePairs for all operands of MI that may need fixing. |
| 1081 | // Treat's MI's index as OldIdx (regardless of what it is in SlotIndexes' |
| 1082 | // maps). |
| 1083 | void collectRanges(MachineInstr* MI, RangeSet& Entering, RangeSet& Internal, |
Lang Hames | ac02714 | 2012-02-19 03:09:55 +0000 | [diff] [blame] | 1084 | RangeSet& Exiting, bool& hasRegMaskOp, SlotIndex OldIdx) { |
| 1085 | hasRegMaskOp = false; |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1086 | for (MachineInstr::mop_iterator MOI = MI->operands_begin(), |
| 1087 | MOE = MI->operands_end(); |
| 1088 | MOI != MOE; ++MOI) { |
| 1089 | const MachineOperand& MO = *MOI; |
Lang Hames | ac02714 | 2012-02-19 03:09:55 +0000 | [diff] [blame] | 1090 | |
| 1091 | if (MO.isRegMask()) { |
| 1092 | hasRegMaskOp = true; |
| 1093 | continue; |
| 1094 | } |
| 1095 | |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1096 | if (!MO.isReg() || MO.getReg() == 0) |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1097 | continue; |
| 1098 | |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1099 | unsigned Reg = MO.getReg(); |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1100 | |
| 1101 | // TODO: Currently we're skipping uses that are reserved or have no |
| 1102 | // interval, but we're not updating their kills. This should be |
| 1103 | // fixed. |
Jakob Stoklund Olesen | bf833f0 | 2012-06-19 23:50:18 +0000 | [diff] [blame] | 1104 | if (TargetRegisterInfo::isPhysicalRegister(Reg) && LIS.isReserved(Reg)) |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1105 | continue; |
| 1106 | |
Jakob Stoklund Olesen | 7824152 | 2012-06-20 18:00:57 +0000 | [diff] [blame] | 1107 | // Collect ranges for register units. These live ranges are computed on |
| 1108 | // demand, so just skip any that haven't been computed yet. |
Jakob Stoklund Olesen | e024874 | 2012-06-22 18:38:57 +0000 | [diff] [blame] | 1109 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) { |
Jakob Stoklund Olesen | 7824152 | 2012-06-20 18:00:57 +0000 | [diff] [blame] | 1110 | for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) |
| 1111 | if (LiveInterval *LI = LIS.getCachedRegUnit(*Units)) |
| 1112 | collectRanges(MO, LI, Entering, Internal, Exiting, OldIdx); |
Jakob Stoklund Olesen | e024874 | 2012-06-22 18:38:57 +0000 | [diff] [blame] | 1113 | } else { |
| 1114 | // Collect ranges for individual virtual registers. |
Jakob Stoklund Olesen | bf833f0 | 2012-06-19 23:50:18 +0000 | [diff] [blame] | 1115 | collectRanges(MO, &LIS.getInterval(Reg), |
| 1116 | Entering, Internal, Exiting, OldIdx); |
Jakob Stoklund Olesen | e024874 | 2012-06-22 18:38:57 +0000 | [diff] [blame] | 1117 | } |
Jakob Stoklund Olesen | bf833f0 | 2012-06-19 23:50:18 +0000 | [diff] [blame] | 1118 | } |
| 1119 | } |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 1120 | |
Jakob Stoklund Olesen | bf833f0 | 2012-06-19 23:50:18 +0000 | [diff] [blame] | 1121 | void collectRanges(const MachineOperand &MO, LiveInterval *LI, |
| 1122 | RangeSet &Entering, RangeSet &Internal, RangeSet &Exiting, |
| 1123 | SlotIndex OldIdx) { |
| 1124 | if (MO.readsReg()) { |
| 1125 | LiveRange* LR = LI->getLiveRangeContaining(OldIdx); |
| 1126 | if (LR != 0) |
| 1127 | Entering.insert(std::make_pair(LI, LR)); |
| 1128 | } |
| 1129 | if (MO.isDef()) { |
| 1130 | LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot()); |
| 1131 | assert(LR != 0 && "No live range for def?"); |
| 1132 | if (LR->end > OldIdx.getDeadSlot()) |
| 1133 | Exiting.insert(std::make_pair(LI, LR)); |
| 1134 | else |
| 1135 | Internal.insert(std::make_pair(LI, LR)); |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1136 | } |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1137 | } |
| 1138 | |
Jakob Stoklund Olesen | fa8becb | 2012-06-19 22:50:53 +0000 | [diff] [blame] | 1139 | BundleRanges createBundleRanges(RangeSet& Entering, |
| 1140 | RangeSet& Internal, |
| 1141 | RangeSet& Exiting) { |
Lang Hames | 4586d25 | 2012-02-21 22:29:38 +0000 | [diff] [blame] | 1142 | BundleRanges BR; |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1143 | |
| 1144 | for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); |
Lang Hames | fd6d321 | 2012-02-21 00:00:36 +0000 | [diff] [blame] | 1145 | EI != EE; ++EI) { |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1146 | LiveInterval* LI = EI->first; |
| 1147 | LiveRange* LR = EI->second; |
| 1148 | BR[LI->reg].Use = LR; |
| 1149 | } |
| 1150 | |
| 1151 | for (RangeSet::iterator II = Internal.begin(), IE = Internal.end(); |
Lang Hames | fd6d321 | 2012-02-21 00:00:36 +0000 | [diff] [blame] | 1152 | II != IE; ++II) { |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1153 | LiveInterval* LI = II->first; |
| 1154 | LiveRange* LR = II->second; |
| 1155 | if (LR->end.isDead()) { |
| 1156 | BR[LI->reg].Dead = LR; |
| 1157 | } else { |
| 1158 | BR[LI->reg].EC = LR; |
| 1159 | } |
| 1160 | } |
| 1161 | |
| 1162 | for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end(); |
Lang Hames | fd6d321 | 2012-02-21 00:00:36 +0000 | [diff] [blame] | 1163 | EI != EE; ++EI) { |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1164 | LiveInterval* LI = EI->first; |
| 1165 | LiveRange* LR = EI->second; |
| 1166 | BR[LI->reg].Def = LR; |
| 1167 | } |
| 1168 | |
| 1169 | return BR; |
| 1170 | } |
| 1171 | |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1172 | void moveKillFlags(unsigned reg, SlotIndex OldIdx, SlotIndex newKillIdx) { |
| 1173 | MachineInstr* OldKillMI = LIS.getInstructionFromIndex(OldIdx); |
| 1174 | if (!OldKillMI->killsRegister(reg)) |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1175 | return; // Bail out if we don't have kill flags on the old register. |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1176 | MachineInstr* NewKillMI = LIS.getInstructionFromIndex(newKillIdx); |
| 1177 | assert(OldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill."); |
Jakob Stoklund Olesen | fa8becb | 2012-06-19 22:50:53 +0000 | [diff] [blame] | 1178 | assert(!NewKillMI->killsRegister(reg) && |
| 1179 | "New kill instr is already a kill."); |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1180 | OldKillMI->clearRegisterKills(reg, &TRI); |
| 1181 | NewKillMI->addRegisterKilled(reg, &TRI); |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1182 | } |
| 1183 | |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1184 | void updateRegMaskSlots(SlotIndex OldIdx) { |
| 1185 | SmallVectorImpl<SlotIndex>::iterator RI = |
| 1186 | std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(), |
| 1187 | OldIdx); |
| 1188 | assert(*RI == OldIdx && "No RegMask at OldIdx."); |
| 1189 | *RI = NewIdx; |
| 1190 | assert(*prior(RI) < *RI && *RI < *next(RI) && |
Lang Hames | fbc8dd3 | 2012-02-17 21:29:41 +0000 | [diff] [blame] | 1191 | "RegSlots out of order. Did you move one call across another?"); |
| 1192 | } |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 1193 | |
| 1194 | // Return the last use of reg between NewIdx and OldIdx. |
| 1195 | SlotIndex findLastUseBefore(unsigned Reg, SlotIndex OldIdx) { |
| 1196 | SlotIndex LastUse = NewIdx; |
| 1197 | for (MachineRegisterInfo::use_nodbg_iterator |
| 1198 | UI = MRI.use_nodbg_begin(Reg), |
| 1199 | UE = MRI.use_nodbg_end(); |
Lang Hames | 038d2d5 | 2012-02-19 04:38:25 +0000 | [diff] [blame] | 1200 | UI != UE; UI.skipInstruction()) { |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 1201 | const MachineInstr* MI = &*UI; |
| 1202 | SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); |
| 1203 | if (InstSlot > LastUse && InstSlot < OldIdx) |
| 1204 | LastUse = InstSlot; |
| 1205 | } |
| 1206 | return LastUse; |
| 1207 | } |
| 1208 | |
| 1209 | void moveEnteringUpFrom(SlotIndex OldIdx, IntRangePair& P) { |
| 1210 | LiveInterval* LI = P.first; |
| 1211 | LiveRange* LR = P.second; |
| 1212 | bool LiveThrough = LR->end > OldIdx.getRegSlot(); |
| 1213 | if (LiveThrough) |
| 1214 | return; |
| 1215 | SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx); |
| 1216 | if (LastUse != NewIdx) |
| 1217 | moveKillFlags(LI->reg, NewIdx, LastUse); |
Lang Hames | 7b23d08 | 2012-09-03 06:31:45 +0000 | [diff] [blame] | 1218 | LR->end = LastUse.getRegSlot(LR->end.isEarlyClobber()); |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 1219 | } |
| 1220 | |
| 1221 | void moveEnteringDownFrom(SlotIndex OldIdx, IntRangePair& P) { |
| 1222 | LiveInterval* LI = P.first; |
| 1223 | LiveRange* LR = P.second; |
Andrew Trick | e0b51ab | 2012-03-21 04:12:01 +0000 | [diff] [blame] | 1224 | // Extend the LiveRange if NewIdx is past the end. |
Lang Hames | 4a0b2d6 | 2012-02-19 06:13:56 +0000 | [diff] [blame] | 1225 | if (NewIdx > LR->end) { |
Andrew Trick | e0b51ab | 2012-03-21 04:12:01 +0000 | [diff] [blame] | 1226 | // Move kill flags if OldIdx was not originally the end |
| 1227 | // (otherwise LR->end points to an invalid slot). |
| 1228 | if (LR->end.getRegSlot() != OldIdx.getRegSlot()) { |
| 1229 | assert(LR->end > OldIdx && "LiveRange does not cover original slot"); |
| 1230 | moveKillFlags(LI->reg, LR->end, NewIdx); |
| 1231 | } |
Lang Hames | 7b23d08 | 2012-09-03 06:31:45 +0000 | [diff] [blame] | 1232 | LR->end = NewIdx.getRegSlot(LR->end.isEarlyClobber()); |
Lang Hames | 55fed62 | 2012-02-19 03:00:30 +0000 | [diff] [blame] | 1233 | } |
| 1234 | } |
| 1235 | |
| 1236 | void moveAllEnteringFrom(SlotIndex OldIdx, RangeSet& Entering) { |
| 1237 | bool GoingUp = NewIdx < OldIdx; |
| 1238 | |
| 1239 | if (GoingUp) { |
| 1240 | for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); |
| 1241 | EI != EE; ++EI) |
| 1242 | moveEnteringUpFrom(OldIdx, *EI); |
| 1243 | } else { |
| 1244 | for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); |
| 1245 | EI != EE; ++EI) |
| 1246 | moveEnteringDownFrom(OldIdx, *EI); |
| 1247 | } |
| 1248 | } |
| 1249 | |
| 1250 | void moveInternalFrom(SlotIndex OldIdx, IntRangePair& P) { |
| 1251 | LiveInterval* LI = P.first; |
| 1252 | LiveRange* LR = P.second; |
| 1253 | assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() && |
| 1254 | LR->end <= OldIdx.getDeadSlot() && |
| 1255 | "Range should be internal to OldIdx."); |
| 1256 | LiveRange Tmp(*LR); |
| 1257 | Tmp.start = NewIdx.getRegSlot(LR->start.isEarlyClobber()); |
| 1258 | Tmp.valno->def = Tmp.start; |
| 1259 | Tmp.end = LR->end.isDead() ? NewIdx.getDeadSlot() : NewIdx.getRegSlot(); |
| 1260 | LI->removeRange(*LR); |
| 1261 | LI->addRange(Tmp); |
| 1262 | } |
| 1263 | |
| 1264 | void moveAllInternalFrom(SlotIndex OldIdx, RangeSet& Internal) { |
| 1265 | for (RangeSet::iterator II = Internal.begin(), IE = Internal.end(); |
| 1266 | II != IE; ++II) |
| 1267 | moveInternalFrom(OldIdx, *II); |
| 1268 | } |
| 1269 | |
| 1270 | void moveExitingFrom(SlotIndex OldIdx, IntRangePair& P) { |
| 1271 | LiveRange* LR = P.second; |
| 1272 | assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() && |
| 1273 | "Range should start in OldIdx."); |
| 1274 | assert(LR->end > OldIdx.getDeadSlot() && "Range should exit OldIdx."); |
| 1275 | SlotIndex NewStart = NewIdx.getRegSlot(LR->start.isEarlyClobber()); |
| 1276 | LR->start = NewStart; |
| 1277 | LR->valno->def = NewStart; |
| 1278 | } |
| 1279 | |
| 1280 | void moveAllExitingFrom(SlotIndex OldIdx, RangeSet& Exiting) { |
| 1281 | for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end(); |
| 1282 | EI != EE; ++EI) |
| 1283 | moveExitingFrom(OldIdx, *EI); |
| 1284 | } |
| 1285 | |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1286 | void moveEnteringUpFromInto(SlotIndex OldIdx, IntRangePair& P, |
| 1287 | BundleRanges& BR) { |
| 1288 | LiveInterval* LI = P.first; |
| 1289 | LiveRange* LR = P.second; |
| 1290 | bool LiveThrough = LR->end > OldIdx.getRegSlot(); |
| 1291 | if (LiveThrough) { |
| 1292 | assert((LR->start < NewIdx || BR[LI->reg].Def == LR) && |
| 1293 | "Def in bundle should be def range."); |
| 1294 | assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) && |
| 1295 | "If bundle has use for this reg it should be LR."); |
| 1296 | BR[LI->reg].Use = LR; |
| 1297 | return; |
| 1298 | } |
| 1299 | |
| 1300 | SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx); |
Lang Hames | fd6d321 | 2012-02-21 00:00:36 +0000 | [diff] [blame] | 1301 | moveKillFlags(LI->reg, OldIdx, LastUse); |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1302 | |
| 1303 | if (LR->start < NewIdx) { |
| 1304 | // Becoming a new entering range. |
| 1305 | assert(BR[LI->reg].Dead == 0 && BR[LI->reg].Def == 0 && |
| 1306 | "Bundle shouldn't be re-defining reg mid-range."); |
Benjamin Kramer | 7db76e7 | 2012-02-19 12:25:07 +0000 | [diff] [blame] | 1307 | assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) && |
Lang Hames | 6aceab1 | 2012-02-19 07:13:05 +0000 | [diff] [blame] | 1308 | "Bundle shouldn't have different use range for same reg."); |
| 1309 | LR->end = LastUse.getRegSlot(); |
| 1310 | BR[LI->reg].Use = LR; |
| 1311 | } else { |
| 1312 | // Becoming a new Dead-def. |
| 1313 | assert(LR->start == NewIdx.getRegSlot(LR->start.isEarlyClobber()) && |
| 1314 | "Live range starting at unexpected slot."); |
| 1315 | assert(BR[LI->reg].Def == LR && "Reg should have def range."); |
| 1316 | assert(BR[LI->reg].Dead == 0 && |
| 1317 | "Can't have def and dead def of same reg in a bundle."); |
| 1318 | LR->end = LastUse.getDeadSlot(); |
| 1319 | BR[LI->reg].Dead = BR[LI->reg].Def; |
| 1320 | BR[LI->reg].Def = 0; |
| 1321 | } |
| 1322 | } |
| 1323 | |
| 1324 | void moveEnteringDownFromInto(SlotIndex OldIdx, IntRangePair& P, |
| 1325 | BundleRanges& BR) { |
| 1326 | LiveInterval* LI = P.first; |
| 1327 | LiveRange* LR = P.second; |
| 1328 | if (NewIdx > LR->end) { |
| 1329 | // Range extended to bundle. Add to bundle uses. |
| 1330 | // Note: Currently adds kill flags to bundle start. |
| 1331 | assert(BR[LI->reg].Use == 0 && |
| 1332 | "Bundle already has use range for reg."); |
| 1333 | moveKillFlags(LI->reg, LR->end, NewIdx); |
| 1334 | LR->end = NewIdx.getRegSlot(); |
| 1335 | BR[LI->reg].Use = LR; |
| 1336 | } else { |
| 1337 | assert(BR[LI->reg].Use != 0 && |
| 1338 | "Bundle should already have a use range for reg."); |
| 1339 | } |
| 1340 | } |
| 1341 | |
| 1342 | void moveAllEnteringFromInto(SlotIndex OldIdx, RangeSet& Entering, |
| 1343 | BundleRanges& BR) { |
| 1344 | bool GoingUp = NewIdx < OldIdx; |
| 1345 | |
| 1346 | if (GoingUp) { |
| 1347 | for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); |
| 1348 | EI != EE; ++EI) |
| 1349 | moveEnteringUpFromInto(OldIdx, *EI, BR); |
| 1350 | } else { |
| 1351 | for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); |
| 1352 | EI != EE; ++EI) |
| 1353 | moveEnteringDownFromInto(OldIdx, *EI, BR); |
| 1354 | } |
| 1355 | } |
| 1356 | |
| 1357 | void moveInternalFromInto(SlotIndex OldIdx, IntRangePair& P, |
| 1358 | BundleRanges& BR) { |
| 1359 | // TODO: Sane rules for moving ranges into bundles. |
| 1360 | } |
| 1361 | |
| 1362 | void moveAllInternalFromInto(SlotIndex OldIdx, RangeSet& Internal, |
| 1363 | BundleRanges& BR) { |
| 1364 | for (RangeSet::iterator II = Internal.begin(), IE = Internal.end(); |
| 1365 | II != IE; ++II) |
| 1366 | moveInternalFromInto(OldIdx, *II, BR); |
| 1367 | } |
| 1368 | |
| 1369 | void moveExitingFromInto(SlotIndex OldIdx, IntRangePair& P, |
| 1370 | BundleRanges& BR) { |
| 1371 | LiveInterval* LI = P.first; |
| 1372 | LiveRange* LR = P.second; |
| 1373 | |
| 1374 | assert(LR->start.isRegister() && |
| 1375 | "Don't know how to merge exiting ECs into bundles yet."); |
| 1376 | |
| 1377 | if (LR->end > NewIdx.getDeadSlot()) { |
| 1378 | // This range is becoming an exiting range on the bundle. |
| 1379 | // If there was an old dead-def of this reg, delete it. |
| 1380 | if (BR[LI->reg].Dead != 0) { |
| 1381 | LI->removeRange(*BR[LI->reg].Dead); |
| 1382 | BR[LI->reg].Dead = 0; |
| 1383 | } |
| 1384 | assert(BR[LI->reg].Def == 0 && |
| 1385 | "Can't have two defs for the same variable exiting a bundle."); |
| 1386 | LR->start = NewIdx.getRegSlot(); |
| 1387 | LR->valno->def = LR->start; |
| 1388 | BR[LI->reg].Def = LR; |
| 1389 | } else { |
| 1390 | // This range is becoming internal to the bundle. |
| 1391 | assert(LR->end == NewIdx.getRegSlot() && |
| 1392 | "Can't bundle def whose kill is before the bundle"); |
| 1393 | if (BR[LI->reg].Dead || BR[LI->reg].Def) { |
| 1394 | // Already have a def for this. Just delete range. |
| 1395 | LI->removeRange(*LR); |
| 1396 | } else { |
| 1397 | // Make range dead, record. |
| 1398 | LR->end = NewIdx.getDeadSlot(); |
| 1399 | BR[LI->reg].Dead = LR; |
| 1400 | assert(BR[LI->reg].Use == LR && |
| 1401 | "Range becoming dead should currently be use."); |
| 1402 | } |
| 1403 | // In both cases the range is no longer a use on the bundle. |
| 1404 | BR[LI->reg].Use = 0; |
| 1405 | } |
| 1406 | } |
| 1407 | |
| 1408 | void moveAllExitingFromInto(SlotIndex OldIdx, RangeSet& Exiting, |
| 1409 | BundleRanges& BR) { |
| 1410 | for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end(); |
| 1411 | EI != EE; ++EI) |
| 1412 | moveExitingFromInto(OldIdx, *EI, BR); |
| 1413 | } |
| 1414 | |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1415 | }; |
| 1416 | |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1417 | void LiveIntervals::handleMove(MachineInstr* MI) { |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 1418 | SlotIndex OldIndex = Indexes->getInstructionIndex(MI); |
| 1419 | Indexes->removeMachineInstrFromMaps(MI); |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1420 | SlotIndex NewIndex = MI->isInsideBundle() ? |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 1421 | Indexes->getInstructionIndex(MI) : |
| 1422 | Indexes->insertMachineInstrInMaps(MI); |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1423 | assert(getMBBStartIdx(MI->getParent()) <= OldIndex && |
| 1424 | OldIndex < getMBBEndIdx(MI->getParent()) && |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1425 | "Cannot handle moves across basic block boundaries."); |
Lang Hames | ecb5062 | 2012-02-17 23:43:40 +0000 | [diff] [blame] | 1426 | assert(!MI->isBundled() && "Can't handle bundled instructions yet."); |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1427 | |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 1428 | HMEditor HME(*this, *MRI, *TRI, NewIndex); |
Lang Hames | 4586d25 | 2012-02-21 22:29:38 +0000 | [diff] [blame] | 1429 | HME.moveAllRangesFrom(MI, OldIndex); |
| 1430 | } |
| 1431 | |
Jakob Stoklund Olesen | fa8becb | 2012-06-19 22:50:53 +0000 | [diff] [blame] | 1432 | void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI, |
| 1433 | MachineInstr* BundleStart) { |
Jakob Stoklund Olesen | 15f1d8c | 2012-06-04 22:39:14 +0000 | [diff] [blame] | 1434 | SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart); |
| 1435 | HMEditor HME(*this, *MRI, *TRI, NewIndex); |
Lang Hames | 4586d25 | 2012-02-21 22:29:38 +0000 | [diff] [blame] | 1436 | HME.moveAllRangesInto(MI, BundleStart); |
Lang Hames | 3dc7c51 | 2012-02-17 18:44:18 +0000 | [diff] [blame] | 1437 | } |