SplitKit.h revision f0179004e94259a8adab6c48f295ea9ab18af4c3 
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#include "llvm/CodeGen/SlotIndexes.h"
18
19namespace llvm {
20
21class LiveInterval;
22class LiveIntervals;
23class MachineInstr;
24class MachineLoop;
25class MachineLoopInfo;
26class MachineRegisterInfo;
27class TargetInstrInfo;
28class VirtRegMap;
29class VNInfo;
30
31/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
32/// opportunities.
33class SplitAnalysis {
34  const MachineFunction &mf_;
35  const LiveIntervals &lis_;
36  const MachineLoopInfo &loops_;
37  const TargetInstrInfo &tii_;
38
39  // Current live interval.
40  const LiveInterval *curli_;
41
42  // Instructions using the the current register.
43  typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
44  InstrPtrSet usingInstrs_;
45
46  // The number of instructions using curli in each basic block.
47  typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
48  BlockCountMap usingBlocks_;
49
50  // Loops where the curent interval is used.
51  typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
52  LoopPtrSet usingLoops_;
53
54  // Sumarize statistics by counting instructions using curli_.
55  void analyzeUses();
56
57  /// canAnalyzeBranch - Return true if MBB ends in a branch that can be
58  /// analyzed.
59  bool canAnalyzeBranch(const MachineBasicBlock *MBB);
60
61public:
62  SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis,
63                const MachineLoopInfo &mli);
64
65  /// analyze - set curli to the specified interval, and analyze how it may be
66  /// split.
67  void analyze(const LiveInterval *li);
68
69  const LiveInterval *getCurLI() { return curli_; }
70
71  /// clear - clear all data structures so SplitAnalysis is ready to analyze a
72  /// new interval.
73  void clear();
74
75  typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
76
77  // Sets of basic blocks surrounding a machine loop.
78  struct LoopBlocks {
79    BlockPtrSet Loop;  // Blocks in the loop.
80    BlockPtrSet Preds; // Loop predecessor blocks.
81    BlockPtrSet Exits; // Loop exit blocks.
82
83    void clear() {
84      Loop.clear();
85      Preds.clear();
86      Exits.clear();
87    }
88  };
89
90  // Calculate the block sets surrounding the loop.
91  void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
92
93  /// LoopPeripheralUse - how is a variable used in and around a loop?
94  /// Peripheral blocks are the loop predecessors and exit blocks.
95  enum LoopPeripheralUse {
96    ContainedInLoop,  // All uses are inside the loop.
97    SinglePeripheral, // At most one instruction per peripheral block.
98    MultiPeripheral,  // Multiple instructions in some peripheral blocks.
99    OutsideLoop       // Uses outside loop periphery.
100  };
101
102  /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
103  /// and around the Loop.
104  LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
105
106  /// getCriticalExits - It may be necessary to partially break critical edges
107  /// leaving the loop if an exit block has phi uses of curli. Collect the exit
108  /// blocks that need special treatment into CriticalExits.
109  void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits);
110
111  /// canSplitCriticalExits - Return true if it is possible to insert new exit
112  /// blocks before the blocks in CriticalExits.
113  bool canSplitCriticalExits(const LoopBlocks &Blocks,
114                             BlockPtrSet &CriticalExits);
115
116  /// getBestSplitLoop - Return the loop where curli may best be split to a
117  /// separate register, or NULL.
118  const MachineLoop *getBestSplitLoop();
119};
120
121/// SplitEditor - Edit machine code and LiveIntervals for live range
122/// splitting.
123///
124/// 1. Create a SplitEditor from a SplitAnalysis. This will create a new
125///    LiveInterval, dupli, that is identical to SA.curli.
126/// 2. Start a new live interval with openLI.
127/// 3. Insert copies to the new interval with copyTo* and mark the ranges where
128///    it should be used with use*.
129/// 4. Insert back-copies with copyFromLI.
130/// 5. Finish the current LI with closeLI and repeat from 2.
131/// 6. Rewrite instructions with rewrite().
132///
133class SplitEditor {
134  SplitAnalysis &sa_;
135  LiveIntervals &lis_;
136  VirtRegMap &vrm_;
137  MachineRegisterInfo &mri_;
138  const TargetInstrInfo &tii_;
139
140  /// dupli_ - Created as a copy of sa_.curli_, ranges are carved out as new
141  /// intervals get added through openLI / closeLI.
142  LiveInterval *dupli_;
143
144  /// Currently open LiveInterval.
145  LiveInterval *openli_;
146
147  /// createInterval - Create a new virtual register and LiveInterval with same
148  /// register class and spill slot as curli.
149  LiveInterval *createInterval();
150
151	/// valueMap_ - Map values in dupli to values in openli. These are direct 1-1
152	/// mappings, and do not include values created by inserted copies.
153	DenseMap<VNInfo*,VNInfo*> valueMap_;
154
155	/// mapValue - Return the openli value that corresponds to the given dupli
156	/// value.
157	VNInfo *mapValue(VNInfo *dupliVNI);
158
159public:
160  /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
161  SplitEditor(SplitAnalysis&, LiveIntervals&, VirtRegMap&);
162
163	/// getAnalysis - Get the corresponding analysis.
164	SplitAnalysis &getAnalysis() { return sa_; }
165
166  /// Create a new virtual register and live interval to be used by following
167  /// use* and copy* calls.
168  void openLI();
169
170  /// copyToPHI - Insert a copy to openli at the end of A, and catch it with a
171  /// PHI def at the beginning of the successor B. This call is ignored if dupli
172  /// is not live out of A.
173  void copyToPHI(MachineBasicBlock &A, MachineBasicBlock &B);
174
175  /// useLI - indicate that all instructions in MBB should use openli.
176  void useLI(const MachineBasicBlock &MBB);
177
178  /// useLI - indicate that all instructions in range should use openli.
179  void useLI(SlotIndex Start, SlotIndex End);
180
181  /// copyFromLI - Insert a copy back to dupli from openli at position I.
182	/// This also marks the remainder of MBB as not used by openli.
183  SlotIndex copyFromLI(MachineBasicBlock &MBB, MachineBasicBlock::iterator I);
184
185  /// closeLI - Indicate that we are done editing the currently open
186  /// LiveInterval, and ranges can be trimmed.
187  void closeLI();
188
189  /// rewrite - after all the new live ranges have been created, rewrite
190  /// instructions using curli to use the new intervals.
191  void rewrite();
192
193  // ===--- High level methods ---===
194
195  /// splitAroundLoop - Split curli into a separate live interval inside
196  /// the loop.
197  void splitAroundLoop(const MachineLoop*);
198
199};
200
201
202}
203