RegisterCoalescer.h revision 2c17c4d8d9f232f0329786ad9abee976bc0f3d27 
1//===-- RegisterCoalescer.h - Register Coalescing Interface ------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
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.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains the abstract interface for register coalescers,
11// allowing them to interact with and query register allocators.
12//
13//===----------------------------------------------------------------------===//
14
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"
21
22#ifndef LLVM_CODEGEN_REGISTER_COALESCER_H
23#define LLVM_CODEGEN_REGISTER_COALESCER_H
24
25namespace llvm
26{
27  class MachineFunction;
28  class RegallocQuery;
29  class AnalysisUsage;
30  class LiveIntervals;
31  class MachineInstr;
32  class MRegisterInfo;
33
34  /// An abstract interface for register coalescers.  Coalescers must
35  /// implement this interface to be part of the coalescer analysis
36  /// group.
37  class RegisterCoalescer {
38  public:
39    static char ID; // Class identification, replacement for typeinfo
40    RegisterCoalescer() {}
41    virtual ~RegisterCoalescer();  // We want to be subclassed
42
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;
47
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) {};
51
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 {};
60  };
61
62  /// An abstract interface for register allocators to interact with
63  /// coalescers
64  ///
65  /// Example:
66  ///
67  /// This is simply an example of how to use the RegallocQuery
68  /// interface.  It is not meant to be used in production.
69  ///
70  ///   class LinearScanRegallocQuery : public RegallocQuery {
71  ///   private:
72  ///     const LiveIntervals &li;
73  ///
74  ///   public:
75  ///     LinearScanRegallocQuery(LiveIntervals &intervals)
76  ///         : li(intervals) {};
77  ///
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(),
86  ///             ivend = li.end();
87  ///           iv != ivend;
88  ///           ++iv) {
89  ///         if (interfere(a, iv->second)) {
90  ///           interferences.insert(&iv->second);
91  ///         }
92  ///       }
93  ///     };
94  ///
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());
100  ///     };
101  ///   };
102  ///
103  ///   In the allocator:
104  ///
105  ///   RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>();
106  ///
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);
111  ///
112  class RegallocQuery {
113  public:
114    typedef SmallPtrSet<const LiveInterval *, 8> IntervalSet;
115
116    virtual ~RegallocQuery() {};
117
118    /// Return whether two live ranges interfere.
119    virtual bool interfere(const LiveInterval &a,
120                           const LiveInterval &b) const {
121      // A naive test
122      return(a.overlaps(b));
123    };
124
125    /// Return the set of intervals that interfere with this one.
126    virtual void getInterferences(IntervalSet &interferences,
127                                  const LiveInterval &a) const = 0;
128
129    /// This can often be cheaper than actually returning the
130    /// interferences.
131    virtual int getNumberOfInterferences(const LiveInterval &a) const = 0;
132
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 &copy) {};
138
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
144    /// coalescer.
145    virtual bool isLegalToCoalesce(const MachineInstr &inst) const {
146      return(true);
147    }
148  };
149}
150
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
155// that uses it.
156FORCE_DEFINING_FILE_TO_BE_LINKED(RegisterCoalescer)
157FORCE_DEFINING_FILE_TO_BE_LINKED(SimpleRegisterCoalescing)
158
159#endif
160