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