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