← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/SplitKit.h

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/SplitKit.h
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
 
 
19
 
namespace llvm {
20
 
 
21
 
class LiveInterval;
22
 
class LiveIntervals;
23
 
class MachineInstr;
24
 
class MachineLoop;
25
 
class MachineLoopInfo;
26
 
class MachineRegisterInfo;
27
 
class TargetInstrInfo;
28
 
class VirtRegMap;
29
 
class VNInfo;
30
 
 
31
 
/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
32
 
/// opportunities.
33
 
class SplitAnalysis {
34
 
public:
35
 
  const MachineFunction &mf_;
36
 
  const LiveIntervals &lis_;
37
 
  const MachineLoopInfo &loops_;
38
 
  const TargetInstrInfo &tii_;
39
 
 
40
 
  // Instructions using the the current register.
41
 
  typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
42
 
  InstrPtrSet usingInstrs_;
43
 
 
44
 
  // The number of instructions using curli in each basic block.
45
 
  typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
46
 
  BlockCountMap usingBlocks_;
47
 
 
48
 
  // The number of basic block using curli in each loop.
49
 
  typedef DenseMap<const MachineLoop*, unsigned> LoopCountMap;
50
 
  LoopCountMap usingLoops_;
51
 
 
52
 
private:
53
 
  // Current live interval.
54
 
  const LiveInterval *curli_;
55
 
 
56
 
  // Sumarize statistics by counting instructions using curli_.
57
 
  void analyzeUses();
58
 
 
59
 
  /// canAnalyzeBranch - Return true if MBB ends in a branch that can be
60
 
  /// analyzed.
61
 
  bool canAnalyzeBranch(const MachineBasicBlock *MBB);
62
 
 
63
 
public:
64
 
  SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis,
65
 
                const MachineLoopInfo &mli);
66
 
 
67
 
  /// analyze - set curli to the specified interval, and analyze how it may be
68
 
  /// split.
69
 
  void analyze(const LiveInterval *li);
70
 
 
71
 
  /// removeUse - Update statistics by noting that mi no longer uses curli.
72
 
  void removeUse(const MachineInstr *mi);
73
 
 
74
 
  const LiveInterval *getCurLI() { return curli_; }
75
 
 
76
 
  /// clear - clear all data structures so SplitAnalysis is ready to analyze a
77
 
  /// new interval.
78
 
  void clear();
79
 
 
80
 
  typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
81
 
  typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
82
 
 
83
 
  // Sets of basic blocks surrounding a machine loop.
84
 
  struct LoopBlocks {
85
 
    BlockPtrSet Loop;  // Blocks in the loop.
86
 
    BlockPtrSet Preds; // Loop predecessor blocks.
87
 
    BlockPtrSet Exits; // Loop exit blocks.
88
 
 
89
 
    void clear() {
90
 
      Loop.clear();
91
 
      Preds.clear();
92
 
      Exits.clear();
93
 
    }
94
 
  };
95
 
 
96
 
  // Calculate the block sets surrounding the loop.
97
 
  void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
98
 
 
99
 
  /// LoopPeripheralUse - how is a variable used in and around a loop?
100
 
  /// Peripheral blocks are the loop predecessors and exit blocks.
101
 
  enum LoopPeripheralUse {
102
 
    ContainedInLoop,  // All uses are inside the loop.
103
 
    SinglePeripheral, // At most one instruction per peripheral block.
104
 
    MultiPeripheral,  // Multiple instructions in some peripheral blocks.
105
 
    OutsideLoop       // Uses outside loop periphery.
106
 
  };
107
 
 
108
 
  /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
109
 
  /// and around the Loop.
110
 
  LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
111
 
 
112
 
  /// getCriticalExits - It may be necessary to partially break critical edges
113
 
  /// leaving the loop if an exit block has phi uses of curli. Collect the exit
114
 
  /// blocks that need special treatment into CriticalExits.
115
 
  void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits);
116
 
 
117
 
  /// canSplitCriticalExits - Return true if it is possible to insert new exit
118
 
  /// blocks before the blocks in CriticalExits.
119
 
  bool canSplitCriticalExits(const LoopBlocks &Blocks,
120
 
                             BlockPtrSet &CriticalExits);
121
 
 
122
 
  /// getBestSplitLoop - Return the loop where curli may best be split to a
123
 
  /// separate register, or NULL.
124
 
  const MachineLoop *getBestSplitLoop();
125
 
 
126
 
  /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from
127
 
  /// having curli split to a new live interval. Return true if Blocks can be
128
 
  /// passed to SplitEditor::splitSingleBlocks.
129
 
  bool getMultiUseBlocks(BlockPtrSet &Blocks);
130
 
 
131
 
  /// getBlockForInsideSplit - If curli is contained inside a single basic block,
