1 //===- CSEInfo.cpp ------------------------------===//
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
7 //===----------------------------------------------------------------------===//
10 //===----------------------------------------------------------------------===//
11 #include "llvm/CodeGen/GlobalISel/CSEInfo.h"
12 #include "llvm/CodeGen/MachineRegisterInfo.h"
14 #define DEBUG_TYPE "cseinfo"
17 char llvm::GISelCSEAnalysisWrapperPass::ID = 0;
18 INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
19 "Analysis containing CSE Info", false, true)
20 INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
21 "Analysis containing CSE Info", false, true)
23 /// -------- UniqueMachineInstr -------------//
25 void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {
26 GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
28 /// -----------------------------------------
30 /// --------- CSEConfigFull ---------- ///
31 bool CSEConfigFull::shouldCSEOpc(unsigned Opc) {
35 case TargetOpcode::G_ADD:
36 case TargetOpcode::G_AND:
37 case TargetOpcode::G_ASHR:
38 case TargetOpcode::G_LSHR:
39 case TargetOpcode::G_MUL:
40 case TargetOpcode::G_OR:
41 case TargetOpcode::G_SHL:
42 case TargetOpcode::G_SUB:
43 case TargetOpcode::G_XOR:
44 case TargetOpcode::G_UDIV:
45 case TargetOpcode::G_SDIV:
46 case TargetOpcode::G_UREM:
47 case TargetOpcode::G_SREM:
48 case TargetOpcode::G_CONSTANT:
49 case TargetOpcode::G_FCONSTANT:
50 case TargetOpcode::G_ZEXT:
51 case TargetOpcode::G_SEXT:
52 case TargetOpcode::G_ANYEXT:
53 case TargetOpcode::G_UNMERGE_VALUES:
54 case TargetOpcode::G_TRUNC:
60 bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
61 return Opc == TargetOpcode::G_CONSTANT;
64 std::unique_ptr<CSEConfigBase>
65 llvm::getStandardCSEConfigForOpt(CodeGenOpt::Level Level) {
66 std::unique_ptr<CSEConfigBase> Config;
67 if (Level == CodeGenOpt::None)
68 Config = make_unique<CSEConfigConstantOnly>();
70 Config = make_unique<CSEConfigFull>();
74 /// -----------------------------------------
76 /// -------- GISelCSEInfo -------------//
77 void GISelCSEInfo::setMF(MachineFunction &MF) {
79 this->MRI = &MF.getRegInfo();
82 GISelCSEInfo::~GISelCSEInfo() {}
84 bool GISelCSEInfo::isUniqueMachineInstValid(
85 const UniqueMachineInstr &UMI) const {
86 // Should we check here and assert that the instruction has been fully
88 // FIXME: Any other checks required to be done here? Remove this method if
93 void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {
94 bool Removed = CSEMap.RemoveNode(UMI);
96 assert(Removed && "Invalidation called on invalid UMI");
97 // FIXME: Should UMI be deallocated/destroyed?
100 UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,
101 MachineBasicBlock *MBB,
103 auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
105 if (!isUniqueMachineInstValid(*Node)) {
106 invalidateUniqueMachineInstr(Node);
110 if (Node->MI->getParent() != MBB)
116 void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {
117 handleRecordedInsts();
119 UniqueMachineInstr *MaybeNewNode = UMI;
121 CSEMap.InsertNode(UMI, InsertPos);
123 MaybeNewNode = CSEMap.GetOrInsertNode(UMI);
124 if (MaybeNewNode != UMI) {
125 // A similar node exists in the folding set. Let's ignore this one.
128 assert(InstrMapping.count(UMI->MI) == 0 &&
129 "This instruction should not be in the map");
130 InstrMapping[UMI->MI] = MaybeNewNode;
133 UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {
134 assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");
135 auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);
139 void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) {
141 // If it exists in temporary insts, remove it.
142 TemporaryInsts.remove(MI);
143 auto *Node = getUniqueInstrForMI(MI);
144 insertNode(Node, InsertPos);
147 MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
148 MachineBasicBlock *MBB,
150 handleRecordedInsts();
151 if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) {
152 LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;);
153 return const_cast<MachineInstr *>(Inst->MI);
158 void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
160 if (OpcodeHitTable.count(Opc))
161 OpcodeHitTable[Opc] += 1;
163 OpcodeHitTable[Opc] = 1;
168 void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) {
169 if (shouldCSE(MI->getOpcode())) {
170 TemporaryInsts.insert(MI);
171 LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
175 void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) {
176 assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
177 auto *UMI = InstrMapping.lookup(MI);
178 LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);
180 // Invalidate this MI.
181 invalidateUniqueMachineInstr(UMI);
182 InstrMapping.erase(MI);
184 /// Now insert the new instruction.
186 /// We'll reuse the same UniqueMachineInstr to avoid the new
188 *UMI = UniqueMachineInstr(MI);
189 insertNode(UMI, nullptr);
191 /// This is a new instruction. Allocate a new UniqueMachineInstr and
197 void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) {
198 if (auto *UMI = InstrMapping.lookup(MI)) {
199 invalidateUniqueMachineInstr(UMI);
200 InstrMapping.erase(MI);
202 TemporaryInsts.remove(MI);
205 void GISelCSEInfo::handleRecordedInsts() {
206 while (!TemporaryInsts.empty()) {
207 auto *MI = TemporaryInsts.pop_back_val();
208 handleRecordedInst(MI);
212 bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
213 // Only GISel opcodes are CSEable
214 if (!isPreISelGenericOpcode(Opc))
216 assert(CSEOpt.get() && "CSEConfig not set");
217 return CSEOpt->shouldCSEOpc(Opc);
220 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
221 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
222 void GISelCSEInfo::changingInstr(MachineInstr &MI) {
223 // For now, perform erase, followed by insert.
227 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
229 void GISelCSEInfo::analyze(MachineFunction &MF) {
231 for (auto &MBB : MF) {
234 for (MachineInstr &MI : MBB) {
235 if (!shouldCSE(MI.getOpcode()))
237 LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
243 void GISelCSEInfo::releaseMemory() {
246 InstrMapping.clear();
247 UniqueInstrAllocator.Reset();
248 TemporaryInsts.clear();
253 OpcodeHitTable.clear();
257 void GISelCSEInfo::print() {
258 LLVM_DEBUG(for (auto &It
260 dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
264 /// -----------------------------------------
265 // ---- Profiling methods for FoldingSetNode --- //
266 const GISelInstProfileBuilder &
267 GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const {
268 addNodeIDMBB(MI->getParent());
269 addNodeIDOpcode(MI->getOpcode());
270 for (auto &Op : MI->operands())
271 addNodeIDMachineOperand(Op);
272 addNodeIDFlag(MI->getFlags());
276 const GISelInstProfileBuilder &
277 GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
282 const GISelInstProfileBuilder &
283 GISelInstProfileBuilder::addNodeIDRegType(const LLT &Ty) const {
284 uint64_t Val = Ty.getUniqueRAWLLTData();
289 const GISelInstProfileBuilder &
290 GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
295 const GISelInstProfileBuilder &
296 GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
301 const GISelInstProfileBuilder &
302 GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
307 const GISelInstProfileBuilder &
308 GISelInstProfileBuilder::addNodeIDRegNum(unsigned Reg) const {
313 const GISelInstProfileBuilder &
314 GISelInstProfileBuilder::addNodeIDRegType(const unsigned Reg) const {
315 addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
319 const GISelInstProfileBuilder &
320 GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
325 const GISelInstProfileBuilder &
326 GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
332 const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
333 const MachineOperand &MO) const {
335 unsigned Reg = MO.getReg();
337 addNodeIDRegNum(Reg);
338 LLT Ty = MRI.getType(Reg);
340 addNodeIDRegType(Ty);
341 auto *RB = MRI.getRegBankOrNull(Reg);
343 addNodeIDRegType(RB);
344 auto *RC = MRI.getRegClassOrNull(Reg);
346 addNodeIDRegType(RC);
347 assert(!MO.isImplicit() && "Unhandled case");
348 } else if (MO.isImm())
349 ID.AddInteger(MO.getImm());
350 else if (MO.isCImm())
351 ID.AddPointer(MO.getCImm());
352 else if (MO.isFPImm())
353 ID.AddPointer(MO.getFPImm());
354 else if (MO.isPredicate())
355 ID.AddInteger(MO.getPredicate());
357 llvm_unreachable("Unhandled operand type");
358 // Handle other types
363 GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,
365 if (!AlreadyComputed || Recompute) {
366 Info.setCSEConfig(std::move(CSEOpt));
368 AlreadyComputed = true;
372 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
373 AU.setPreservesAll();
374 MachineFunctionPass::getAnalysisUsage(AU);
377 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {