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