blob: d02aa6fe601a127d578b77fb7b706471218c0ae5 [file] [log] [blame]
Chris Lattnerc4ce73f2008-01-04 07:36:53 +00001//===-- MachineSink.cpp - Sinking for machine instructions ----------------===//
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//
Bill Wendling05c68372010-06-02 23:04:26 +000010// This pass moves instructions into successor blocks when possible, so that
Dan Gohmana5225ad2009-08-05 01:19:01 +000011// they aren't executed on paths where their results aren't needed.
12//
13// This pass is not intended to be a replacement or a complete alternative
14// for an LLVM-IR-level sinking pass. It is only designed to sink simple
15// constructs that are not exposed before lowering and instruction selection.
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000016//
17//===----------------------------------------------------------------------===//
18
19#define DEBUG_TYPE "machine-sink"
20#include "llvm/CodeGen/Passes.h"
21#include "llvm/CodeGen/MachineRegisterInfo.h"
22#include "llvm/CodeGen/MachineDominators.h"
Jakob Stoklund Olesen626f3d72010-04-15 23:41:02 +000023#include "llvm/CodeGen/MachineLoopInfo.h"
Dan Gohmana70dca12009-10-09 23:27:56 +000024#include "llvm/Analysis/AliasAnalysis.h"
Dan Gohman6f0d0242008-02-10 18:45:23 +000025#include "llvm/Target/TargetRegisterInfo.h"
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000026#include "llvm/Target/TargetInstrInfo.h"
27#include "llvm/Target/TargetMachine.h"
Evan Cheng6edb0ea2010-09-17 22:28:18 +000028#include "llvm/ADT/SmallSet.h"
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000029#include "llvm/ADT/Statistic.h"
Evan Cheng4dc301a2010-08-19 17:33:11 +000030#include "llvm/Support/CommandLine.h"
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000031#include "llvm/Support/Debug.h"
Bill Wendling1e973aa2009-08-22 20:26:23 +000032#include "llvm/Support/raw_ostream.h"
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000033using namespace llvm;
34
Andrew Trick1df91b02012-02-08 21:22:43 +000035static cl::opt<bool>
Evan Cheng4dc301a2010-08-19 17:33:11 +000036SplitEdges("machine-sink-split",
37 cl::desc("Split critical edges during machine sinking"),
Evan Cheng44be1a82010-09-20 22:52:00 +000038 cl::init(true), cl::Hidden);
Evan Cheng4dc301a2010-08-19 17:33:11 +000039
Evan Cheng6edb0ea2010-09-17 22:28:18 +000040STATISTIC(NumSunk, "Number of machine instructions sunk");
41STATISTIC(NumSplit, "Number of critical edges split");
42STATISTIC(NumCoalesces, "Number of copies coalesced");
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000043
44namespace {
Nick Lewycky6726b6d2009-10-25 06:33:48 +000045 class MachineSinking : public MachineFunctionPass {
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000046 const TargetInstrInfo *TII;
Dan Gohman19778e72009-09-25 22:53:29 +000047 const TargetRegisterInfo *TRI;
Evan Cheng6edb0ea2010-09-17 22:28:18 +000048 MachineRegisterInfo *MRI; // Machine register information
Dan Gohmana5225ad2009-08-05 01:19:01 +000049 MachineDominatorTree *DT; // Machine dominator tree
Jakob Stoklund Olesen626f3d72010-04-15 23:41:02 +000050 MachineLoopInfo *LI;
Dan Gohmana70dca12009-10-09 23:27:56 +000051 AliasAnalysis *AA;
Dan Gohman45094e32009-09-26 02:34:00 +000052 BitVector AllocatableSet; // Which physregs are allocatable?
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000053
Evan Cheng6edb0ea2010-09-17 22:28:18 +000054 // Remember which edges have been considered for breaking.
55 SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8>
56 CEBCandidates;
57
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000058 public:
59 static char ID; // Pass identification
Owen Anderson081c34b2010-10-19 17:21:58 +000060 MachineSinking() : MachineFunctionPass(ID) {
61 initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
62 }
Jim Grosbach6ee358b2010-06-03 23:49:57 +000063
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000064 virtual bool runOnMachineFunction(MachineFunction &MF);
Jim Grosbach6ee358b2010-06-03 23:49:57 +000065
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000066 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
Dan Gohman845012e2009-07-31 23:37:33 +000067 AU.setPreservesCFG();
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000068 MachineFunctionPass::getAnalysisUsage(AU);
Dan Gohmana70dca12009-10-09 23:27:56 +000069 AU.addRequired<AliasAnalysis>();
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000070 AU.addRequired<MachineDominatorTree>();
Jakob Stoklund Olesen626f3d72010-04-15 23:41:02 +000071 AU.addRequired<MachineLoopInfo>();
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000072 AU.addPreserved<MachineDominatorTree>();
Jakob Stoklund Olesen626f3d72010-04-15 23:41:02 +000073 AU.addPreserved<MachineLoopInfo>();
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000074 }
Evan Cheng6edb0ea2010-09-17 22:28:18 +000075
76 virtual void releaseMemory() {
77 CEBCandidates.clear();
78 }
79
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000080 private:
81 bool ProcessBlock(MachineBasicBlock &MBB);
Evan Cheng6edb0ea2010-09-17 22:28:18 +000082 bool isWorthBreakingCriticalEdge(MachineInstr *MI,
83 MachineBasicBlock *From,
84 MachineBasicBlock *To);
85 MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI,
86 MachineBasicBlock *From,
87 MachineBasicBlock *To,
Evan Cheng7af6dc42010-09-20 19:12:55 +000088 bool BreakPHIEdge);
Chris Lattneraad193a2008-01-12 00:17:41 +000089 bool SinkInstruction(MachineInstr *MI, bool &SawStore);
Evan Chengc3439ad2010-08-18 23:09:25 +000090 bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
Evan Cheng6edb0ea2010-09-17 22:28:18 +000091 MachineBasicBlock *DefMBB,
Evan Cheng7af6dc42010-09-20 19:12:55 +000092 bool &BreakPHIEdge, bool &LocalUse) const;
Devang Patel52111342011-12-14 23:20:38 +000093 MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB,
94 bool &BreakPHIEdge);
Andrew Trick1df91b02012-02-08 21:22:43 +000095 bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI,
Devang Patel52111342011-12-14 23:20:38 +000096 MachineBasicBlock *MBB,
97 MachineBasicBlock *SuccToSinkTo);
Devang Patele265bcf2011-12-08 21:48:01 +000098
Evan Cheng6edb0ea2010-09-17 22:28:18 +000099 bool PerformTrivialForwardCoalescing(MachineInstr *MI,
100 MachineBasicBlock *MBB);
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000101 };
Manman Ren53b59d12012-07-31 18:10:39 +0000102
103 // SuccessorSorter - Sort Successors according to their loop depth.
104 struct SuccessorSorter {
105 SuccessorSorter(MachineLoopInfo *LoopInfo) : LI(LoopInfo) {}
106 bool operator()(const MachineBasicBlock *LHS,
107 const MachineBasicBlock *RHS) const {
108 return LI->getLoopDepth(LHS) < LI->getLoopDepth(RHS);
109 }
110 MachineLoopInfo *LI;
111 };
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000112} // end anonymous namespace
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000113
Dan Gohman844731a2008-05-13 00:00:25 +0000114char MachineSinking::ID = 0;
Andrew Trick1dd8c852012-02-08 21:23:13 +0000115char &llvm::MachineSinkingID = MachineSinking::ID;
Owen Anderson2ab36d32010-10-12 19:48:12 +0000116INITIALIZE_PASS_BEGIN(MachineSinking, "machine-sink",
117 "Machine code sinking", false, false)
118INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
119INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
120INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
121INITIALIZE_PASS_END(MachineSinking, "machine-sink",
Owen Andersonce665bd2010-10-07 22:25:06 +0000122 "Machine code sinking", false, false)
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000123
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000124bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI,
125 MachineBasicBlock *MBB) {
126 if (!MI->isCopy())
127 return false;
128
129 unsigned SrcReg = MI->getOperand(1).getReg();
130 unsigned DstReg = MI->getOperand(0).getReg();
131 if (!TargetRegisterInfo::isVirtualRegister(SrcReg) ||
132 !TargetRegisterInfo::isVirtualRegister(DstReg) ||
133 !MRI->hasOneNonDBGUse(SrcReg))
134 return false;
135
136 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
137 const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
138 if (SRC != DRC)
139 return false;
140
141 MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
142 if (DefMI->isCopyLike())
143 return false;
144 DEBUG(dbgs() << "Coalescing: " << *DefMI);
145 DEBUG(dbgs() << "*** to: " << *MI);
146 MRI->replaceRegWith(DstReg, SrcReg);
147 MI->eraseFromParent();
148 ++NumCoalesces;
149 return true;
150}
151
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000152/// AllUsesDominatedByBlock - Return true if all uses of the specified register
Evan Chengc3439ad2010-08-18 23:09:25 +0000153/// occur in blocks dominated by the specified block. If any use is in the
154/// definition block, then return false since it is never legal to move def
155/// after uses.
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000156bool
157MachineSinking::AllUsesDominatedByBlock(unsigned Reg,
158 MachineBasicBlock *MBB,
159 MachineBasicBlock *DefMBB,
Evan Cheng7af6dc42010-09-20 19:12:55 +0000160 bool &BreakPHIEdge,
161 bool &LocalUse) const {
Dan Gohman6f0d0242008-02-10 18:45:23 +0000162 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
163 "Only makes sense for vregs");
Evan Cheng23997862010-09-18 06:42:17 +0000164
Devang Patelf5b9a742011-12-09 01:25:04 +0000165 // Ignore debug uses because debug info doesn't affect the code.
Evan Cheng23997862010-09-18 06:42:17 +0000166 if (MRI->use_nodbg_empty(Reg))
167 return true;
168
Evan Cheng7af6dc42010-09-20 19:12:55 +0000169 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
170 // into and they are all PHI nodes. In this case, machine-sink must break
171 // the critical edge first. e.g.
172 //
Evan Cheng23997862010-09-18 06:42:17 +0000173 // BB#1: derived from LLVM BB %bb4.preheader
174 // Predecessors according to CFG: BB#0
175 // ...
176 // %reg16385<def> = DEC64_32r %reg16437, %EFLAGS<imp-def,dead>
177 // ...
178 // JE_4 <BB#37>, %EFLAGS<imp-use>
179 // Successors according to CFG: BB#37 BB#2
180 //
181 // BB#2: derived from LLVM BB %bb.nph
182 // Predecessors according to CFG: BB#0 BB#1
183 // %reg16386<def> = PHI %reg16434, <BB#0>, %reg16385, <BB#1>
Evan Cheng7af6dc42010-09-20 19:12:55 +0000184 BreakPHIEdge = true;
Evan Cheng23997862010-09-18 06:42:17 +0000185 for (MachineRegisterInfo::use_nodbg_iterator
186 I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end();
187 I != E; ++I) {
188 MachineInstr *UseInst = &*I;
189 MachineBasicBlock *UseBlock = UseInst->getParent();
190 if (!(UseBlock == MBB && UseInst->isPHI() &&
191 UseInst->getOperand(I.getOperandNo()+1).getMBB() == DefMBB)) {
Evan Cheng7af6dc42010-09-20 19:12:55 +0000192 BreakPHIEdge = false;
Evan Cheng23997862010-09-18 06:42:17 +0000193 break;
194 }
195 }
Evan Cheng7af6dc42010-09-20 19:12:55 +0000196 if (BreakPHIEdge)
Evan Cheng23997862010-09-18 06:42:17 +0000197 return true;
198
Bill Wendling05c68372010-06-02 23:04:26 +0000199 for (MachineRegisterInfo::use_nodbg_iterator
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000200 I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end();
Bill Wendling05c68372010-06-02 23:04:26 +0000201 I != E; ++I) {
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000202 // Determine the block of the use.
203 MachineInstr *UseInst = &*I;
204 MachineBasicBlock *UseBlock = UseInst->getParent();
Evan Cheng23997862010-09-18 06:42:17 +0000205 if (UseInst->isPHI()) {
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000206 // PHI nodes use the operand in the predecessor block, not the block with
207 // the PHI.
208 UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB();
Evan Chenge5e79462010-08-19 18:33:29 +0000209 } else if (UseBlock == DefMBB) {
210 LocalUse = true;
211 return false;
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000212 }
Bill Wendling05c68372010-06-02 23:04:26 +0000213
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000214 // Check that it dominates.
215 if (!DT->dominates(MBB, UseBlock))
216 return false;
217 }
Bill Wendling05c68372010-06-02 23:04:26 +0000218
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000219 return true;
220}
221
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000222bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
David Greenec19a9cd2010-01-05 01:26:00 +0000223 DEBUG(dbgs() << "******** Machine Sinking ********\n");
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000224
Dan Gohman4e9785e2009-10-19 14:52:05 +0000225 const TargetMachine &TM = MF.getTarget();
226 TII = TM.getInstrInfo();
227 TRI = TM.getRegisterInfo();
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000228 MRI = &MF.getRegInfo();
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000229 DT = &getAnalysis<MachineDominatorTree>();
Jakob Stoklund Olesen626f3d72010-04-15 23:41:02 +0000230 LI = &getAnalysis<MachineLoopInfo>();
Dan Gohmana70dca12009-10-09 23:27:56 +0000231 AA = &getAnalysis<AliasAnalysis>();
Dan Gohman4e9785e2009-10-19 14:52:05 +0000232 AllocatableSet = TRI->getAllocatableSet(MF);
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000233
234 bool EverMadeChange = false;
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000235
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000236 while (1) {
237 bool MadeChange = false;
238
239 // Process all basic blocks.
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000240 CEBCandidates.clear();
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000241 for (MachineFunction::iterator I = MF.begin(), E = MF.end();
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000242 I != E; ++I)
243 MadeChange |= ProcessBlock(*I);
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000244
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000245 // If this iteration over the code changed anything, keep iterating.
246 if (!MadeChange) break;
247 EverMadeChange = true;
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000248 }
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000249 return EverMadeChange;
250}
251
252bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000253 // Can't sink anything out of a block that has less than two successors.
Chris Lattner296185c2009-04-10 16:38:36 +0000254 if (MBB.succ_size() <= 1 || MBB.empty()) return false;
255
Dan Gohmanc4ae94d2010-04-05 19:17:22 +0000256 // Don't bother sinking code out of unreachable blocks. In addition to being
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000257 // unprofitable, it can also lead to infinite looping, because in an
258 // unreachable loop there may be nowhere to stop.
Dan Gohmanc4ae94d2010-04-05 19:17:22 +0000259 if (!DT->isReachableFromEntry(&MBB)) return false;
260
Chris Lattner296185c2009-04-10 16:38:36 +0000261 bool MadeChange = false;
262
Chris Lattneraad193a2008-01-12 00:17:41 +0000263 // Walk the basic block bottom-up. Remember if we saw a store.
Chris Lattner296185c2009-04-10 16:38:36 +0000264 MachineBasicBlock::iterator I = MBB.end();
265 --I;
266 bool ProcessedBegin, SawStore = false;
267 do {
268 MachineInstr *MI = I; // The instruction to sink.
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000269
Chris Lattner296185c2009-04-10 16:38:36 +0000270 // Predecrement I (if it's not begin) so that it isn't invalidated by
271 // sinking.
272 ProcessedBegin = I == MBB.begin();
273 if (!ProcessedBegin)
274 --I;
Dale Johannesenb0812f12010-03-05 00:02:59 +0000275
276 if (MI->isDebugValue())
277 continue;
278
Evan Chengcfea9852011-04-11 18:47:20 +0000279 bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
280 if (Joined) {
281 MadeChange = true;
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000282 continue;
Evan Chengcfea9852011-04-11 18:47:20 +0000283 }
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000284
Chris Lattner296185c2009-04-10 16:38:36 +0000285 if (SinkInstruction(MI, SawStore))
286 ++NumSunk, MadeChange = true;
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000287
Chris Lattner296185c2009-04-10 16:38:36 +0000288 // If we just processed the first instruction in the block, we're done.
289 } while (!ProcessedBegin);
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000290
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000291 return MadeChange;
292}
293
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000294bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI,
295 MachineBasicBlock *From,
296 MachineBasicBlock *To) {
297 // FIXME: Need much better heuristics.
298
299 // If the pass has already considered breaking this edge (during this pass
300 // through the function), then let's go ahead and break it. This means
301 // sinking multiple "cheap" instructions into the same block.
302 if (!CEBCandidates.insert(std::make_pair(From, To)))
303 return true;
304
Evan Cheng5a96b3d2011-12-07 07:15:52 +0000305 if (!MI->isCopy() && !MI->isAsCheapAsAMove())
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000306 return true;
307
308 // MI is cheap, we probably don't want to break the critical edge for it.
309 // However, if this would allow some definitions of its source operands
310 // to be sunk then it's probably worth it.
311 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
312 const MachineOperand &MO = MI->getOperand(i);
313 if (!MO.isReg()) continue;
314 unsigned Reg = MO.getReg();
315 if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg))
316 continue;
317 if (MRI->hasOneNonDBGUse(Reg))
318 return true;
319 }
320
321 return false;
322}
323
324MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI,
325 MachineBasicBlock *FromBB,
326 MachineBasicBlock *ToBB,
Evan Cheng7af6dc42010-09-20 19:12:55 +0000327 bool BreakPHIEdge) {
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000328 if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
329 return 0;
330
Evan Cheng4dc301a2010-08-19 17:33:11 +0000331 // Avoid breaking back edge. From == To means backedge for single BB loop.
Evan Cheng44be1a82010-09-20 22:52:00 +0000332 if (!SplitEdges || FromBB == ToBB)
Evan Cheng4dc301a2010-08-19 17:33:11 +0000333 return 0;
334
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000335 // Check for backedges of more "complex" loops.
336 if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
337 LI->isLoopHeader(ToBB))
338 return 0;
339
340 // It's not always legal to break critical edges and sink the computation
341 // to the edge.
342 //
343 // BB#1:
344 // v1024
345 // Beq BB#3
346 // <fallthrough>
347 // BB#2:
348 // ... no uses of v1024
349 // <fallthrough>
350 // BB#3:
351 // ...
352 // = v1024
353 //
354 // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted:
355 //
356 // BB#1:
357 // ...
358 // Bne BB#2
359 // BB#4:
360 // v1024 =
361 // B BB#3
362 // BB#2:
363 // ... no uses of v1024
364 // <fallthrough>
365 // BB#3:
366 // ...
367 // = v1024
368 //
369 // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3
370 // flow. We need to ensure the new basic block where the computation is
371 // sunk to dominates all the uses.
372 // It's only legal to break critical edge and sink the computation to the
373 // new block if all the predecessors of "To", except for "From", are
374 // not dominated by "From". Given SSA property, this means these
375 // predecessors are dominated by "To".
376 //
377 // There is no need to do this check if all the uses are PHI nodes. PHI
378 // sources are only defined on the specific predecessor edges.
Evan Cheng7af6dc42010-09-20 19:12:55 +0000379 if (!BreakPHIEdge) {
Evan Cheng4dc301a2010-08-19 17:33:11 +0000380 for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(),
381 E = ToBB->pred_end(); PI != E; ++PI) {
382 if (*PI == FromBB)
383 continue;
384 if (!DT->dominates(ToBB, *PI))
385 return 0;
386 }
Evan Cheng4dc301a2010-08-19 17:33:11 +0000387 }
388
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000389 return FromBB->SplitCriticalEdge(ToBB, this);
Evan Cheng4dc301a2010-08-19 17:33:11 +0000390}
391
Evan Chengb0cdf8a2010-09-23 06:53:00 +0000392static bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) {
393 return MI->isInsertSubreg() || MI->isSubregToReg() || MI->isRegSequence();
394}
395
Andrew Trick1df91b02012-02-08 21:22:43 +0000396/// collectDebgValues - Scan instructions following MI and collect any
Devang Patel541a81c2011-09-07 00:07:58 +0000397/// matching DBG_VALUEs.
Andrew Trick1df91b02012-02-08 21:22:43 +0000398static void collectDebugValues(MachineInstr *MI,
Devang Patel541a81c2011-09-07 00:07:58 +0000399 SmallVector<MachineInstr *, 2> & DbgValues) {
400 DbgValues.clear();
401 if (!MI->getOperand(0).isReg())
402 return;
403
404 MachineBasicBlock::iterator DI = MI; ++DI;
405 for (MachineBasicBlock::iterator DE = MI->getParent()->end();
406 DI != DE; ++DI) {
407 if (!DI->isDebugValue())
408 return;
409 if (DI->getOperand(0).isReg() &&
410 DI->getOperand(0).getReg() == MI->getOperand(0).getReg())
411 DbgValues.push_back(DI);
412 }
413}
414
Devang Patel52111342011-12-14 23:20:38 +0000415/// isPostDominatedBy - Return true if A is post dominated by B.
416static bool isPostDominatedBy(MachineBasicBlock *A, MachineBasicBlock *B) {
417
418 // FIXME - Use real post dominator.
419 if (A->succ_size() != 2)
420 return false;
421 MachineBasicBlock::succ_iterator I = A->succ_begin();
422 if (B == *I)
423 ++I;
424 MachineBasicBlock *OtherSuccBlock = *I;
425 if (OtherSuccBlock->succ_size() != 1 ||
426 *(OtherSuccBlock->succ_begin()) != B)
427 return false;
428
429 return true;
430}
431
432/// isProfitableToSinkTo - Return true if it is profitable to sink MI.
Andrew Trick1df91b02012-02-08 21:22:43 +0000433bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI,
Devang Patel52111342011-12-14 23:20:38 +0000434 MachineBasicBlock *MBB,
435 MachineBasicBlock *SuccToSinkTo) {
436 assert (MI && "Invalid MachineInstr!");
437 assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
438
439 if (MBB == SuccToSinkTo)
440 return false;
441
442 // It is profitable if SuccToSinkTo does not post dominate current block.
443 if (!isPostDominatedBy(MBB, SuccToSinkTo))
444 return true;
445
446 // Check if only use in post dominated block is PHI instruction.
447 bool NonPHIUse = false;
448 for (MachineRegisterInfo::use_nodbg_iterator
449 I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end();
450 I != E; ++I) {
451 MachineInstr *UseInst = &*I;
452 MachineBasicBlock *UseBlock = UseInst->getParent();
453 if (UseBlock == SuccToSinkTo && !UseInst->isPHI())
454 NonPHIUse = true;
455 }
456 if (!NonPHIUse)
457 return true;
458
459 // If SuccToSinkTo post dominates then also it may be profitable if MI
460 // can further profitably sinked into another block in next round.
461 bool BreakPHIEdge = false;
462 // FIXME - If finding successor is compile time expensive then catch results.
463 if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge))
464 return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2);
465
466 // If SuccToSinkTo is final destination and it is a post dominator of current
467 // block then it is not profitable to sink MI into SuccToSinkTo block.
468 return false;
469}
470
Devang Patele265bcf2011-12-08 21:48:01 +0000471/// FindSuccToSinkTo - Find a successor to sink this instruction to.
472MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI,
Devang Patel52111342011-12-14 23:20:38 +0000473 MachineBasicBlock *MBB,
474 bool &BreakPHIEdge) {
475
476 assert (MI && "Invalid MachineInstr!");
477 assert (MBB && "Invalid MachineBasicBlock!");
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000478
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000479 // Loop over all the operands of the specified instruction. If there is
480 // anything we can't handle, bail out.
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000481
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000482 // SuccToSinkTo - This is the successor to sink this instruction to, once we
483 // decide.
484 MachineBasicBlock *SuccToSinkTo = 0;
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000485 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
486 const MachineOperand &MO = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +0000487 if (!MO.isReg()) continue; // Ignore non-register operands.
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000488
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000489 unsigned Reg = MO.getReg();
490 if (Reg == 0) continue;
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000491
Dan Gohman6f0d0242008-02-10 18:45:23 +0000492 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
Dan Gohman19778e72009-09-25 22:53:29 +0000493 if (MO.isUse()) {
494 // If the physreg has no defs anywhere, it's just an ambient register
Dan Gohman45094e32009-09-26 02:34:00 +0000495 // and we can freely move its uses. Alternatively, if it's allocatable,
496 // it could get allocated to something with a def during allocation.
Jakob Stoklund Olesenc035c942012-01-16 22:34:08 +0000497 if (!MRI->isConstantPhysReg(Reg, *MBB->getParent()))
Devang Patele265bcf2011-12-08 21:48:01 +0000498 return NULL;
Bill Wendling730c07e2010-06-25 20:48:10 +0000499 } else if (!MO.isDead()) {
500 // A def that isn't dead. We can't move it.
Devang Patele265bcf2011-12-08 21:48:01 +0000501 return NULL;
Dan Gohman19778e72009-09-25 22:53:29 +0000502 }
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000503 } else {
504 // Virtual register uses are always safe to sink.
505 if (MO.isUse()) continue;
Evan Chengb6f54172009-02-07 01:21:47 +0000506
507 // If it's not safe to move defs of the register class, then abort.
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000508 if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
Devang Patele265bcf2011-12-08 21:48:01 +0000509 return NULL;
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000510
Chris Lattnere430e1c2008-01-05 06:47:58 +0000511 // FIXME: This picks a successor to sink into based on having one
512 // successor that dominates all the uses. However, there are cases where
513 // sinking can happen but where the sink point isn't a successor. For
514 // example:
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000515 //
Chris Lattnere430e1c2008-01-05 06:47:58 +0000516 // x = computation
517 // if () {} else {}
518 // use x
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000519 //
Bill Wendling05c68372010-06-02 23:04:26 +0000520 // the instruction could be sunk over the whole diamond for the
Chris Lattnere430e1c2008-01-05 06:47:58 +0000521 // if/then/else (or loop, etc), allowing it to be sunk into other blocks
522 // after that.
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000523
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000524 // Virtual register defs can only be sunk if all their uses are in blocks
525 // dominated by one of the successors.
526 if (SuccToSinkTo) {
527 // If a previous operand picked a block to sink to, then this operand
528 // must be sinkable to the same block.
Evan Chenge5e79462010-08-19 18:33:29 +0000529 bool LocalUse = false;
Devang Patel52111342011-12-14 23:20:38 +0000530 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
Evan Cheng7af6dc42010-09-20 19:12:55 +0000531 BreakPHIEdge, LocalUse))
Devang Patele265bcf2011-12-08 21:48:01 +0000532 return NULL;
Bill Wendling05c68372010-06-02 23:04:26 +0000533
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000534 continue;
535 }
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000536
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000537 // Otherwise, we should look at all the successors and decide which one
538 // we should sink to.
Manman Ren53b59d12012-07-31 18:10:39 +0000539 // We give successors with smaller loop depth higher priority.
540 SmallVector<MachineBasicBlock*, 4> Succs(MBB->succ_begin(), MBB->succ_end());
541 std::sort(Succs.begin(), Succs.end(), SuccessorSorter(LI));
542 for (SmallVector<MachineBasicBlock*, 4>::iterator SI = Succs.begin(),
543 E = Succs.end(); SI != E; ++SI) {
Devang Patel52111342011-12-14 23:20:38 +0000544 MachineBasicBlock *SuccBlock = *SI;
Evan Chenge5e79462010-08-19 18:33:29 +0000545 bool LocalUse = false;
Devang Patel52111342011-12-14 23:20:38 +0000546 if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
Evan Cheng7af6dc42010-09-20 19:12:55 +0000547 BreakPHIEdge, LocalUse)) {
Devang Patelcf405ba2011-12-08 21:33:23 +0000548 SuccToSinkTo = SuccBlock;
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000549 break;
550 }
Evan Chengc3439ad2010-08-18 23:09:25 +0000551 if (LocalUse)
552 // Def is used locally, it's never safe to move this def.
Devang Patele265bcf2011-12-08 21:48:01 +0000553 return NULL;
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000554 }
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000555
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000556 // If we couldn't find a block to sink to, ignore this instruction.
557 if (SuccToSinkTo == 0)
Devang Patele265bcf2011-12-08 21:48:01 +0000558 return NULL;
Devang Patel52111342011-12-14 23:20:38 +0000559 else if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo))
560 return NULL;
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000561 }
562 }
Devang Patel7f7f0902011-12-08 23:52:00 +0000563
564 // It is not possible to sink an instruction into its own block. This can
565 // happen with loops.
Devang Patel52111342011-12-14 23:20:38 +0000566 if (MBB == SuccToSinkTo)
Devang Patel7f7f0902011-12-08 23:52:00 +0000567 return NULL;
568
569 // It's not safe to sink instructions to EH landing pad. Control flow into
570 // landing pad is implicitly defined.
571 if (SuccToSinkTo && SuccToSinkTo->isLandingPad())
572 return NULL;
573
Devang Patele265bcf2011-12-08 21:48:01 +0000574 return SuccToSinkTo;
575}
576
577/// SinkInstruction - Determine whether it is safe to sink the specified machine
578/// instruction out of its current block into a successor.
579bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) {
580 // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to
581 // be close to the source to make it easier to coalesce.
582 if (AvoidsSinking(MI, MRI))
583 return false;
584
585 // Check if it's safe to move the instruction.
586 if (!MI->isSafeToMove(TII, AA, SawStore))
587 return false;
588
589 // FIXME: This should include support for sinking instructions within the
590 // block they are currently in to shorten the live ranges. We often get
591 // instructions sunk into the top of a large block, but it would be better to
592 // also sink them down before their first use in the block. This xform has to
593 // be careful not to *increase* register pressure though, e.g. sinking
594 // "x = y + z" down if it kills y and z would increase the live ranges of y
595 // and z and only shrink the live range of x.
596
597 bool BreakPHIEdge = false;
Devang Patel52111342011-12-14 23:20:38 +0000598 MachineBasicBlock *ParentBlock = MI->getParent();
599 MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge);
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000600
Chris Lattner9bb459b2008-01-05 01:39:17 +0000601 // If there are no outputs, it must have side-effects.
602 if (SuccToSinkTo == 0)
603 return false;
Evan Chengb5999792009-02-15 08:36:12 +0000604
Bill Wendling869d60d2010-06-03 07:54:20 +0000605
Daniel Dunbard24c9d52010-06-23 00:48:25 +0000606 // If the instruction to move defines a dead physical register which is live
607 // when leaving the basic block, don't move it because it could turn into a
608 // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
Bill Wendling730c07e2010-06-25 20:48:10 +0000609 for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) {
610 const MachineOperand &MO = MI->getOperand(I);
611 if (!MO.isReg()) continue;
612 unsigned Reg = MO.getReg();
613 if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
614 if (SuccToSinkTo->isLiveIn(Reg))
Bill Wendling869d60d2010-06-03 07:54:20 +0000615 return false;
Bill Wendling730c07e2010-06-25 20:48:10 +0000616 }
Bill Wendling869d60d2010-06-03 07:54:20 +0000617
Bill Wendling05c68372010-06-02 23:04:26 +0000618 DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo);
619
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000620 // If the block has multiple predecessors, this would introduce computation on
621 // a path that it doesn't already exist. We could split the critical edge,
622 // but for now we just punt.
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000623 if (SuccToSinkTo->pred_size() > 1) {
Jakob Stoklund Olesen8d171602010-04-13 19:06:14 +0000624 // We cannot sink a load across a critical edge - there may be stores in
625 // other code paths.
Evan Cheng4dc301a2010-08-19 17:33:11 +0000626 bool TryBreak = false;
Jakob Stoklund Olesen8d171602010-04-13 19:06:14 +0000627 bool store = true;
628 if (!MI->isSafeToMove(TII, AA, store)) {
Evan Chengf942c132010-08-19 23:33:02 +0000629 DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
Evan Cheng4dc301a2010-08-19 17:33:11 +0000630 TryBreak = true;
Jakob Stoklund Olesen8d171602010-04-13 19:06:14 +0000631 }
632
633 // We don't want to sink across a critical edge if we don't dominate the
634 // successor. We could be introducing calculations to new code paths.
Evan Cheng4dc301a2010-08-19 17:33:11 +0000635 if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
Evan Chengf942c132010-08-19 23:33:02 +0000636 DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
Evan Cheng4dc301a2010-08-19 17:33:11 +0000637 TryBreak = true;
Jakob Stoklund Olesen8d171602010-04-13 19:06:14 +0000638 }
639
Jakob Stoklund Olesen626f3d72010-04-15 23:41:02 +0000640 // Don't sink instructions into a loop.
Evan Cheng4dc301a2010-08-19 17:33:11 +0000641 if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
Evan Chengf942c132010-08-19 23:33:02 +0000642 DEBUG(dbgs() << " *** NOTE: Loop header found\n");
Evan Cheng4dc301a2010-08-19 17:33:11 +0000643 TryBreak = true;
Jakob Stoklund Olesen626f3d72010-04-15 23:41:02 +0000644 }
645
Jakob Stoklund Olesen8d171602010-04-13 19:06:14 +0000646 // Otherwise we are OK with sinking along a critical edge.
Evan Cheng4dc301a2010-08-19 17:33:11 +0000647 if (!TryBreak)
648 DEBUG(dbgs() << "Sinking along critical edge.\n");
649 else {
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000650 MachineBasicBlock *NewSucc =
Evan Cheng7af6dc42010-09-20 19:12:55 +0000651 SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
Evan Cheng4dc301a2010-08-19 17:33:11 +0000652 if (!NewSucc) {
Evan Cheng6edb0ea2010-09-17 22:28:18 +0000653 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
654 "break critical edge\n");
Evan Cheng4dc301a2010-08-19 17:33:11 +0000655 return false;
656 } else {
Evan Chengf942c132010-08-19 23:33:02 +0000657 DEBUG(dbgs() << " *** Splitting critical edge:"
Evan Cheng4dc301a2010-08-19 17:33:11 +0000658 " BB#" << ParentBlock->getNumber()
659 << " -- BB#" << NewSucc->getNumber()
660 << " -- BB#" << SuccToSinkTo->getNumber() << '\n');
Evan Cheng4dc301a2010-08-19 17:33:11 +0000661 SuccToSinkTo = NewSucc;
662 ++NumSplit;
Evan Cheng7af6dc42010-09-20 19:12:55 +0000663 BreakPHIEdge = false;
Evan Cheng4dc301a2010-08-19 17:33:11 +0000664 }
665 }
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000666 }
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000667
Evan Cheng7af6dc42010-09-20 19:12:55 +0000668 if (BreakPHIEdge) {
669 // BreakPHIEdge is true if all the uses are in the successor MBB being
670 // sunken into and they are all PHI nodes. In this case, machine-sink must
671 // break the critical edge first.
Evan Cheng23997862010-09-18 06:42:17 +0000672 MachineBasicBlock *NewSucc = SplitCriticalEdge(MI, ParentBlock,
Evan Cheng7af6dc42010-09-20 19:12:55 +0000673 SuccToSinkTo, BreakPHIEdge);
Evan Cheng23997862010-09-18 06:42:17 +0000674 if (!NewSucc) {
675 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
676 "break critical edge\n");
677 return false;
678 }
679
680 DEBUG(dbgs() << " *** Splitting critical edge:"
681 " BB#" << ParentBlock->getNumber()
682 << " -- BB#" << NewSucc->getNumber()
683 << " -- BB#" << SuccToSinkTo->getNumber() << '\n');
684 SuccToSinkTo = NewSucc;
685 ++NumSplit;
686 }
687
Bill Wendling05c68372010-06-02 23:04:26 +0000688 // Determine where to insert into. Skip phi nodes.
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000689 MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
Evan Cheng23997862010-09-18 06:42:17 +0000690 while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000691 ++InsertPos;
Jim Grosbach6ee358b2010-06-03 23:49:57 +0000692
Devang Patel541a81c2011-09-07 00:07:58 +0000693 // collect matching debug values.
694 SmallVector<MachineInstr *, 2> DbgValuesToSink;
695 collectDebugValues(MI, DbgValuesToSink);
696
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000697 // Move the instruction.
698 SuccToSinkTo->splice(InsertPos, ParentBlock, MI,
699 ++MachineBasicBlock::iterator(MI));
Dan Gohmane6cd7572010-05-13 20:34:42 +0000700
Devang Patel541a81c2011-09-07 00:07:58 +0000701 // Move debug values.
702 for (SmallVector<MachineInstr *, 2>::iterator DBI = DbgValuesToSink.begin(),
703 DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) {
704 MachineInstr *DbgMI = *DBI;
705 SuccToSinkTo->splice(InsertPos, ParentBlock, DbgMI,
706 ++MachineBasicBlock::iterator(DbgMI));
707 }
708
Bill Wendling05c68372010-06-02 23:04:26 +0000709 // Conservatively, clear any kill flags, since it's possible that they are no
710 // longer correct.
Dan Gohmane6cd7572010-05-13 20:34:42 +0000711 MI->clearKillInfo();
712
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000713 return true;
714}