132
 
  /// and it wou pay to subdivide the interval inside that block, return it.
133
 
  /// Otherwise return NULL. The returned block can be passed to
134
 
  /// SplitEditor::splitInsideBlock.
135
 
  const MachineBasicBlock *getBlockForInsideSplit();
136
 
};
137
 
 
138
 
 
139
 
/// LiveIntervalMap - Map values from a large LiveInterval into a small
140
 
/// interval that is a subset. Insert phi-def values as needed. This class is
141
 
/// used by SplitEditor to create new smaller LiveIntervals.
142
 
///
143
 
/// parentli_ is the larger interval, li_ is the subset interval. Every value
144
 
/// in li_ corresponds to exactly one value in parentli_, and the live range
145
 
/// of the value is contained within the live range of the parentli_ value.
146
 
/// Values in parentli_ may map to any number of openli_ values, including 0.
147
 
class LiveIntervalMap {
148
 
  LiveIntervals &lis_;
149
 
 
150
 
  // The parent interval is never changed.
151
 
  const LiveInterval &parentli_;
152
 
 
153
 
  // The child interval's values are fully contained inside parentli_ values.
154
 
  LiveInterval &li_;
155
 
 
156
 
  typedef DenseMap<const VNInfo*, VNInfo*> ValueMap;
157
 
 
158
 
  // Map parentli_ values to simple values in li_ that are defined at the same
159
 
  // SlotIndex, or NULL for parentli_ values that have complex li_ defs.
160
 
  // Note there is a difference between values mapping to NULL (complex), and
161
 
  // values not present (unknown/unmapped).
162
 
  ValueMap valueMap_;
163
 
 
164
 
  // extendTo - Find the last li_ value defined in MBB at or before Idx. The
165
 
  // parentli_ is assumed to be live at Idx. Extend the live range to Idx.
166
 
  // Return the found VNInfo, or NULL.
167
 
  VNInfo *extendTo(MachineBasicBlock *MBB, SlotIndex Idx);
168
 
 
169
 
  // addSimpleRange - Add a simple range from parentli_ to li_.
170
 
  // ParentVNI must be live in the [Start;End) interval.
171
 
  void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI);
172
 
 
173
 
public:
174
 
  LiveIntervalMap(LiveIntervals &lis,
175
 
                  const LiveInterval &parentli,
176
 
                  LiveInterval &li)
177
 
    : lis_(lis), parentli_(parentli), li_(li) {}
178
 
 
179
 
  /// defValue - define a value in li_ from the parentli_ value VNI and Idx.
180
 
  /// Idx does not have to be ParentVNI->def, but it must be contained within
181
 
  /// ParentVNI's live range in parentli_.
182
 
  /// Return the new li_ value.
183
 
  VNInfo *defValue(const VNInfo *ParentVNI, SlotIndex Idx);
184
 
 
185
 
  /// mapValue - map ParentVNI to the corresponding li_ value at Idx. It is
186
 
  /// assumed that ParentVNI is live at Idx.
187
 
  /// If ParentVNI has not been defined by defValue, it is assumed that
188
 
  /// ParentVNI->def dominates Idx.
189
 
  /// If ParentVNI has been defined by defValue one or more times, a value that
190
 
  /// dominates Idx will be returned. This may require creating extra phi-def
191
 
  /// values and adding live ranges to li_.
192
 
  VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx);
193
 
 
194
 
  /// addRange - Add live ranges to li_ where [Start;End) intersects parentli_.
195
 
  /// All needed values whose def is not inside [Start;End) must be defined
196
 
  /// beforehand so mapValue will work.
197
 
  void addRange(SlotIndex Start, SlotIndex End);
198
 
};
199
 
 
200
 
 
201
 
/// SplitEditor - Edit machine code and LiveIntervals for live range
202
 
/// splitting.
203
 
///
204
 
/// - Create a SplitEditor from a SplitAnalysis.
205
 
/// - Start a new live interval with openIntv.
206
 
/// - Mark the places where the new interval is entered using enterIntv*
207
 
/// - Mark the ranges where the new interval is used with useIntv* 
208
 
/// - Mark the places where the interval is exited with exitIntv*.
209
 
/// - Finish the current interval with closeIntv and repeat from 2.
210
 
/// - Rewrite instructions with rewrite().
211
 
///
212
 
class SplitEditor {
213
 
  SplitAnalysis &sa_;
214
 
  LiveIntervals &lis_;
215
 
  VirtRegMap &vrm_;
216
 
  MachineRegisterInfo &mri_;
217
 
  const TargetInstrInfo &tii_;
218
 
 
219
 
  /// curli_ - The immutable interval we are currently splitting.
220
 
  const LiveInterval *const curli_;
221
 
 
222
 
  /// dupli_ - Created as a copy of curli_, ranges are carved out as new
223
 
