SplitKit.h revision 1c2a730810e1039c1fcce2386a3e924a5efaddad 
1//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===//
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 file contains the SplitAnalysis class as well as mutator functions for
11// live range splitting.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/ADT/SmallPtrSet.h"
16#include "llvm/ADT/DenseMap.h"
17
18namespace llvm {
19
20class LiveInterval;
21class LiveIntervals;
22class MachineBasicBlock;
23class MachineInstr;
24class MachineFunction;
25class MachineFunctionPass;
26class MachineLoop;
27class MachineLoopInfo;
28class TargetInstrInfo;
29
30class SplitAnalysis {
31  const MachineFunction &mf_;
32  const LiveIntervals &lis_;
33  const MachineLoopInfo &loops_;
34  const TargetInstrInfo &tii_;
35
36  // Current live interval.
37  const LiveInterval *curli_;
38
39  // Instructions using the the current register.
40  typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
41  InstrPtrSet usingInstrs_;
42
43  // The number of instructions using curli in each basic block.
44  typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
45  BlockCountMap usingBlocks_;
46
47  // Loops where the curent interval is used.
48  typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
49  LoopPtrSet usingLoops_;
50
51  // Sumarize statistics by counting instructions using curli_.
52  void analyzeUses();
53
54  /// canAnalyzeBranch - Return true if MBB ends in a branch that can be
55  /// analyzed.
56  bool canAnalyzeBranch(const MachineBasicBlock *MBB);
57
58public:
59  SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis,
60                const MachineLoopInfo &mli);
61
62  /// analyze - set curli to the specified interval, and analyze how it may be
63  /// split.
64  void analyze(const LiveInterval *li);
65
66  /// clear - clear all data structures so SplitAnalysis is ready to analyze a
67  /// new interval.
68  void clear();
69
70  typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
71
72  // Sets of basic blocks surrounding a machine loop.
73  struct LoopBlocks {
74    BlockPtrSet Loop;  // Blocks in the loop.
75    BlockPtrSet Preds; // Loop predecessor blocks.
76    BlockPtrSet Exits; // Loop exit blocks.
77
78    void clear() {
79      Loop.clear();
80      Preds.clear();
81      Exits.clear();
82    }
83  };
84
85  // Calculate the block sets surrounding the loop.
86  void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
87
88  /// LoopPeripheralUse - how is a variable used in and around a loop?
89  /// Peripheral blocks are the loop predecessors and exit blocks.
90  enum LoopPeripheralUse {
91    ContainedInLoop,  // All uses are inside the loop.
92    SinglePeripheral, // At most one instruction per peripheral block.
93    MultiPeripheral,  // Multiple instructions in some peripheral blocks.
94    OutsideLoop       // Uses outside loop periphery.
95  };
96
97  /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
98  /// and around the Loop.
99  LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
100
101  /// getCriticalExits - It may be necessary to partially break critical edges
102  /// leaving the loop if an exit block has phi uses of curli. Collect the exit
103  /// blocks that need special treatment into CriticalExits.
104  void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits);
105
106  /// canSplitCriticalExits - Return true if it is possible to insert new exit
107  /// blocks before the blocks in CriticalExits.
108  bool canSplitCriticalExits(const LoopBlocks &Blocks,
109                             BlockPtrSet &CriticalExits);
110
111  /// getBestSplitLoop - Return the loop where curli may best be split to a
112  /// separate register, or NULL.
113  const MachineLoop *getBestSplitLoop();
114};
115
116/// splitAroundLoop - Try to split curli into a separate live interval inside
117/// the loop. Retun true on success.
118bool splitAroundLoop(SplitAnalysis&, const MachineLoop*);
119
120}
121