| //===-- llvm/CodeGen/GlobalISel/CSEMIRBuilder.cpp - MIBuilder--*- C++ -*-==// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| /// \file |
| /// This file implements the CSEMIRBuilder class which CSEs as it builds |
| /// instructions. |
| //===----------------------------------------------------------------------===// |
| // |
| |
| #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h" |
| #include "llvm/CodeGen/GlobalISel/CSEInfo.h" |
| #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h" |
| #include "llvm/CodeGen/GlobalISel/Utils.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/IR/DebugInfoMetadata.h" |
| |
| using namespace llvm; |
| |
| bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A, |
| MachineBasicBlock::const_iterator B) const { |
| auto MBBEnd = getMBB().end(); |
| if (B == MBBEnd) |
| return true; |
| assert(A->getParent() == B->getParent() && |
| "Iterators should be in same block"); |
| const MachineBasicBlock *BBA = A->getParent(); |
| MachineBasicBlock::const_iterator I = BBA->begin(); |
| for (; &*I != A && &*I != B; ++I) |
| ; |
| return &*I == A; |
| } |
| |
| MachineInstrBuilder |
| CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID, |
| void *&NodeInsertPos) { |
| GISelCSEInfo *CSEInfo = getCSEInfo(); |
| assert(CSEInfo && "Can't get here without setting CSEInfo"); |
| MachineBasicBlock *CurMBB = &getMBB(); |
| MachineInstr *MI = |
| CSEInfo->getMachineInstrIfExists(ID, CurMBB, NodeInsertPos); |
| if (MI) { |
| CSEInfo->countOpcodeHit(MI->getOpcode()); |
| auto CurrPos = getInsertPt(); |
| auto MII = MachineBasicBlock::iterator(MI); |
| if (MII == CurrPos) { |
| // Move the insert point ahead of the instruction so any future uses of |
| // this builder will have the def ready. |
| setInsertPt(*CurMBB, std::next(MII)); |
| } else if (!dominates(MI, CurrPos)) { |
| CurMBB->splice(CurrPos, CurMBB, MI); |
| } |
| return MachineInstrBuilder(getMF(), MI); |
| } |
| return MachineInstrBuilder(); |
| } |
| |
| bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const { |
| const GISelCSEInfo *CSEInfo = getCSEInfo(); |
| if (!CSEInfo || !CSEInfo->shouldCSE(Opc)) |
| return false; |
| return true; |
| } |
| |
| void CSEMIRBuilder::profileDstOp(const DstOp &Op, |
| GISelInstProfileBuilder &B) const { |
| switch (Op.getDstOpKind()) { |
| case DstOp::DstType::Ty_RC: |
| B.addNodeIDRegType(Op.getRegClass()); |
| break; |
| case DstOp::DstType::Ty_Reg: { |
| // Regs can have LLT&(RB|RC). If those exist, profile them as well. |
| B.addNodeIDReg(Op.getReg()); |
| break; |
| } |
| default: |
| B.addNodeIDRegType(Op.getLLTTy(*getMRI())); |
| break; |
| } |
| } |
| |
| void CSEMIRBuilder::profileSrcOp(const SrcOp &Op, |
| GISelInstProfileBuilder &B) const { |
| switch (Op.getSrcOpKind()) { |
| case SrcOp::SrcType::Ty_Imm: |
| B.addNodeIDImmediate(static_cast<int64_t>(Op.getImm())); |
| break; |
| case SrcOp::SrcType::Ty_Predicate: |
| B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate())); |
| break; |
| default: |
| B.addNodeIDRegType(Op.getReg()); |
| break; |
| } |
| } |
| |
| void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B, |
| unsigned Opc) const { |
| // First add the MBB (Local CSE). |
| B.addNodeIDMBB(&getMBB()); |
| // Then add the opcode. |
| B.addNodeIDOpcode(Opc); |
| } |
| |
| void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps, |
| ArrayRef<SrcOp> SrcOps, |
| std::optional<unsigned> Flags, |
| GISelInstProfileBuilder &B) const { |
| |
| profileMBBOpcode(B, Opc); |
| // Then add the DstOps. |
| profileDstOps(DstOps, B); |
| // Then add the SrcOps. |
| profileSrcOps(SrcOps, B); |
| // Add Flags if passed in. |
| if (Flags) |
| B.addNodeIDFlag(*Flags); |
| } |
| |
| MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB, |
| void *NodeInsertPos) { |
| assert(canPerformCSEForOpc(MIB->getOpcode()) && |
| "Attempting to CSE illegal op"); |
| MachineInstr *MIBInstr = MIB; |
| getCSEInfo()->insertInstr(MIBInstr, NodeInsertPos); |
| return MIB; |
| } |
| |
| bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) { |
| if (DstOps.size() == 1) |
| return true; // always possible to emit copy to just 1 vreg. |
| |
| return llvm::all_of(DstOps, [](const DstOp &Op) { |
| DstOp::DstType DT = Op.getDstOpKind(); |
| return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC; |
| }); |
| } |
| |
| MachineInstrBuilder |
| CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps, |
| MachineInstrBuilder &MIB) { |
| assert(checkCopyToDefsPossible(DstOps) && |
| "Impossible return a single MIB with copies to multiple defs"); |
| if (DstOps.size() == 1) { |
| const DstOp &Op = DstOps[0]; |
| if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg) |
| return buildCopy(Op.getReg(), MIB.getReg(0)); |
| } |
| |
| // If we didn't generate a copy then we're re-using an existing node directly |
| // instead of emitting any code. Merge the debug location we wanted to emit |
| // into the instruction we're CSE'ing with. Debug locations arent part of the |
| // profile so we don't need to recompute it. |
| if (getDebugLoc()) { |
| GISelChangeObserver *Observer = getState().Observer; |
| if (Observer) |
| Observer->changingInstr(*MIB); |
| MIB->setDebugLoc( |
| DILocation::getMergedLocation(MIB->getDebugLoc(), getDebugLoc())); |
| if (Observer) |
| Observer->changedInstr(*MIB); |
| } |
| |
| return MIB; |
| } |
| |
| MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc, |
| ArrayRef<DstOp> DstOps, |
| ArrayRef<SrcOp> SrcOps, |
| std::optional<unsigned> Flag) { |
| switch (Opc) { |
| default: |
| break; |
| case TargetOpcode::G_ADD: |
| case TargetOpcode::G_PTR_ADD: |
| case TargetOpcode::G_AND: |
| case TargetOpcode::G_ASHR: |
| case TargetOpcode::G_LSHR: |
| case TargetOpcode::G_MUL: |
| case TargetOpcode::G_OR: |
| case TargetOpcode::G_SHL: |
| case TargetOpcode::G_SUB: |
| case TargetOpcode::G_XOR: |
| case TargetOpcode::G_UDIV: |
| case TargetOpcode::G_SDIV: |
| case TargetOpcode::G_UREM: |
| case TargetOpcode::G_SREM: |
| case TargetOpcode::G_SMIN: |
| case TargetOpcode::G_SMAX: |
| case TargetOpcode::G_UMIN: |
| case TargetOpcode::G_UMAX: { |
| // Try to constant fold these. |
| assert(SrcOps.size() == 2 && "Invalid sources"); |
| assert(DstOps.size() == 1 && "Invalid dsts"); |
| LLT SrcTy = SrcOps[0].getLLTTy(*getMRI()); |
| |
| if (Opc == TargetOpcode::G_PTR_ADD && |
| getDataLayout().isNonIntegralAddressSpace(SrcTy.getAddressSpace())) |
| break; |
| |
| if (SrcTy.isVector()) { |
| // Try to constant fold vector constants. |
| SmallVector<APInt> VecCst = ConstantFoldVectorBinop( |
| Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()); |
| if (!VecCst.empty()) |
| return buildBuildVectorConstant(DstOps[0], VecCst); |
| break; |
| } |
| |
| if (std::optional<APInt> Cst = ConstantFoldBinOp( |
| Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI())) |
| return buildConstant(DstOps[0], *Cst); |
| break; |
| } |
| case TargetOpcode::G_FADD: |
| case TargetOpcode::G_FSUB: |
| case TargetOpcode::G_FMUL: |
| case TargetOpcode::G_FDIV: |
| case TargetOpcode::G_FREM: |
| case TargetOpcode::G_FMINNUM: |
| case TargetOpcode::G_FMAXNUM: |
| case TargetOpcode::G_FMINNUM_IEEE: |
| case TargetOpcode::G_FMAXNUM_IEEE: |
| case TargetOpcode::G_FMINIMUM: |
| case TargetOpcode::G_FMAXIMUM: |
| case TargetOpcode::G_FCOPYSIGN: { |
| // Try to constant fold these. |
| assert(SrcOps.size() == 2 && "Invalid sources"); |
| assert(DstOps.size() == 1 && "Invalid dsts"); |
| if (std::optional<APFloat> Cst = ConstantFoldFPBinOp( |
| Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI())) |
| return buildFConstant(DstOps[0], *Cst); |
| break; |
| } |
| case TargetOpcode::G_SEXT_INREG: { |
| assert(DstOps.size() == 1 && "Invalid dst ops"); |
| assert(SrcOps.size() == 2 && "Invalid src ops"); |
| const DstOp &Dst = DstOps[0]; |
| const SrcOp &Src0 = SrcOps[0]; |
| const SrcOp &Src1 = SrcOps[1]; |
| if (auto MaybeCst = |
| ConstantFoldExtOp(Opc, Src0.getReg(), Src1.getImm(), *getMRI())) |
| return buildConstant(Dst, *MaybeCst); |
| break; |
| } |
| case TargetOpcode::G_SITOFP: |
| case TargetOpcode::G_UITOFP: { |
| // Try to constant fold these. |
| assert(SrcOps.size() == 1 && "Invalid sources"); |
| assert(DstOps.size() == 1 && "Invalid dsts"); |
| if (std::optional<APFloat> Cst = ConstantFoldIntToFloat( |
| Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI())) |
| return buildFConstant(DstOps[0], *Cst); |
| break; |
| } |
| case TargetOpcode::G_CTLZ: { |
| assert(SrcOps.size() == 1 && "Expected one source"); |
| assert(DstOps.size() == 1 && "Expected one dest"); |
| auto MaybeCsts = ConstantFoldCTLZ(SrcOps[0].getReg(), *getMRI()); |
| if (!MaybeCsts) |
| break; |
| if (MaybeCsts->size() == 1) |
| return buildConstant(DstOps[0], (*MaybeCsts)[0]); |
| // This was a vector constant. Build a G_BUILD_VECTOR for them. |
| SmallVector<Register> ConstantRegs; |
| LLT VecTy = DstOps[0].getLLTTy(*getMRI()); |
| for (unsigned Cst : *MaybeCsts) |
| ConstantRegs.emplace_back( |
| buildConstant(VecTy.getScalarType(), Cst).getReg(0)); |
| return buildBuildVector(DstOps[0], ConstantRegs); |
| } |
| } |
| bool CanCopy = checkCopyToDefsPossible(DstOps); |
| if (!canPerformCSEForOpc(Opc)) |
| return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag); |
| // If we can CSE this instruction, but involves generating copies to multiple |
| // regs, give up. This frequently happens to UNMERGEs. |
| if (!CanCopy) { |
| auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag); |
| // CSEInfo would have tracked this instruction. Remove it from the temporary |
| // insts. |
| getCSEInfo()->handleRemoveInst(&*MIB); |
| return MIB; |
| } |
| FoldingSetNodeID ID; |
| GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); |
| void *InsertPos = nullptr; |
| profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder); |
| MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos); |
| if (MIB) { |
| // Handle generating copies here. |
| return generateCopiesIfRequired(DstOps, MIB); |
| } |
| // This instruction does not exist in the CSEInfo. Build it and CSE it. |
| MachineInstrBuilder NewMIB = |
| MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag); |
| return memoizeMI(NewMIB, InsertPos); |
| } |
| |
| MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res, |
| const ConstantInt &Val) { |
| constexpr unsigned Opc = TargetOpcode::G_CONSTANT; |
| if (!canPerformCSEForOpc(Opc)) |
| return MachineIRBuilder::buildConstant(Res, Val); |
| |
| // For vectors, CSE the element only for now. |
| LLT Ty = Res.getLLTTy(*getMRI()); |
| if (Ty.isVector()) |
| return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val)); |
| |
| FoldingSetNodeID ID; |
| GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); |
| void *InsertPos = nullptr; |
| profileMBBOpcode(ProfBuilder, Opc); |
| profileDstOp(Res, ProfBuilder); |
| ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val)); |
| MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos); |
| if (MIB) { |
| // Handle generating copies here. |
| return generateCopiesIfRequired({Res}, MIB); |
| } |
| |
| MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val); |
| return memoizeMI(NewMIB, InsertPos); |
| } |
| |
| MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res, |
| const ConstantFP &Val) { |
| constexpr unsigned Opc = TargetOpcode::G_FCONSTANT; |
| if (!canPerformCSEForOpc(Opc)) |
| return MachineIRBuilder::buildFConstant(Res, Val); |
| |
| // For vectors, CSE the element only for now. |
| LLT Ty = Res.getLLTTy(*getMRI()); |
| if (Ty.isVector()) |
| return buildSplatVector(Res, buildFConstant(Ty.getElementType(), Val)); |
| |
| FoldingSetNodeID ID; |
| GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); |
| void *InsertPos = nullptr; |
| profileMBBOpcode(ProfBuilder, Opc); |
| profileDstOp(Res, ProfBuilder); |
| ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val)); |
| MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos); |
| if (MIB) { |
| // Handle generating copies here. |
| return generateCopiesIfRequired({Res}, MIB); |
| } |
| MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val); |
| return memoizeMI(NewMIB, InsertPos); |
| } |