blob: 880a78fb5e1ca2b6739523d0694f87e6649c23a8 [file] [log] [blame]
Jim Grosbach2973b572010-01-06 16:48:02 +00001//===----- AggressiveAntiDepBreaker.cpp - Anti-dep breaker ----------------===//
David Goodwin34877712009-10-26 19:32:42 +00002//
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 Goodwin4de099d2009-11-03 20:57:50 +000017#define DEBUG_TYPE "post-RA-sched"
David Goodwin34877712009-10-26 19:32:42 +000018#include "AggressiveAntiDepBreaker.h"
19#include "llvm/CodeGen/MachineBasicBlock.h"
20#include "llvm/CodeGen/MachineFrameInfo.h"
21#include "llvm/CodeGen/MachineInstr.h"
Andrew Trick15252602012-06-06 20:29:31 +000022#include "llvm/CodeGen/RegisterClassInfo.h"
David Goodwin34877712009-10-26 19:32:42 +000023#include "llvm/Target/TargetInstrInfo.h"
24#include "llvm/Target/TargetMachine.h"
Evan Cheng46df4eb2010-06-16 07:35:02 +000025#include "llvm/Target/TargetInstrInfo.h"
Bill Wendling75a5b712010-07-15 06:05:18 +000026#include "llvm/Target/TargetRegisterInfo.h"
David Goodwine10deca2009-10-26 22:31:16 +000027#include "llvm/Support/CommandLine.h"
David Goodwin34877712009-10-26 19:32:42 +000028#include "llvm/Support/Debug.h"
29#include "llvm/Support/ErrorHandling.h"
30#include "llvm/Support/raw_ostream.h"
David Goodwin34877712009-10-26 19:32:42 +000031using namespace llvm;
32
David Goodwin3e72d302009-11-19 23:12:37 +000033// If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod
34static cl::opt<int>
35DebugDiv("agg-antidep-debugdiv",
Bob Wilson347fa3f2010-04-09 21:38:26 +000036 cl::desc("Debug control for aggressive anti-dep breaker"),
37 cl::init(0), cl::Hidden);
David Goodwin3e72d302009-11-19 23:12:37 +000038static cl::opt<int>
39DebugMod("agg-antidep-debugmod",
Bob Wilson347fa3f2010-04-09 21:38:26 +000040 cl::desc("Debug control for aggressive anti-dep breaker"),
41 cl::init(0), cl::Hidden);
David Goodwin3e72d302009-11-19 23:12:37 +000042
David Goodwin990d2852009-12-09 17:18:22 +000043AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs,
44 MachineBasicBlock *BB) :
Bill Wendling9c2a0342010-07-15 19:58:14 +000045 NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),
46 GroupNodeIndices(TargetRegs, 0),
47 KillIndices(TargetRegs, 0),
48 DefIndices(TargetRegs, 0)
49{
David Goodwin990d2852009-12-09 17:18:22 +000050 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 Goodwin34877712009-10-26 19:32:42 +000059}
60
Bill Wendlinge4a41472010-07-15 19:41:20 +000061unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) {
David Goodwin34877712009-10-26 19:32:42 +000062 unsigned Node = GroupNodeIndices[Reg];
63 while (GroupNodes[Node] != Node)
64 Node = GroupNodes[Node];
65
66 return Node;
67}
68
David Goodwin87d21b92009-11-13 19:52:48 +000069void AggressiveAntiDepState::GetGroupRegs(
70 unsigned Group,
71 std::vector<unsigned> &Regs,
72 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs)
David Goodwin34877712009-10-26 19:32:42 +000073{
David Goodwin990d2852009-12-09 17:18:22 +000074 for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {
David Goodwin87d21b92009-11-13 19:52:48 +000075 if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0))
David Goodwin34877712009-10-26 19:32:42 +000076 Regs.push_back(Reg);
77 }
78}
79
David Goodwine10deca2009-10-26 22:31:16 +000080unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1, unsigned Reg2)
David Goodwin34877712009-10-26 19:32:42 +000081{
82 assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!");
83 assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!");
Jim Grosbach2973b572010-01-06 16:48:02 +000084
David Goodwin34877712009-10-26 19:32:42 +000085 // find group for each register
86 unsigned Group1 = GetGroup(Reg1);
87 unsigned Group2 = GetGroup(Reg2);
Jim Grosbach2973b572010-01-06 16:48:02 +000088
David Goodwin34877712009-10-26 19:32:42 +000089 // 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 Grosbach2973b572010-01-06 16:48:02 +000095
David Goodwine10deca2009-10-26 22:31:16 +000096unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg)
David Goodwin34877712009-10-26 19:32:42 +000097{
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 Goodwine10deca2009-10-26 22:31:16 +0000107bool AggressiveAntiDepState::IsLive(unsigned Reg)
David Goodwin34877712009-10-26 19:32:42 +0000108{
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 Goodwine10deca2009-10-26 22:31:16 +0000114
115
116AggressiveAntiDepBreaker::
David Goodwin0855dee2009-11-10 00:15:47 +0000117AggressiveAntiDepBreaker(MachineFunction& MFi,
Jakob Stoklund Olesenfa796dd2011-06-16 21:56:21 +0000118 const RegisterClassInfo &RCI,
Evan Cheng5b1b44892011-07-01 21:01:15 +0000119 TargetSubtargetInfo::RegClassVector& CriticalPathRCs) :
David Goodwine10deca2009-10-26 22:31:16 +0000120 AntiDepBreaker(), MF(MFi),
121 MRI(MF.getRegInfo()),
Evan Cheng46df4eb2010-06-16 07:35:02 +0000122 TII(MF.getTarget().getInstrInfo()),
David Goodwine10deca2009-10-26 22:31:16 +0000123 TRI(MF.getTarget().getRegisterInfo()),
Jakob Stoklund Olesenfa796dd2011-06-16 21:56:21 +0000124 RegClassInfo(RCI),
David Goodwin557bbe62009-11-20 19:32:48 +0000125 State(NULL) {
David Goodwin87d21b92009-11-13 19:52:48 +0000126 /* 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 Grosbach2973b572010-01-06 16:48:02 +0000135
David Greene5393b252009-12-24 00:14:25 +0000136 DEBUG(dbgs() << "AntiDep Critical-Path Registers:");
Jim Grosbach2973b572010-01-06 16:48:02 +0000137 DEBUG(for (int r = CriticalPathSet.find_first(); r != -1;
David Goodwin87d21b92009-11-13 19:52:48 +0000138 r = CriticalPathSet.find_next(r))
David Greene5393b252009-12-24 00:14:25 +0000139 dbgs() << " " << TRI->getName(r));
140 DEBUG(dbgs() << '\n');
David Goodwine10deca2009-10-26 22:31:16 +0000141}
142
143AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() {
144 delete State;
David Goodwine10deca2009-10-26 22:31:16 +0000145}
146
147void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
148 assert(State == NULL);
David Goodwin990d2852009-12-09 17:18:22 +0000149 State = new AggressiveAntiDepState(TRI->getNumRegs(), BB);
David Goodwine10deca2009-10-26 22:31:16 +0000150
Evan Cheng5a96b3d2011-12-07 07:15:52 +0000151 bool IsReturnBlock = (!BB->empty() && BB->back().isReturn());
Bill Wendling38306d52010-07-15 18:43:09 +0000152 std::vector<unsigned> &KillIndices = State->GetKillIndices();
153 std::vector<unsigned> &DefIndices = State->GetDefIndices();
David Goodwine10deca2009-10-26 22:31:16 +0000154
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 Olesen396618b2012-06-01 23:28:30 +0000160 for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) {
161 unsigned Reg = *AI;
Jakob Stoklund Olesen597faa82010-12-14 23:23:15 +0000162 State->UnionGroups(Reg, 0);
163 KillIndices[Reg] = BB->size();
164 DefIndices[Reg] = ~0u;
David Goodwine10deca2009-10-26 22:31:16 +0000165 }
166 }
David Goodwine10deca2009-10-26 22:31:16 +0000167 }
168
Evan Cheng46df4eb2010-06-16 07:35:02 +0000169 // 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 Olesen396618b2012-06-01 23:28:30 +0000176 for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) {
177 unsigned Reg = *AI;
Jakob Stoklund Olesen597faa82010-12-14 23:23:15 +0000178 State->UnionGroups(Reg, 0);
179 KillIndices[Reg] = BB->size();
180 DefIndices[Reg] = ~0u;
Evan Cheng46df4eb2010-06-16 07:35:02 +0000181 }
182 }
183
David Goodwine10deca2009-10-26 22:31:16 +0000184 // 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 Topper015f2282012-03-04 03:33:22 +0000189 for (const uint16_t *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) {
David Goodwine10deca2009-10-26 22:31:16 +0000190 unsigned Reg = *I;
191 if (!IsReturnBlock && !Pristine.test(Reg)) continue;
Jakob Stoklund Olesen396618b2012-06-01 23:28:30 +0000192 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
193 unsigned AliasReg = *AI;
David Goodwine10deca2009-10-26 22:31:16 +0000194 State->UnionGroups(AliasReg, 0);
195 KillIndices[AliasReg] = BB->size();
196 DefIndices[AliasReg] = ~0u;
197 }
198 }
199}
200
201void AggressiveAntiDepBreaker::FinishBlock() {
202 delete State;
203 State = NULL;
David Goodwine10deca2009-10-26 22:31:16 +0000204}
205
206void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count,
Bob Wilson347fa3f2010-04-09 21:38:26 +0000207 unsigned InsertPosIndex) {
David Goodwine10deca2009-10-26 22:31:16 +0000208 assert(Count < InsertPosIndex && "Instruction index out of expected range!");
209
David Goodwin5b3c3082009-10-29 23:30:59 +0000210 std::set<unsigned> PassthruRegs;
211 GetPassthruRegs(MI, PassthruRegs);
212 PrescanInstruction(MI, Count, PassthruRegs);
213 ScanInstruction(MI, Count);
214
David Greene5393b252009-12-24 00:14:25 +0000215 DEBUG(dbgs() << "Observe: ");
David Goodwine10deca2009-10-26 22:31:16 +0000216 DEBUG(MI->dump());
David Greene5393b252009-12-24 00:14:25 +0000217 DEBUG(dbgs() << "\tRegs:");
David Goodwine10deca2009-10-26 22:31:16 +0000218
Bill Wendling38306d52010-07-15 18:43:09 +0000219 std::vector<unsigned> &DefIndices = State->GetDefIndices();
David Goodwin990d2852009-12-09 17:18:22 +0000220 for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) {
David Goodwine10deca2009-10-26 22:31:16 +0000221 // 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 Grosbach2973b572010-01-06 16:48:02 +0000229 dbgs() << " " << TRI->getName(Reg) << "=g" <<
David Goodwine10deca2009-10-26 22:31:16 +0000230 State->GetGroup(Reg) << "->g0(region live-out)");
231 State->UnionGroups(Reg, 0);
Jim Grosbach2973b572010-01-06 16:48:02 +0000232 } else if ((DefIndices[Reg] < InsertPosIndex)
233 && (DefIndices[Reg] >= Count)) {
David Goodwine10deca2009-10-26 22:31:16 +0000234 DefIndices[Reg] = Count;
235 }
236 }
David Greene5393b252009-12-24 00:14:25 +0000237 DEBUG(dbgs() << '\n');
David Goodwine10deca2009-10-26 22:31:16 +0000238}
239
David Goodwin34877712009-10-26 19:32:42 +0000240bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr *MI,
Bob Wilson347fa3f2010-04-09 21:38:26 +0000241 MachineOperand& MO)
David Goodwin34877712009-10-26 19:32:42 +0000242{
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
259void 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 Grosbach2973b572010-01-06 16:48:02 +0000264 if ((MO.isDef() && MI->isRegTiedToUseOperand(i)) ||
David Goodwin34877712009-10-26 19:32:42 +0000265 IsImplicitDefUse(MI, MO)) {
266 const unsigned Reg = MO.getReg();
267 PassthruRegs.insert(Reg);
Jakob Stoklund Olesen396618b2012-06-01 23:28:30 +0000268 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
269 PassthruRegs.insert(*SubRegs);
David Goodwin34877712009-10-26 19:32:42 +0000270 }
271 }
272}
273
David Goodwin557bbe62009-11-20 19:32:48 +0000274/// AntiDepEdges - Return in Edges the anti- and output- dependencies
275/// in SU that we want to consider for breaking.
Dan Gohman66db3a02010-04-19 23:11:58 +0000276static void AntiDepEdges(const SUnit *SU, std::vector<const SDep*>& Edges) {
David Goodwin557bbe62009-11-20 19:32:48 +0000277 SmallSet<unsigned, 4> RegSet;
Dan Gohman66db3a02010-04-19 23:11:58 +0000278 for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
David Goodwin34877712009-10-26 19:32:42 +0000279 P != PE; ++P) {
David Goodwin12dd99d2009-11-12 19:08:21 +0000280 if ((P->getKind() == SDep::Anti) || (P->getKind() == SDep::Output)) {
David Goodwin34877712009-10-26 19:32:42 +0000281 unsigned Reg = P->getReg();
David Goodwin557bbe62009-11-20 19:32:48 +0000282 if (RegSet.count(Reg) == 0) {
David Goodwin34877712009-10-26 19:32:42 +0000283 Edges.push_back(&*P);
David Goodwin557bbe62009-11-20 19:32:48 +0000284 RegSet.insert(Reg);
David Goodwin34877712009-10-26 19:32:42 +0000285 }
286 }
287 }
288}
289
David Goodwin87d21b92009-11-13 19:52:48 +0000290/// CriticalPathStep - Return the next SUnit after SU on the bottom-up
291/// critical path.
Dan Gohman66db3a02010-04-19 23:11:58 +0000292static const SUnit *CriticalPathStep(const SUnit *SU) {
293 const SDep *Next = 0;
David Goodwin87d21b92009-11-13 19:52:48 +0000294 unsigned NextDepth = 0;
295 // Find the predecessor edge with the greatest depth.
296 if (SU != 0) {
Dan Gohman66db3a02010-04-19 23:11:58 +0000297 for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
David Goodwin87d21b92009-11-13 19:52:48 +0000298 P != PE; ++P) {
Dan Gohman66db3a02010-04-19 23:11:58 +0000299 const SUnit *PredSU = P->getSUnit();
David Goodwin87d21b92009-11-13 19:52:48 +0000300 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 Goodwin67a8a7b2009-10-29 19:17:04 +0000315void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx,
Jim Grosbach2973b572010-01-06 16:48:02 +0000316 const char *tag,
317 const char *header,
David Goodwin3e72d302009-11-19 23:12:37 +0000318 const char *footer) {
Bill Wendling38306d52010-07-15 18:43:09 +0000319 std::vector<unsigned> &KillIndices = State->GetKillIndices();
320 std::vector<unsigned> &DefIndices = State->GetDefIndices();
Jim Grosbach2973b572010-01-06 16:48:02 +0000321 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
David Goodwin67a8a7b2009-10-29 19:17:04 +0000322 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 Goodwin3e72d302009-11-19 23:12:37 +0000329 DEBUG(if (header != NULL) {
David Greene5393b252009-12-24 00:14:25 +0000330 dbgs() << header << TRI->getName(Reg); header = NULL; });
331 DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag);
David Goodwin67a8a7b2009-10-29 19:17:04 +0000332 }
333 // Repeat for subregisters.
Jakob Stoklund Olesen396618b2012-06-01 23:28:30 +0000334 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
335 unsigned SubregReg = *SubRegs;
David Goodwin67a8a7b2009-10-29 19:17:04 +0000336 if (!State->IsLive(SubregReg)) {
337 KillIndices[SubregReg] = KillIdx;
338 DefIndices[SubregReg] = ~0u;
339 RegRefs.erase(SubregReg);
340 State->LeaveGroup(SubregReg);
David Goodwin3e72d302009-11-19 23:12:37 +0000341 DEBUG(if (header != NULL) {
David Greene5393b252009-12-24 00:14:25 +0000342 dbgs() << header << TRI->getName(Reg); header = NULL; });
343 DEBUG(dbgs() << " " << TRI->getName(SubregReg) << "->g" <<
David Goodwin67a8a7b2009-10-29 19:17:04 +0000344 State->GetGroup(SubregReg) << tag);
345 }
346 }
David Goodwin3e72d302009-11-19 23:12:37 +0000347
David Greene5393b252009-12-24 00:14:25 +0000348 DEBUG(if ((header == NULL) && (footer != NULL)) dbgs() << footer);
David Goodwin67a8a7b2009-10-29 19:17:04 +0000349}
350
Jim Grosbach2973b572010-01-06 16:48:02 +0000351void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI,
352 unsigned Count,
Bob Wilson347fa3f2010-04-09 21:38:26 +0000353 std::set<unsigned>& PassthruRegs) {
Bill Wendling38306d52010-07-15 18:43:09 +0000354 std::vector<unsigned> &DefIndices = State->GetDefIndices();
Jim Grosbach2973b572010-01-06 16:48:02 +0000355 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
David Goodwine10deca2009-10-26 22:31:16 +0000356 RegRefs = State->GetRegRefs();
357
David Goodwin67a8a7b2009-10-29 19:17:04 +0000358 // Handle dead defs by simulating a last-use of the register just
Chris Lattner7a2bdde2011-04-15 05:18:47 +0000359 // after the def. A dead def can occur because the def is truly
David Goodwin67a8a7b2009-10-29 19:17:04 +0000360 // 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 Goodwin34877712009-10-26 19:32:42 +0000363 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 Grosbach2973b572010-01-06 16:48:02 +0000368
David Goodwin3e72d302009-11-19 23:12:37 +0000369 HandleLastUse(Reg, Count + 1, "", "\tDead Def: ", "\n");
David Goodwin34877712009-10-26 19:32:42 +0000370 }
371
David Greene5393b252009-12-24 00:14:25 +0000372 DEBUG(dbgs() << "\tDef Groups:");
David Goodwin34877712009-10-26 19:32:42 +0000373 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 Grosbach2973b572010-01-06 16:48:02 +0000379 DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" << State->GetGroup(Reg));
David Goodwin34877712009-10-26 19:32:42 +0000380
David Goodwin67a8a7b2009-10-29 19:17:04 +0000381 // If MI's defs have a special allocation requirement, don't allow
David Goodwin34877712009-10-26 19:32:42 +0000382 // any def registers to be changed. Also assume all registers
383 // defined in a call must not be changed (ABI).
Evan Cheng5a96b3d2011-12-07 07:15:52 +0000384 if (MI->isCall() || MI->hasExtraDefRegAllocReq() ||
Evan Cheng46df4eb2010-06-16 07:35:02 +0000385 TII->isPredicated(MI)) {
David Greene5393b252009-12-24 00:14:25 +0000386 DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)");
David Goodwine10deca2009-10-26 22:31:16 +0000387 State->UnionGroups(Reg, 0);
David Goodwin34877712009-10-26 19:32:42 +0000388 }
389
390 // Any aliased that are live at this point are completely or
David Goodwin67a8a7b2009-10-29 19:17:04 +0000391 // partially defined here, so group those aliases with Reg.
Jakob Stoklund Olesen396618b2012-06-01 23:28:30 +0000392 for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) {
393 unsigned AliasReg = *AI;
David Goodwine10deca2009-10-26 22:31:16 +0000394 if (State->IsLive(AliasReg)) {
395 State->UnionGroups(Reg, AliasReg);
Jim Grosbach2973b572010-01-06 16:48:02 +0000396 DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via " <<
David Goodwin34877712009-10-26 19:32:42 +0000397 TRI->getName(AliasReg) << ")");
398 }
399 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000400
David Goodwin34877712009-10-26 19:32:42 +0000401 // Note register reference...
402 const TargetRegisterClass *RC = NULL;
403 if (i < MI->getDesc().getNumOperands())
Jakob Stoklund Olesen397fc482012-05-07 22:10:26 +0000404 RC = TII->getRegClass(MI->getDesc(), i, TRI, MF);
David Goodwine10deca2009-10-26 22:31:16 +0000405 AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
David Goodwin34877712009-10-26 19:32:42 +0000406 RegRefs.insert(std::make_pair(Reg, RR));
407 }
408
David Greene5393b252009-12-24 00:14:25 +0000409 DEBUG(dbgs() << '\n');
David Goodwin67a8a7b2009-10-29 19:17:04 +0000410
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 Goodwin3e72d302009-11-19 23:12:37 +0000418 // Ignore KILLs and passthru registers for liveness...
Chris Lattner518bb532010-02-09 19:54:29 +0000419 if (MI->isKill() || (PassthruRegs.count(Reg) != 0))
David Goodwin3e72d302009-11-19 23:12:37 +0000420 continue;
David Goodwin67a8a7b2009-10-29 19:17:04 +0000421
David Goodwin3e72d302009-11-19 23:12:37 +0000422 // Update def for Reg and aliases.
Jakob Stoklund Olesen396618b2012-06-01 23:28:30 +0000423 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
424 DefIndices[*AI] = Count;
David Goodwin67a8a7b2009-10-29 19:17:04 +0000425 }
David Goodwin34877712009-10-26 19:32:42 +0000426}
427
428void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI,
Bob Wilson347fa3f2010-04-09 21:38:26 +0000429 unsigned Count) {
David Greene5393b252009-12-24 00:14:25 +0000430 DEBUG(dbgs() << "\tUse Groups:");
Jim Grosbach2973b572010-01-06 16:48:02 +0000431 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
David Goodwine10deca2009-10-26 22:31:16 +0000432 RegRefs = State->GetRegRefs();
David Goodwin34877712009-10-26 19:32:42 +0000433
Evan Cheng46df4eb2010-06-16 07:35:02 +0000434 // 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 Cheng5a96b3d2011-12-07 07:15:52 +0000450 bool Special = MI->isCall() ||
451 MI->hasExtraSrcRegAllocReq() ||
Evan Cheng46df4eb2010-06-16 07:35:02 +0000452 TII->isPredicated(MI);
453
David Goodwin34877712009-10-26 19:32:42 +0000454 // 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 Grosbach2973b572010-01-06 16:48:02 +0000461
462 DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" <<
463 State->GetGroup(Reg));
David Goodwin34877712009-10-26 19:32:42 +0000464
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 Goodwin67a8a7b2009-10-29 19:17:04 +0000468 HandleLastUse(Reg, Count, "(last-use)");
David Goodwin34877712009-10-26 19:32:42 +0000469
Evan Cheng46df4eb2010-06-16 07:35:02 +0000470 if (Special) {
David Greene5393b252009-12-24 00:14:25 +0000471 DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)");
David Goodwine10deca2009-10-26 22:31:16 +0000472 State->UnionGroups(Reg, 0);
David Goodwin34877712009-10-26 19:32:42 +0000473 }
474
475 // Note register reference...
476 const TargetRegisterClass *RC = NULL;
477 if (i < MI->getDesc().getNumOperands())
Jakob Stoklund Olesen397fc482012-05-07 22:10:26 +0000478 RC = TII->getRegClass(MI->getDesc(), i, TRI, MF);
David Goodwine10deca2009-10-26 22:31:16 +0000479 AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
David Goodwin34877712009-10-26 19:32:42 +0000480 RegRefs.insert(std::make_pair(Reg, RR));
481 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000482
David Greene5393b252009-12-24 00:14:25 +0000483 DEBUG(dbgs() << '\n');
David Goodwin34877712009-10-26 19:32:42 +0000484
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 Lattner518bb532010-02-09 19:54:29 +0000487 if (MI->isKill()) {
David Greene5393b252009-12-24 00:14:25 +0000488 DEBUG(dbgs() << "\tKill Group:");
David Goodwin34877712009-10-26 19:32:42 +0000489
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 Grosbach2973b572010-01-06 16:48:02 +0000496
David Goodwin34877712009-10-26 19:32:42 +0000497 if (FirstReg != 0) {
David Greene5393b252009-12-24 00:14:25 +0000498 DEBUG(dbgs() << "=" << TRI->getName(Reg));
David Goodwine10deca2009-10-26 22:31:16 +0000499 State->UnionGroups(FirstReg, Reg);
David Goodwin34877712009-10-26 19:32:42 +0000500 } else {
David Greene5393b252009-12-24 00:14:25 +0000501 DEBUG(dbgs() << " " << TRI->getName(Reg));
David Goodwin34877712009-10-26 19:32:42 +0000502 FirstReg = Reg;
503 }
504 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000505
David Greene5393b252009-12-24 00:14:25 +0000506 DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n');
David Goodwin34877712009-10-26 19:32:42 +0000507 }
508}
509
510BitVector 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 Grosbach2973b572010-01-06 16:48:02 +0000517 std::pair<std::multimap<unsigned,
David Goodwine10deca2009-10-26 22:31:16 +0000518 AggressiveAntiDepState::RegisterReference>::iterator,
519 std::multimap<unsigned,
520 AggressiveAntiDepState::RegisterReference>::iterator>
521 Range = State->GetRegRefs().equal_range(Reg);
Jim Grosbach2973b572010-01-06 16:48:02 +0000522 for (std::multimap<unsigned,
523 AggressiveAntiDepState::RegisterReference>::iterator Q = Range.first,
524 QE = Range.second; Q != QE; ++Q) {
David Goodwin34877712009-10-26 19:32:42 +0000525 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 Greene5393b252009-12-24 00:14:25 +0000536 DEBUG(dbgs() << " " << RC->getName());
David Goodwin34877712009-10-26 19:32:42 +0000537 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000538
David Goodwin34877712009-10-26 19:32:42 +0000539 return BV;
Jim Grosbach2973b572010-01-06 16:48:02 +0000540}
David Goodwin34877712009-10-26 19:32:42 +0000541
542bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
David Goodwin54097832009-11-05 01:19:35 +0000543 unsigned AntiDepGroupIndex,
544 RenameOrderType& RenameOrder,
545 std::map<unsigned, unsigned> &RenameMap) {
Bill Wendling38306d52010-07-15 18:43:09 +0000546 std::vector<unsigned> &KillIndices = State->GetKillIndices();
547 std::vector<unsigned> &DefIndices = State->GetDefIndices();
Jim Grosbach2973b572010-01-06 16:48:02 +0000548 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
David Goodwine10deca2009-10-26 22:31:16 +0000549 RegRefs = State->GetRegRefs();
550
David Goodwin87d21b92009-11-13 19:52:48 +0000551 // 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 Goodwin34877712009-10-26 19:32:42 +0000554 std::vector<unsigned> Regs;
David Goodwin87d21b92009-11-13 19:52:48 +0000555 State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs);
David Goodwin34877712009-10-26 19:32:42 +0000556 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 Grosbach2973b572010-01-06 16:48:02 +0000563 DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex
564 << ":\n");
David Goodwin34877712009-10-26 19:32:42 +0000565 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 Greene5393b252009-12-24 00:14:25 +0000574 DEBUG(dbgs() << "\t\t" << TRI->getName(Reg) << ":");
Jim Grosbach2973b572010-01-06 16:48:02 +0000575
David Goodwin34877712009-10-26 19:32:42 +0000576 BitVector BV = GetRenameRegisters(Reg);
577 RenameRegisterMap.insert(std::pair<unsigned, BitVector>(Reg, BV));
578
David Greene5393b252009-12-24 00:14:25 +0000579 DEBUG(dbgs() << " ::");
David Goodwin34877712009-10-26 19:32:42 +0000580 DEBUG(for (int r = BV.find_first(); r != -1; r = BV.find_next(r))
David Greene5393b252009-12-24 00:14:25 +0000581 dbgs() << " " << TRI->getName(r));
582 DEBUG(dbgs() << "\n");
David Goodwin34877712009-10-26 19:32:42 +0000583 }
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 Goodwin00621ef2009-11-20 23:33:54 +0000596#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 Grosbach2973b572010-01-06 16:48:02 +0000602
David Greene5393b252009-12-24 00:14:25 +0000603 dbgs() << "*** Performing rename " << TRI->getName(SuperReg) <<
David Goodwin00621ef2009-11-20 23:33:54 +0000604 " for debug ***\n";
605 }
606#endif
607
David Goodwin54097832009-11-05 01:19:35 +0000608 // 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 Espindola7e1b5662010-07-12 02:55:34 +0000612
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 Grosbach2973b572010-01-06 16:48:02 +0000616 const TargetRegisterClass *SuperRC =
Rafael Espindola7e1b5662010-07-12 02:55:34 +0000617 TRI->getMinimalPhysRegClass(SuperReg, MVT::Other);
Jim Grosbach2973b572010-01-06 16:48:02 +0000618
Jakob Stoklund Olesen39b5c0c2012-11-29 03:34:17 +0000619 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC);
Jakob Stoklund Olesenfa796dd2011-06-16 21:56:21 +0000620 if (Order.empty()) {
David Greene5393b252009-12-24 00:14:25 +0000621 DEBUG(dbgs() << "\tEmpty Super Regclass!!\n");
David Goodwin54097832009-11-05 01:19:35 +0000622 return false;
623 }
624
David Greene5393b252009-12-24 00:14:25 +0000625 DEBUG(dbgs() << "\tFind Registers:");
David Goodwin3e72d302009-11-19 23:12:37 +0000626
David Goodwin54097832009-11-05 01:19:35 +0000627 if (RenameOrder.count(SuperRC) == 0)
Jakob Stoklund Olesenfa796dd2011-06-16 21:56:21 +0000628 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size()));
David Goodwin54097832009-11-05 01:19:35 +0000629
Jakob Stoklund Olesenfa796dd2011-06-16 21:56:21 +0000630 unsigned OrigR = RenameOrder[SuperRC];
631 unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR);
632 unsigned R = OrigR;
David Goodwin54097832009-11-05 01:19:35 +0000633 do {
Jakob Stoklund Olesenfa796dd2011-06-16 21:56:21 +0000634 if (R == 0) R = Order.size();
David Goodwin54097832009-11-05 01:19:35 +0000635 --R;
Jakob Stoklund Olesenfa796dd2011-06-16 21:56:21 +0000636 const unsigned NewSuperReg = Order[R];
Jim Grosbach9b041c92010-09-02 17:12:55 +0000637 // Don't consider non-allocatable registers
Jakob Stoklund Olesen14d1dd92012-10-15 22:41:03 +0000638 if (!MRI.isAllocatable(NewSuperReg)) continue;
David Goodwin34877712009-10-26 19:32:42 +0000639 // Don't replace a register with itself.
David Goodwin00621ef2009-11-20 23:33:54 +0000640 if (NewSuperReg == SuperReg) continue;
Jim Grosbach2973b572010-01-06 16:48:02 +0000641
David Greene5393b252009-12-24 00:14:25 +0000642 DEBUG(dbgs() << " [" << TRI->getName(NewSuperReg) << ':');
David Goodwin00621ef2009-11-20 23:33:54 +0000643 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 Goodwin34877712009-10-26 19:32:42 +0000657 }
David Goodwin00621ef2009-11-20 23:33:54 +0000658
David Greene5393b252009-12-24 00:14:25 +0000659 DEBUG(dbgs() << " " << TRI->getName(NewReg));
Jim Grosbach2973b572010-01-06 16:48:02 +0000660
David Goodwin00621ef2009-11-20 23:33:54 +0000661 // Check if Reg can be renamed to NewReg.
662 BitVector BV = RenameRegisterMap[Reg];
663 if (!BV.test(NewReg)) {
David Greene5393b252009-12-24 00:14:25 +0000664 DEBUG(dbgs() << "(no rename)");
David Goodwin00621ef2009-11-20 23:33:54 +0000665 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 Greene5393b252009-12-24 00:14:25 +0000673 DEBUG(dbgs() << "(live)");
David Goodwin00621ef2009-11-20 23:33:54 +0000674 goto next_super_reg;
675 } else {
676 bool found = false;
Jakob Stoklund Olesen396618b2012-06-01 23:28:30 +0000677 for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) {
678 unsigned AliasReg = *AI;
Jim Grosbach2973b572010-01-06 16:48:02 +0000679 if (State->IsLive(AliasReg) ||
680 (KillIndices[Reg] > DefIndices[AliasReg])) {
David Greene5393b252009-12-24 00:14:25 +0000681 DEBUG(dbgs() << "(alias " << TRI->getName(AliasReg) << " live)");
David Goodwin00621ef2009-11-20 23:33:54 +0000682 found = true;
683 break;
684 }
685 }
686 if (found)
687 goto next_super_reg;
688 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000689
David Goodwin00621ef2009-11-20 23:33:54 +0000690 // Record that 'Reg' can be renamed to 'NewReg'.
691 RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg));
David Goodwin34877712009-10-26 19:32:42 +0000692 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000693
David Goodwin00621ef2009-11-20 23:33:54 +0000694 // 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 Greene5393b252009-12-24 00:14:25 +0000698 DEBUG(dbgs() << "]\n");
David Goodwin00621ef2009-11-20 23:33:54 +0000699 return true;
700
701 next_super_reg:
David Greene5393b252009-12-24 00:14:25 +0000702 DEBUG(dbgs() << ']');
David Goodwin54097832009-11-05 01:19:35 +0000703 } while (R != EndR);
David Goodwin34877712009-10-26 19:32:42 +0000704
David Greene5393b252009-12-24 00:14:25 +0000705 DEBUG(dbgs() << '\n');
David Goodwin34877712009-10-26 19:32:42 +0000706
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 Goodwine10deca2009-10-26 22:31:16 +0000714unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(
Dan Gohman66db3a02010-04-19 23:11:58 +0000715 const std::vector<SUnit>& SUnits,
716 MachineBasicBlock::iterator Begin,
717 MachineBasicBlock::iterator End,
Devang Patele29e8e12011-06-02 21:26:52 +0000718 unsigned InsertPosIndex,
719 DbgValueVector &DbgValues) {
720
Bill Wendling38306d52010-07-15 18:43:09 +0000721 std::vector<unsigned> &KillIndices = State->GetKillIndices();
722 std::vector<unsigned> &DefIndices = State->GetDefIndices();
Jim Grosbach2973b572010-01-06 16:48:02 +0000723 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
David Goodwine10deca2009-10-26 22:31:16 +0000724 RegRefs = State->GetRegRefs();
725
David Goodwin34877712009-10-26 19:32:42 +0000726 // The code below assumes that there is at least one instruction,
727 // so just duck out immediately if the block is empty.
David Goodwin4de099d2009-11-03 20:57:50 +0000728 if (SUnits.empty()) return 0;
Jim Grosbach2973b572010-01-06 16:48:02 +0000729
David Goodwin54097832009-11-05 01:19:35 +0000730 // For each regclass the next register to use for renaming.
731 RenameOrderType RenameOrder;
David Goodwin34877712009-10-26 19:32:42 +0000732
733 // ...need a map from MI to SUnit.
Dan Gohman66db3a02010-04-19 23:11:58 +0000734 std::map<MachineInstr *, const SUnit *> MISUnitMap;
David Goodwin34877712009-10-26 19:32:42 +0000735 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
Dan Gohman66db3a02010-04-19 23:11:58 +0000736 const SUnit *SU = &SUnits[i];
737 MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(SU->getInstr(),
738 SU));
David Goodwin34877712009-10-26 19:32:42 +0000739 }
740
David Goodwin87d21b92009-11-13 19:52:48 +0000741 // 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 Gohman66db3a02010-04-19 23:11:58 +0000744 const SUnit *CriticalPathSU = 0;
David Goodwin87d21b92009-11-13 19:52:48 +0000745 MachineInstr *CriticalPathMI = 0;
746 if (CriticalPathSet.any()) {
747 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
Dan Gohman66db3a02010-04-19 23:11:58 +0000748 const SUnit *SU = &SUnits[i];
Jim Grosbach2973b572010-01-06 16:48:02 +0000749 if (!CriticalPathSU ||
750 ((SU->getDepth() + SU->Latency) >
David Goodwin87d21b92009-11-13 19:52:48 +0000751 (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) {
752 CriticalPathSU = SU;
753 }
754 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000755
David Goodwin87d21b92009-11-13 19:52:48 +0000756 CriticalPathMI = CriticalPathSU->getInstr();
757 }
758
Jim Grosbach2973b572010-01-06 16:48:02 +0000759#ifndef NDEBUG
David Greene5393b252009-12-24 00:14:25 +0000760 DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n");
761 DEBUG(dbgs() << "Available regs:");
David Goodwin557bbe62009-11-20 19:32:48 +0000762 for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
763 if (!State->IsLive(Reg))
David Greene5393b252009-12-24 00:14:25 +0000764 DEBUG(dbgs() << " " << TRI->getName(Reg));
David Goodwin34877712009-10-26 19:32:42 +0000765 }
David Greene5393b252009-12-24 00:14:25 +0000766 DEBUG(dbgs() << '\n');
David Goodwin34877712009-10-26 19:32:42 +0000767#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 Finkel504d1d22012-01-16 22:53:41 +0000778 if (MI->isDebugValue())
779 continue;
780
David Greene5393b252009-12-24 00:14:25 +0000781 DEBUG(dbgs() << "Anti: ");
David Goodwin34877712009-10-26 19:32:42 +0000782 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 Grosbach2973b572010-01-06 16:48:02 +0000789
David Goodwin557bbe62009-11-20 19:32:48 +0000790 // The dependence edges that represent anti- and output-
David Goodwin87d21b92009-11-13 19:52:48 +0000791 // dependencies that are candidates for breaking.
Dan Gohman66db3a02010-04-19 23:11:58 +0000792 std::vector<const SDep *> Edges;
793 const SUnit *PathSU = MISUnitMap[MI];
David Goodwin557bbe62009-11-20 19:32:48 +0000794 AntiDepEdges(PathSU, Edges);
David Goodwin87d21b92009-11-13 19:52:48 +0000795
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 Grosbach2973b572010-01-06 16:48:02 +0000802 } else {
David Goodwin87d21b92009-11-13 19:52:48 +0000803 ExcludeRegs = &CriticalPathSet;
804 }
805
David Goodwin34877712009-10-26 19:32:42 +0000806 // Ignore KILL instructions (they form a group in ScanInstruction
807 // but don't cause any anti-dependence breaking themselves)
Chris Lattner518bb532010-02-09 19:54:29 +0000808 if (!MI->isKill()) {
David Goodwin34877712009-10-26 19:32:42 +0000809 // Attempt to break each anti-dependency...
810 for (unsigned i = 0, e = Edges.size(); i != e; ++i) {
Dan Gohman66db3a02010-04-19 23:11:58 +0000811 const SDep *Edge = Edges[i];
David Goodwin34877712009-10-26 19:32:42 +0000812 SUnit *NextSU = Edge->getSUnit();
Jim Grosbach2973b572010-01-06 16:48:02 +0000813
David Goodwin12dd99d2009-11-12 19:08:21 +0000814 if ((Edge->getKind() != SDep::Anti) &&
815 (Edge->getKind() != SDep::Output)) continue;
Jim Grosbach2973b572010-01-06 16:48:02 +0000816
David Goodwin34877712009-10-26 19:32:42 +0000817 unsigned AntiDepReg = Edge->getReg();
David Greene5393b252009-12-24 00:14:25 +0000818 DEBUG(dbgs() << "\tAntidep reg: " << TRI->getName(AntiDepReg));
David Goodwin34877712009-10-26 19:32:42 +0000819 assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
Jim Grosbach2973b572010-01-06 16:48:02 +0000820
Jakob Stoklund Olesen14d1dd92012-10-15 22:41:03 +0000821 if (!MRI.isAllocatable(AntiDepReg)) {
David Goodwin34877712009-10-26 19:32:42 +0000822 // Don't break anti-dependencies on non-allocatable registers.
David Greene5393b252009-12-24 00:14:25 +0000823 DEBUG(dbgs() << " (non-allocatable)\n");
David Goodwin34877712009-10-26 19:32:42 +0000824 continue;
David Goodwin87d21b92009-11-13 19:52:48 +0000825 } 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 Greene5393b252009-12-24 00:14:25 +0000828 DEBUG(dbgs() << " (not critical-path)\n");
David Goodwin87d21b92009-11-13 19:52:48 +0000829 continue;
David Goodwin34877712009-10-26 19:32:42 +0000830 } 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 Greene5393b252009-12-24 00:14:25 +0000834 DEBUG(dbgs() << " (passthru)\n");
David Goodwin34877712009-10-26 19:32:42 +0000835 continue;
836 } else {
837 // No anti-dep breaking for implicit deps
838 MachineOperand *AntiDepOp = MI->findRegisterDefOperand(AntiDepReg);
Jim Grosbach2973b572010-01-06 16:48:02 +0000839 assert(AntiDepOp != NULL &&
840 "Can't find index for defined register operand");
David Goodwin34877712009-10-26 19:32:42 +0000841 if ((AntiDepOp == NULL) || AntiDepOp->isImplicit()) {
David Greene5393b252009-12-24 00:14:25 +0000842 DEBUG(dbgs() << " (implicit)\n");
David Goodwin34877712009-10-26 19:32:42 +0000843 continue;
844 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000845
David Goodwin34877712009-10-26 19:32:42 +0000846 // 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 Goodwin557bbe62009-11-20 19:32:48 +0000851 //
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 Gohman66db3a02010-04-19 23:11:58 +0000855 for (SUnit::const_pred_iterator P = PathSU->Preds.begin(),
David Goodwin34877712009-10-26 19:32:42 +0000856 PE = PathSU->Preds.end(); P != PE; ++P) {
David Goodwin557bbe62009-11-20 19:32:48 +0000857 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 Gohman66db3a02010-04-19 23:11:58 +0000864 for (SUnit::const_pred_iterator P = PathSU->Preds.begin(),
David Goodwin557bbe62009-11-20 19:32:48 +0000865 PE = PathSU->Preds.end(); P != PE; ++P) {
866 if ((P->getSUnit() == NextSU) && (P->getKind() != SDep::Anti) &&
867 (P->getKind() != SDep::Output)) {
David Greene5393b252009-12-24 00:14:25 +0000868 DEBUG(dbgs() << " (real dependency)\n");
David Goodwin34877712009-10-26 19:32:42 +0000869 AntiDepReg = 0;
870 break;
Jim Grosbach2973b572010-01-06 16:48:02 +0000871 } else if ((P->getSUnit() != NextSU) &&
872 (P->getKind() == SDep::Data) &&
David Goodwin557bbe62009-11-20 19:32:48 +0000873 (P->getReg() == AntiDepReg)) {
David Greene5393b252009-12-24 00:14:25 +0000874 DEBUG(dbgs() << " (other dependency)\n");
David Goodwin557bbe62009-11-20 19:32:48 +0000875 AntiDepReg = 0;
876 break;
David Goodwin34877712009-10-26 19:32:42 +0000877 }
878 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000879
David Goodwin34877712009-10-26 19:32:42 +0000880 if (AntiDepReg == 0) continue;
881 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000882
David Goodwin34877712009-10-26 19:32:42 +0000883 assert(AntiDepReg != 0);
884 if (AntiDepReg == 0) continue;
Jim Grosbach2973b572010-01-06 16:48:02 +0000885
David Goodwin34877712009-10-26 19:32:42 +0000886 // Determine AntiDepReg's register group.
David Goodwine10deca2009-10-26 22:31:16 +0000887 const unsigned GroupIndex = State->GetGroup(AntiDepReg);
David Goodwin34877712009-10-26 19:32:42 +0000888 if (GroupIndex == 0) {
David Greene5393b252009-12-24 00:14:25 +0000889 DEBUG(dbgs() << " (zero group)\n");
David Goodwin34877712009-10-26 19:32:42 +0000890 continue;
891 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000892
David Greene5393b252009-12-24 00:14:25 +0000893 DEBUG(dbgs() << '\n');
Jim Grosbach2973b572010-01-06 16:48:02 +0000894
David Goodwin34877712009-10-26 19:32:42 +0000895 // Look for a suitable register to use to break the anti-dependence.
896 std::map<unsigned, unsigned> RenameMap;
David Goodwin54097832009-11-05 01:19:35 +0000897 if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) {
David Greene5393b252009-12-24 00:14:25 +0000898 DEBUG(dbgs() << "\tBreaking anti-dependence edge on "
David Goodwin34877712009-10-26 19:32:42 +0000899 << TRI->getName(AntiDepReg) << ":");
Jim Grosbach2973b572010-01-06 16:48:02 +0000900
David Goodwin34877712009-10-26 19:32:42 +0000901 // 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 Grosbach2973b572010-01-06 16:48:02 +0000906
907 DEBUG(dbgs() << " " << TRI->getName(CurrReg) << "->" <<
908 TRI->getName(NewReg) << "(" <<
David Goodwin34877712009-10-26 19:32:42 +0000909 RegRefs.count(CurrReg) << " refs)");
Jim Grosbach2973b572010-01-06 16:48:02 +0000910
David Goodwin34877712009-10-26 19:32:42 +0000911 // Update the references to the old register CurrReg to
912 // refer to the new register NewReg.
Jim Grosbach2973b572010-01-06 16:48:02 +0000913 std::pair<std::multimap<unsigned,
914 AggressiveAntiDepState::RegisterReference>::iterator,
David Goodwine10deca2009-10-26 22:31:16 +0000915 std::multimap<unsigned,
Jim Grosbach2973b572010-01-06 16:48:02 +0000916 AggressiveAntiDepState::RegisterReference>::iterator>
David Goodwin34877712009-10-26 19:32:42 +0000917 Range = RegRefs.equal_range(CurrReg);
Jim Grosbach2973b572010-01-06 16:48:02 +0000918 for (std::multimap<unsigned,
919 AggressiveAntiDepState::RegisterReference>::iterator
David Goodwin34877712009-10-26 19:32:42 +0000920 Q = Range.first, QE = Range.second; Q != QE; ++Q) {
921 Q->second.Operand->setReg(NewReg);
Jim Grosbach533934e2010-06-01 23:48:44 +0000922 // 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 Grosbach086723d2010-06-02 15:29:36 +0000926 if (!SU) continue;
Devang Patele29e8e12011-06-02 21:26:52 +0000927 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 Goodwin34877712009-10-26 19:32:42 +0000931 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000932
David Goodwin34877712009-10-26 19:32:42 +0000933 // 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 Goodwine10deca2009-10-26 22:31:16 +0000936 State->UnionGroups(NewReg, 0);
David Goodwin34877712009-10-26 19:32:42 +0000937 RegRefs.erase(NewReg);
938 DefIndices[NewReg] = DefIndices[CurrReg];
939 KillIndices[NewReg] = KillIndices[CurrReg];
Jim Grosbach2973b572010-01-06 16:48:02 +0000940
David Goodwine10deca2009-10-26 22:31:16 +0000941 State->UnionGroups(CurrReg, 0);
David Goodwin34877712009-10-26 19:32:42 +0000942 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 Grosbach2973b572010-01-06 16:48:02 +0000949
David Goodwin34877712009-10-26 19:32:42 +0000950 ++Broken;
David Greene5393b252009-12-24 00:14:25 +0000951 DEBUG(dbgs() << '\n');
David Goodwin34877712009-10-26 19:32:42 +0000952 }
953 }
954 }
955
956 ScanInstruction(MI, Count);
957 }
Jim Grosbach2973b572010-01-06 16:48:02 +0000958
David Goodwin34877712009-10-26 19:32:42 +0000959 return Broken;
960}