RegisterCoalescer.cpp revision 5c00e077952d14899c3fc26709c7b2dfd36d0209 
1//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface -------==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the generic RegisterCoalescer interface which
11// is used as the common interface used by all clients and
12// implementations of register coalescing.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/CodeGen/RegisterCoalescer.h"
17#include "llvm/CodeGen/LiveIntervalAnalysis.h"
18#include "llvm/CodeGen/MachineInstr.h"
19#include "llvm/CodeGen/MachineRegisterInfo.h"
20#include "llvm/Target/TargetInstrInfo.h"
21#include "llvm/Target/TargetRegisterInfo.h"
22#include "llvm/Pass.h"
23
24using namespace llvm;
25
26// Register the RegisterCoalescer interface, providing a nice name to refer to.
27static RegisterAnalysisGroup<RegisterCoalescer> Z("Register Coalescer");
28char RegisterCoalescer::ID = 0;
29
30// RegisterCoalescer destructor: DO NOT move this to the header file
31// for RegisterCoalescer or else clients of the RegisterCoalescer
32// class may not depend on the RegisterCoalescer.o file in the current
33// .a file, causing alias analysis support to not be included in the
34// tool correctly!
35//
36RegisterCoalescer::~RegisterCoalescer() {}
37
38unsigned CoalescerPair::compose(unsigned a, unsigned b) const {
39  if (!a) return b;
40  if (!b) return a;
41  return tri_.composeSubRegIndices(a, b);
42}
43
44bool CoalescerPair::isMoveInstr(const MachineInstr *MI,
45                                unsigned &Src, unsigned &Dst,
46                                unsigned &SrcSub, unsigned &DstSub) const {
47  if (MI->isCopy()) {
48    Dst = MI->getOperand(0).getReg();
49    DstSub = MI->getOperand(0).getSubReg();
50    Src = MI->getOperand(1).getReg();
51    SrcSub = MI->getOperand(1).getSubReg();
52  } else if (MI->isExtractSubreg()) {
53    Dst = MI->getOperand(0).getReg();
54    DstSub = MI->getOperand(0).getSubReg();
55    Src = MI->getOperand(1).getReg();
56    SrcSub = compose(MI->getOperand(1).getSubReg(), MI->getOperand(2).getImm());
57  } else if (MI->isSubregToReg()) {
58    Dst = MI->getOperand(0).getReg();
59    DstSub = compose(MI->getOperand(0).getSubReg(), MI->getOperand(3).getImm());
60    Src = MI->getOperand(2).getReg();
61    SrcSub = MI->getOperand(2).getSubReg();
62  } else if (!tii_.isMoveInstr(*MI, Src, Dst, SrcSub, DstSub)) {
63    return false;
64  }
65  return true;
66}
67
68bool CoalescerPair::setRegisters(const MachineInstr *MI) {
69  srcReg_ = dstReg_ = subIdx_ = 0;
70  newRC_ = 0;
71  flipped_ = crossClass_ = false;
72
73  unsigned Src, Dst, SrcSub, DstSub;
74  if (!isMoveInstr(MI, Src, Dst, SrcSub, DstSub))
75    return false;
76  partial_ = SrcSub || DstSub;
77
78  // If one register is a physreg, it must be Dst.
79  if (TargetRegisterInfo::isPhysicalRegister(Src)) {
80    if (TargetRegisterInfo::isPhysicalRegister(Dst))
81      return false;
82    std::swap(Src, Dst);
83    std::swap(SrcSub, DstSub);
84    flipped_ = true;
85  }
86
87  const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo();
88
89  if (TargetRegisterInfo::isPhysicalRegister(Dst)) {
90    // Eliminate DstSub on a physreg.
91    if (DstSub) {
92      Dst = tri_.getSubReg(Dst, DstSub);
93      if (!Dst) return false;
94      DstSub = 0;
95    }
96
97    // Eliminate SrcSub by picking a corresponding Dst superregister.
98    if (SrcSub) {
99      Dst = tri_.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src));
100      if (!Dst) return false;
101      SrcSub = 0;
102    } else if (!MRI.getRegClass(Src)->contains(Dst)) {
103      return false;
104    }
105  } else {
106    // Both registers are virtual.
107
108    // Both registers have subreg indices.
109    if (SrcSub && DstSub) {
110      // For now we only handle the case of identical indices in commensurate
111      // registers: Dreg:ssub_1 + Dreg:ssub_1 -> Dreg
112      // FIXME: Handle Qreg:ssub_3 + Dreg:ssub_1 as QReg:dsub_1 + Dreg.
113      if (SrcSub != DstSub)
114        return false;
115      const TargetRegisterClass *SrcRC = MRI.getRegClass(Src);
116      const TargetRegisterClass *DstRC = MRI.getRegClass(Dst);
117      if (!getCommonSubClass(DstRC, SrcRC))
118        return false;
119      SrcSub = DstSub = 0;
120    }
121
122    // There can be no SrcSub.
123    if (SrcSub) {
124      std::swap(Src, Dst);
125      DstSub = SrcSub;
126      SrcSub = 0;
127      assert(!flipped_ && "Unexpected flip");
128      flipped_ = true;
129    }
130
131    // Find the new register class.
132    const TargetRegisterClass *SrcRC = MRI.getRegClass(Src);
133    const TargetRegisterClass *DstRC = MRI.getRegClass(Dst);
134    if (DstSub)
135      newRC_ = tri_.getMatchingSuperRegClass(DstRC, SrcRC, DstSub);
136    else
137      newRC_ = getCommonSubClass(DstRC, SrcRC);
138    if (!newRC_)
139      return false;
140    crossClass_ = newRC_ != DstRC || newRC_ != SrcRC;
141  }
142  // Check our invariants
143  assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual");
144  assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) &&
145         "Cannot have a physical SubIdx");
146  srcReg_ = Src;
147  dstReg_ = Dst;
148  subIdx_ = DstSub;
149  return true;
150}
151
152bool CoalescerPair::flip() {
153  if (subIdx_ || TargetRegisterInfo::isPhysicalRegister(dstReg_))
154    return false;
155  std::swap(srcReg_, dstReg_);
156  flipped_ = !flipped_;
157  return true;
158}
159
160bool CoalescerPair::isCoalescable(const MachineInstr *MI) const {
161  if (!MI)
162    return false;
163  unsigned Src, Dst, SrcSub, DstSub;
164  if (!isMoveInstr(MI, Src, Dst, SrcSub, DstSub))
165    return false;
166
167  // Find the virtual register that is srcReg_.
168  if (Dst == srcReg_) {
169    std::swap(Src, Dst);
170    std::swap(SrcSub, DstSub);
171  } else if (Src != srcReg_) {
172    return false;
173  }
174
175  // Now check that Dst matches dstReg_.
176  if (TargetRegisterInfo::isPhysicalRegister(dstReg_)) {
177    if (!TargetRegisterInfo::isPhysicalRegister(Dst))
178      return false;
179    assert(!subIdx_ && "Inconsistent CoalescerPair state.");
180    // DstSub could be set for a physreg from INSERT_SUBREG.
181    if (DstSub)
182      Dst = tri_.getSubReg(Dst, DstSub);
183    // Full copy of Src.
184    if (!SrcSub)
185      return dstReg_ == Dst;
186    // This is a partial register copy. Check that the parts match.
187    return tri_.getSubReg(dstReg_, SrcSub) == Dst;
188  } else {
189    // dstReg_ is virtual.
190    if (dstReg_ != Dst)
191      return false;
192    // Registers match, do the subregisters line up?
193    return compose(subIdx_, SrcSub) == DstSub;
194  }
195}
196
197// Because of the way .a files work, we must force the SimpleRC
198// implementation to be pulled in if the RegisterCoalescer classes are
199// pulled in.  Otherwise we run the risk of RegisterCoalescer being
200// used, but the default implementation not being linked into the tool
201// that uses it.
202DEFINING_FILE_FOR(RegisterCoalescer)
203