1 //===-- RegisterCoalescer.h - Register Coalescing Interface ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains the abstract interface for register coalescers,
11 // allowing them to interact with and query register allocators.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/System/IncludeFile.h"
16 #include "llvm/CodeGen/MachineInstr.h"
17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
18 #include "llvm/CodeGen/LiveVariables.h"
19 #include "llvm/Target/TargetRegisterInfo.h"
21 #ifndef LLVM_CODEGEN_REGISTER_COALESCER_H
22 #define LLVM_CODEGEN_REGISTER_COALESCER_H
26 class MachineFunction;
31 class TargetRegisterInfo;
33 /// An abstract interface for register coalescers. Coalescers must
34 /// implement this interface to be part of the coalescer analysis
36 class RegisterCoalescer {
38 static char ID; // Class identification, replacement for typeinfo
39 RegisterCoalescer() {}
40 virtual ~RegisterCoalescer(); // We want to be subclassed
42 /// Run the coalescer on this function, providing interference
43 /// data to query. Return whether we removed any copies.
44 virtual bool coalesceFunction(MachineFunction &mf,
45 RegallocQuery &ifd) = 0;
47 /// Reset state. Can be used to allow a coalescer run by
48 /// PassManager to be run again by the register allocator.
49 virtual void reset(MachineFunction &mf) {};
51 /// Register allocators must call this from their own
52 /// getAnalysisUsage to cover the case where the coalescer is not
53 /// a Pass in the proper sense and isn't managed by PassManager.
54 /// PassManager needs to know which analyses to make available and
55 /// which to invalidate when running the register allocator or any
56 /// pass that might call coalescing. The long-term solution is to
57 /// allow hierarchies of PassManagers.
58 virtual void getAnalysisUsage(AnalysisUsage &AU) const {};
61 /// An abstract interface for register allocators to interact with
66 /// This is simply an example of how to use the RegallocQuery
67 /// interface. It is not meant to be used in production.
69 /// class LinearScanRegallocQuery : public RegallocQuery {
71 /// const LiveIntervals &li;
74 /// LinearScanRegallocQuery(LiveIntervals &intervals)
75 /// : li(intervals) {};
77 /// /// This is pretty slow and conservative, but since linear scan
78 /// /// allocation doesn't pre-compute interference information it's
79 /// /// the best we can do. Coalescers are always free to ignore this
80 /// /// and implement their own discovery strategy. See
81 /// /// SimpleRegisterCoalescing for an example.
82 /// void getInterferences(IntervalSet &interferences,
83 /// const LiveInterval &a) const {
84 /// for(LiveIntervals::const_iterator iv = li.begin(),
88 /// if (interfere(a, iv->second)) {
89 /// interferences.insert(&iv->second);
94 /// /// This is *really* slow and stupid. See above.
95 /// int getNumberOfInterferences(const LiveInterval &a) const {
96 /// IntervalSet intervals;
97 /// getInterferences(intervals, a);
98 /// return(intervals.size());
102 /// In the allocator:
104 /// RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>();
106 /// // We don't reset the coalescer so if it's already been run this
107 /// // takes almost no time.
108 /// LinearScanRegallocQuery ifd(*li_);
109 /// coalescer.coalesceFunction(fn, ifd);
111 class RegallocQuery {
113 typedef SmallPtrSet<const LiveInterval *, 8> IntervalSet;
115 virtual ~RegallocQuery() {};
117 /// Return whether two live ranges interfere.
118 virtual bool interfere(const LiveInterval &a,
119 const LiveInterval &b) const {
121 return(a.overlaps(b));
124 /// Return the set of intervals that interfere with this one.
125 virtual void getInterferences(IntervalSet &interferences,
126 const LiveInterval &a) const = 0;
128 /// This can often be cheaper than actually returning the
130 virtual int getNumberOfInterferences(const LiveInterval &a) const = 0;
132 /// Make any data structure updates necessary to reflect
133 /// coalescing or other modifications.
134 virtual void updateDataForMerge(const LiveInterval &a,
135 const LiveInterval &b,
136 const MachineInstr ©) {};
138 /// Allow the register allocator to communicate when it doesn't
139 /// want a copy coalesced. This may be due to assumptions made by
140 /// the allocator about various invariants and so this question is
141 /// a matter of legality, not performance. Performance decisions
142 /// about which copies to coalesce should be made by the
144 virtual bool isLegalToCoalesce(const MachineInstr &inst) const {
150 // Because of the way .a files work, we must force the SimpleRC
151 // implementation to be pulled in if the RegisterCoalescing header is
152 // included. Otherwise we run the risk of RegisterCoalescing being
153 // used, but the default implementation not being linked into the tool
155 FORCE_DEFINING_FILE_TO_BE_LINKED(RegisterCoalescer)
156 FORCE_DEFINING_FILE_TO_BE_LINKED(SimpleRegisterCoalescing)