1 //===-- llvm/CodeGen/GlobalISel/CSEMIRBuilder.cpp - MIBuilder--*- C++ -*-==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// \file 9 /// This file implements the CSEMIRBuilder class which CSEs as it builds 10 /// instructions. 11 //===----------------------------------------------------------------------===// 12 // 13 14 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h" 15 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h" 16 #include "llvm/CodeGen/GlobalISel/Utils.h" 17 #include "llvm/CodeGen/MachineInstrBuilder.h" 18 #include "llvm/IR/DebugInfoMetadata.h" 19 20 using namespace llvm; 21 22 bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A, 23 MachineBasicBlock::const_iterator B) const { 24 auto MBBEnd = getMBB().end(); 25 if (B == MBBEnd) 26 return true; 27 assert(A->getParent() == B->getParent() && 28 "Iterators should be in same block"); 29 const MachineBasicBlock *BBA = A->getParent(); 30 MachineBasicBlock::const_iterator I = BBA->begin(); 31 for (; &*I != A && &*I != B; ++I) 32 ; 33 return &*I == A; 34 } 35 36 MachineInstrBuilder 37 CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID, 38 void *&NodeInsertPos) { 39 GISelCSEInfo *CSEInfo = getCSEInfo(); 40 assert(CSEInfo && "Can't get here without setting CSEInfo"); 41 MachineBasicBlock *CurMBB = &getMBB(); 42 MachineInstr *MI = 43 CSEInfo->getMachineInstrIfExists(ID, CurMBB, NodeInsertPos); 44 if (MI) { 45 CSEInfo->countOpcodeHit(MI->getOpcode()); 46 auto CurrPos = getInsertPt(); 47 auto MII = MachineBasicBlock::iterator(MI); 48 if (MII == CurrPos) { 49 // Move the insert point ahead of the instruction so any future uses of 50 // this builder will have the def ready. 51 setInsertPt(*CurMBB, std::next(MII)); 52 } else if (!dominates(MI, CurrPos)) { 53 CurMBB->splice(CurrPos, CurMBB, MI); 54 } 55 return MachineInstrBuilder(getMF(), MI); 56 } 57 return MachineInstrBuilder(); 58 } 59 60 bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const { 61 const GISelCSEInfo *CSEInfo = getCSEInfo(); 62 if (!CSEInfo || !CSEInfo->shouldCSE(Opc)) 63 return false; 64 return true; 65 } 66 67 void CSEMIRBuilder::profileDstOp(const DstOp &Op, 68 GISelInstProfileBuilder &B) const { 69 switch (Op.getDstOpKind()) { 70 case DstOp::DstType::Ty_RC: 71 B.addNodeIDRegType(Op.getRegClass()); 72 break; 73 case DstOp::DstType::Ty_Reg: { 74 // Regs can have LLT&(RB|RC). If those exist, profile them as well. 75 B.addNodeIDReg(Op.getReg()); 76 break; 77 } 78 default: 79 B.addNodeIDRegType(Op.getLLTTy(*getMRI())); 80 break; 81 } 82 } 83 84 void CSEMIRBuilder::profileSrcOp(const SrcOp &Op, 85 GISelInstProfileBuilder &B) const { 86 switch (Op.getSrcOpKind()) { 87 case SrcOp::SrcType::Ty_Imm: 88 B.addNodeIDImmediate(static_cast<int64_t>(Op.getImm())); 89 break; 90 case SrcOp::SrcType::Ty_Predicate: 91 B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate())); 92 break; 93 default: 94 B.addNodeIDRegType(Op.getReg()); 95 break; 96 } 97 } 98 99 void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B, 100 unsigned Opc) const { 101 // First add the MBB (Local CSE). 102 B.addNodeIDMBB(&getMBB()); 103 // Then add the opcode. 104 B.addNodeIDOpcode(Opc); 105 } 106 107 void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps, 108 ArrayRef<SrcOp> SrcOps, 109 Optional<unsigned> Flags, 110 GISelInstProfileBuilder &B) const { 111 112 profileMBBOpcode(B, Opc); 113 // Then add the DstOps. 114 profileDstOps(DstOps, B); 115 // Then add the SrcOps. 116 profileSrcOps(SrcOps, B); 117 // Add Flags if passed in. 118 if (Flags) 119 B.addNodeIDFlag(*Flags); 120 } 121 122 MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB, 123 void *NodeInsertPos) { 124 assert(canPerformCSEForOpc(MIB->getOpcode()) && 125 "Attempting to CSE illegal op"); 126 MachineInstr *MIBInstr = MIB; 127 getCSEInfo()->insertInstr(MIBInstr, NodeInsertPos); 128 return MIB; 129 } 130 131 bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) { 132 if (DstOps.size() == 1) 133 return true; // always possible to emit copy to just 1 vreg. 134 135 return llvm::all_of(DstOps, [](const DstOp &Op) { 136 DstOp::DstType DT = Op.getDstOpKind(); 137 return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC; 138 }); 139 } 140 141 MachineInstrBuilder 142 CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps, 143 MachineInstrBuilder &MIB) { 144 assert(checkCopyToDefsPossible(DstOps) && 145 "Impossible return a single MIB with copies to multiple defs"); 146 if (DstOps.size() == 1) { 147 const DstOp &Op = DstOps[0]; 148 if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg) 149 return buildCopy(Op.getReg(), MIB.getReg(0)); 150 } 151 152 // If we didn't generate a copy then we're re-using an existing node directly 153 // instead of emitting any code. Merge the debug location we wanted to emit 154 // into the instruction we're CSE'ing with. Debug locations arent part of the 155 // profile so we don't need to recompute it. 156 if (getDebugLoc()) { 157 GISelChangeObserver *Observer = getState().Observer; 158 if (Observer) 159 Observer->changingInstr(*MIB); 160 MIB->setDebugLoc( 161 DILocation::getMergedLocation(MIB->getDebugLoc(), getDebugLoc())); 162 if (Observer) 163 Observer->changedInstr(*MIB); 164 } 165 166 return MIB; 167 } 168 169 MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc, 170 ArrayRef<DstOp> DstOps, 171 ArrayRef<SrcOp> SrcOps, 172 Optional<unsigned> Flag) { 173 switch (Opc) { 174 default: 175 break; 176 case TargetOpcode::G_ADD: 177 case TargetOpcode::G_AND: 178 case TargetOpcode::G_ASHR: 179 case TargetOpcode::G_LSHR: 180 case TargetOpcode::G_MUL: 181 case TargetOpcode::G_OR: 182 case TargetOpcode::G_SHL: 183 case TargetOpcode::G_SUB: 184 case TargetOpcode::G_XOR: 185 case TargetOpcode::G_UDIV: 186 case TargetOpcode::G_SDIV: 187 case TargetOpcode::G_UREM: 188 case TargetOpcode::G_SREM: 189 case TargetOpcode::G_SMIN: 190 case TargetOpcode::G_SMAX: 191 case TargetOpcode::G_UMIN: 192 case TargetOpcode::G_UMAX: { 193 // Try to constant fold these. 194 assert(SrcOps.size() == 2 && "Invalid sources"); 195 assert(DstOps.size() == 1 && "Invalid dsts"); 196 if (SrcOps[0].getLLTTy(*getMRI()).isVector()) { 197 // Try to constant fold vector constants. 198 Register VecCst = ConstantFoldVectorBinop( 199 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI(), *this); 200 if (VecCst) 201 return buildCopy(DstOps[0], VecCst); 202 break; 203 } 204 if (Optional<APInt> Cst = ConstantFoldBinOp(Opc, SrcOps[0].getReg(), 205 SrcOps[1].getReg(), *getMRI())) 206 return buildConstant(DstOps[0], *Cst); 207 break; 208 } 209 case TargetOpcode::G_FADD: 210 case TargetOpcode::G_FSUB: 211 case TargetOpcode::G_FMUL: 212 case TargetOpcode::G_FDIV: 213 case TargetOpcode::G_FREM: 214 case TargetOpcode::G_FMINNUM: 215 case TargetOpcode::G_FMAXNUM: 216 case TargetOpcode::G_FMINNUM_IEEE: 217 case TargetOpcode::G_FMAXNUM_IEEE: 218 case TargetOpcode::G_FMINIMUM: 219 case TargetOpcode::G_FMAXIMUM: 220 case TargetOpcode::G_FCOPYSIGN: { 221 // Try to constant fold these. 222 assert(SrcOps.size() == 2 && "Invalid sources"); 223 assert(DstOps.size() == 1 && "Invalid dsts"); 224 if (Optional<APFloat> Cst = ConstantFoldFPBinOp( 225 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI())) 226 return buildFConstant(DstOps[0], *Cst); 227 break; 228 } 229 case TargetOpcode::G_SEXT_INREG: { 230 assert(DstOps.size() == 1 && "Invalid dst ops"); 231 assert(SrcOps.size() == 2 && "Invalid src ops"); 232 const DstOp &Dst = DstOps[0]; 233 const SrcOp &Src0 = SrcOps[0]; 234 const SrcOp &Src1 = SrcOps[1]; 235 if (auto MaybeCst = 236 ConstantFoldExtOp(Opc, Src0.getReg(), Src1.getImm(), *getMRI())) 237 return buildConstant(Dst, *MaybeCst); 238 break; 239 } 240 case TargetOpcode::G_SITOFP: 241 case TargetOpcode::G_UITOFP: { 242 // Try to constant fold these. 243 assert(SrcOps.size() == 1 && "Invalid sources"); 244 assert(DstOps.size() == 1 && "Invalid dsts"); 245 if (Optional<APFloat> Cst = ConstantFoldIntToFloat( 246 Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI())) 247 return buildFConstant(DstOps[0], *Cst); 248 break; 249 } 250 case TargetOpcode::G_CTLZ: { 251 assert(SrcOps.size() == 1 && "Expected one source"); 252 assert(DstOps.size() == 1 && "Expected one dest"); 253 auto MaybeCsts = ConstantFoldCTLZ(SrcOps[0].getReg(), *getMRI()); 254 if (!MaybeCsts) 255 break; 256 if (MaybeCsts->size() == 1) 257 return buildConstant(DstOps[0], (*MaybeCsts)[0]); 258 // This was a vector constant. Build a G_BUILD_VECTOR for them. 259 SmallVector<Register> ConstantRegs; 260 LLT VecTy = DstOps[0].getLLTTy(*getMRI()); 261 for (unsigned Cst : *MaybeCsts) 262 ConstantRegs.emplace_back( 263 buildConstant(VecTy.getScalarType(), Cst).getReg(0)); 264 return buildBuildVector(DstOps[0], ConstantRegs); 265 } 266 } 267 bool CanCopy = checkCopyToDefsPossible(DstOps); 268 if (!canPerformCSEForOpc(Opc)) 269 return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag); 270 // If we can CSE this instruction, but involves generating copies to multiple 271 // regs, give up. This frequently happens to UNMERGEs. 272 if (!CanCopy) { 273 auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag); 274 // CSEInfo would have tracked this instruction. Remove it from the temporary 275 // insts. 276 getCSEInfo()->handleRemoveInst(&*MIB); 277 return MIB; 278 } 279 FoldingSetNodeID ID; 280 GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); 281 void *InsertPos = nullptr; 282 profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder); 283 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos); 284 if (MIB) { 285 // Handle generating copies here. 286 return generateCopiesIfRequired(DstOps, MIB); 287 } 288 // This instruction does not exist in the CSEInfo. Build it and CSE it. 289 MachineInstrBuilder NewMIB = 290 MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag); 291 return memoizeMI(NewMIB, InsertPos); 292 } 293 294 MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res, 295 const ConstantInt &Val) { 296 constexpr unsigned Opc = TargetOpcode::G_CONSTANT; 297 if (!canPerformCSEForOpc(Opc)) 298 return MachineIRBuilder::buildConstant(Res, Val); 299 300 // For vectors, CSE the element only for now. 301 LLT Ty = Res.getLLTTy(*getMRI()); 302 if (Ty.isVector()) 303 return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val)); 304 305 FoldingSetNodeID ID; 306 GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); 307 void *InsertPos = nullptr; 308 profileMBBOpcode(ProfBuilder, Opc); 309 profileDstOp(Res, ProfBuilder); 310 ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val)); 311 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos); 312 if (MIB) { 313 // Handle generating copies here. 314 return generateCopiesIfRequired({Res}, MIB); 315 } 316 317 MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val); 318 return memoizeMI(NewMIB, InsertPos); 319 } 320 321 MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res, 322 const ConstantFP &Val) { 323 constexpr unsigned Opc = TargetOpcode::G_FCONSTANT; 324 if (!canPerformCSEForOpc(Opc)) 325 return MachineIRBuilder::buildFConstant(Res, Val); 326 327 // For vectors, CSE the element only for now. 328 LLT Ty = Res.getLLTTy(*getMRI()); 329 if (Ty.isVector()) 330 return buildSplatVector(Res, buildFConstant(Ty.getElementType(), Val)); 331 332 FoldingSetNodeID ID; 333 GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); 334 void *InsertPos = nullptr; 335 profileMBBOpcode(ProfBuilder, Opc); 336 profileDstOp(Res, ProfBuilder); 337 ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val)); 338 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos); 339 if (MIB) { 340 // Handle generating copies here. 341 return generateCopiesIfRequired({Res}, MIB); 342 } 343 MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val); 344 return memoizeMI(NewMIB, InsertPos); 345 } 346