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