1 //===-- MachineSink.cpp - Sinking for machine instructions ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass moves instructions into successor blocks, when possible, so that
11 // they aren't executed on paths where their results aren't needed.
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.
17 //===----------------------------------------------------------------------===//
19 #define DEBUG_TYPE "machine-sink"
20 #include "llvm/CodeGen/Passes.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/CodeGen/MachineDominators.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Target/TargetRegisterInfo.h"
25 #include "llvm/Target/TargetInstrInfo.h"
26 #include "llvm/Target/TargetMachine.h"
27 #include "llvm/ADT/Statistic.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
32 STATISTIC(NumSunk
, "Number of machine instructions sunk");
35 class MachineSinking
: public MachineFunctionPass
{
36 const TargetInstrInfo
*TII
;
37 const TargetRegisterInfo
*TRI
;
38 MachineRegisterInfo
*RegInfo
; // Machine register information
39 MachineDominatorTree
*DT
; // Machine dominator tree
41 BitVector AllocatableSet
; // Which physregs are allocatable?
44 static char ID
; // Pass identification
45 MachineSinking() : MachineFunctionPass(&ID
) {}
47 virtual bool runOnMachineFunction(MachineFunction
&MF
);
49 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
51 MachineFunctionPass::getAnalysisUsage(AU
);
52 AU
.addRequired
<AliasAnalysis
>();
53 AU
.addRequired
<MachineDominatorTree
>();
54 AU
.addPreserved
<MachineDominatorTree
>();
57 bool ProcessBlock(MachineBasicBlock
&MBB
);
58 bool SinkInstruction(MachineInstr
*MI
, bool &SawStore
);
59 bool AllUsesDominatedByBlock(unsigned Reg
, MachineBasicBlock
*MBB
) const;
61 } // end anonymous namespace
63 char MachineSinking::ID
= 0;
64 static RegisterPass
<MachineSinking
>
65 X("machine-sink", "Machine code sinking");
67 FunctionPass
*llvm::createMachineSinkingPass() { return new MachineSinking(); }
69 /// AllUsesDominatedByBlock - Return true if all uses of the specified register
70 /// occur in blocks dominated by the specified block.
71 bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg
,
72 MachineBasicBlock
*MBB
) const {
73 assert(TargetRegisterInfo::isVirtualRegister(Reg
) &&
74 "Only makes sense for vregs");
75 for (MachineRegisterInfo::use_iterator I
= RegInfo
->use_begin(Reg
),
76 E
= RegInfo
->use_end(); I
!= E
; ++I
) {
77 // Determine the block of the use.
78 MachineInstr
*UseInst
= &*I
;
79 MachineBasicBlock
*UseBlock
= UseInst
->getParent();
80 if (UseInst
->getOpcode() == TargetInstrInfo::PHI
) {
81 // PHI nodes use the operand in the predecessor block, not the block with
83 UseBlock
= UseInst
->getOperand(I
.getOperandNo()+1).getMBB();
85 // Check that it dominates.
86 if (!DT
->dominates(MBB
, UseBlock
))
92 bool MachineSinking::runOnMachineFunction(MachineFunction
&MF
) {
93 DEBUG(errs() << "******** Machine Sinking ********\n");
95 const TargetMachine
&TM
= MF
.getTarget();
96 TII
= TM
.getInstrInfo();
97 TRI
= TM
.getRegisterInfo();
98 RegInfo
= &MF
.getRegInfo();
99 DT
= &getAnalysis
<MachineDominatorTree
>();
100 AA
= &getAnalysis
<AliasAnalysis
>();
101 AllocatableSet
= TRI
->getAllocatableSet(MF
);
103 bool EverMadeChange
= false;
106 bool MadeChange
= false;
108 // Process all basic blocks.
109 for (MachineFunction::iterator I
= MF
.begin(), E
= MF
.end();
111 MadeChange
|= ProcessBlock(*I
);
113 // If this iteration over the code changed anything, keep iterating.
114 if (!MadeChange
) break;
115 EverMadeChange
= true;
117 return EverMadeChange
;
120 bool MachineSinking::ProcessBlock(MachineBasicBlock
&MBB
) {
121 // Can't sink anything out of a block that has less than two successors.
122 if (MBB
.succ_size() <= 1 || MBB
.empty()) return false;
124 bool MadeChange
= false;
126 // Walk the basic block bottom-up. Remember if we saw a store.
127 MachineBasicBlock::iterator I
= MBB
.end();
129 bool ProcessedBegin
, SawStore
= false;
131 MachineInstr
*MI
= I
; // The instruction to sink.
133 // Predecrement I (if it's not begin) so that it isn't invalidated by
135 ProcessedBegin
= I
== MBB
.begin();
139 if (SinkInstruction(MI
, SawStore
))
140 ++NumSunk
, MadeChange
= true;
142 // If we just processed the first instruction in the block, we're done.
143 } while (!ProcessedBegin
);
148 /// SinkInstruction - Determine whether it is safe to sink the specified machine
149 /// instruction out of its current block into a successor.
150 bool MachineSinking::SinkInstruction(MachineInstr
*MI
, bool &SawStore
) {
151 // Check if it's safe to move the instruction.
152 if (!MI
->isSafeToMove(TII
, SawStore
, AA
))
155 // FIXME: This should include support for sinking instructions within the
156 // block they are currently in to shorten the live ranges. We often get
157 // instructions sunk into the top of a large block, but it would be better to
158 // also sink them down before their first use in the block. This xform has to
159 // be careful not to *increase* register pressure though, e.g. sinking
160 // "x = y + z" down if it kills y and z would increase the live ranges of y
161 // and z and only shrink the live range of x.
163 // Loop over all the operands of the specified instruction. If there is
164 // anything we can't handle, bail out.
165 MachineBasicBlock
*ParentBlock
= MI
->getParent();
167 // SuccToSinkTo - This is the successor to sink this instruction to, once we
169 MachineBasicBlock
*SuccToSinkTo
= 0;
171 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
172 const MachineOperand
&MO
= MI
->getOperand(i
);
173 if (!MO
.isReg()) continue; // Ignore non-register operands.
175 unsigned Reg
= MO
.getReg();
176 if (Reg
== 0) continue;
178 if (TargetRegisterInfo::isPhysicalRegister(Reg
)) {
180 // If the physreg has no defs anywhere, it's just an ambient register
181 // and we can freely move its uses. Alternatively, if it's allocatable,
182 // it could get allocated to something with a def during allocation.
183 if (!RegInfo
->def_empty(Reg
))
185 if (AllocatableSet
.test(Reg
))
187 // Check for a def among the register's aliases too.
188 for (const unsigned *Alias
= TRI
->getAliasSet(Reg
); *Alias
; ++Alias
) {
189 unsigned AliasReg
= *Alias
;
190 if (!RegInfo
->def_empty(AliasReg
))
192 if (AllocatableSet
.test(AliasReg
))
195 } else if (!MO
.isDead()) {
196 // A def that isn't dead. We can't move it.
200 // Virtual register uses are always safe to sink.
201 if (MO
.isUse()) continue;
203 // If it's not safe to move defs of the register class, then abort.
204 if (!TII
->isSafeToMoveRegClassDefs(RegInfo
->getRegClass(Reg
)))
207 // FIXME: This picks a successor to sink into based on having one
208 // successor that dominates all the uses. However, there are cases where
209 // sinking can happen but where the sink point isn't a successor. For
214 // the instruction could be sunk over the whole diamond for the
215 // if/then/else (or loop, etc), allowing it to be sunk into other blocks
218 // Virtual register defs can only be sunk if all their uses are in blocks
219 // dominated by one of the successors.
221 // If a previous operand picked a block to sink to, then this operand
222 // must be sinkable to the same block.
223 if (!AllUsesDominatedByBlock(Reg
, SuccToSinkTo
))
228 // Otherwise, we should look at all the successors and decide which one
229 // we should sink to.
230 for (MachineBasicBlock::succ_iterator SI
= ParentBlock
->succ_begin(),
231 E
= ParentBlock
->succ_end(); SI
!= E
; ++SI
) {
232 if (AllUsesDominatedByBlock(Reg
, *SI
)) {
238 // If we couldn't find a block to sink to, ignore this instruction.
239 if (SuccToSinkTo
== 0)
244 // If there are no outputs, it must have side-effects.
245 if (SuccToSinkTo
== 0)
248 // It's not safe to sink instructions to EH landing pad. Control flow into
249 // landing pad is implicitly defined.
250 if (SuccToSinkTo
->isLandingPad())
253 // It is not possible to sink an instruction into its own block. This can
254 // happen with loops.
255 if (MI
->getParent() == SuccToSinkTo
)
258 DEBUG(errs() << "Sink instr " << *MI
);
259 DEBUG(errs() << "to block " << *SuccToSinkTo
);
261 // If the block has multiple predecessors, this would introduce computation on
262 // a path that it doesn't already exist. We could split the critical edge,
263 // but for now we just punt.
264 // FIXME: Split critical edges if not backedges.
265 if (SuccToSinkTo
->pred_size() > 1) {
266 DEBUG(errs() << " *** PUNTING: Critical edge found\n");
270 // Determine where to insert into. Skip phi nodes.
271 MachineBasicBlock::iterator InsertPos
= SuccToSinkTo
->begin();
272 while (InsertPos
!= SuccToSinkTo
->end() &&
273 InsertPos
->getOpcode() == TargetInstrInfo::PHI
)
276 // Move the instruction.
277 SuccToSinkTo
->splice(InsertPos
, ParentBlock
, MI
,
278 ++MachineBasicBlock::iterator(MI
));