Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 1 | //===----- AggressiveAntiDepBreaker.cpp - Anti-dep breaker ----------------===// |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements the AggressiveAntiDepBreaker class, which |
| 11 | // implements register anti-dependence breaking during post-RA |
| 12 | // scheduling. It attempts to break all anti-dependencies within a |
| 13 | // block. |
| 14 | // |
| 15 | //===----------------------------------------------------------------------===// |
| 16 | |
David Goodwin | 4de099d | 2009-11-03 20:57:50 +0000 | [diff] [blame] | 17 | #define DEBUG_TYPE "post-RA-sched" |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 18 | #include "AggressiveAntiDepBreaker.h" |
| 19 | #include "llvm/CodeGen/MachineBasicBlock.h" |
| 20 | #include "llvm/CodeGen/MachineFrameInfo.h" |
| 21 | #include "llvm/CodeGen/MachineInstr.h" |
Andrew Trick | 1525260 | 2012-06-06 20:29:31 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/RegisterClassInfo.h" |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 23 | #include "llvm/Target/TargetInstrInfo.h" |
| 24 | #include "llvm/Target/TargetMachine.h" |
Evan Cheng | 46df4eb | 2010-06-16 07:35:02 +0000 | [diff] [blame] | 25 | #include "llvm/Target/TargetInstrInfo.h" |
Bill Wendling | 75a5b71 | 2010-07-15 06:05:18 +0000 | [diff] [blame] | 26 | #include "llvm/Target/TargetRegisterInfo.h" |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 27 | #include "llvm/Support/CommandLine.h" |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 28 | #include "llvm/Support/Debug.h" |
| 29 | #include "llvm/Support/ErrorHandling.h" |
| 30 | #include "llvm/Support/raw_ostream.h" |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 31 | using namespace llvm; |
| 32 | |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 33 | // If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod |
| 34 | static cl::opt<int> |
| 35 | DebugDiv("agg-antidep-debugdiv", |
Bob Wilson | 347fa3f | 2010-04-09 21:38:26 +0000 | [diff] [blame] | 36 | cl::desc("Debug control for aggressive anti-dep breaker"), |
| 37 | cl::init(0), cl::Hidden); |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 38 | static cl::opt<int> |
| 39 | DebugMod("agg-antidep-debugmod", |
Bob Wilson | 347fa3f | 2010-04-09 21:38:26 +0000 | [diff] [blame] | 40 | cl::desc("Debug control for aggressive anti-dep breaker"), |
| 41 | cl::init(0), cl::Hidden); |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 42 | |
David Goodwin | 990d285 | 2009-12-09 17:18:22 +0000 | [diff] [blame] | 43 | AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs, |
| 44 | MachineBasicBlock *BB) : |
Bill Wendling | 9c2a034 | 2010-07-15 19:58:14 +0000 | [diff] [blame] | 45 | NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0), |
| 46 | GroupNodeIndices(TargetRegs, 0), |
| 47 | KillIndices(TargetRegs, 0), |
| 48 | DefIndices(TargetRegs, 0) |
| 49 | { |
David Goodwin | 990d285 | 2009-12-09 17:18:22 +0000 | [diff] [blame] | 50 | const unsigned BBSize = BB->size(); |
| 51 | for (unsigned i = 0; i < NumTargetRegs; ++i) { |
| 52 | // Initialize all registers to be in their own group. Initially we |
| 53 | // assign the register to the same-indexed GroupNode. |
| 54 | GroupNodeIndices[i] = i; |
| 55 | // Initialize the indices to indicate that no registers are live. |
| 56 | KillIndices[i] = ~0u; |
| 57 | DefIndices[i] = BBSize; |
| 58 | } |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 59 | } |
| 60 | |
Bill Wendling | e4a4147 | 2010-07-15 19:41:20 +0000 | [diff] [blame] | 61 | unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) { |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 62 | unsigned Node = GroupNodeIndices[Reg]; |
| 63 | while (GroupNodes[Node] != Node) |
| 64 | Node = GroupNodes[Node]; |
| 65 | |
| 66 | return Node; |
| 67 | } |
| 68 | |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 69 | void AggressiveAntiDepState::GetGroupRegs( |
| 70 | unsigned Group, |
| 71 | std::vector<unsigned> &Regs, |
| 72 | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs) |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 73 | { |
David Goodwin | 990d285 | 2009-12-09 17:18:22 +0000 | [diff] [blame] | 74 | for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) { |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 75 | if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0)) |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 76 | Regs.push_back(Reg); |
| 77 | } |
| 78 | } |
| 79 | |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 80 | unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1, unsigned Reg2) |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 81 | { |
| 82 | assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!"); |
| 83 | assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!"); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 84 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 85 | // find group for each register |
| 86 | unsigned Group1 = GetGroup(Reg1); |
| 87 | unsigned Group2 = GetGroup(Reg2); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 88 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 89 | // if either group is 0, then that must become the parent |
| 90 | unsigned Parent = (Group1 == 0) ? Group1 : Group2; |
| 91 | unsigned Other = (Parent == Group1) ? Group2 : Group1; |
| 92 | GroupNodes.at(Other) = Parent; |
| 93 | return Parent; |
| 94 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 95 | |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 96 | unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg) |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 97 | { |
| 98 | // Create a new GroupNode for Reg. Reg's existing GroupNode must |
| 99 | // stay as is because there could be other GroupNodes referring to |
| 100 | // it. |
| 101 | unsigned idx = GroupNodes.size(); |
| 102 | GroupNodes.push_back(idx); |
| 103 | GroupNodeIndices[Reg] = idx; |
| 104 | return idx; |
| 105 | } |
| 106 | |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 107 | bool AggressiveAntiDepState::IsLive(unsigned Reg) |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 108 | { |
| 109 | // KillIndex must be defined and DefIndex not defined for a register |
| 110 | // to be live. |
| 111 | return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u)); |
| 112 | } |
| 113 | |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 114 | |
| 115 | |
| 116 | AggressiveAntiDepBreaker:: |
David Goodwin | 0855dee | 2009-11-10 00:15:47 +0000 | [diff] [blame] | 117 | AggressiveAntiDepBreaker(MachineFunction& MFi, |
Jakob Stoklund Olesen | fa796dd | 2011-06-16 21:56:21 +0000 | [diff] [blame] | 118 | const RegisterClassInfo &RCI, |
Evan Cheng | 5b1b4489 | 2011-07-01 21:01:15 +0000 | [diff] [blame] | 119 | TargetSubtargetInfo::RegClassVector& CriticalPathRCs) : |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 120 | AntiDepBreaker(), MF(MFi), |
| 121 | MRI(MF.getRegInfo()), |
Evan Cheng | 46df4eb | 2010-06-16 07:35:02 +0000 | [diff] [blame] | 122 | TII(MF.getTarget().getInstrInfo()), |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 123 | TRI(MF.getTarget().getRegisterInfo()), |
Jakob Stoklund Olesen | fa796dd | 2011-06-16 21:56:21 +0000 | [diff] [blame] | 124 | RegClassInfo(RCI), |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 125 | State(NULL) { |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 126 | /* Collect a bitset of all registers that are only broken if they |
| 127 | are on the critical path. */ |
| 128 | for (unsigned i = 0, e = CriticalPathRCs.size(); i < e; ++i) { |
| 129 | BitVector CPSet = TRI->getAllocatableSet(MF, CriticalPathRCs[i]); |
| 130 | if (CriticalPathSet.none()) |
| 131 | CriticalPathSet = CPSet; |
| 132 | else |
| 133 | CriticalPathSet |= CPSet; |
| 134 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 135 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 136 | DEBUG(dbgs() << "AntiDep Critical-Path Registers:"); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 137 | DEBUG(for (int r = CriticalPathSet.find_first(); r != -1; |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 138 | r = CriticalPathSet.find_next(r)) |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 139 | dbgs() << " " << TRI->getName(r)); |
| 140 | DEBUG(dbgs() << '\n'); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 141 | } |
| 142 | |
| 143 | AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() { |
| 144 | delete State; |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 145 | } |
| 146 | |
| 147 | void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { |
| 148 | assert(State == NULL); |
David Goodwin | 990d285 | 2009-12-09 17:18:22 +0000 | [diff] [blame] | 149 | State = new AggressiveAntiDepState(TRI->getNumRegs(), BB); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 150 | |
Evan Cheng | 5a96b3d | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 151 | bool IsReturnBlock = (!BB->empty() && BB->back().isReturn()); |
Bill Wendling | 38306d5 | 2010-07-15 18:43:09 +0000 | [diff] [blame] | 152 | std::vector<unsigned> &KillIndices = State->GetKillIndices(); |
| 153 | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 154 | |
| 155 | // Determine the live-out physregs for this block. |
| 156 | if (IsReturnBlock) { |
| 157 | // In a return block, examine the function live-out regs. |
| 158 | for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), |
| 159 | E = MRI.liveout_end(); I != E; ++I) { |
Jakob Stoklund Olesen | 396618b | 2012-06-01 23:28:30 +0000 | [diff] [blame] | 160 | for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) { |
| 161 | unsigned Reg = *AI; |
Jakob Stoklund Olesen | 597faa8 | 2010-12-14 23:23:15 +0000 | [diff] [blame] | 162 | State->UnionGroups(Reg, 0); |
| 163 | KillIndices[Reg] = BB->size(); |
| 164 | DefIndices[Reg] = ~0u; |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 165 | } |
| 166 | } |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 167 | } |
| 168 | |
Evan Cheng | 46df4eb | 2010-06-16 07:35:02 +0000 | [diff] [blame] | 169 | // In a non-return block, examine the live-in regs of all successors. |
| 170 | // Note a return block can have successors if the return instruction is |
| 171 | // predicated. |
| 172 | for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), |
| 173 | SE = BB->succ_end(); SI != SE; ++SI) |
| 174 | for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), |
| 175 | E = (*SI)->livein_end(); I != E; ++I) { |
Jakob Stoklund Olesen | 396618b | 2012-06-01 23:28:30 +0000 | [diff] [blame] | 176 | for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) { |
| 177 | unsigned Reg = *AI; |
Jakob Stoklund Olesen | 597faa8 | 2010-12-14 23:23:15 +0000 | [diff] [blame] | 178 | State->UnionGroups(Reg, 0); |
| 179 | KillIndices[Reg] = BB->size(); |
| 180 | DefIndices[Reg] = ~0u; |
Evan Cheng | 46df4eb | 2010-06-16 07:35:02 +0000 | [diff] [blame] | 181 | } |
| 182 | } |
| 183 | |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 184 | // Mark live-out callee-saved registers. In a return block this is |
| 185 | // all callee-saved registers. In non-return this is any |
| 186 | // callee-saved register that is not saved in the prolog. |
| 187 | const MachineFrameInfo *MFI = MF.getFrameInfo(); |
| 188 | BitVector Pristine = MFI->getPristineRegs(BB); |
Craig Topper | 015f228 | 2012-03-04 03:33:22 +0000 | [diff] [blame] | 189 | for (const uint16_t *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) { |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 190 | unsigned Reg = *I; |
| 191 | if (!IsReturnBlock && !Pristine.test(Reg)) continue; |
Jakob Stoklund Olesen | 396618b | 2012-06-01 23:28:30 +0000 | [diff] [blame] | 192 | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { |
| 193 | unsigned AliasReg = *AI; |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 194 | State->UnionGroups(AliasReg, 0); |
| 195 | KillIndices[AliasReg] = BB->size(); |
| 196 | DefIndices[AliasReg] = ~0u; |
| 197 | } |
| 198 | } |
| 199 | } |
| 200 | |
| 201 | void AggressiveAntiDepBreaker::FinishBlock() { |
| 202 | delete State; |
| 203 | State = NULL; |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 204 | } |
| 205 | |
| 206 | void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, |
Bob Wilson | 347fa3f | 2010-04-09 21:38:26 +0000 | [diff] [blame] | 207 | unsigned InsertPosIndex) { |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 208 | assert(Count < InsertPosIndex && "Instruction index out of expected range!"); |
| 209 | |
David Goodwin | 5b3c308 | 2009-10-29 23:30:59 +0000 | [diff] [blame] | 210 | std::set<unsigned> PassthruRegs; |
| 211 | GetPassthruRegs(MI, PassthruRegs); |
| 212 | PrescanInstruction(MI, Count, PassthruRegs); |
| 213 | ScanInstruction(MI, Count); |
| 214 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 215 | DEBUG(dbgs() << "Observe: "); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 216 | DEBUG(MI->dump()); |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 217 | DEBUG(dbgs() << "\tRegs:"); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 218 | |
Bill Wendling | 38306d5 | 2010-07-15 18:43:09 +0000 | [diff] [blame] | 219 | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
David Goodwin | 990d285 | 2009-12-09 17:18:22 +0000 | [diff] [blame] | 220 | for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) { |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 221 | // If Reg is current live, then mark that it can't be renamed as |
| 222 | // we don't know the extent of its live-range anymore (now that it |
| 223 | // has been scheduled). If it is not live but was defined in the |
| 224 | // previous schedule region, then set its def index to the most |
| 225 | // conservative location (i.e. the beginning of the previous |
| 226 | // schedule region). |
| 227 | if (State->IsLive(Reg)) { |
| 228 | DEBUG(if (State->GetGroup(Reg) != 0) |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 229 | dbgs() << " " << TRI->getName(Reg) << "=g" << |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 230 | State->GetGroup(Reg) << "->g0(region live-out)"); |
| 231 | State->UnionGroups(Reg, 0); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 232 | } else if ((DefIndices[Reg] < InsertPosIndex) |
| 233 | && (DefIndices[Reg] >= Count)) { |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 234 | DefIndices[Reg] = Count; |
| 235 | } |
| 236 | } |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 237 | DEBUG(dbgs() << '\n'); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 238 | } |
| 239 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 240 | bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr *MI, |
Bob Wilson | 347fa3f | 2010-04-09 21:38:26 +0000 | [diff] [blame] | 241 | MachineOperand& MO) |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 242 | { |
| 243 | if (!MO.isReg() || !MO.isImplicit()) |
| 244 | return false; |
| 245 | |
| 246 | unsigned Reg = MO.getReg(); |
| 247 | if (Reg == 0) |
| 248 | return false; |
| 249 | |
| 250 | MachineOperand *Op = NULL; |
| 251 | if (MO.isDef()) |
| 252 | Op = MI->findRegisterUseOperand(Reg, true); |
| 253 | else |
| 254 | Op = MI->findRegisterDefOperand(Reg); |
| 255 | |
| 256 | return((Op != NULL) && Op->isImplicit()); |
| 257 | } |
| 258 | |
| 259 | void AggressiveAntiDepBreaker::GetPassthruRegs(MachineInstr *MI, |
| 260 | std::set<unsigned>& PassthruRegs) { |
| 261 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 262 | MachineOperand &MO = MI->getOperand(i); |
| 263 | if (!MO.isReg()) continue; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 264 | if ((MO.isDef() && MI->isRegTiedToUseOperand(i)) || |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 265 | IsImplicitDefUse(MI, MO)) { |
| 266 | const unsigned Reg = MO.getReg(); |
| 267 | PassthruRegs.insert(Reg); |
Jakob Stoklund Olesen | 396618b | 2012-06-01 23:28:30 +0000 | [diff] [blame] | 268 | for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) |
| 269 | PassthruRegs.insert(*SubRegs); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 270 | } |
| 271 | } |
| 272 | } |
| 273 | |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 274 | /// AntiDepEdges - Return in Edges the anti- and output- dependencies |
| 275 | /// in SU that we want to consider for breaking. |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 276 | static void AntiDepEdges(const SUnit *SU, std::vector<const SDep*>& Edges) { |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 277 | SmallSet<unsigned, 4> RegSet; |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 278 | for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 279 | P != PE; ++P) { |
David Goodwin | 12dd99d | 2009-11-12 19:08:21 +0000 | [diff] [blame] | 280 | if ((P->getKind() == SDep::Anti) || (P->getKind() == SDep::Output)) { |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 281 | unsigned Reg = P->getReg(); |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 282 | if (RegSet.count(Reg) == 0) { |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 283 | Edges.push_back(&*P); |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 284 | RegSet.insert(Reg); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 285 | } |
| 286 | } |
| 287 | } |
| 288 | } |
| 289 | |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 290 | /// CriticalPathStep - Return the next SUnit after SU on the bottom-up |
| 291 | /// critical path. |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 292 | static const SUnit *CriticalPathStep(const SUnit *SU) { |
| 293 | const SDep *Next = 0; |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 294 | unsigned NextDepth = 0; |
| 295 | // Find the predecessor edge with the greatest depth. |
| 296 | if (SU != 0) { |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 297 | for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 298 | P != PE; ++P) { |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 299 | const SUnit *PredSU = P->getSUnit(); |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 300 | unsigned PredLatency = P->getLatency(); |
| 301 | unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; |
| 302 | // In the case of a latency tie, prefer an anti-dependency edge over |
| 303 | // other types of edges. |
| 304 | if (NextDepth < PredTotalLatency || |
| 305 | (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) { |
| 306 | NextDepth = PredTotalLatency; |
| 307 | Next = &*P; |
| 308 | } |
| 309 | } |
| 310 | } |
| 311 | |
| 312 | return (Next) ? Next->getSUnit() : 0; |
| 313 | } |
| 314 | |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 315 | void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx, |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 316 | const char *tag, |
| 317 | const char *header, |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 318 | const char *footer) { |
Bill Wendling | 38306d5 | 2010-07-15 18:43:09 +0000 | [diff] [blame] | 319 | std::vector<unsigned> &KillIndices = State->GetKillIndices(); |
| 320 | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 321 | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 322 | RegRefs = State->GetRegRefs(); |
| 323 | |
| 324 | if (!State->IsLive(Reg)) { |
| 325 | KillIndices[Reg] = KillIdx; |
| 326 | DefIndices[Reg] = ~0u; |
| 327 | RegRefs.erase(Reg); |
| 328 | State->LeaveGroup(Reg); |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 329 | DEBUG(if (header != NULL) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 330 | dbgs() << header << TRI->getName(Reg); header = NULL; }); |
| 331 | DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag); |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 332 | } |
| 333 | // Repeat for subregisters. |
Jakob Stoklund Olesen | 396618b | 2012-06-01 23:28:30 +0000 | [diff] [blame] | 334 | for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { |
| 335 | unsigned SubregReg = *SubRegs; |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 336 | if (!State->IsLive(SubregReg)) { |
| 337 | KillIndices[SubregReg] = KillIdx; |
| 338 | DefIndices[SubregReg] = ~0u; |
| 339 | RegRefs.erase(SubregReg); |
| 340 | State->LeaveGroup(SubregReg); |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 341 | DEBUG(if (header != NULL) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 342 | dbgs() << header << TRI->getName(Reg); header = NULL; }); |
| 343 | DEBUG(dbgs() << " " << TRI->getName(SubregReg) << "->g" << |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 344 | State->GetGroup(SubregReg) << tag); |
| 345 | } |
| 346 | } |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 347 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 348 | DEBUG(if ((header == NULL) && (footer != NULL)) dbgs() << footer); |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 349 | } |
| 350 | |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 351 | void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, |
| 352 | unsigned Count, |
Bob Wilson | 347fa3f | 2010-04-09 21:38:26 +0000 | [diff] [blame] | 353 | std::set<unsigned>& PassthruRegs) { |
Bill Wendling | 38306d5 | 2010-07-15 18:43:09 +0000 | [diff] [blame] | 354 | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 355 | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 356 | RegRefs = State->GetRegRefs(); |
| 357 | |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 358 | // Handle dead defs by simulating a last-use of the register just |
Chris Lattner | 7a2bdde | 2011-04-15 05:18:47 +0000 | [diff] [blame] | 359 | // after the def. A dead def can occur because the def is truly |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 360 | // dead, or because only a subregister is live at the def. If we |
| 361 | // don't do this the dead def will be incorrectly merged into the |
| 362 | // previous def. |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 363 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 364 | MachineOperand &MO = MI->getOperand(i); |
| 365 | if (!MO.isReg() || !MO.isDef()) continue; |
| 366 | unsigned Reg = MO.getReg(); |
| 367 | if (Reg == 0) continue; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 368 | |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 369 | HandleLastUse(Reg, Count + 1, "", "\tDead Def: ", "\n"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 370 | } |
| 371 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 372 | DEBUG(dbgs() << "\tDef Groups:"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 373 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 374 | MachineOperand &MO = MI->getOperand(i); |
| 375 | if (!MO.isReg() || !MO.isDef()) continue; |
| 376 | unsigned Reg = MO.getReg(); |
| 377 | if (Reg == 0) continue; |
| 378 | |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 379 | DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" << State->GetGroup(Reg)); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 380 | |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 381 | // If MI's defs have a special allocation requirement, don't allow |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 382 | // any def registers to be changed. Also assume all registers |
| 383 | // defined in a call must not be changed (ABI). |
Evan Cheng | 5a96b3d | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 384 | if (MI->isCall() || MI->hasExtraDefRegAllocReq() || |
Evan Cheng | 46df4eb | 2010-06-16 07:35:02 +0000 | [diff] [blame] | 385 | TII->isPredicated(MI)) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 386 | DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 387 | State->UnionGroups(Reg, 0); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 388 | } |
| 389 | |
| 390 | // Any aliased that are live at this point are completely or |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 391 | // partially defined here, so group those aliases with Reg. |
Jakob Stoklund Olesen | 396618b | 2012-06-01 23:28:30 +0000 | [diff] [blame] | 392 | for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { |
| 393 | unsigned AliasReg = *AI; |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 394 | if (State->IsLive(AliasReg)) { |
| 395 | State->UnionGroups(Reg, AliasReg); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 396 | DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via " << |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 397 | TRI->getName(AliasReg) << ")"); |
| 398 | } |
| 399 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 400 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 401 | // Note register reference... |
| 402 | const TargetRegisterClass *RC = NULL; |
| 403 | if (i < MI->getDesc().getNumOperands()) |
Jakob Stoklund Olesen | 397fc48 | 2012-05-07 22:10:26 +0000 | [diff] [blame] | 404 | RC = TII->getRegClass(MI->getDesc(), i, TRI, MF); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 405 | AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 406 | RegRefs.insert(std::make_pair(Reg, RR)); |
| 407 | } |
| 408 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 409 | DEBUG(dbgs() << '\n'); |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 410 | |
| 411 | // Scan the register defs for this instruction and update |
| 412 | // live-ranges. |
| 413 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 414 | MachineOperand &MO = MI->getOperand(i); |
| 415 | if (!MO.isReg() || !MO.isDef()) continue; |
| 416 | unsigned Reg = MO.getReg(); |
| 417 | if (Reg == 0) continue; |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 418 | // Ignore KILLs and passthru registers for liveness... |
Chris Lattner | 518bb53 | 2010-02-09 19:54:29 +0000 | [diff] [blame] | 419 | if (MI->isKill() || (PassthruRegs.count(Reg) != 0)) |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 420 | continue; |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 421 | |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 422 | // Update def for Reg and aliases. |
Jakob Stoklund Olesen | 396618b | 2012-06-01 23:28:30 +0000 | [diff] [blame] | 423 | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) |
| 424 | DefIndices[*AI] = Count; |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 425 | } |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 426 | } |
| 427 | |
| 428 | void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI, |
Bob Wilson | 347fa3f | 2010-04-09 21:38:26 +0000 | [diff] [blame] | 429 | unsigned Count) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 430 | DEBUG(dbgs() << "\tUse Groups:"); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 431 | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 432 | RegRefs = State->GetRegRefs(); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 433 | |
Evan Cheng | 46df4eb | 2010-06-16 07:35:02 +0000 | [diff] [blame] | 434 | // If MI's uses have special allocation requirement, don't allow |
| 435 | // any use registers to be changed. Also assume all registers |
| 436 | // used in a call must not be changed (ABI). |
| 437 | // FIXME: The issue with predicated instruction is more complex. We are being |
| 438 | // conservatively here because the kill markers cannot be trusted after |
| 439 | // if-conversion: |
| 440 | // %R6<def> = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14] |
| 441 | // ... |
| 442 | // STR %R0, %R6<kill>, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395] |
| 443 | // %R6<def> = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12] |
| 444 | // STR %R0, %R6<kill>, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8) |
| 445 | // |
| 446 | // The first R6 kill is not really a kill since it's killed by a predicated |
| 447 | // instruction which may not be executed. The second R6 def may or may not |
| 448 | // re-define R6 so it's not safe to change it since the last R6 use cannot be |
| 449 | // changed. |
Evan Cheng | 5a96b3d | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 450 | bool Special = MI->isCall() || |
| 451 | MI->hasExtraSrcRegAllocReq() || |
Evan Cheng | 46df4eb | 2010-06-16 07:35:02 +0000 | [diff] [blame] | 452 | TII->isPredicated(MI); |
| 453 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 454 | // Scan the register uses for this instruction and update |
| 455 | // live-ranges, groups and RegRefs. |
| 456 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 457 | MachineOperand &MO = MI->getOperand(i); |
| 458 | if (!MO.isReg() || !MO.isUse()) continue; |
| 459 | unsigned Reg = MO.getReg(); |
| 460 | if (Reg == 0) continue; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 461 | |
| 462 | DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" << |
| 463 | State->GetGroup(Reg)); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 464 | |
| 465 | // It wasn't previously live but now it is, this is a kill. Forget |
| 466 | // the previous live-range information and start a new live-range |
| 467 | // for the register. |
David Goodwin | 67a8a7b | 2009-10-29 19:17:04 +0000 | [diff] [blame] | 468 | HandleLastUse(Reg, Count, "(last-use)"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 469 | |
Evan Cheng | 46df4eb | 2010-06-16 07:35:02 +0000 | [diff] [blame] | 470 | if (Special) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 471 | DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 472 | State->UnionGroups(Reg, 0); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 473 | } |
| 474 | |
| 475 | // Note register reference... |
| 476 | const TargetRegisterClass *RC = NULL; |
| 477 | if (i < MI->getDesc().getNumOperands()) |
Jakob Stoklund Olesen | 397fc48 | 2012-05-07 22:10:26 +0000 | [diff] [blame] | 478 | RC = TII->getRegClass(MI->getDesc(), i, TRI, MF); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 479 | AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 480 | RegRefs.insert(std::make_pair(Reg, RR)); |
| 481 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 482 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 483 | DEBUG(dbgs() << '\n'); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 484 | |
| 485 | // Form a group of all defs and uses of a KILL instruction to ensure |
| 486 | // that all registers are renamed as a group. |
Chris Lattner | 518bb53 | 2010-02-09 19:54:29 +0000 | [diff] [blame] | 487 | if (MI->isKill()) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 488 | DEBUG(dbgs() << "\tKill Group:"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 489 | |
| 490 | unsigned FirstReg = 0; |
| 491 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 492 | MachineOperand &MO = MI->getOperand(i); |
| 493 | if (!MO.isReg()) continue; |
| 494 | unsigned Reg = MO.getReg(); |
| 495 | if (Reg == 0) continue; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 496 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 497 | if (FirstReg != 0) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 498 | DEBUG(dbgs() << "=" << TRI->getName(Reg)); |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 499 | State->UnionGroups(FirstReg, Reg); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 500 | } else { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 501 | DEBUG(dbgs() << " " << TRI->getName(Reg)); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 502 | FirstReg = Reg; |
| 503 | } |
| 504 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 505 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 506 | DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n'); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 507 | } |
| 508 | } |
| 509 | |
| 510 | BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) { |
| 511 | BitVector BV(TRI->getNumRegs(), false); |
| 512 | bool first = true; |
| 513 | |
| 514 | // Check all references that need rewriting for Reg. For each, use |
| 515 | // the corresponding register class to narrow the set of registers |
| 516 | // that are appropriate for renaming. |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 517 | std::pair<std::multimap<unsigned, |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 518 | AggressiveAntiDepState::RegisterReference>::iterator, |
| 519 | std::multimap<unsigned, |
| 520 | AggressiveAntiDepState::RegisterReference>::iterator> |
| 521 | Range = State->GetRegRefs().equal_range(Reg); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 522 | for (std::multimap<unsigned, |
| 523 | AggressiveAntiDepState::RegisterReference>::iterator Q = Range.first, |
| 524 | QE = Range.second; Q != QE; ++Q) { |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 525 | const TargetRegisterClass *RC = Q->second.RC; |
| 526 | if (RC == NULL) continue; |
| 527 | |
| 528 | BitVector RCBV = TRI->getAllocatableSet(MF, RC); |
| 529 | if (first) { |
| 530 | BV |= RCBV; |
| 531 | first = false; |
| 532 | } else { |
| 533 | BV &= RCBV; |
| 534 | } |
| 535 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 536 | DEBUG(dbgs() << " " << RC->getName()); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 537 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 538 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 539 | return BV; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 540 | } |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 541 | |
| 542 | bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( |
David Goodwin | 5409783 | 2009-11-05 01:19:35 +0000 | [diff] [blame] | 543 | unsigned AntiDepGroupIndex, |
| 544 | RenameOrderType& RenameOrder, |
| 545 | std::map<unsigned, unsigned> &RenameMap) { |
Bill Wendling | 38306d5 | 2010-07-15 18:43:09 +0000 | [diff] [blame] | 546 | std::vector<unsigned> &KillIndices = State->GetKillIndices(); |
| 547 | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 548 | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 549 | RegRefs = State->GetRegRefs(); |
| 550 | |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 551 | // Collect all referenced registers in the same group as |
| 552 | // AntiDepReg. These all need to be renamed together if we are to |
| 553 | // break the anti-dependence. |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 554 | std::vector<unsigned> Regs; |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 555 | State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 556 | assert(Regs.size() > 0 && "Empty register group!"); |
| 557 | if (Regs.size() == 0) |
| 558 | return false; |
| 559 | |
| 560 | // Find the "superest" register in the group. At the same time, |
| 561 | // collect the BitVector of registers that can be used to rename |
| 562 | // each register. |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 563 | DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex |
| 564 | << ":\n"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 565 | std::map<unsigned, BitVector> RenameRegisterMap; |
| 566 | unsigned SuperReg = 0; |
| 567 | for (unsigned i = 0, e = Regs.size(); i != e; ++i) { |
| 568 | unsigned Reg = Regs[i]; |
| 569 | if ((SuperReg == 0) || TRI->isSuperRegister(SuperReg, Reg)) |
| 570 | SuperReg = Reg; |
| 571 | |
| 572 | // If Reg has any references, then collect possible rename regs |
| 573 | if (RegRefs.count(Reg) > 0) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 574 | DEBUG(dbgs() << "\t\t" << TRI->getName(Reg) << ":"); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 575 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 576 | BitVector BV = GetRenameRegisters(Reg); |
| 577 | RenameRegisterMap.insert(std::pair<unsigned, BitVector>(Reg, BV)); |
| 578 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 579 | DEBUG(dbgs() << " ::"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 580 | DEBUG(for (int r = BV.find_first(); r != -1; r = BV.find_next(r)) |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 581 | dbgs() << " " << TRI->getName(r)); |
| 582 | DEBUG(dbgs() << "\n"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 583 | } |
| 584 | } |
| 585 | |
| 586 | // All group registers should be a subreg of SuperReg. |
| 587 | for (unsigned i = 0, e = Regs.size(); i != e; ++i) { |
| 588 | unsigned Reg = Regs[i]; |
| 589 | if (Reg == SuperReg) continue; |
| 590 | bool IsSub = TRI->isSubRegister(SuperReg, Reg); |
| 591 | assert(IsSub && "Expecting group subregister"); |
| 592 | if (!IsSub) |
| 593 | return false; |
| 594 | } |
| 595 | |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 596 | #ifndef NDEBUG |
| 597 | // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod |
| 598 | if (DebugDiv > 0) { |
| 599 | static int renamecnt = 0; |
| 600 | if (renamecnt++ % DebugDiv != DebugMod) |
| 601 | return false; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 602 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 603 | dbgs() << "*** Performing rename " << TRI->getName(SuperReg) << |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 604 | " for debug ***\n"; |
| 605 | } |
| 606 | #endif |
| 607 | |
David Goodwin | 5409783 | 2009-11-05 01:19:35 +0000 | [diff] [blame] | 608 | // Check each possible rename register for SuperReg in round-robin |
| 609 | // order. If that register is available, and the corresponding |
| 610 | // registers are available for the other group subregisters, then we |
| 611 | // can use those registers to rename. |
Rafael Espindola | 7e1b566 | 2010-07-12 02:55:34 +0000 | [diff] [blame] | 612 | |
| 613 | // FIXME: Using getMinimalPhysRegClass is very conservative. We should |
| 614 | // check every use of the register and find the largest register class |
| 615 | // that can be used in all of them. |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 616 | const TargetRegisterClass *SuperRC = |
Rafael Espindola | 7e1b566 | 2010-07-12 02:55:34 +0000 | [diff] [blame] | 617 | TRI->getMinimalPhysRegClass(SuperReg, MVT::Other); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 618 | |
Jakob Stoklund Olesen | 39b5c0c | 2012-11-29 03:34:17 +0000 | [diff] [blame^] | 619 | ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC); |
Jakob Stoklund Olesen | fa796dd | 2011-06-16 21:56:21 +0000 | [diff] [blame] | 620 | if (Order.empty()) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 621 | DEBUG(dbgs() << "\tEmpty Super Regclass!!\n"); |
David Goodwin | 5409783 | 2009-11-05 01:19:35 +0000 | [diff] [blame] | 622 | return false; |
| 623 | } |
| 624 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 625 | DEBUG(dbgs() << "\tFind Registers:"); |
David Goodwin | 3e72d30 | 2009-11-19 23:12:37 +0000 | [diff] [blame] | 626 | |
David Goodwin | 5409783 | 2009-11-05 01:19:35 +0000 | [diff] [blame] | 627 | if (RenameOrder.count(SuperRC) == 0) |
Jakob Stoklund Olesen | fa796dd | 2011-06-16 21:56:21 +0000 | [diff] [blame] | 628 | RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size())); |
David Goodwin | 5409783 | 2009-11-05 01:19:35 +0000 | [diff] [blame] | 629 | |
Jakob Stoklund Olesen | fa796dd | 2011-06-16 21:56:21 +0000 | [diff] [blame] | 630 | unsigned OrigR = RenameOrder[SuperRC]; |
| 631 | unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR); |
| 632 | unsigned R = OrigR; |
David Goodwin | 5409783 | 2009-11-05 01:19:35 +0000 | [diff] [blame] | 633 | do { |
Jakob Stoklund Olesen | fa796dd | 2011-06-16 21:56:21 +0000 | [diff] [blame] | 634 | if (R == 0) R = Order.size(); |
David Goodwin | 5409783 | 2009-11-05 01:19:35 +0000 | [diff] [blame] | 635 | --R; |
Jakob Stoklund Olesen | fa796dd | 2011-06-16 21:56:21 +0000 | [diff] [blame] | 636 | const unsigned NewSuperReg = Order[R]; |
Jim Grosbach | 9b041c9 | 2010-09-02 17:12:55 +0000 | [diff] [blame] | 637 | // Don't consider non-allocatable registers |
Jakob Stoklund Olesen | 14d1dd9 | 2012-10-15 22:41:03 +0000 | [diff] [blame] | 638 | if (!MRI.isAllocatable(NewSuperReg)) continue; |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 639 | // Don't replace a register with itself. |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 640 | if (NewSuperReg == SuperReg) continue; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 641 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 642 | DEBUG(dbgs() << " [" << TRI->getName(NewSuperReg) << ':'); |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 643 | RenameMap.clear(); |
| 644 | |
| 645 | // For each referenced group register (which must be a SuperReg or |
| 646 | // a subregister of SuperReg), find the corresponding subregister |
| 647 | // of NewSuperReg and make sure it is free to be renamed. |
| 648 | for (unsigned i = 0, e = Regs.size(); i != e; ++i) { |
| 649 | unsigned Reg = Regs[i]; |
| 650 | unsigned NewReg = 0; |
| 651 | if (Reg == SuperReg) { |
| 652 | NewReg = NewSuperReg; |
| 653 | } else { |
| 654 | unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg); |
| 655 | if (NewSubRegIdx != 0) |
| 656 | NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 657 | } |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 658 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 659 | DEBUG(dbgs() << " " << TRI->getName(NewReg)); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 660 | |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 661 | // Check if Reg can be renamed to NewReg. |
| 662 | BitVector BV = RenameRegisterMap[Reg]; |
| 663 | if (!BV.test(NewReg)) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 664 | DEBUG(dbgs() << "(no rename)"); |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 665 | goto next_super_reg; |
| 666 | } |
| 667 | |
| 668 | // If NewReg is dead and NewReg's most recent def is not before |
| 669 | // Regs's kill, it's safe to replace Reg with NewReg. We |
| 670 | // must also check all aliases of NewReg, because we can't define a |
| 671 | // register when any sub or super is already live. |
| 672 | if (State->IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 673 | DEBUG(dbgs() << "(live)"); |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 674 | goto next_super_reg; |
| 675 | } else { |
| 676 | bool found = false; |
Jakob Stoklund Olesen | 396618b | 2012-06-01 23:28:30 +0000 | [diff] [blame] | 677 | for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) { |
| 678 | unsigned AliasReg = *AI; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 679 | if (State->IsLive(AliasReg) || |
| 680 | (KillIndices[Reg] > DefIndices[AliasReg])) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 681 | DEBUG(dbgs() << "(alias " << TRI->getName(AliasReg) << " live)"); |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 682 | found = true; |
| 683 | break; |
| 684 | } |
| 685 | } |
| 686 | if (found) |
| 687 | goto next_super_reg; |
| 688 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 689 | |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 690 | // Record that 'Reg' can be renamed to 'NewReg'. |
| 691 | RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg)); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 692 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 693 | |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 694 | // If we fall-out here, then every register in the group can be |
| 695 | // renamed, as recorded in RenameMap. |
| 696 | RenameOrder.erase(SuperRC); |
| 697 | RenameOrder.insert(RenameOrderType::value_type(SuperRC, R)); |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 698 | DEBUG(dbgs() << "]\n"); |
David Goodwin | 00621ef | 2009-11-20 23:33:54 +0000 | [diff] [blame] | 699 | return true; |
| 700 | |
| 701 | next_super_reg: |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 702 | DEBUG(dbgs() << ']'); |
David Goodwin | 5409783 | 2009-11-05 01:19:35 +0000 | [diff] [blame] | 703 | } while (R != EndR); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 704 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 705 | DEBUG(dbgs() << '\n'); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 706 | |
| 707 | // No registers are free and available! |
| 708 | return false; |
| 709 | } |
| 710 | |
| 711 | /// BreakAntiDependencies - Identifiy anti-dependencies within the |
| 712 | /// ScheduleDAG and break them by renaming registers. |
| 713 | /// |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 714 | unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 715 | const std::vector<SUnit>& SUnits, |
| 716 | MachineBasicBlock::iterator Begin, |
| 717 | MachineBasicBlock::iterator End, |
Devang Patel | e29e8e1 | 2011-06-02 21:26:52 +0000 | [diff] [blame] | 718 | unsigned InsertPosIndex, |
| 719 | DbgValueVector &DbgValues) { |
| 720 | |
Bill Wendling | 38306d5 | 2010-07-15 18:43:09 +0000 | [diff] [blame] | 721 | std::vector<unsigned> &KillIndices = State->GetKillIndices(); |
| 722 | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 723 | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 724 | RegRefs = State->GetRegRefs(); |
| 725 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 726 | // The code below assumes that there is at least one instruction, |
| 727 | // so just duck out immediately if the block is empty. |
David Goodwin | 4de099d | 2009-11-03 20:57:50 +0000 | [diff] [blame] | 728 | if (SUnits.empty()) return 0; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 729 | |
David Goodwin | 5409783 | 2009-11-05 01:19:35 +0000 | [diff] [blame] | 730 | // For each regclass the next register to use for renaming. |
| 731 | RenameOrderType RenameOrder; |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 732 | |
| 733 | // ...need a map from MI to SUnit. |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 734 | std::map<MachineInstr *, const SUnit *> MISUnitMap; |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 735 | for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 736 | const SUnit *SU = &SUnits[i]; |
| 737 | MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(SU->getInstr(), |
| 738 | SU)); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 739 | } |
| 740 | |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 741 | // Track progress along the critical path through the SUnit graph as |
| 742 | // we walk the instructions. This is needed for regclasses that only |
| 743 | // break critical-path anti-dependencies. |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 744 | const SUnit *CriticalPathSU = 0; |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 745 | MachineInstr *CriticalPathMI = 0; |
| 746 | if (CriticalPathSet.any()) { |
| 747 | for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 748 | const SUnit *SU = &SUnits[i]; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 749 | if (!CriticalPathSU || |
| 750 | ((SU->getDepth() + SU->Latency) > |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 751 | (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) { |
| 752 | CriticalPathSU = SU; |
| 753 | } |
| 754 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 755 | |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 756 | CriticalPathMI = CriticalPathSU->getInstr(); |
| 757 | } |
| 758 | |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 759 | #ifndef NDEBUG |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 760 | DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n"); |
| 761 | DEBUG(dbgs() << "Available regs:"); |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 762 | for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { |
| 763 | if (!State->IsLive(Reg)) |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 764 | DEBUG(dbgs() << " " << TRI->getName(Reg)); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 765 | } |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 766 | DEBUG(dbgs() << '\n'); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 767 | #endif |
| 768 | |
| 769 | // Attempt to break anti-dependence edges. Walk the instructions |
| 770 | // from the bottom up, tracking information about liveness as we go |
| 771 | // to help determine which registers are available. |
| 772 | unsigned Broken = 0; |
| 773 | unsigned Count = InsertPosIndex - 1; |
| 774 | for (MachineBasicBlock::iterator I = End, E = Begin; |
| 775 | I != E; --Count) { |
| 776 | MachineInstr *MI = --I; |
| 777 | |
Hal Finkel | 504d1d2 | 2012-01-16 22:53:41 +0000 | [diff] [blame] | 778 | if (MI->isDebugValue()) |
| 779 | continue; |
| 780 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 781 | DEBUG(dbgs() << "Anti: "); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 782 | DEBUG(MI->dump()); |
| 783 | |
| 784 | std::set<unsigned> PassthruRegs; |
| 785 | GetPassthruRegs(MI, PassthruRegs); |
| 786 | |
| 787 | // Process the defs in MI... |
| 788 | PrescanInstruction(MI, Count, PassthruRegs); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 789 | |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 790 | // The dependence edges that represent anti- and output- |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 791 | // dependencies that are candidates for breaking. |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 792 | std::vector<const SDep *> Edges; |
| 793 | const SUnit *PathSU = MISUnitMap[MI]; |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 794 | AntiDepEdges(PathSU, Edges); |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 795 | |
| 796 | // If MI is not on the critical path, then we don't rename |
| 797 | // registers in the CriticalPathSet. |
| 798 | BitVector *ExcludeRegs = NULL; |
| 799 | if (MI == CriticalPathMI) { |
| 800 | CriticalPathSU = CriticalPathStep(CriticalPathSU); |
| 801 | CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : 0; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 802 | } else { |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 803 | ExcludeRegs = &CriticalPathSet; |
| 804 | } |
| 805 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 806 | // Ignore KILL instructions (they form a group in ScanInstruction |
| 807 | // but don't cause any anti-dependence breaking themselves) |
Chris Lattner | 518bb53 | 2010-02-09 19:54:29 +0000 | [diff] [blame] | 808 | if (!MI->isKill()) { |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 809 | // Attempt to break each anti-dependency... |
| 810 | for (unsigned i = 0, e = Edges.size(); i != e; ++i) { |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 811 | const SDep *Edge = Edges[i]; |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 812 | SUnit *NextSU = Edge->getSUnit(); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 813 | |
David Goodwin | 12dd99d | 2009-11-12 19:08:21 +0000 | [diff] [blame] | 814 | if ((Edge->getKind() != SDep::Anti) && |
| 815 | (Edge->getKind() != SDep::Output)) continue; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 816 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 817 | unsigned AntiDepReg = Edge->getReg(); |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 818 | DEBUG(dbgs() << "\tAntidep reg: " << TRI->getName(AntiDepReg)); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 819 | assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 820 | |
Jakob Stoklund Olesen | 14d1dd9 | 2012-10-15 22:41:03 +0000 | [diff] [blame] | 821 | if (!MRI.isAllocatable(AntiDepReg)) { |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 822 | // Don't break anti-dependencies on non-allocatable registers. |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 823 | DEBUG(dbgs() << " (non-allocatable)\n"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 824 | continue; |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 825 | } else if ((ExcludeRegs != NULL) && ExcludeRegs->test(AntiDepReg)) { |
| 826 | // Don't break anti-dependencies for critical path registers |
| 827 | // if not on the critical path |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 828 | DEBUG(dbgs() << " (not critical-path)\n"); |
David Goodwin | 87d21b9 | 2009-11-13 19:52:48 +0000 | [diff] [blame] | 829 | continue; |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 830 | } else if (PassthruRegs.count(AntiDepReg) != 0) { |
| 831 | // If the anti-dep register liveness "passes-thru", then |
| 832 | // don't try to change it. It will be changed along with |
| 833 | // the use if required to break an earlier antidep. |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 834 | DEBUG(dbgs() << " (passthru)\n"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 835 | continue; |
| 836 | } else { |
| 837 | // No anti-dep breaking for implicit deps |
| 838 | MachineOperand *AntiDepOp = MI->findRegisterDefOperand(AntiDepReg); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 839 | assert(AntiDepOp != NULL && |
| 840 | "Can't find index for defined register operand"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 841 | if ((AntiDepOp == NULL) || AntiDepOp->isImplicit()) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 842 | DEBUG(dbgs() << " (implicit)\n"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 843 | continue; |
| 844 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 845 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 846 | // If the SUnit has other dependencies on the SUnit that |
| 847 | // it anti-depends on, don't bother breaking the |
| 848 | // anti-dependency since those edges would prevent such |
| 849 | // units from being scheduled past each other |
| 850 | // regardless. |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 851 | // |
| 852 | // Also, if there are dependencies on other SUnits with the |
| 853 | // same register as the anti-dependency, don't attempt to |
| 854 | // break it. |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 855 | for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 856 | PE = PathSU->Preds.end(); P != PE; ++P) { |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 857 | if (P->getSUnit() == NextSU ? |
| 858 | (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) : |
| 859 | (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) { |
| 860 | AntiDepReg = 0; |
| 861 | break; |
| 862 | } |
| 863 | } |
Dan Gohman | 66db3a0 | 2010-04-19 23:11:58 +0000 | [diff] [blame] | 864 | for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 865 | PE = PathSU->Preds.end(); P != PE; ++P) { |
| 866 | if ((P->getSUnit() == NextSU) && (P->getKind() != SDep::Anti) && |
| 867 | (P->getKind() != SDep::Output)) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 868 | DEBUG(dbgs() << " (real dependency)\n"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 869 | AntiDepReg = 0; |
| 870 | break; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 871 | } else if ((P->getSUnit() != NextSU) && |
| 872 | (P->getKind() == SDep::Data) && |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 873 | (P->getReg() == AntiDepReg)) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 874 | DEBUG(dbgs() << " (other dependency)\n"); |
David Goodwin | 557bbe6 | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 875 | AntiDepReg = 0; |
| 876 | break; |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 877 | } |
| 878 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 879 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 880 | if (AntiDepReg == 0) continue; |
| 881 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 882 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 883 | assert(AntiDepReg != 0); |
| 884 | if (AntiDepReg == 0) continue; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 885 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 886 | // Determine AntiDepReg's register group. |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 887 | const unsigned GroupIndex = State->GetGroup(AntiDepReg); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 888 | if (GroupIndex == 0) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 889 | DEBUG(dbgs() << " (zero group)\n"); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 890 | continue; |
| 891 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 892 | |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 893 | DEBUG(dbgs() << '\n'); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 894 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 895 | // Look for a suitable register to use to break the anti-dependence. |
| 896 | std::map<unsigned, unsigned> RenameMap; |
David Goodwin | 5409783 | 2009-11-05 01:19:35 +0000 | [diff] [blame] | 897 | if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) { |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 898 | DEBUG(dbgs() << "\tBreaking anti-dependence edge on " |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 899 | << TRI->getName(AntiDepReg) << ":"); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 900 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 901 | // Handle each group register... |
| 902 | for (std::map<unsigned, unsigned>::iterator |
| 903 | S = RenameMap.begin(), E = RenameMap.end(); S != E; ++S) { |
| 904 | unsigned CurrReg = S->first; |
| 905 | unsigned NewReg = S->second; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 906 | |
| 907 | DEBUG(dbgs() << " " << TRI->getName(CurrReg) << "->" << |
| 908 | TRI->getName(NewReg) << "(" << |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 909 | RegRefs.count(CurrReg) << " refs)"); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 910 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 911 | // Update the references to the old register CurrReg to |
| 912 | // refer to the new register NewReg. |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 913 | std::pair<std::multimap<unsigned, |
| 914 | AggressiveAntiDepState::RegisterReference>::iterator, |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 915 | std::multimap<unsigned, |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 916 | AggressiveAntiDepState::RegisterReference>::iterator> |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 917 | Range = RegRefs.equal_range(CurrReg); |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 918 | for (std::multimap<unsigned, |
| 919 | AggressiveAntiDepState::RegisterReference>::iterator |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 920 | Q = Range.first, QE = Range.second; Q != QE; ++Q) { |
| 921 | Q->second.Operand->setReg(NewReg); |
Jim Grosbach | 533934e | 2010-06-01 23:48:44 +0000 | [diff] [blame] | 922 | // If the SU for the instruction being updated has debug |
| 923 | // information related to the anti-dependency register, make |
| 924 | // sure to update that as well. |
| 925 | const SUnit *SU = MISUnitMap[Q->second.Operand->getParent()]; |
Jim Grosbach | 086723d | 2010-06-02 15:29:36 +0000 | [diff] [blame] | 926 | if (!SU) continue; |
Devang Patel | e29e8e1 | 2011-06-02 21:26:52 +0000 | [diff] [blame] | 927 | for (DbgValueVector::iterator DVI = DbgValues.begin(), |
| 928 | DVE = DbgValues.end(); DVI != DVE; ++DVI) |
| 929 | if (DVI->second == Q->second.Operand->getParent()) |
| 930 | UpdateDbgValue(DVI->first, AntiDepReg, NewReg); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 931 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 932 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 933 | // We just went back in time and modified history; the |
| 934 | // liveness information for CurrReg is now inconsistent. Set |
| 935 | // the state as if it were dead. |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 936 | State->UnionGroups(NewReg, 0); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 937 | RegRefs.erase(NewReg); |
| 938 | DefIndices[NewReg] = DefIndices[CurrReg]; |
| 939 | KillIndices[NewReg] = KillIndices[CurrReg]; |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 940 | |
David Goodwin | e10deca | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 941 | State->UnionGroups(CurrReg, 0); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 942 | RegRefs.erase(CurrReg); |
| 943 | DefIndices[CurrReg] = KillIndices[CurrReg]; |
| 944 | KillIndices[CurrReg] = ~0u; |
| 945 | assert(((KillIndices[CurrReg] == ~0u) != |
| 946 | (DefIndices[CurrReg] == ~0u)) && |
| 947 | "Kill and Def maps aren't consistent for AntiDepReg!"); |
| 948 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 949 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 950 | ++Broken; |
David Greene | 5393b25 | 2009-12-24 00:14:25 +0000 | [diff] [blame] | 951 | DEBUG(dbgs() << '\n'); |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 952 | } |
| 953 | } |
| 954 | } |
| 955 | |
| 956 | ScanInstruction(MI, Count); |
| 957 | } |
Jim Grosbach | 2973b57 | 2010-01-06 16:48:02 +0000 | [diff] [blame] | 958 | |
David Goodwin | 3487771 | 2009-10-26 19:32:42 +0000 | [diff] [blame] | 959 | return Broken; |
| 960 | } |