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 // Try to constant fold these. 190 assert(SrcOps.size() == 2 && "Invalid sources"); 191 assert(DstOps.size() == 1 && "Invalid dsts"); 192 if (SrcOps[0].getLLTTy(*getMRI()).isVector()) { 193 // Try to constant fold vector constants. 194 Register VecCst = ConstantFoldVectorBinop( 195 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI(), *this); 196 if (VecCst) 197 return buildCopy(DstOps[0], VecCst); 198 break; 199 } 200 if (Optional<APInt> Cst = ConstantFoldBinOp(Opc, SrcOps[0].getReg(), 201 SrcOps[1].getReg(), *getMRI())) 202 return buildConstant(DstOps[0], *Cst); 203 break; 204 } 205 case TargetOpcode::G_SEXT_INREG: { 206 assert(DstOps.size() == 1 && "Invalid dst ops"); 207 assert(SrcOps.size() == 2 && "Invalid src ops"); 208 const DstOp &Dst = DstOps[0]; 209 const SrcOp &Src0 = SrcOps[0]; 210 const SrcOp &Src1 = SrcOps[1]; 211 if (auto MaybeCst = 212 ConstantFoldExtOp(Opc, Src0.getReg(), Src1.getImm(), *getMRI())) 213 return buildConstant(Dst, *MaybeCst); 214 break; 215 } 216 case TargetOpcode::G_SITOFP: 217 case TargetOpcode::G_UITOFP: { 218 // Try to constant fold these. 219 assert(SrcOps.size() == 1 && "Invalid sources"); 220 assert(DstOps.size() == 1 && "Invalid dsts"); 221 if (Optional<APFloat> Cst = ConstantFoldIntToFloat( 222 Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI())) 223 return buildFConstant(DstOps[0], *Cst); 224 break; 225 } 226 case TargetOpcode::G_CTLZ: { 227 assert(SrcOps.size() == 1 && "Expected one source"); 228 assert(DstOps.size() == 1 && "Expected one dest"); 229 auto MaybeCsts = ConstantFoldCTLZ(SrcOps[0].getReg(), *getMRI()); 230 if (!MaybeCsts) 231 break; 232 if (MaybeCsts->size() == 1) 233 return buildConstant(DstOps[0], (*MaybeCsts)[0]); 234 // This was a vector constant. Build a G_BUILD_VECTOR for them. 235 SmallVector<Register> ConstantRegs; 236 LLT VecTy = DstOps[0].getLLTTy(*getMRI()); 237 for (unsigned Cst : *MaybeCsts) 238 ConstantRegs.emplace_back( 239 buildConstant(VecTy.getScalarType(), Cst).getReg(0)); 240 return buildBuildVector(DstOps[0], ConstantRegs); 241 } 242 } 243 bool CanCopy = checkCopyToDefsPossible(DstOps); 244 if (!canPerformCSEForOpc(Opc)) 245 return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag); 246 // If we can CSE this instruction, but involves generating copies to multiple 247 // regs, give up. This frequently happens to UNMERGEs. 248 if (!CanCopy) { 249 auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag); 250 // CSEInfo would have tracked this instruction. Remove it from the temporary 251 // insts. 252 getCSEInfo()->handleRemoveInst(&*MIB); 253 return MIB; 254 } 255 FoldingSetNodeID ID; 256 GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); 257 void *InsertPos = nullptr; 258 profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder); 259 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos); 260 if (MIB) { 261 // Handle generating copies here. 262 return generateCopiesIfRequired(DstOps, MIB); 263 } 264 // This instruction does not exist in the CSEInfo. Build it and CSE it. 265 MachineInstrBuilder NewMIB = 266 MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag); 267 return memoizeMI(NewMIB, InsertPos); 268 } 269 270 MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res, 271 const ConstantInt &Val) { 272 constexpr unsigned Opc = TargetOpcode::G_CONSTANT; 273 if (!canPerformCSEForOpc(Opc)) 274 return MachineIRBuilder::buildConstant(Res, Val); 275 276 // For vectors, CSE the element only for now. 277 LLT Ty = Res.getLLTTy(*getMRI()); 278 if (Ty.isVector()) 279 return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val)); 280 281 FoldingSetNodeID ID; 282 GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); 283 void *InsertPos = nullptr; 284 profileMBBOpcode(ProfBuilder, Opc); 285 profileDstOp(Res, ProfBuilder); 286 ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val)); 287 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos); 288 if (MIB) { 289 // Handle generating copies here. 290 return generateCopiesIfRequired({Res}, MIB); 291 } 292 293 MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val); 294 return memoizeMI(NewMIB, InsertPos); 295 } 296 297 MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res, 298 const ConstantFP &Val) { 299 constexpr unsigned Opc = TargetOpcode::G_FCONSTANT; 300 if (!canPerformCSEForOpc(Opc)) 301 return MachineIRBuilder::buildFConstant(Res, Val); 302 303 // For vectors, CSE the element only for now. 304 LLT Ty = Res.getLLTTy(*getMRI()); 305 if (Ty.isVector()) 306 return buildSplatVector(Res, buildFConstant(Ty.getElementType(), Val)); 307 308 FoldingSetNodeID ID; 309 GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); 310 void *InsertPos = nullptr; 311 profileMBBOpcode(ProfBuilder, Opc); 312 profileDstOp(Res, ProfBuilder); 313 ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val)); 314 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos); 315 if (MIB) { 316 // Handle generating copies here. 317 return generateCopiesIfRequired({Res}, MIB); 318 } 319 MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val); 320 return memoizeMI(NewMIB, InsertPos); 321 } 322