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