MachineSink.cpp revision 492d06efde44a4e38a6ed321ada4af5a75494df6 
1//===-- 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//
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.
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.
16//
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"
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/Compiler.h"
29#include "llvm/Support/Debug.h"
30#include "llvm/Support/raw_ostream.h"
31using namespace llvm;
32
33STATISTIC(NumSunk, "Number of machine instructions sunk");
34
35namespace {
36  class MachineSinking : public MachineFunctionPass {
37    const TargetInstrInfo *TII;
38    const TargetRegisterInfo *TRI;
39    MachineRegisterInfo  *RegInfo; // Machine register information
40    MachineDominatorTree *DT;   // Machine dominator tree
41    AliasAnalysis *AA;
42    BitVector AllocatableSet;   // Which physregs are allocatable?
43
44  public:
45    static char ID; // Pass identification
46    MachineSinking() : MachineFunctionPass(&ID) {}
47
48    virtual bool runOnMachineFunction(MachineFunction &MF);
49
50    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
51      AU.setPreservesCFG();
52      MachineFunctionPass::getAnalysisUsage(AU);
53      AU.addRequired<AliasAnalysis>();
54      AU.addRequired<MachineDominatorTree>();
55      AU.addPreserved<MachineDominatorTree>();
56    }
57  private:
58    bool ProcessBlock(MachineBasicBlock &MBB);
59    bool SinkInstruction(MachineInstr *MI, bool &SawStore);
60    bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB) const;
61  };
62} // end anonymous namespace
63
64char MachineSinking::ID = 0;
65static RegisterPass<MachineSinking>
66X("machine-sink", "Machine code sinking");
67
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 {
74  assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
75         "Only makes sense for vregs");
76  for (MachineRegisterInfo::use_iterator I = RegInfo->use_begin(Reg),
77       E = RegInfo->use_end(); I != E; ++I) {
78    // 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
93bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
94  DEBUG(errs() << "******** Machine Sinking ********\n");
95
96  const TargetMachine &TM = MF.getTarget();
97  TII = TM.getInstrInfo();
98  TRI = TM.getRegisterInfo();
99  RegInfo = &MF.getRegInfo();
100  DT = &getAnalysis<MachineDominatorTree>();
101  AA = &getAnalysis<AliasAnalysis>();
102  AllocatableSet = TRI->getAllocatableSet(MF);
103
104  bool EverMadeChange = false;
105
106  while (1) {
107    bool MadeChange = false;
108
109    // Process all basic blocks.
110    for (MachineFunction::iterator I = MF.begin(), E = MF.end();
111         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) {
122  // Can't sink anything out of a block that has less than two successors.
123  if (MBB.succ_size() <= 1 || MBB.empty()) return false;
124
125  bool MadeChange = false;
126
127  // Walk the basic block bottom-up.  Remember if we saw a store.
128  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);
145
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.
151bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) {
152  // Check if it's safe to move the instruction.
153  if (!MI->isSafeToMove(TII, SawStore, AA))
154    return false;
155
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
162  // and z and only shrink the live range of x.
163
164  // 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);
174    if (!MO.isReg()) continue;  // Ignore non-register operands.
175
176    unsigned Reg = MO.getReg();
177    if (Reg == 0) continue;
178
179    if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
180      if (MO.isUse()) {
181        // If the physreg has no defs anywhere, it's just an ambient register
182        // and we can freely move its uses. Alternatively, if it's allocatable,
183        // it could get allocated to something with a def during allocation.
184        if (!RegInfo->def_empty(Reg))
185          return false;
186        if (AllocatableSet.test(Reg))
187          return false;
188        // Check for a def among the register's aliases too.
189        for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
190          unsigned AliasReg = *Alias;
191          if (!RegInfo->def_empty(AliasReg))
192            return false;
193          if (AllocatableSet.test(AliasReg))
194            return false;
195        }
196      } else if (!MO.isDead()) {
197        // A def that isn't dead. We can't move it.
198        return false;
199      }
200    } else {
201      // Virtual register uses are always safe to sink.
202      if (MO.isUse()) continue;
203
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;
207
208      // 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
219      // 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
245  // If there are no outputs, it must have side-effects.
246  if (SuccToSinkTo == 0)
247    return false;
248
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;
253
254  // It is not possible to sink an instruction into its own block.  This can
255  // happen with loops.
256  if (MI->getParent() == SuccToSinkTo)
257    return false;
258
259  DEBUG(errs() << "Sink instr " << *MI);
260  DEBUG(errs() << "to block " << *SuccToSinkTo);
261
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.
265  // FIXME: Split critical edges if not backedges.
266  if (SuccToSinkTo->pred_size() > 1) {
267    DEBUG(errs() << " *** PUNTING: Critical edge found\n");
268    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}
282