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 31 using namespace llvm; 32 33 namespace llvm { 34 FunctionPass *createHexagonGenMux(); 35 void initializeHexagonGenMuxPass(PassRegistry& Registry); 36 } 37 38 namespace { 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 104 INITIALIZE_PASS(HexagonGenMux, "hexagon-mux", 105 "Hexagon generate mux instructions", false, false) 106 107 108 void HexagonGenMux::getSubRegs(unsigned Reg, BitVector &SRs) const { 109 for (MCSubRegIterator I(Reg, HRI); I.isValid(); ++I) 110 SRs[*I] = true; 111 } 112 113 114 void HexagonGenMux::expandReg(unsigned Reg, BitVector &Set) const { 115 if (isRegPair(Reg)) 116 getSubRegs(Reg, Set); 117 else 118 Set[Reg] = true; 119 } 120 121 122 void 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 145 void 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 163 bool 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 175 unsigned 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 192 bool 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 311 bool 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 322 FunctionPass *llvm::createHexagonGenMux() { 323 return new HexagonGenMux(); 324 } 325