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