blob: a00bebb191c98c32594718c771b919cb277071b9 [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//
Dan Gohmana5225ad2009-08-05 01:19:01 +000010// This pass moves instructions into successor blocks, when possible, so that
11// 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"
Dan Gohmana70dca12009-10-09 23:27:56 +000023#include "llvm/Analysis/AliasAnalysis.h"
Dan Gohman6f0d0242008-02-10 18:45:23 +000024#include "llvm/Target/TargetRegisterInfo.h"
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000025#include "llvm/Target/TargetInstrInfo.h"
26#include "llvm/Target/TargetMachine.h"
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000027#include "llvm/ADT/Statistic.h"
28#include "llvm/Support/Compiler.h"
29#include "llvm/Support/Debug.h"
Bill Wendling1e973aa2009-08-22 20:26:23 +000030#include "llvm/Support/raw_ostream.h"
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000031using namespace llvm;
32
33STATISTIC(NumSunk, "Number of machine instructions sunk");
34
35namespace {
36 class VISIBILITY_HIDDEN MachineSinking : public MachineFunctionPass {
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000037 const TargetInstrInfo *TII;
Dan Gohman19778e72009-09-25 22:53:29 +000038 const TargetRegisterInfo *TRI;
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000039 MachineRegisterInfo *RegInfo; // Machine register information
Dan Gohmana5225ad2009-08-05 01:19:01 +000040 MachineDominatorTree *DT; // Machine dominator tree
Dan Gohmana70dca12009-10-09 23:27:56 +000041 AliasAnalysis *AA;
Dan Gohman45094e32009-09-26 02:34:00 +000042 BitVector AllocatableSet; // Which physregs are allocatable?
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000043
44 public:
45 static char ID; // Pass identification
Dan Gohmanae73dc12008-09-04 17:05:41 +000046 MachineSinking() : MachineFunctionPass(&ID) {}
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000047
48 virtual bool runOnMachineFunction(MachineFunction &MF);
49
50 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
Dan Gohman845012e2009-07-31 23:37:33 +000051 AU.setPreservesCFG();
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000052 MachineFunctionPass::getAnalysisUsage(AU);
Dan Gohmana70dca12009-10-09 23:27:56 +000053 AU.addRequired<AliasAnalysis>();
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000054 AU.addRequired<MachineDominatorTree>();
55 AU.addPreserved<MachineDominatorTree>();
56 }
57 private:
58 bool ProcessBlock(MachineBasicBlock &MBB);
Chris Lattneraad193a2008-01-12 00:17:41 +000059 bool SinkInstruction(MachineInstr *MI, bool &SawStore);
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000060 bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB) const;
61 };
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000062} // end anonymous namespace
Dan Gohman844731a2008-05-13 00:00:25 +000063
64char MachineSinking::ID = 0;
65static RegisterPass<MachineSinking>
66X("machine-sink", "Machine code sinking");
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000067
68FunctionPass *llvm::createMachineSinkingPass() { return new MachineSinking(); }
69
70/// AllUsesDominatedByBlock - Return true if all uses of the specified register
71/// occur in blocks dominated by the specified block.
72bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg,
73 MachineBasicBlock *MBB) const {
Dan Gohman6f0d0242008-02-10 18:45:23 +000074 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
75 "Only makes sense for vregs");
Dan Gohman29438d12009-09-25 22:24:52 +000076 for (MachineRegisterInfo::use_iterator I = RegInfo->use_begin(Reg),
77 E = RegInfo->use_end(); I != E; ++I) {
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000078 // Determine the block of the use.
79 MachineInstr *UseInst = &*I;
80 MachineBasicBlock *UseBlock = UseInst->getParent();
81 if (UseInst->getOpcode() == TargetInstrInfo::PHI) {
82 // PHI nodes use the operand in the predecessor block, not the block with
83 // the PHI.
84 UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB();
85 }
86 // Check that it dominates.
87 if (!DT->dominates(MBB, UseBlock))
88 return false;
89 }
90 return true;
91}
92
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000093bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
Bill Wendling1e973aa2009-08-22 20:26:23 +000094 DEBUG(errs() << "******** Machine Sinking ********\n");
Chris Lattnerc4ce73f2008-01-04 07:36:53 +000095
Dan Gohman4e9785e2009-10-19 14:52:05 +000096 const TargetMachine &TM = MF.getTarget();
97 TII = TM.getInstrInfo();
98 TRI = TM.getRegisterInfo();
99 RegInfo = &MF.getRegInfo();
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000100 DT = &getAnalysis<MachineDominatorTree>();
Dan Gohmana70dca12009-10-09 23:27:56 +0000101 AA = &getAnalysis<AliasAnalysis>();
Dan Gohman4e9785e2009-10-19 14:52:05 +0000102 AllocatableSet = TRI->getAllocatableSet(MF);
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000103
104 bool EverMadeChange = false;
105
106 while (1) {
107 bool MadeChange = false;
108
109 // Process all basic blocks.
Dan Gohman4e9785e2009-10-19 14:52:05 +0000110 for (MachineFunction::iterator I = MF.begin(), E = MF.end();
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000111 I != E; ++I)
112 MadeChange |= ProcessBlock(*I);
113
114 // If this iteration over the code changed anything, keep iterating.
115 if (!MadeChange) break;
116 EverMadeChange = true;
117 }
118 return EverMadeChange;
119}
120
121bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000122 // Can't sink anything out of a block that has less than two successors.
Chris Lattner296185c2009-04-10 16:38:36 +0000123 if (MBB.succ_size() <= 1 || MBB.empty()) return false;
124
125 bool MadeChange = false;
126
Chris Lattneraad193a2008-01-12 00:17:41 +0000127 // Walk the basic block bottom-up. Remember if we saw a store.
Chris Lattner296185c2009-04-10 16:38:36 +0000128 MachineBasicBlock::iterator I = MBB.end();
129 --I;
130 bool ProcessedBegin, SawStore = false;
131 do {
132 MachineInstr *MI = I; // The instruction to sink.
133
134 // Predecrement I (if it's not begin) so that it isn't invalidated by
135 // sinking.
136 ProcessedBegin = I == MBB.begin();
137 if (!ProcessedBegin)
138 --I;
139
140 if (SinkInstruction(MI, SawStore))
141 ++NumSunk, MadeChange = true;
142
143 // If we just processed the first instruction in the block, we're done.
144 } while (!ProcessedBegin);
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000145
146 return MadeChange;
147}
148
149/// SinkInstruction - Determine whether it is safe to sink the specified machine
150/// instruction out of its current block into a successor.
Chris Lattneraad193a2008-01-12 00:17:41 +0000151bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) {
Evan Chengb27087f2008-03-13 00:44:09 +0000152 // Check if it's safe to move the instruction.
Dan Gohmana70dca12009-10-09 23:27:56 +0000153 if (!MI->isSafeToMove(TII, SawStore, AA))
Chris Lattneraad193a2008-01-12 00:17:41 +0000154 return false;
Chris Lattnere430e1c2008-01-05 06:47:58 +0000155
156 // FIXME: This should include support for sinking instructions within the
157 // block they are currently in to shorten the live ranges. We often get
158 // instructions sunk into the top of a large block, but it would be better to
159 // also sink them down before their first use in the block. This xform has to
160 // be careful not to *increase* register pressure though, e.g. sinking
161 // "x = y + z" down if it kills y and z would increase the live ranges of y
Dan Gohmana5225ad2009-08-05 01:19:01 +0000162 // and z and only shrink the live range of x.
Chris Lattnere430e1c2008-01-05 06:47:58 +0000163
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000164 // Loop over all the operands of the specified instruction. If there is
165 // anything we can't handle, bail out.
166 MachineBasicBlock *ParentBlock = MI->getParent();
167
168 // SuccToSinkTo - This is the successor to sink this instruction to, once we
169 // decide.
170 MachineBasicBlock *SuccToSinkTo = 0;
171
172 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
173 const MachineOperand &MO = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +0000174 if (!MO.isReg()) continue; // Ignore non-register operands.
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000175
176 unsigned Reg = MO.getReg();
177 if (Reg == 0) continue;
178
Dan Gohman6f0d0242008-02-10 18:45:23 +0000179 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
Dan Gohman19778e72009-09-25 22:53:29 +0000180 if (MO.isUse()) {
181 // If the physreg has no defs anywhere, it's just an ambient register
Dan Gohman45094e32009-09-26 02:34:00 +0000182 // and we can freely move its uses. Alternatively, if it's allocatable,
183 // it could get allocated to something with a def during allocation.
Dan Gohman19778e72009-09-25 22:53:29 +0000184 if (!RegInfo->def_empty(Reg))
185 return false;
Dan Gohman45094e32009-09-26 02:34:00 +0000186 if (AllocatableSet.test(Reg))
187 return false;
Dan Gohman19778e72009-09-25 22:53:29 +0000188 // Check for a def among the register's aliases too.
Dan Gohman45094e32009-09-26 02:34:00 +0000189 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
190 unsigned AliasReg = *Alias;
191 if (!RegInfo->def_empty(AliasReg))
Dan Gohman19778e72009-09-25 22:53:29 +0000192 return false;
Dan Gohman45094e32009-09-26 02:34:00 +0000193 if (AllocatableSet.test(AliasReg))
194 return false;
195 }
Dan Gohman19778e72009-09-25 22:53:29 +0000196 } else if (!MO.isDead()) {
197 // A def that isn't dead. We can't move it.
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000198 return false;
Dan Gohman19778e72009-09-25 22:53:29 +0000199 }
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000200 } else {
201 // Virtual register uses are always safe to sink.
202 if (MO.isUse()) continue;
Evan Chengb6f54172009-02-07 01:21:47 +0000203
204 // If it's not safe to move defs of the register class, then abort.
205 if (!TII->isSafeToMoveRegClassDefs(RegInfo->getRegClass(Reg)))
206 return false;
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000207
Chris Lattnere430e1c2008-01-05 06:47:58 +0000208 // FIXME: This picks a successor to sink into based on having one
209 // successor that dominates all the uses. However, there are cases where
210 // sinking can happen but where the sink point isn't a successor. For
211 // example:
212 // x = computation
213 // if () {} else {}
214 // use x
215 // the instruction could be sunk over the whole diamond for the
216 // if/then/else (or loop, etc), allowing it to be sunk into other blocks
217 // after that.
218
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000219 // Virtual register defs can only be sunk if all their uses are in blocks
220 // dominated by one of the successors.
221 if (SuccToSinkTo) {
222 // If a previous operand picked a block to sink to, then this operand
223 // must be sinkable to the same block.
224 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo))
225 return false;
226 continue;
227 }
228
229 // Otherwise, we should look at all the successors and decide which one
230 // we should sink to.
231 for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(),
232 E = ParentBlock->succ_end(); SI != E; ++SI) {
233 if (AllUsesDominatedByBlock(Reg, *SI)) {
234 SuccToSinkTo = *SI;
235 break;
236 }
237 }
238
239 // If we couldn't find a block to sink to, ignore this instruction.
240 if (SuccToSinkTo == 0)
241 return false;
242 }
243 }
244
Chris Lattner9bb459b2008-01-05 01:39:17 +0000245 // If there are no outputs, it must have side-effects.
246 if (SuccToSinkTo == 0)
247 return false;
Evan Chengb5999792009-02-15 08:36:12 +0000248
249 // It's not safe to sink instructions to EH landing pad. Control flow into
250 // landing pad is implicitly defined.
251 if (SuccToSinkTo->isLandingPad())
252 return false;
Chris Lattner9bb459b2008-01-05 01:39:17 +0000253
Dan Gohmandfffba62009-10-19 14:56:05 +0000254 // It is not possible to sink an instruction into its own block. This can
Chris Lattner296185c2009-04-10 16:38:36 +0000255 // happen with loops.
256 if (MI->getParent() == SuccToSinkTo)
257 return false;
258
Chris Lattnercf143a42009-08-23 03:13:20 +0000259 DEBUG(errs() << "Sink instr " << *MI);
260 DEBUG(errs() << "to block " << *SuccToSinkTo);
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000261
262 // If the block has multiple predecessors, this would introduce computation on
263 // a path that it doesn't already exist. We could split the critical edge,
264 // but for now we just punt.
Chris Lattnere430e1c2008-01-05 06:47:58 +0000265 // FIXME: Split critical edges if not backedges.
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000266 if (SuccToSinkTo->pred_size() > 1) {
Chris Lattnercf143a42009-08-23 03:13:20 +0000267 DEBUG(errs() << " *** PUNTING: Critical edge found\n");
Chris Lattnerc4ce73f2008-01-04 07:36:53 +0000268 return false;
269 }
270
271 // Determine where to insert into. Skip phi nodes.
272 MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
273 while (InsertPos != SuccToSinkTo->end() &&
274 InsertPos->getOpcode() == TargetInstrInfo::PHI)
275 ++InsertPos;
276
277 // Move the instruction.
278 SuccToSinkTo->splice(InsertPos, ParentBlock, MI,
279 ++MachineBasicBlock::iterator(MI));
280 return true;
281}