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