1//===--- HexagonGenMux.cpp ------------------------------------------------===// 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// During instruction selection, MUX instructions are generated for 11// conditional assignments. Since such assignments often present an 12// opportunity to predicate instructions, HexagonExpandCondsets 13// expands MUXes into pairs of conditional transfers, and then proceeds 14// with predication of the producers/consumers of the registers involved. 15// This happens after exiting from the SSA form, but before the machine 16// instruction scheduler. After the scheduler and after the register 17// allocation there can be cases of pairs of conditional transfers 18// resulting from a MUX where neither of them was further predicated. If 19// these transfers are now placed far enough from the instruction defining 20// the predicate register, they cannot use the .new form. In such cases it 21// is better to collapse them back to a single MUX instruction. 22 23#define DEBUG_TYPE "hexmux" 24 25#include "llvm/CodeGen/Passes.h" 26#include "llvm/CodeGen/MachineFunctionPass.h" 27#include "llvm/CodeGen/MachineInstrBuilder.h" 28#include "llvm/CodeGen/MachineRegisterInfo.h" 29#include "HexagonTargetMachine.h" 30 31using namespace llvm; 32 33namespace llvm { 34 FunctionPass *createHexagonGenMux(); 35 void initializeHexagonGenMuxPass(PassRegistry& Registry); 36} 37 38namespace { 39 class HexagonGenMux : public MachineFunctionPass { 40 public: 41 static char ID; 42 HexagonGenMux() : MachineFunctionPass(ID), HII(0), HRI(0) { 43 initializeHexagonGenMuxPass(*PassRegistry::getPassRegistry()); 44 } 45 const char *getPassName() const override { 46 return "Hexagon generate mux instructions"; 47 } 48 void getAnalysisUsage(AnalysisUsage &AU) const override { 49 MachineFunctionPass::getAnalysisUsage(AU); 50 } 51 bool runOnMachineFunction(MachineFunction &MF) override; 52 MachineFunctionProperties getRequiredProperties() const override { 53 return MachineFunctionProperties().set( 54 MachineFunctionProperties::Property::AllVRegsAllocated); 55 } 56 57 private: 58 const HexagonInstrInfo *HII; 59 const HexagonRegisterInfo *HRI; 60 61 struct CondsetInfo { 62 unsigned PredR; 63 unsigned TrueX, FalseX; 64 CondsetInfo() : PredR(0), TrueX(UINT_MAX), FalseX(UINT_MAX) {} 65 }; 66 struct DefUseInfo { 67 BitVector Defs, Uses; 68 DefUseInfo() : Defs(), Uses() {} 69 DefUseInfo(const BitVector &D, const BitVector &U) : Defs(D), Uses(U) {} 70 }; 71 struct MuxInfo { 72 MachineBasicBlock::iterator At; 73 unsigned DefR, PredR; 74 MachineOperand *SrcT, *SrcF; 75 MachineInstr *Def1, *Def2; 76 MuxInfo(MachineBasicBlock::iterator It, unsigned DR, unsigned PR, 77 MachineOperand *TOp, MachineOperand *FOp, MachineInstr &D1, 78 MachineInstr &D2) 79 : At(It), DefR(DR), PredR(PR), SrcT(TOp), SrcF(FOp), Def1(&D1), 80 Def2(&D2) {} 81 }; 82 typedef DenseMap<MachineInstr*,unsigned> InstrIndexMap; 83 typedef DenseMap<unsigned,DefUseInfo> DefUseInfoMap; 84 typedef SmallVector<MuxInfo,4> MuxInfoList; 85 86 bool isRegPair(unsigned Reg) const { 87 return Hexagon::DoubleRegsRegClass.contains(Reg); 88 } 89 void getSubRegs(unsigned Reg, BitVector &SRs) const; 90 void expandReg(unsigned Reg, BitVector &Set) const; 91 void getDefsUses(const MachineInstr *MI, BitVector &Defs, 92 BitVector &Uses) const; 93 void buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X, 94 DefUseInfoMap &DUM); 95 bool isCondTransfer(unsigned Opc) const; 96 unsigned getMuxOpcode(const MachineOperand &Src1, 97 const MachineOperand &Src2) const; 98 bool genMuxInBlock(MachineBasicBlock &B); 99 }; 100 101 char HexagonGenMux::ID = 0; 102} 103 104INITIALIZE_PASS(HexagonGenMux, "hexagon-mux", 105 "Hexagon generate mux instructions", false, false) 106 107 108void HexagonGenMux::getSubRegs(unsigned Reg, BitVector &SRs) const { 109 for (MCSubRegIterator I(Reg, HRI); I.isValid(); ++I) 110 SRs[*I] = true; 111} 112 113 114void HexagonGenMux::expandReg(unsigned Reg, BitVector &Set) const { 115 if (isRegPair(Reg)) 116 getSubRegs(Reg, Set); 117 else 118 Set[Reg] = true; 119} 120 121 122void HexagonGenMux::getDefsUses(const MachineInstr *MI, BitVector &Defs, 123 BitVector &Uses) const { 124 // First, get the implicit defs and uses for this instruction. 125 unsigned Opc = MI->getOpcode(); 126 const MCInstrDesc &D = HII->get(Opc); 127 if (const MCPhysReg *R = D.ImplicitDefs) 128 while (*R) 129 expandReg(*R++, Defs); 130 if (const MCPhysReg *R = D.ImplicitUses) 131 while (*R) 132 expandReg(*R++, Uses); 133 134 // Look over all operands, and collect explicit defs and uses. 135 for (ConstMIOperands Mo(*MI); Mo.isValid(); ++Mo) { 136 if (!Mo->isReg() || Mo->isImplicit()) 137 continue; 138 unsigned R = Mo->getReg(); 139 BitVector &Set = Mo->isDef() ? Defs : Uses; 140 expandReg(R, Set); 141 } 142} 143 144 145void HexagonGenMux::buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X, 146 DefUseInfoMap &DUM) { 147 unsigned Index = 0; 148 unsigned NR = HRI->getNumRegs(); 149 BitVector Defs(NR), Uses(NR); 150 151 for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; ++I) { 152 MachineInstr *MI = &*I; 153 I2X.insert(std::make_pair(MI, Index)); 154 Defs.reset(); 155 Uses.reset(); 156 getDefsUses(MI, Defs, Uses); 157 DUM.insert(std::make_pair(Index, DefUseInfo(Defs, Uses))); 158 Index++; 159 } 160} 161 162 163bool HexagonGenMux::isCondTransfer(unsigned Opc) const { 164 switch (Opc) { 165 case Hexagon::A2_tfrt: 166 case Hexagon::A2_tfrf: 167 case Hexagon::C2_cmoveit: 168 case Hexagon::C2_cmoveif: 169 return true; 170 } 171 return false; 172} 173 174 175unsigned HexagonGenMux::getMuxOpcode(const MachineOperand &Src1, 176 const MachineOperand &Src2) const { 177 bool IsReg1 = Src1.isReg(), IsReg2 = Src2.isReg(); 178 if (IsReg1) 179 return IsReg2 ? Hexagon::C2_mux : Hexagon::C2_muxir; 180 if (IsReg2) 181 return Hexagon::C2_muxri; 182 183 // Neither is a register. The first source is extendable, but the second 184 // is not (s8). 185 if (Src2.isImm() && isInt<8>(Src2.getImm())) 186 return Hexagon::C2_muxii; 187 188 return 0; 189} 190 191 192bool HexagonGenMux::genMuxInBlock(MachineBasicBlock &B) { 193 bool Changed = false; 194 InstrIndexMap I2X; 195 DefUseInfoMap DUM; 196 buildMaps(B, I2X, DUM); 197 198 typedef DenseMap<unsigned,CondsetInfo> CondsetMap; 199 CondsetMap CM; 200 MuxInfoList ML; 201 202 MachineBasicBlock::iterator NextI, End = B.end(); 203 for (MachineBasicBlock::iterator I = B.begin(); I != End; I = NextI) { 204 MachineInstr *MI = &*I; 205 NextI = std::next(I); 206 unsigned Opc = MI->getOpcode(); 207 if (!isCondTransfer(Opc)) 208 continue; 209 unsigned DR = MI->getOperand(0).getReg(); 210 if (isRegPair(DR)) 211 continue; 212 213 unsigned PR = MI->getOperand(1).getReg(); 214 unsigned Idx = I2X.lookup(MI); 215 CondsetMap::iterator F = CM.find(DR); 216 bool IfTrue = HII->isPredicatedTrue(Opc); 217 218 // If there is no record of a conditional transfer for this register, 219 // or the predicate register differs, create a new record for it. 220 if (F != CM.end() && F->second.PredR != PR) { 221 CM.erase(F); 222 F = CM.end(); 223 } 224 if (F == CM.end()) { 225 auto It = CM.insert(std::make_pair(DR, CondsetInfo())); 226 F = It.first; 227 F->second.PredR = PR; 228 } 229 CondsetInfo &CI = F->second; 230 if (IfTrue) 231 CI.TrueX = Idx; 232 else 233 CI.FalseX = Idx; 234 if (CI.TrueX == UINT_MAX || CI.FalseX == UINT_MAX) 235 continue; 236 237 // There is now a complete definition of DR, i.e. we have the predicate 238 // register, the definition if-true, and definition if-false. 239 240 // First, check if both definitions are far enough from the definition 241 // of the predicate register. 242 unsigned MinX = std::min(CI.TrueX, CI.FalseX); 243 unsigned MaxX = std::max(CI.TrueX, CI.FalseX); 244 unsigned SearchX = (MaxX > 4) ? MaxX-4 : 0; 245 bool NearDef = false; 246 for (unsigned X = SearchX; X < MaxX; ++X) { 247 const DefUseInfo &DU = DUM.lookup(X); 248 if (!DU.Defs[PR]) 249 continue; 250 NearDef = true; 251 break; 252 } 253 if (NearDef) 254 continue; 255 256 // The predicate register is not defined in the last few instructions. 257 // Check if the conversion to MUX is possible (either "up", i.e. at the 258 // place of the earlier partial definition, or "down", where the later 259 // definition is located). Examine all defs and uses between these two 260 // definitions. 261 // SR1, SR2 - source registers from the first and the second definition. 262 MachineBasicBlock::iterator It1 = B.begin(), It2 = B.begin(); 263 std::advance(It1, MinX); 264 std::advance(It2, MaxX); 265 MachineInstr &Def1 = *It1, &Def2 = *It2; 266 MachineOperand *Src1 = &Def1.getOperand(2), *Src2 = &Def2.getOperand(2); 267 unsigned SR1 = Src1->isReg() ? Src1->getReg() : 0; 268 unsigned SR2 = Src2->isReg() ? Src2->getReg() : 0; 269 bool Failure = false, CanUp = true, CanDown = true; 270 for (unsigned X = MinX+1; X < MaxX; X++) { 271 const DefUseInfo &DU = DUM.lookup(X); 272 if (DU.Defs[PR] || DU.Defs[DR] || DU.Uses[DR]) { 273 Failure = true; 274 break; 275 } 276 if (CanDown && DU.Defs[SR1]) 277 CanDown = false; 278 if (CanUp && DU.Defs[SR2]) 279 CanUp = false; 280 } 281 if (Failure || (!CanUp && !CanDown)) 282 continue; 283 284 MachineOperand *SrcT = (MinX == CI.TrueX) ? Src1 : Src2; 285 MachineOperand *SrcF = (MinX == CI.FalseX) ? Src1 : Src2; 286 // Prefer "down", since this will move the MUX farther away from the 287 // predicate definition. 288 MachineBasicBlock::iterator At = CanDown ? Def2 : Def1; 289 ML.push_back(MuxInfo(At, DR, PR, SrcT, SrcF, Def1, Def2)); 290 } 291 292 for (unsigned I = 0, N = ML.size(); I < N; ++I) { 293 MuxInfo &MX = ML[I]; 294 MachineBasicBlock &B = *MX.At->getParent(); 295 DebugLoc DL = MX.At->getDebugLoc(); 296 unsigned MxOpc = getMuxOpcode(*MX.SrcT, *MX.SrcF); 297 if (!MxOpc) 298 continue; 299 BuildMI(B, MX.At, DL, HII->get(MxOpc), MX.DefR) 300 .addReg(MX.PredR) 301 .addOperand(*MX.SrcT) 302 .addOperand(*MX.SrcF); 303 B.erase(MX.Def1); 304 B.erase(MX.Def2); 305 Changed = true; 306 } 307 308 return Changed; 309} 310 311bool HexagonGenMux::runOnMachineFunction(MachineFunction &MF) { 312 if (skipFunction(*MF.getFunction())) 313 return false; 314 HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo(); 315 HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo(); 316 bool Changed = false; 317 for (auto &I : MF) 318 Changed |= genMuxInBlock(I); 319 return Changed; 320} 321 322FunctionPass *llvm::createHexagonGenMux() { 323 return new HexagonGenMux(); 324} 325