1 //===-- RegisterCoalescer.h - Register Coalescing Interface ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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/MRegisterInfo.h"
20 #include "llvm/Support/Debug.h"
22 #ifndef LLVM_CODEGEN_REGISTER_COALESCER_H
23 #define LLVM_CODEGEN_REGISTER_COALESCER_H
27 class MachineFunction;
34 /// An abstract interface for register coalescers. Coalescers must
35 /// implement this interface to be part of the coalescer analysis
37 class RegisterCoalescer {
39 static char ID; // Class identification, replacement for typeinfo
40 RegisterCoalescer() {}
41 virtual ~RegisterCoalescer(); // We want to be subclassed
43 /// Run the coalescer on this function, providing interference
44 /// data to query. Return whether we removed any copies.
45 virtual bool coalesceFunction(MachineFunction &mf,
46 RegallocQuery &ifd) = 0;
48 /// Reset state. Can be used to allow a coalescer run by
49 /// PassManager to be run again by the register allocator.
50 virtual void reset(MachineFunction &mf) {};
52 /// Register allocators must call this from their own
53 /// getAnalysisUsage to cover the case where the coalescer is not
54 /// a Pass in the proper sense and isn't managed by PassManager.
55 /// PassManager needs to know which analyses to make available and
56 /// which to invalidate when running the register allocator or any
57 /// pass that might call coalescing. The long-term solution is to
58 /// allow hierarchies of PassManagers.
59 virtual void getAnalysisUsage(AnalysisUsage &AU) const {};
62 /// An abstract interface for register allocators to interact with
67 /// This is simply an example of how to use the RegallocQuery
68 /// interface. It is not meant to be used in production.
70 /// class LinearScanRegallocQuery : public RegallocQuery {
72 /// const LiveIntervals &li;
75 /// LinearScanRegallocQuery(LiveIntervals &intervals)
76 /// : li(intervals) {};
78 /// /// This is pretty slow and conservative, but since linear scan
79 /// /// allocation doesn't pre-compute interference information it's
80 /// /// the best we can do. Coalescers are always free to ignore this
81 /// /// and implement their own discovery strategy. See
82 /// /// SimpleRegisterCoalescing for an example.
83 /// void getInterferences(IntervalSet &interferences,
84 /// const LiveInterval &a) const {
85 /// for(LiveIntervals::const_iterator iv = li.begin(),
89 /// if (interfere(a, iv->second)) {
90 /// interferences.insert(&iv->second);
95 /// /// This is *really* slow and stupid. See above.
96 /// int getNumberOfInterferences(const LiveInterval &a) const {
97 /// IntervalSet intervals;
98 /// getInterferences(intervals, a);
99 /// return(intervals.size());
103 /// In the allocator:
105 /// RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>();
107 /// // We don't reset the coalescer so if it's already been run this
108 /// // takes almost no time.
109 /// LinearScanRegallocQuery ifd(*li_);
110 /// coalescer.coalesceFunction(fn, ifd);
112 class RegallocQuery {
114 typedef SmallPtrSet<const LiveInterval *, 8> IntervalSet;
116 virtual ~RegallocQuery() {};
118 /// Return whether two live ranges interfere.
119 virtual bool interfere(const LiveInterval &a,
120 const LiveInterval &b) const {
122 return(a.overlaps(b));
125 /// Return the set of intervals that interfere with this one.
126 virtual void getInterferences(IntervalSet &interferences,
127 const LiveInterval &a) const = 0;
129 /// This can often be cheaper than actually returning the
131 virtual int getNumberOfInterferences(const LiveInterval &a) const = 0;
133 /// Make any data structure updates necessary to reflect
134 /// coalescing or other modifications.
135 virtual void updateDataForMerge(const LiveInterval &a,
136 const LiveInterval &b,
137 const MachineInstr ©) {};
139 /// Allow the register allocator to communicate when it doesn't
140 /// want a copy coalesced. This may be due to assumptions made by
141 /// the allocator about various invariants and so this question is
142 /// a matter of legality, not performance. Performance decisions
143 /// about which copies to coalesce should be made by the
145 virtual bool isLegalToCoalesce(const MachineInstr &inst) const {
151 // Because of the way .a files work, we must force the SimpleRC
152 // implementation to be pulled in if the RegisterCoalescing header is
153 // included. Otherwise we run the risk of RegisterCoalescing being
154 // used, but the default implementation not being linked into the tool
156 FORCE_DEFINING_FILE_TO_BE_LINKED(RegisterCoalescer)
157 FORCE_DEFINING_FILE_TO_BE_LINKED(SimpleRegisterCoalescing)