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