RegisterCoalescer.cpp revision 218893
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