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