SplitKit.h revision abff28087fd6be8150ff0e69def7de7312b2f76b 
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;
28
29class SplitAnalysis {
30  const MachineFunction &mf_;
31  const LiveIntervals &lis_;
32  const MachineLoopInfo &loops_;
33
34  // Current live interval.
35  const LiveInterval *curli_;
36
37  // Instructions using the the current register.
38  typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
39  InstrPtrSet usingInstrs_;
40
41  // The number of instructions using curli in each basic block.
42  typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
43  BlockCountMap usingBlocks_;
44
45  // Loops where the curent interval is used.
46  typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
47  LoopPtrSet usingLoops_;
48
49  // Sumarize statistics by counting instructions using curli_.
50  void analyzeUses();
51
52public:
53  SplitAnalysis(const MachineFunction *mf, const LiveIntervals *lis,
54                const MachineLoopInfo *mli);
55
56  /// analyze - set curli to the specified interval, and analyze how it may be
57  /// split.
58  void analyze(const LiveInterval *li);
59
60  /// clear - clear all data structures so SplitAnalysis is ready to analyze a
61  /// new interval.
62  void clear();
63
64  /// LoopPeripheralUse - how is a variable used in and around a loop?
65  /// Peripheral blocks are the loop predecessors and exit blocks.
66  enum LoopPeripheralUse {
67    ContainedInLoop,  // All uses are inside the loop.
68    SinglePeripheral, // At most one instruction per peripheral block.
69    MultiPeripheral,  // Multiple instructions in some peripheral blocks.
70    OutsideLoop       // Uses outside loop periphery.
71  };
72
73  /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
74  /// and around the Loop.
75  LoopPeripheralUse analyzeLoopPeripheralUse(const MachineLoop*);
76
77  /// getBestSplitLoop - Return the loop where curli may best be split to a
78  /// separate register, or NULL.
79  const MachineLoop *getBestSplitLoop();
80};
81
82/// splitAroundLoop - Try to split curli into a separate live interval inside
83/// the loop. Retun true on success.
84bool splitAroundLoop(SplitAnalysis&, const MachineLoop*);
85
86}
87