lib/CodeGen/RegisterCoalescer.cpp

   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
  24 using namespace llvm;
  25
  26 // Register the RegisterCoalescer interface, providing a nice name to refer to.
  27 static RegisterAnalysisGroup<RegisterCoalescer> Z("Register Coalescer");
  28 char 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 //
  36 RegisterCoalescer::~RegisterCoalescer() {}
  37
  38 unsigned 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
  44 bool 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
  68 bool 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
 152 bool CoalescerPair::flip() {
 153   if (subIdx_ || TargetRegisterInfo::isPhysicalRegister(dstReg_))
 154     return false;
 155   std::swap(srcReg_, dstReg_);
 156   flipped_ = !flipped_;
 157   return true;
 158 }
 159
 160 bool 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.
 202 DEFINING_FILE_FOR(RegisterCoalescer)