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