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 INITIALIZE_ANALYSIS_GROUP(RegisterCoalescer, "Register Coalescer",
  28                           SimpleRegisterCoalescing)
  29 char 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 //
  37 RegisterCoalescer::~RegisterCoalescer() {}
  38
  39 unsigned 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
  45 bool 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
  63 bool 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
 147 bool CoalescerPair::flip() {
 148   if (subIdx_ || TargetRegisterInfo::isPhysicalRegister(dstReg_))
 149     return false;
 150   std::swap(srcReg_, dstReg_);
 151   flipped_ = !flipped_;
 152   return true;
 153 }
 154
 155 bool 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.
 197 DEFINING_FILE_FOR(RegisterCoalescer)