RegisterCoalescer.h revision 2c17c4d8d9f232f0329786ad9abee976bc0f3d27
12c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene//===-- RegisterCoalescer.h - Register Coalescing Interface ------*- C++ -*-===// 22c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 32c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// The LLVM Compiler Infrastructure 42c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 52c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// This file was developed by the LLVM research group and is distributed under 62c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// the University of Illinois Open Source License. See LICENSE.TXT for details. 72c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 82c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene//===----------------------------------------------------------------------===// 92c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 102c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// This file contains the abstract interface for register coalescers, 112c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// allowing them to interact with and query register allocators. 122c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 132c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene//===----------------------------------------------------------------------===// 142c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 152c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/System/IncludeFile.h" 162c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/CodeGen/MachineInstr.h" 172c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/CodeGen/LiveIntervalAnalysis.h" 182c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/CodeGen/LiveVariables.h" 192c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/Target/MRegisterInfo.h" 202c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/Support/Debug.h" 212c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 222c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#ifndef LLVM_CODEGEN_REGISTER_COALESCER_H 232c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#define LLVM_CODEGEN_REGISTER_COALESCER_H 242c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 252c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greenenamespace llvm 262c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene{ 272c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene class MachineFunction; 282c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene class RegallocQuery; 292c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene class AnalysisUsage; 302c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene class LiveIntervals; 312c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene class MachineInstr; 322c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene class MRegisterInfo; 332c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 342c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// An abstract interface for register coalescers. Coalescers must 352c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// implement this interface to be part of the coalescer analysis 362c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// group. 372c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene class RegisterCoalescer { 382c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene public: 392c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene static char ID; // Class identification, replacement for typeinfo 402c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene RegisterCoalescer() {} 412c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene virtual ~RegisterCoalescer(); // We want to be subclassed 422c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 432c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// Run the coalescer on this function, providing interference 442c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// data to query. Return whether we removed any copies. 452c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene virtual bool coalesceFunction(MachineFunction &mf, 462c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene RegallocQuery &ifd) = 0; 472c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 482c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// Reset state. Can be used to allow a coalescer run by 492c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// PassManager to be run again by the register allocator. 502c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene virtual void reset(MachineFunction &mf) {}; 512c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 522c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// Register allocators must call this from their own 532c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// getAnalysisUsage to cover the case where the coalescer is not 542c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// a Pass in the proper sense and isn't managed by PassManager. 552c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// PassManager needs to know which analyses to make available and 562c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// which to invalidate when running the register allocator or any 572c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// pass that might call coalescing. The long-term solution is to 582c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// allow hierarchies of PassManagers. 592c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene virtual void getAnalysisUsage(AnalysisUsage &AU) const {}; 602c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene }; 612c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 622c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// An abstract interface for register allocators to interact with 632c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// coalescers 642c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// 652c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// Example: 662c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// 672c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// This is simply an example of how to use the RegallocQuery 682c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// interface. It is not meant to be used in production. 692c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// 702c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// class LinearScanRegallocQuery : public RegallocQuery { 712c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// private: 722c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// const LiveIntervals &li; 732c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// 742c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// public: 752c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// LinearScanRegallocQuery(LiveIntervals &intervals) 762c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// : li(intervals) {}; 772c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// 782c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// /// This is pretty slow and conservative, but since linear scan 792c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// /// allocation doesn't pre-compute interference information it's 802c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// /// the best we can do. Coalescers are always free to ignore this 812c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// /// and implement their own discovery strategy. See 822c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// /// SimpleRegisterCoalescing for an example. 832c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// void getInterferences(IntervalSet &interferences, 842c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// const LiveInterval &a) const { 852c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// for(LiveIntervals::const_iterator iv = li.begin(), 862c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// ivend = li.end(); 872c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// iv != ivend; 882c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// ++iv) { 892c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// if (interfere(a, iv->second)) { 902c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// interferences.insert(&iv->second); 912c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// } 922c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// } 932c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// }; 942c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// 952c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// /// This is *really* slow and stupid. See above. 962c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// int getNumberOfInterferences(const LiveInterval &a) const { 972c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// IntervalSet intervals; 982c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// getInterferences(intervals, a); 992c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// return(intervals.size()); 1002c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// }; 1012c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// }; 1022c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// 1032c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// In the allocator: 1042c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// 1052c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>(); 1062c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// 1072c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// // We don't reset the coalescer so if it's already been run this 1082c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// // takes almost no time. 1092c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// LinearScanRegallocQuery ifd(*li_); 1102c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// coalescer.coalesceFunction(fn, ifd); 1112c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// 1122c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene class RegallocQuery { 1132c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene public: 1142c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene typedef SmallPtrSet<const LiveInterval *, 8> IntervalSet; 1152c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 1162c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene virtual ~RegallocQuery() {}; 1172c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 1182c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// Return whether two live ranges interfere. 1192c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene virtual bool interfere(const LiveInterval &a, 1202c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene const LiveInterval &b) const { 1212c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene // A naive test 1222c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene return(a.overlaps(b)); 1232c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene }; 1242c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 1252c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// Return the set of intervals that interfere with this one. 1262c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene virtual void getInterferences(IntervalSet &interferences, 1272c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene const LiveInterval &a) const = 0; 1282c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 1292c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// This can often be cheaper than actually returning the 1302c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// interferences. 1312c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene virtual int getNumberOfInterferences(const LiveInterval &a) const = 0; 1322c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 1332c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// Make any data structure updates necessary to reflect 1342c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// coalescing or other modifications. 1352c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene virtual void updateDataForMerge(const LiveInterval &a, 1362c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene const LiveInterval &b, 1372c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene const MachineInstr ©) {}; 1382c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 1392c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// Allow the register allocator to communicate when it doesn't 1402c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// want a copy coalesced. This may be due to assumptions made by 1412c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// the allocator about various invariants and so this question is 1422c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// a matter of legality, not performance. Performance decisions 1432c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// about which copies to coalesce should be made by the 1442c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene /// coalescer. 1452c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene virtual bool isLegalToCoalesce(const MachineInstr &inst) const { 1462c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene return(true); 1472c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene } 1482c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene }; 1492c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene} 1502c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 1512c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// Because of the way .a files work, we must force the SimpleRC 1522c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// implementation to be pulled in if the RegisterCoalescing header is 1532c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// included. Otherwise we run the risk of RegisterCoalescing being 1542c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// used, but the default implementation not being linked into the tool 1552c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// that uses it. 1562c17c4d8d9f232f0329786ad9abee976bc0f3d27David GreeneFORCE_DEFINING_FILE_TO_BE_LINKED(RegisterCoalescer) 1572c17c4d8d9f232f0329786ad9abee976bc0f3d27David GreeneFORCE_DEFINING_FILE_TO_BE_LINKED(SimpleRegisterCoalescing) 1582c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 1592c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#endif 160