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/LiveInterval.h"
17 #include "llvm/ADT/SmallPtrSet.h"
19 #ifndef LLVM_CODEGEN_REGISTER_COALESCER_H
20 #define LLVM_CODEGEN_REGISTER_COALESCER_H
24 class MachineFunction;
29 /// An abstract interface for register coalescers. Coalescers must
30 /// implement this interface to be part of the coalescer analysis
32 class RegisterCoalescer {
34 static char ID; // Class identification, replacement for typeinfo
35 RegisterCoalescer() {}
36 virtual ~RegisterCoalescer(); // We want to be subclassed
38 /// Run the coalescer on this function, providing interference
39 /// data to query. Return whether we removed any copies.
40 virtual bool coalesceFunction(MachineFunction &mf,
41 RegallocQuery &ifd) = 0;
43 /// Reset state. Can be used to allow a coalescer run by
44 /// PassManager to be run again by the register allocator.
45 virtual void reset(MachineFunction &mf) {}
47 /// Register allocators must call this from their own
48 /// getAnalysisUsage to cover the case where the coalescer is not
49 /// a Pass in the proper sense and isn't managed by PassManager.
50 /// PassManager needs to know which analyses to make available and
51 /// which to invalidate when running the register allocator or any
52 /// pass that might call coalescing. The long-term solution is to
53 /// allow hierarchies of PassManagers.
54 virtual void getAnalysisUsage(AnalysisUsage &AU) const {}
57 /// An abstract interface for register allocators to interact with
62 /// This is simply an example of how to use the RegallocQuery
63 /// interface. It is not meant to be used in production.
65 /// class LinearScanRegallocQuery : public RegallocQuery {
67 /// const LiveIntervals \&li;
70 /// LinearScanRegallocQuery(LiveIntervals &intervals)
71 /// : li(intervals) {}
73 /// /// This is pretty slow and conservative, but since linear scan
74 /// /// allocation doesn't pre-compute interference information it's
75 /// /// the best we can do. Coalescers are always free to ignore this
76 /// /// and implement their own discovery strategy. See
77 /// /// SimpleRegisterCoalescing for an example.
78 /// void getInterferences(IntervalSet &interferences,
79 /// const LiveInterval &a) const {
80 /// for(LiveIntervals::const_iterator iv = li.begin(),
84 /// if (interfere(a, iv->second)) {
85 /// interferences.insert(&iv->second);
90 /// /// This is *really* slow and stupid. See above.
91 /// int getNumberOfInterferences(const LiveInterval &a) const {
92 /// IntervalSet intervals;
93 /// getInterferences(intervals, a);
94 /// return intervals.size();
100 /// RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>();
102 /// // We don't reset the coalescer so if it's already been run this
103 /// // takes almost no time.
104 /// LinearScanRegallocQuery ifd(*li_);
105 /// coalescer.coalesceFunction(fn, ifd);
107 class RegallocQuery {
109 typedef SmallPtrSet<const LiveInterval *, 8> IntervalSet;
111 virtual ~RegallocQuery() {}
113 /// Return whether two live ranges interfere.
114 virtual bool interfere(const LiveInterval &a,
115 const LiveInterval &b) const {
117 return a.overlaps(b);
120 /// Return the set of intervals that interfere with this one.
121 virtual void getInterferences(IntervalSet &interferences,
122 const LiveInterval &a) const = 0;
124 /// This can often be cheaper than actually returning the
126 virtual int getNumberOfInterferences(const LiveInterval &a) const = 0;
128 /// Make any data structure updates necessary to reflect
129 /// coalescing or other modifications.
130 virtual void updateDataForMerge(const LiveInterval &a,
131 const LiveInterval &b,
132 const MachineInstr ©) {}
134 /// Allow the register allocator to communicate when it doesn't
135 /// want a copy coalesced. This may be due to assumptions made by
136 /// the allocator about various invariants and so this question is
137 /// a matter of legality, not performance. Performance decisions
138 /// about which copies to coalesce should be made by the
140 virtual bool isLegalToCoalesce(const MachineInstr &inst) const {
146 // Because of the way .a files work, we must force the SimpleRC
147 // implementation to be pulled in if the RegisterCoalescing header is
148 // included. Otherwise we run the risk of RegisterCoalescing being
149 // used, but the default implementation not being linked into the tool
151 FORCE_DEFINING_FILE_TO_BE_LINKED(RegisterCoalescer)
152 FORCE_DEFINING_FILE_TO_BE_LINKED(SimpleRegisterCoalescing)