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