388 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8/// \file9/// This file implements the CSEMIRBuilder class which CSEs as it builds10/// instructions.11//===----------------------------------------------------------------------===//12//13 14#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"15#include "llvm/CodeGen/GlobalISel/CSEInfo.h"16#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"17#include "llvm/CodeGen/GlobalISel/Utils.h"18#include "llvm/CodeGen/MachineInstrBuilder.h"19 20using namespace llvm;21 22bool 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 36MachineInstrBuilder37CSEMIRBuilder::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 of50 // this builder will have the def ready.51 setInsertPt(*CurMBB, std::next(MII));52 } else if (!dominates(MI, CurrPos)) {53 // Update the spliced machineinstr's debug location by merging it with the54 // debug location of the instruction at the insertion point.55 auto Loc = DebugLoc::getMergedLocation(getDebugLoc(), MI->getDebugLoc());56 MI->setDebugLoc(Loc);57 CurMBB->splice(CurrPos, CurMBB, MI);58 }59 return MachineInstrBuilder(getMF(), MI);60 }61 return MachineInstrBuilder();62}63 64bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {65 const GISelCSEInfo *CSEInfo = getCSEInfo();66 if (!CSEInfo || !CSEInfo->shouldCSE(Opc))67 return false;68 return true;69}70 71void CSEMIRBuilder::profileDstOp(const DstOp &Op,72 GISelInstProfileBuilder &B) const {73 switch (Op.getDstOpKind()) {74 case DstOp::DstType::Ty_RC: {75 B.addNodeIDRegType(Op.getRegClass());76 break;77 }78 case DstOp::DstType::Ty_Reg: {79 // Regs can have LLT&(RB|RC). If those exist, profile them as well.80 B.addNodeIDReg(Op.getReg());81 break;82 }83 case DstOp::DstType::Ty_LLT: {84 B.addNodeIDRegType(Op.getLLTTy(*getMRI()));85 break;86 }87 case DstOp::DstType::Ty_VRegAttrs: {88 B.addNodeIDRegType(Op.getVRegAttrs());89 break;90 }91 }92}93 94void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,95 GISelInstProfileBuilder &B) const {96 switch (Op.getSrcOpKind()) {97 case SrcOp::SrcType::Ty_Imm:98 B.addNodeIDImmediate(Op.getImm());99 break;100 case SrcOp::SrcType::Ty_Predicate:101 B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));102 break;103 default:104 B.addNodeIDRegType(Op.getReg());105 break;106 }107}108 109void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,110 unsigned Opc) const {111 // First add the MBB (Local CSE).112 B.addNodeIDMBB(&getMBB());113 // Then add the opcode.114 B.addNodeIDOpcode(Opc);115}116 117void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps,118 ArrayRef<SrcOp> SrcOps,119 std::optional<unsigned> Flags,120 GISelInstProfileBuilder &B) const {121 122 profileMBBOpcode(B, Opc);123 // Then add the DstOps.124 profileDstOps(DstOps, B);125 // Then add the SrcOps.126 profileSrcOps(SrcOps, B);127 // Add Flags if passed in.128 if (Flags)129 B.addNodeIDFlag(*Flags);130}131 132MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB,133 void *NodeInsertPos) {134 assert(canPerformCSEForOpc(MIB->getOpcode()) &&135 "Attempting to CSE illegal op");136 MachineInstr *MIBInstr = MIB;137 getCSEInfo()->insertInstr(MIBInstr, NodeInsertPos);138 return MIB;139}140 141bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) {142 if (DstOps.size() == 1)143 return true; // always possible to emit copy to just 1 vreg.144 145 return llvm::all_of(DstOps, [](const DstOp &Op) {146 DstOp::DstType DT = Op.getDstOpKind();147 return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;148 });149}150 151MachineInstrBuilder152CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps,153 MachineInstrBuilder &MIB) {154 assert(checkCopyToDefsPossible(DstOps) &&155 "Impossible return a single MIB with copies to multiple defs");156 if (DstOps.size() == 1) {157 const DstOp &Op = DstOps[0];158 if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg)159 return buildCopy(Op.getReg(), MIB.getReg(0));160 }161 162 // If we didn't generate a copy then we're re-using an existing node directly163 // instead of emitting any code. Merge the debug location we wanted to emit164 // into the instruction we're CSE'ing with. Debug locations arent part of the165 // profile so we don't need to recompute it.166 if (getDebugLoc()) {167 GISelChangeObserver *Observer = getState().Observer;168 if (Observer)169 Observer->changingInstr(*MIB);170 MIB->setDebugLoc(171 DebugLoc::getMergedLocation(MIB->getDebugLoc(), getDebugLoc()));172 if (Observer)173 Observer->changedInstr(*MIB);174 }175 176 return MIB;177}178 179MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc,180 ArrayRef<DstOp> DstOps,181 ArrayRef<SrcOp> SrcOps,182 std::optional<unsigned> Flag) {183 switch (Opc) {184 default:185 break;186 case TargetOpcode::G_ICMP: {187 assert(SrcOps.size() == 3 && "Invalid sources");188 assert(DstOps.size() == 1 && "Invalid dsts");189 LLT SrcTy = SrcOps[1].getLLTTy(*getMRI());190 LLT DstTy = DstOps[0].getLLTTy(*getMRI());191 auto BoolExtOp = getBoolExtOp(SrcTy.isVector(), false);192 193 if (std::optional<SmallVector<APInt>> Cst = ConstantFoldICmp(194 SrcOps[0].getPredicate(), SrcOps[1].getReg(), SrcOps[2].getReg(),195 DstTy.getScalarSizeInBits(), BoolExtOp, *getMRI())) {196 if (SrcTy.isVector())197 return buildBuildVectorConstant(DstOps[0], *Cst);198 return buildConstant(DstOps[0], Cst->front());199 }200 break;201 }202 case TargetOpcode::G_ADD:203 case TargetOpcode::G_PTR_ADD:204 case TargetOpcode::G_AND:205 case TargetOpcode::G_ASHR:206 case TargetOpcode::G_LSHR:207 case TargetOpcode::G_MUL:208 case TargetOpcode::G_OR:209 case TargetOpcode::G_SHL:210 case TargetOpcode::G_SUB:211 case TargetOpcode::G_XOR:212 case TargetOpcode::G_UDIV:213 case TargetOpcode::G_SDIV:214 case TargetOpcode::G_UREM:215 case TargetOpcode::G_SREM:216 case TargetOpcode::G_SMIN:217 case TargetOpcode::G_SMAX:218 case TargetOpcode::G_UMIN:219 case TargetOpcode::G_UMAX: {220 // Try to constant fold these.221 assert(SrcOps.size() == 2 && "Invalid sources");222 assert(DstOps.size() == 1 && "Invalid dsts");223 LLT SrcTy = SrcOps[0].getLLTTy(*getMRI());224 225 if (Opc == TargetOpcode::G_PTR_ADD &&226 getDataLayout().isNonIntegralAddressSpace(SrcTy.getAddressSpace()))227 break;228 229 if (SrcTy.isVector()) {230 // Try to constant fold vector constants.231 SmallVector<APInt> VecCst = ConstantFoldVectorBinop(232 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI());233 if (!VecCst.empty())234 return buildBuildVectorConstant(DstOps[0], VecCst);235 break;236 }237 238 if (std::optional<APInt> Cst = ConstantFoldBinOp(239 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))240 return buildConstant(DstOps[0], *Cst);241 break;242 }243 case TargetOpcode::G_FADD:244 case TargetOpcode::G_FSUB:245 case TargetOpcode::G_FMUL:246 case TargetOpcode::G_FDIV:247 case TargetOpcode::G_FREM:248 case TargetOpcode::G_FMINNUM:249 case TargetOpcode::G_FMAXNUM:250 case TargetOpcode::G_FMINNUM_IEEE:251 case TargetOpcode::G_FMAXNUM_IEEE:252 case TargetOpcode::G_FMINIMUM:253 case TargetOpcode::G_FMAXIMUM:254 case TargetOpcode::G_FCOPYSIGN: {255 // Try to constant fold these.256 assert(SrcOps.size() == 2 && "Invalid sources");257 assert(DstOps.size() == 1 && "Invalid dsts");258 if (std::optional<APFloat> Cst = ConstantFoldFPBinOp(259 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))260 return buildFConstant(DstOps[0], *Cst);261 break;262 }263 case TargetOpcode::G_SEXT_INREG: {264 assert(DstOps.size() == 1 && "Invalid dst ops");265 assert(SrcOps.size() == 2 && "Invalid src ops");266 const DstOp &Dst = DstOps[0];267 const SrcOp &Src0 = SrcOps[0];268 const SrcOp &Src1 = SrcOps[1];269 if (auto MaybeCst =270 ConstantFoldExtOp(Opc, Src0.getReg(), Src1.getImm(), *getMRI()))271 return buildConstant(Dst, *MaybeCst);272 break;273 }274 case TargetOpcode::G_SITOFP:275 case TargetOpcode::G_UITOFP: {276 // Try to constant fold these.277 assert(SrcOps.size() == 1 && "Invalid sources");278 assert(DstOps.size() == 1 && "Invalid dsts");279 if (std::optional<APFloat> Cst = ConstantFoldIntToFloat(280 Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI()))281 return buildFConstant(DstOps[0], *Cst);282 break;283 }284 case TargetOpcode::G_CTLZ:285 case TargetOpcode::G_CTTZ: {286 assert(SrcOps.size() == 1 && "Expected one source");287 assert(DstOps.size() == 1 && "Expected one dest");288 std::function<unsigned(APInt)> CB;289 if (Opc == TargetOpcode::G_CTLZ)290 CB = [](APInt V) -> unsigned { return V.countl_zero(); };291 else292 CB = [](APInt V) -> unsigned { return V.countTrailingZeros(); };293 auto MaybeCsts = ConstantFoldCountZeros(SrcOps[0].getReg(), *getMRI(), CB);294 if (!MaybeCsts)295 break;296 if (MaybeCsts->size() == 1)297 return buildConstant(DstOps[0], (*MaybeCsts)[0]);298 // This was a vector constant. Build a G_BUILD_VECTOR for them.299 SmallVector<Register> ConstantRegs;300 LLT VecTy = DstOps[0].getLLTTy(*getMRI());301 for (unsigned Cst : *MaybeCsts)302 ConstantRegs.emplace_back(303 buildConstant(VecTy.getScalarType(), Cst).getReg(0));304 return buildBuildVector(DstOps[0], ConstantRegs);305 }306 }307 bool CanCopy = checkCopyToDefsPossible(DstOps);308 if (!canPerformCSEForOpc(Opc))309 return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);310 // If we can CSE this instruction, but involves generating copies to multiple311 // regs, give up. This frequently happens to UNMERGEs.312 if (!CanCopy) {313 auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);314 // CSEInfo would have tracked this instruction. Remove it from the temporary315 // insts.316 getCSEInfo()->handleRemoveInst(&*MIB);317 return MIB;318 }319 FoldingSetNodeID ID;320 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());321 void *InsertPos = nullptr;322 profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);323 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);324 if (MIB) {325 // Handle generating copies here.326 return generateCopiesIfRequired(DstOps, MIB);327 }328 // This instruction does not exist in the CSEInfo. Build it and CSE it.329 MachineInstrBuilder NewMIB =330 MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);331 return memoizeMI(NewMIB, InsertPos);332}333 334MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res,335 const ConstantInt &Val) {336 constexpr unsigned Opc = TargetOpcode::G_CONSTANT;337 if (!canPerformCSEForOpc(Opc))338 return MachineIRBuilder::buildConstant(Res, Val);339 340 // For vectors, CSE the element only for now.341 LLT Ty = Res.getLLTTy(*getMRI());342 if (Ty.isFixedVector())343 return buildSplatBuildVector(Res, buildConstant(Ty.getElementType(), Val));344 if (Ty.isScalableVector())345 return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val));346 347 FoldingSetNodeID ID;348 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());349 void *InsertPos = nullptr;350 profileMBBOpcode(ProfBuilder, Opc);351 profileDstOp(Res, ProfBuilder);352 ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val));353 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);354 if (MIB) {355 // Handle generating copies here.356 return generateCopiesIfRequired({Res}, MIB);357 }358 359 MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);360 return memoizeMI(NewMIB, InsertPos);361}362 363MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res,364 const ConstantFP &Val) {365 constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;366 if (!canPerformCSEForOpc(Opc))367 return MachineIRBuilder::buildFConstant(Res, Val);368 369 // For vectors, CSE the element only for now.370 LLT Ty = Res.getLLTTy(*getMRI());371 if (Ty.isVector())372 return buildSplatBuildVector(Res, buildFConstant(Ty.getElementType(), Val));373 374 FoldingSetNodeID ID;375 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());376 void *InsertPos = nullptr;377 profileMBBOpcode(ProfBuilder, Opc);378 profileDstOp(Res, ProfBuilder);379 ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val));380 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);381 if (MIB) {382 // Handle generating copies here.383 return generateCopiesIfRequired({Res}, MIB);384 }385 MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);386 return memoizeMI(NewMIB, InsertPos);387}388