OLD | NEW |
1 //===- subzero/src/IceRegAlloc.h - Linear-scan reg. allocation --*- C++ -*-===// | 1 //===- subzero/src/IceRegAlloc.h - Linear-scan reg. allocation --*- C++ -*-===// |
2 // | 2 // |
3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 // | 9 // |
10 // This file declares the data structures used during linear-scan | 10 // This file declares the LinearScan data structure used during |
11 // register allocation. This includes LiveRangeWrapper which | 11 // linear-scan register allocation, which holds the various work |
12 // encapsulates a variable and its live range, and LinearScan which | 12 // queues for the linear-scan algorithm. |
13 // holds the various work queues for the linear-scan algorithm. | |
14 // | 13 // |
15 //===----------------------------------------------------------------------===// | 14 //===----------------------------------------------------------------------===// |
16 | 15 |
17 #ifndef SUBZERO_SRC_ICEREGALLOC_H | 16 #ifndef SUBZERO_SRC_ICEREGALLOC_H |
18 #define SUBZERO_SRC_ICEREGALLOC_H | 17 #define SUBZERO_SRC_ICEREGALLOC_H |
19 | 18 |
20 #include "IceDefs.h" | 19 #include "IceDefs.h" |
21 #include "IceTypes.h" | 20 #include "IceTypes.h" |
22 | 21 |
23 namespace Ice { | 22 namespace Ice { |
24 | 23 |
25 // Currently this just wraps a Variable pointer, so in principle we | 24 class LinearScan { |
26 // could use containers of Variable* instead of LiveRangeWrapper. But | 25 LinearScan(const LinearScan &) = delete; |
27 // in the future, we may want to do more complex things such as live | 26 LinearScan &operator=(const LinearScan &) = delete; |
28 // range splitting, and keeping a wrapper should make that simpler. | |
29 class LiveRangeWrapper { | |
30 public: | |
31 LiveRangeWrapper(Variable *Var) : Var(Var) {} | |
32 const LiveRange &range() const { return Var->getLiveRange(); } | |
33 bool endsBefore(const LiveRangeWrapper &Other) const { | |
34 return range().endsBefore(Other.range()); | |
35 } | |
36 bool overlaps(const LiveRangeWrapper &Other) const { | |
37 const bool UseTrimmed = true; | |
38 return range().overlaps(Other.range(), UseTrimmed); | |
39 } | |
40 bool overlapsStart(const LiveRangeWrapper &Other) const { | |
41 const bool UseTrimmed = true; | |
42 return range().overlapsInst(Other.range().getStart(), UseTrimmed); | |
43 } | |
44 Variable *Var; | |
45 void dump(const Cfg *Func) const; | |
46 | 27 |
47 private: | |
48 // LiveRangeWrapper(const LiveRangeWrapper &) = delete; | |
49 // LiveRangeWrapper &operator=(const LiveRangeWrapper &) = delete; | |
50 }; | |
51 | |
52 class LinearScan { | |
53 public: | 28 public: |
54 LinearScan(Cfg *Func) : Func(Func) {} | 29 LinearScan(Cfg *Func) : Func(Func) {} |
55 void scan(const llvm::SmallBitVector &RegMask); | 30 void scan(const llvm::SmallBitVector &RegMask); |
56 void dump(Cfg *Func) const; | 31 void dump(Cfg *Func) const; |
57 | 32 |
58 private: | 33 private: |
59 Cfg *const Func; | 34 Cfg *const Func; |
60 typedef std::vector<LiveRangeWrapper> OrderedRanges; | 35 typedef std::vector<Variable *> OrderedRanges; |
61 typedef std::list<LiveRangeWrapper> UnorderedRanges; | 36 typedef std::list<Variable *> UnorderedRanges; |
62 OrderedRanges Unhandled; | 37 OrderedRanges Unhandled; |
63 // UnhandledPrecolored is a subset of Unhandled, specially collected | 38 // UnhandledPrecolored is a subset of Unhandled, specially collected |
64 // for faster processing. | 39 // for faster processing. |
65 OrderedRanges UnhandledPrecolored; | 40 OrderedRanges UnhandledPrecolored; |
66 UnorderedRanges Active, Inactive, Handled; | 41 UnorderedRanges Active, Inactive, Handled; |
67 LinearScan(const LinearScan &) = delete; | |
68 LinearScan &operator=(const LinearScan &) = delete; | |
69 }; | 42 }; |
70 | 43 |
71 } // end of namespace Ice | 44 } // end of namespace Ice |
72 | 45 |
73 #endif // SUBZERO_SRC_ICEREGALLOC_H | 46 #endif // SUBZERO_SRC_ICEREGALLOC_H |
OLD | NEW |