Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/RegAllocBase.h
Line
Count
Source
1
//===- RegAllocBase.h - basic regalloc interface and driver -----*- C++ -*-===//
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 defines the RegAllocBase class, which is the skeleton of a basic
11
// register allocation algorithm and interface for extending it. It provides the
12
// building blocks on which to construct other experimental allocators and test
13
// the validity of two principles:
14
//
15
// - If virtual and physical register liveness is modeled using intervals, then
16
// on-the-fly interference checking is cheap. Furthermore, interferences can be
17
// lazily cached and reused.
18
//
19
// - Register allocation complexity, and generated code performance is
20
// determined by the effectiveness of live range splitting rather than optimal
21
// coloring.
22
//
23
// Following the first principle, interfering checking revolves around the
24
// LiveIntervalUnion data structure.
25
//
26
// To fulfill the second principle, the basic allocator provides a driver for
27
// incremental splitting. It essentially punts on the problem of register
28
// coloring, instead driving the assignment of virtual to physical registers by
29
// the cost of splitting. The basic allocator allows for heuristic reassignment
30
// of registers, if a more sophisticated allocator chooses to do that.
31
//
32
// This framework provides a way to engineer the compile time vs. code
33
// quality trade-off without relying on a particular theoretical solver.
34
//
35
//===----------------------------------------------------------------------===//
36
37
#ifndef LLVM_LIB_CODEGEN_REGALLOCBASE_H
38
#define LLVM_LIB_CODEGEN_REGALLOCBASE_H
39
40
#include "llvm/ADT/SmallPtrSet.h"
41
#include "llvm/CodeGen/RegisterClassInfo.h"
42
43
namespace llvm {
44
45
class LiveInterval;
46
class LiveIntervals;
47
class LiveRegMatrix;
48
class MachineInstr;
49
class MachineRegisterInfo;
50
template<typename T> class SmallVectorImpl;
51
class Spiller;
52
class TargetRegisterInfo;
53
class VirtRegMap;
54
55
/// RegAllocBase provides the register allocation driver and interface that can
56
/// be extended to add interesting heuristics.
57
///
58
/// Register allocators must override the selectOrSplit() method to implement
59
/// live range splitting. They must also override enqueue/dequeue to provide an
60
/// assignment order.
61
class RegAllocBase {
62
  virtual void anchor();
63
64
protected:
65
  const TargetRegisterInfo *TRI = nullptr;
66
  MachineRegisterInfo *MRI = nullptr;
67
  VirtRegMap *VRM = nullptr;
68
  LiveIntervals *LIS = nullptr;
69
  LiveRegMatrix *Matrix = nullptr;
70
  RegisterClassInfo RegClassInfo;
71
72
  /// Inst which is a def of an original reg and whose defs are already all
73
  /// dead after remat is saved in DeadRemats. The deletion of such inst is
74
  /// postponed till all the allocations are done, so its remat expr is
75
  /// always available for the remat of all the siblings of the original reg.
76
  SmallPtrSet<MachineInstr *, 32> DeadRemats;
77
78
31.8k
  RegAllocBase() = default;
79
31.7k
  virtual ~RegAllocBase() = default;
80
81
  // A RegAlloc pass should call this before allocatePhysRegs.
82
  void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat);
83
84
  // The top-level driver. The output is a VirtRegMap that us updated with
85
  // physical register assignments.
86
  void allocatePhysRegs();
87
88
  // Include spiller post optimization and removing dead defs left because of
89
  // rematerialization.
90
  virtual void postOptimization();
91
92
  // Get a temporary reference to a Spiller instance.
93
  virtual Spiller &spiller() = 0;
94
95
  /// enqueue - Add VirtReg to the priority queue of unassigned registers.
96
  virtual void enqueue(LiveInterval *LI) = 0;
97
98
  /// dequeue - Return the next unassigned register, or NULL.
99
  virtual LiveInterval *dequeue() = 0;
100
101
  // A RegAlloc pass should override this to provide the allocation heuristics.
102
  // Each call must guarantee forward progess by returning an available PhysReg
103
  // or new set of split live virtual registers. It is up to the splitter to
104
  // converge quickly toward fully spilled live ranges.
105
  virtual unsigned selectOrSplit(LiveInterval &VirtReg,
106
                                 SmallVectorImpl<unsigned> &splitLVRs) = 0;
107
108
  // Use this group name for NamedRegionTimer.
109
  static const char TimerGroupName[];
110
  static const char TimerGroupDescription[];
111
112
  /// Method called when the allocator is about to remove a LiveInterval.
113
1
  virtual void aboutToRemoveInterval(LiveInterval &LI) {}
114
115
public:
116
  /// VerifyEnabled - True when -verify-regalloc is given.
117
  static bool VerifyEnabled;
118
119
private:
120
  void seedLiveRegs();
121
};
122
123
} // end namespace llvm
124
125
#endif // LLVM_LIB_CODEGEN_REGALLOCBASE_H