  /// intervals get added through openIntv / closeIntv. This is used to avoid
224
 
  /// editing curli_.
225
 
  LiveInterval *dupli_;
226
 
 
227
 
  /// Currently open LiveInterval.
228
 
  LiveInterval *openli_;
229
 
 
230
 
  /// createInterval - Create a new virtual register and LiveInterval with same
231
 
  /// register class and spill slot as curli.
232
 
  LiveInterval *createInterval();
233
 
 
234
 
  /// getDupLI - Ensure dupli is created and return it.
235
 
  LiveInterval *getDupLI();
236
 
 
237
 
  /// valueMap_ - Map values in cupli to values in openli. These are direct 1-1
238
 
  /// mappings, and do not include values created by inserted copies.
239
 
  DenseMap<const VNInfo*, VNInfo*> valueMap_;
240
 
 
241
 
  /// mapValue - Return the openIntv value that corresponds to the given curli
242
 
  /// value.
243
 
  VNInfo *mapValue(const VNInfo *curliVNI);
244
 
 
245
 
  /// A dupli value is live through openIntv.
246
 
  bool liveThrough_;
247
 
 
248
 
  /// All the new intervals created for this split are added to intervals_.
249
 
  SmallVectorImpl<LiveInterval*> &intervals_;
250
 
 
251
 
  /// The index into intervals_ of the first interval we added. There may be
252
 
  /// others from before we got it.
253
 
  unsigned firstInterval;
254
 
 
255
 
  /// Insert a COPY instruction curli -> li. Allocate a new value from li
256
 
  /// defined by the COPY
257
 
  VNInfo *insertCopy(LiveInterval &LI,
258
 
                     MachineBasicBlock &MBB,
259
 
                     MachineBasicBlock::iterator I);
260
 
 
261
 
public:
262
 
  /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
263
 
  /// Newly created intervals will be appended to newIntervals.
264
 
  SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&,
265
 
              SmallVectorImpl<LiveInterval*> &newIntervals);
266
 
 
267
 
  /// getAnalysis - Get the corresponding analysis.
268
 
  SplitAnalysis &getAnalysis() { return sa_; }
269
 
 
270
 
  /// Create a new virtual register and live interval.
271
 
  void openIntv();
272
 
 
273
 
  /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is
274
 
  /// not live before Idx, a COPY is not inserted.
275
 
  void enterIntvBefore(SlotIndex Idx);
276
 
 
277
 
  /// enterIntvAtEnd - Enter openli at the end of MBB.
278
 
  /// PhiMBB is a successor inside openli where a PHI value is created.
279
 
  /// Currently, all entries must share the same PhiMBB.
280
 
  void enterIntvAtEnd(MachineBasicBlock &MBB, MachineBasicBlock &PhiMBB);
281
 
 
282
 
  /// useIntv - indicate that all instructions in MBB should use openli.
283
 
  void useIntv(const MachineBasicBlock &MBB);
284
 
 
285
 
  /// useIntv - indicate that all instructions in range should use openli.
286
 
  void useIntv(SlotIndex Start, SlotIndex End);
287
 
 
288
 
  /// leaveIntvAfter - Leave openli after the instruction at Idx.
289
 
  void leaveIntvAfter(SlotIndex Idx);
290
 
 
291
 
  /// leaveIntvAtTop - Leave the interval at the top of MBB.
292
 
  /// Currently, only one value can leave the interval.
293
 
  void leaveIntvAtTop(MachineBasicBlock &MBB);
294
 
 
295
 
  /// closeIntv - Indicate that we are done editing the currently open
296
 
  /// LiveInterval, and ranges can be trimmed.
297
 
  void closeIntv();
298
 
 
299
 
  /// rewrite - after all the new live ranges have been created, rewrite
300
 
  /// instructions using curli to use the new intervals.
301
 
  void rewrite();
302
 
 
303
 
  // ===--- High level methods ---===
304
 
 
305
 
  /// splitAroundLoop - Split curli into a separate live interval inside
306
 
  /// the loop. Return true if curli has been completely replaced, false if
307
 
  /// curli is still intact, and needs to be spilled or split further.
308
 
  bool splitAroundLoop(const MachineLoop*);
309
 
 
310
 
  /// splitSingleBlocks - Split curli into a separate live interval inside each
311
 
  /// basic block in Blocks. Return true if curli has been completely replaced,
312
 
  /// false if curli is still intact, and needs to be spilled or split further.
313
 
  bool splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks);
314
 
 
315
 
  /// splitInsideBlock - Split curli into multiple intervals inside MBB. Return
316
 
  /// true if curli has been completely replaced, false if curli is still
317
 
  /// intact, and needs to be spilled or split further.
318
 
  bool splitInsideBlock(const MachineBasicBlock *);
319
 
};
320
 
 
321
 
}