MachineTraceMetrics.cpp revision 9f63e104271eb91e545fa8cdb16fb9e10a8a9578 
1//===- lib/CodeGen/MachineTraceMetrics.cpp ----------------------*- C++ -*-===//
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#define DEBUG_TYPE "early-ifcvt"
11#include "MachineTraceMetrics.h"
12#include "llvm/CodeGen/MachineBasicBlock.h"
13#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
14#include "llvm/CodeGen/MachineLoopInfo.h"
15#include "llvm/CodeGen/MachineRegisterInfo.h"
16#include "llvm/CodeGen/Passes.h"
17#include "llvm/Target/TargetInstrInfo.h"
18#include "llvm/Target/TargetRegisterInfo.h"
19#include "llvm/Support/Debug.h"
20#include "llvm/Support/raw_ostream.h"
21#include "llvm/ADT/PostOrderIterator.h"
22
23using namespace llvm;
24
25char MachineTraceMetrics::ID = 0;
26char &llvm::MachineTraceMetricsID = MachineTraceMetrics::ID;
27
28INITIALIZE_PASS_BEGIN(MachineTraceMetrics,
29                  "machine-trace-metrics", "Machine Trace Metrics", false, true)
30INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
31INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
32INITIALIZE_PASS_END(MachineTraceMetrics,
33                  "machine-trace-metrics", "Machine Trace Metrics", false, true)
34
35MachineTraceMetrics::MachineTraceMetrics()
36  : MachineFunctionPass(ID), TII(0), TRI(0), MRI(0), Loops(0) {
37  std::fill(Ensembles, array_endof(Ensembles), (Ensemble*)0);
38}
39
40void MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const {
41  AU.setPreservesAll();
42  AU.addRequired<MachineBranchProbabilityInfo>();
43  AU.addRequired<MachineLoopInfo>();
44  MachineFunctionPass::getAnalysisUsage(AU);
45}
46
47bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &MF) {
48  TII = MF.getTarget().getInstrInfo();
49  TRI = MF.getTarget().getRegisterInfo();
50  MRI = &MF.getRegInfo();
51  Loops = &getAnalysis<MachineLoopInfo>();
52  unsigned NumBlocks = MF.getNumBlockIDs();
53  BlockInfo.resize(NumBlocks);
54  return false;
55}
56
57void MachineTraceMetrics::releaseMemory() {
58  BlockInfo.clear();
59  for (unsigned i = 0; i != TS_NumStrategies; ++i) {
60    delete Ensembles[i];
61    Ensembles[i] = 0;
62  }
63}
64
65//===----------------------------------------------------------------------===//
66//                          Fixed block information
67//===----------------------------------------------------------------------===//
68//
69// The number of instructions in a basic block and the CPU resources used by
70// those instructions don't depend on any given trace strategy.
71
72/// Is MI an instruction that should be considered free because it will likely
73/// be eliminated by later passes?
74static bool isFree(const MachineInstr *MI) {
75  switch(MI->getOpcode()) {
76  default: return false;
77  case TargetOpcode::PHI:
78  case TargetOpcode::PROLOG_LABEL:
79  case TargetOpcode::EH_LABEL:
80  case TargetOpcode::GC_LABEL:
81  case TargetOpcode::KILL:
82  case TargetOpcode::EXTRACT_SUBREG:
83  case TargetOpcode::INSERT_SUBREG:
84  case TargetOpcode::IMPLICIT_DEF:
85  case TargetOpcode::SUBREG_TO_REG:
86  case TargetOpcode::COPY_TO_REGCLASS:
87  case TargetOpcode::DBG_VALUE:
88  case TargetOpcode::REG_SEQUENCE:
89  case TargetOpcode::COPY:
90    return true;
91  }
92}
93
94/// Compute the resource usage in basic block MBB.
95const MachineTraceMetrics::FixedBlockInfo*
96MachineTraceMetrics::getResources(const MachineBasicBlock *MBB) {
97  assert(MBB && "No basic block");
98  FixedBlockInfo *FBI = &BlockInfo[MBB->getNumber()];
99  if (FBI->hasResources())
100    return FBI;
101
102  // Compute resource usage in the block.
103  // FIXME: Compute per-functional unit counts.
104  FBI->HasCalls = false;
105  unsigned InstrCount = 0;
106  for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
107       I != E; ++I) {
108    const MachineInstr *MI = I;
109    if (isFree(MI))
110      continue;
111    ++InstrCount;
112    if (MI->isCall())
113      FBI->HasCalls = true;
114  }
115  FBI->InstrCount = InstrCount;
116  return FBI;
117}
118
119//===----------------------------------------------------------------------===//
120//                         Ensemble utility functions
121//===----------------------------------------------------------------------===//
122
123MachineTraceMetrics::Ensemble::Ensemble(MachineTraceMetrics *ct)
124  : CT(*ct) {
125  BlockInfo.resize(CT.BlockInfo.size());
126}
127
128// Virtual destructor serves as an anchor.
129MachineTraceMetrics::Ensemble::~Ensemble() {}
130
131MachineLoop*
132MachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) {
133  return CT.Loops->getLoopFor(MBB);
134}
135
136// Update resource-related information in the TraceBlockInfo for MBB.
137// Only update resources related to the trace above MBB.
138void MachineTraceMetrics::Ensemble::
139computeDepthResources(const MachineBasicBlock *MBB) {
140  TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
141
142  // Compute resources from trace above. The top block is simple.
143  if (!TBI->Pred) {
144    TBI->InstrDepth = 0;
145    return;
146  }
147
148  // Compute from the block above. A post-order traversal ensures the
149  // predecessor is always computed first.
150  TraceBlockInfo *PredTBI = &BlockInfo[TBI->Pred->getNumber()];
151  assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet");
152  const FixedBlockInfo *PredFBI = CT.getResources(TBI->Pred);
153  TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount;
154}
155
156// Update resource-related information in the TraceBlockInfo for MBB.
157// Only update resources related to the trace below MBB.
158void MachineTraceMetrics::Ensemble::
159computeHeightResources(const MachineBasicBlock *MBB) {
160  TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
161
162  // Compute resources for the current block.
163  TBI->InstrHeight = CT.getResources(MBB)->InstrCount;
164
165  // The trace tail is done.
166  if (!TBI->Succ)
167    return;
168
169  // Compute from the block below. A post-order traversal ensures the
170  // predecessor is always computed first.
171  TraceBlockInfo *SuccTBI = &BlockInfo[TBI->Succ->getNumber()];
172  assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet");
173  TBI->InstrHeight += SuccTBI->InstrHeight;
174}
175
176// Check if depth resources for MBB are valid and return the TBI.
177// Return NULL if the resources have been invalidated.
178const MachineTraceMetrics::TraceBlockInfo*
179MachineTraceMetrics::Ensemble::
180getDepthResources(const MachineBasicBlock *MBB) const {
181  const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
182  return TBI->hasValidDepth() ? TBI : 0;
183}
184
185// Check if height resources for MBB are valid and return the TBI.
186// Return NULL if the resources have been invalidated.
187const MachineTraceMetrics::TraceBlockInfo*
188MachineTraceMetrics::Ensemble::
189getHeightResources(const MachineBasicBlock *MBB) const {
190  const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
191  return TBI->hasValidHeight() ? TBI : 0;
192}
193
194//===----------------------------------------------------------------------===//
195//                         Trace Selection Strategies
196//===----------------------------------------------------------------------===//
197//
198// A trace selection strategy is implemented as a sub-class of Ensemble. The
199// trace through a block B is computed by two DFS traversals of the CFG
200// starting from B. One upwards, and one downwards. During the upwards DFS,
201// pickTracePred() is called on the post-ordered blocks. During the downwards
202// DFS, pickTraceSucc() is called in a post-order.
203//
204
205// MinInstrCountEnsemble - Pick the trace that executes the least number of
206// instructions.
207namespace {
208class MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble {
209  const char *getName() { return "MinInstr"; }
210  const MachineBasicBlock *pickTracePred(const MachineBasicBlock*);
211  const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*);
212
213public:
214  MinInstrCountEnsemble(MachineTraceMetrics *ct)
215    : MachineTraceMetrics::Ensemble(ct) {}
216};
217}
218
219// Select the preferred predecessor for MBB.
220const MachineBasicBlock*
221MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) {
222  if (MBB->pred_empty())
223    return 0;
224  MachineLoop *CurLoop = getLoopFor(MBB);
225  // Don't leave loops, and never follow back-edges.
226  if (CurLoop && MBB == CurLoop->getHeader())
227    return 0;
228  unsigned CurCount = CT.getResources(MBB)->InstrCount;
229  const MachineBasicBlock *Best = 0;
230  unsigned BestDepth = 0;
231  for (MachineBasicBlock::const_pred_iterator
232       I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) {
233    const MachineBasicBlock *Pred = *I;
234    const MachineTraceMetrics::TraceBlockInfo *PredTBI =
235      getDepthResources(Pred);
236    // Ignore invalidated predecessors. This never happens on the first scan,
237    // but if we rejected this predecessor earlier, it won't be revalidated.
238    if (!PredTBI)
239      continue;
240    // Don't consider predecessors in other loops.
241    if (getLoopFor(Pred) != CurLoop)
242      continue;
243    // Pick the predecessor that would give this block the smallest InstrDepth.
244    unsigned Depth = PredTBI->InstrDepth + CurCount;
245    if (!Best || Depth < BestDepth)
246      Best = Pred, BestDepth = Depth;
247  }
248  return Best;
249}
250
251// Select the preferred successor for MBB.
252const MachineBasicBlock*
253MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) {
254  if (MBB->pred_empty())
255    return 0;
256  MachineLoop *CurLoop = getLoopFor(MBB);
257  const MachineBasicBlock *Best = 0;
258  unsigned BestHeight = 0;
259  for (MachineBasicBlock::const_succ_iterator
260       I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) {
261    const MachineBasicBlock *Succ = *I;
262    const MachineTraceMetrics::TraceBlockInfo *SuccTBI =
263      getHeightResources(Succ);
264    // Ignore invalidated successors.
265    if (!SuccTBI)
266      continue;
267    // Don't consider back-edges.
268    if (CurLoop && Succ == CurLoop->getHeader())
269      continue;
270    // Don't consider successors in other loops.
271    if (getLoopFor(Succ) != CurLoop)
272      continue;
273    // Pick the successor that would give this block the smallest InstrHeight.
274    unsigned Height = SuccTBI->InstrHeight;
275    if (!Best || Height < BestHeight)
276      Best = Succ, BestHeight = Height;
277  }
278  return Best;
279}
280
281// Get an Ensemble sub-class for the requested trace strategy.
282MachineTraceMetrics::Ensemble *
283MachineTraceMetrics::getEnsemble(MachineTraceMetrics::Strategy strategy) {
284  assert(strategy < TS_NumStrategies && "Invalid trace strategy enum");
285  Ensemble *&E = Ensembles[strategy];
286  if (E)
287    return E;
288
289  // Allocate new Ensemble on demand.
290  switch (strategy) {
291  case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this));
292  default: llvm_unreachable("Invalid trace strategy enum");
293  }
294}
295
296void MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) {
297  DEBUG(dbgs() << "Invalidate traces through BB#" << MBB->getNumber() << '\n');
298  BlockInfo[MBB->getNumber()].invalidate();
299  for (unsigned i = 0; i != TS_NumStrategies; ++i)
300    if (Ensembles[i])
301      Ensembles[i]->invalidate(MBB);
302}
303
304//===----------------------------------------------------------------------===//
305//                               Trace building
306//===----------------------------------------------------------------------===//
307//
308// Traces are built by two CFG traversals. To avoid recomputing too much, use a
309// set abstraction that confines the search to the current loop, and doesn't
310// revisit blocks.
311
312namespace {
313struct LoopBounds {
314  MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks;
315  const MachineLoopInfo *Loops;
316  const MachineLoop *CurLoop;
317  bool Downward;
318  LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks,
319             const MachineLoopInfo *loops, const MachineLoop *curloop)
320    : Blocks(blocks), Loops(loops), CurLoop(curloop), Downward(false) {}
321};
322}
323
324// Specialize po_iterator_storage in order to prune the post-order traversal so
325// it is limited to the current loop and doesn't traverse the loop back edges.
326namespace llvm {
327template<>
328class po_iterator_storage<LoopBounds, true> {
329  LoopBounds &LB;
330public:
331  po_iterator_storage(LoopBounds &lb) : LB(lb) {}
332  void finishPostorder(const MachineBasicBlock*) {}
333
334  bool insertEdge(const MachineBasicBlock *From, const MachineBasicBlock *To) {
335    // Skip already visited To blocks.
336    MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()];
337    if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth())
338      return false;
339    // Don't follow CurLoop backedges.
340    if (LB.CurLoop && (LB.Downward ? To : From) == LB.CurLoop->getHeader())
341      return false;
342    // Don't leave CurLoop.
343    if (LB.Loops->getLoopFor(To) != LB.CurLoop)
344      return false;
345    // This is a new block. The PO traversal will compute height/depth
346    // resources, causing us to reject new edges to To. This only works because
347    // we reject back-edges, so the CFG is cycle-free.
348    return true;
349  }
350};
351}
352
353/// Compute the trace through MBB.
354void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) {
355  DEBUG(dbgs() << "Computing " << getName() << " trace through BB#"
356               << MBB->getNumber() << '\n');
357  // Set up loop bounds for the backwards post-order traversal.
358  LoopBounds Bounds(BlockInfo, CT.Loops, getLoopFor(MBB));
359
360  // Run an upwards post-order search for the trace start.
361  Bounds.Downward = false;
362  typedef ipo_ext_iterator<const MachineBasicBlock*, LoopBounds> UpwardPO;
363  for (UpwardPO I = ipo_ext_begin(MBB, Bounds), E = ipo_ext_end(MBB, Bounds);
364       I != E; ++I) {
365    DEBUG(dbgs() << "  pred for BB#" << I->getNumber() << ": ");
366    TraceBlockInfo &TBI = BlockInfo[I->getNumber()];
367    // All the predecessors have been visited, pick the preferred one.
368    TBI.Pred = pickTracePred(*I);
369    DEBUG({
370      if (TBI.Pred)
371        dbgs() << "BB#" << TBI.Pred->getNumber() << '\n';
372      else
373        dbgs() << "null\n";
374    });
375    // The trace leading to I is now known, compute the depth resources.
376    computeDepthResources(*I);
377  }
378
379  // Run a downwards post-order search for the trace end.
380  Bounds.Downward = true;
381  typedef po_ext_iterator<const MachineBasicBlock*, LoopBounds> DownwardPO;
382  for (DownwardPO I = po_ext_begin(MBB, Bounds), E = po_ext_end(MBB, Bounds);
383       I != E; ++I) {
384    DEBUG(dbgs() << "  succ for BB#" << I->getNumber() << ": ");
385    TraceBlockInfo &TBI = BlockInfo[I->getNumber()];
386    // All the successors have been visited, pick the preferred one.
387    BlockInfo[I->getNumber()].Succ = pickTraceSucc(*I);
388    DEBUG({
389      if (TBI.Pred)
390        dbgs() << "BB#" << TBI.Succ->getNumber() << '\n';
391      else
392        dbgs() << "null\n";
393    });
394    // The trace leaving I is now known, compute the height resources.
395    computeHeightResources(*I);
396  }
397}
398
399/// Invalidate traces through BadMBB.
400void
401MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) {
402  SmallVector<const MachineBasicBlock*, 16> WorkList;
403  TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()];
404
405  // Invalidate height resources of blocks above MBB.
406  if (BadTBI.hasValidHeight()) {
407    BadTBI.invalidateHeight();
408    WorkList.push_back(BadMBB);
409    do {
410      const MachineBasicBlock *MBB = WorkList.pop_back_val();
411      DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName()
412            << " height.\n");
413      // Find any MBB predecessors that have MBB as their preferred successor.
414      // They are the only ones that need to be invalidated.
415      for (MachineBasicBlock::const_pred_iterator
416           I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) {
417        TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()];
418        if (TBI.hasValidHeight() && TBI.Succ == MBB) {
419          TBI.invalidateHeight();
420          WorkList.push_back(*I);
421        }
422      }
423    } while (!WorkList.empty());
424  }
425
426  // Invalidate depth resources of blocks below MBB.
427  if (BadTBI.hasValidDepth()) {
428    BadTBI.invalidateDepth();
429    WorkList.push_back(BadMBB);
430    do {
431      const MachineBasicBlock *MBB = WorkList.pop_back_val();
432      DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName()
433            << " depth.\n");
434      // Find any MBB successors that have MBB as their preferred predecessor.
435      // They are the only ones that need to be invalidated.
436      for (MachineBasicBlock::const_succ_iterator
437           I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) {
438        TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()];
439        if (TBI.hasValidDepth() && TBI.Pred == MBB) {
440          TBI.invalidateDepth();
441          WorkList.push_back(*I);
442        }
443      }
444    } while (!WorkList.empty());
445  }
446}
447
448
449MachineTraceMetrics::Trace
450MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) {
451  // FIXME: Check cache tags, recompute as needed.
452  computeTrace(MBB);
453  return Trace(*this, BlockInfo[MBB->getNumber()]);
454}
455
456void MachineTraceMetrics::Trace::print(raw_ostream &OS) const {
457  OS << TE.getName() << " trace:";
458  if (TBI.hasValidHeight() && TBI.hasValidDepth())
459    OS << ' ' << getInstrCount() << " instrs.";
460
461  const MachineTraceMetrics::TraceBlockInfo *Block = &TBI;
462  OS << "\n *";
463  while (Block->hasValidDepth() && Block->Pred) {
464    unsigned Num = Block->Pred->getNumber();
465    OS << " <- BB#" << Num;
466    Block = &TE.BlockInfo[Num];
467  }
468
469  Block = &TBI;
470  OS << "\n *";
471  while (Block->hasValidHeight() && Block->Succ) {
472    unsigned Num = Block->Succ->getNumber();
473    OS << " -> BB#" << Num;
474    Block = &TE.BlockInfo[Num];
475  }
476  OS << '\n';
477}
478