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"
13 #include "llvm/InitializePasses.h"
15 #define DEBUG_TYPE "cseinfo"
18 char llvm::GISelCSEAnalysisWrapperPass::ID = 0;
19 GISelCSEAnalysisWrapperPass::GISelCSEAnalysisWrapperPass()
20 : MachineFunctionPass(ID) {
21 initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry());
23 INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
24 "Analysis containing CSE Info", false, true)
25 INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
26 "Analysis containing CSE Info", false, true)
28 /// -------- UniqueMachineInstr -------------//
30 void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {
31 GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
33 /// -----------------------------------------
35 /// --------- CSEConfigFull ---------- ///
36 bool CSEConfigFull::shouldCSEOpc(unsigned Opc) {
40 case TargetOpcode::G_ADD:
41 case TargetOpcode::G_AND:
42 case TargetOpcode::G_ASHR:
43 case TargetOpcode::G_LSHR:
44 case TargetOpcode::G_MUL:
45 case TargetOpcode::G_OR:
46 case TargetOpcode::G_SHL:
47 case TargetOpcode::G_SUB:
48 case TargetOpcode::G_XOR:
49 case TargetOpcode::G_UDIV:
50 case TargetOpcode::G_SDIV:
51 case TargetOpcode::G_UREM:
52 case TargetOpcode::G_SREM:
53 case TargetOpcode::G_CONSTANT:
54 case TargetOpcode::G_FCONSTANT:
55 case TargetOpcode::G_IMPLICIT_DEF:
56 case TargetOpcode::G_ZEXT:
57 case TargetOpcode::G_SEXT:
58 case TargetOpcode::G_ANYEXT:
59 case TargetOpcode::G_UNMERGE_VALUES:
60 case TargetOpcode::G_TRUNC:
61 case TargetOpcode::G_PTR_ADD:
67 bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
68 return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_IMPLICIT_DEF;
71 std::unique_ptr<CSEConfigBase>
72 llvm::getStandardCSEConfigForOpt(CodeGenOpt::Level Level) {
73 std::unique_ptr<CSEConfigBase> Config;
74 if (Level == CodeGenOpt::None)
75 Config = std::make_unique<CSEConfigConstantOnly>();
77 Config = std::make_unique<CSEConfigFull>();
81 /// -----------------------------------------
83 /// -------- GISelCSEInfo -------------//
84 void GISelCSEInfo::setMF(MachineFunction &MF) {
86 this->MRI = &MF.getRegInfo();
89 GISelCSEInfo::~GISelCSEInfo() {}
91 bool GISelCSEInfo::isUniqueMachineInstValid(
92 const UniqueMachineInstr &UMI) const {
93 // Should we check here and assert that the instruction has been fully
95 // FIXME: Any other checks required to be done here? Remove this method if
100 void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {
101 bool Removed = CSEMap.RemoveNode(UMI);
103 assert(Removed && "Invalidation called on invalid UMI");
104 // FIXME: Should UMI be deallocated/destroyed?
107 UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,
108 MachineBasicBlock *MBB,
110 auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
112 if (!isUniqueMachineInstValid(*Node)) {
113 invalidateUniqueMachineInstr(Node);
117 if (Node->MI->getParent() != MBB)
123 void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {
124 handleRecordedInsts();
126 UniqueMachineInstr *MaybeNewNode = UMI;
128 CSEMap.InsertNode(UMI, InsertPos);
130 MaybeNewNode = CSEMap.GetOrInsertNode(UMI);
131 if (MaybeNewNode != UMI) {
132 // A similar node exists in the folding set. Let's ignore this one.
135 assert(InstrMapping.count(UMI->MI) == 0 &&
136 "This instruction should not be in the map");
137 InstrMapping[UMI->MI] = MaybeNewNode;
140 UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {
141 assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");
142 auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);
146 void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) {
148 // If it exists in temporary insts, remove it.
149 TemporaryInsts.remove(MI);
150 auto *Node = getUniqueInstrForMI(MI);
151 insertNode(Node, InsertPos);
154 MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
155 MachineBasicBlock *MBB,
157 handleRecordedInsts();
158 if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) {
159 LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;);
160 return const_cast<MachineInstr *>(Inst->MI);
165 void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
167 if (OpcodeHitTable.count(Opc))
168 OpcodeHitTable[Opc] += 1;
170 OpcodeHitTable[Opc] = 1;
175 void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) {
176 if (shouldCSE(MI->getOpcode())) {
177 TemporaryInsts.insert(MI);
178 LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
182 void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) {
183 assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
184 auto *UMI = InstrMapping.lookup(MI);
185 LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);
187 // Invalidate this MI.
188 invalidateUniqueMachineInstr(UMI);
189 InstrMapping.erase(MI);
191 /// Now insert the new instruction.
193 /// We'll reuse the same UniqueMachineInstr to avoid the new
195 *UMI = UniqueMachineInstr(MI);
196 insertNode(UMI, nullptr);
198 /// This is a new instruction. Allocate a new UniqueMachineInstr and
204 void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) {
205 if (auto *UMI = InstrMapping.lookup(MI)) {
206 invalidateUniqueMachineInstr(UMI);
207 InstrMapping.erase(MI);
209 TemporaryInsts.remove(MI);
212 void GISelCSEInfo::handleRecordedInsts() {
213 while (!TemporaryInsts.empty()) {
214 auto *MI = TemporaryInsts.pop_back_val();
215 handleRecordedInst(MI);
219 bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
220 assert(CSEOpt.get() && "CSEConfig not set");
221 return CSEOpt->shouldCSEOpc(Opc);
224 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
225 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
226 void GISelCSEInfo::changingInstr(MachineInstr &MI) {
227 // For now, perform erase, followed by insert.
231 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
233 void GISelCSEInfo::analyze(MachineFunction &MF) {
235 for (auto &MBB : MF) {
238 for (MachineInstr &MI : MBB) {
239 if (!shouldCSE(MI.getOpcode()))
241 LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
247 void GISelCSEInfo::releaseMemory() {
250 InstrMapping.clear();
251 UniqueInstrAllocator.Reset();
252 TemporaryInsts.clear();
257 OpcodeHitTable.clear();
261 Error GISelCSEInfo::verify() {
263 handleRecordedInsts();
264 // For each instruction in map from MI -> UMI,
265 // Profile(MI) and make sure UMI is found for that profile.
266 for (auto &It : InstrMapping) {
267 FoldingSetNodeID TmpID;
268 GISelInstProfileBuilder(TmpID, *MRI).addNodeID(It.first);
270 UniqueMachineInstr *FoundNode =
271 CSEMap.FindNodeOrInsertPos(TmpID, InsertPos);
272 if (FoundNode != It.second)
273 return createStringError(std::errc::not_supported,
274 "CSEMap mismatch, InstrMapping has MIs without "
275 "corresponding Nodes in CSEMap");
278 // For every node in the CSEMap, make sure that the InstrMapping
280 for (auto It = CSEMap.begin(), End = CSEMap.end(); It != End; ++It) {
281 const UniqueMachineInstr &UMI = *It;
282 if (!InstrMapping.count(UMI.MI))
283 return createStringError(std::errc::not_supported,
284 "Node in CSE without InstrMapping", UMI.MI);
286 if (InstrMapping[UMI.MI] != &UMI)
287 return createStringError(std::make_error_code(std::errc::not_supported),
288 "Mismatch in CSE mapping");
291 return Error::success();
294 void GISelCSEInfo::print() {
295 LLVM_DEBUG(for (auto &It
297 dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
301 /// -----------------------------------------
302 // ---- Profiling methods for FoldingSetNode --- //
303 const GISelInstProfileBuilder &
304 GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const {
305 addNodeIDMBB(MI->getParent());
306 addNodeIDOpcode(MI->getOpcode());
307 for (auto &Op : MI->operands())
308 addNodeIDMachineOperand(Op);
309 addNodeIDFlag(MI->getFlags());
313 const GISelInstProfileBuilder &
314 GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
319 const GISelInstProfileBuilder &
320 GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const {
321 uint64_t Val = Ty.getUniqueRAWLLTData();
326 const GISelInstProfileBuilder &
327 GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
332 const GISelInstProfileBuilder &
333 GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
338 const GISelInstProfileBuilder &
339 GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
344 const GISelInstProfileBuilder &
345 GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const {
350 const GISelInstProfileBuilder &
351 GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const {
352 addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
356 const GISelInstProfileBuilder &
357 GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
362 const GISelInstProfileBuilder &
363 GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
369 const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
370 const MachineOperand &MO) const {
372 Register Reg = MO.getReg();
374 addNodeIDRegNum(Reg);
375 LLT Ty = MRI.getType(Reg);
377 addNodeIDRegType(Ty);
379 if (const RegClassOrRegBank &RCOrRB = MRI.getRegClassOrRegBank(Reg)) {
380 if (const auto *RB = RCOrRB.dyn_cast<const RegisterBank *>())
381 addNodeIDRegType(RB);
382 else if (const auto *RC = RCOrRB.dyn_cast<const TargetRegisterClass *>())
383 addNodeIDRegType(RC);
386 assert(!MO.isImplicit() && "Unhandled case");
387 } else if (MO.isImm())
388 ID.AddInteger(MO.getImm());
389 else if (MO.isCImm())
390 ID.AddPointer(MO.getCImm());
391 else if (MO.isFPImm())
392 ID.AddPointer(MO.getFPImm());
393 else if (MO.isPredicate())
394 ID.AddInteger(MO.getPredicate());
396 llvm_unreachable("Unhandled operand type");
397 // Handle other types
402 GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,
404 if (!AlreadyComputed || Recompute) {
405 Info.releaseMemory();
406 Info.setCSEConfig(std::move(CSEOpt));
408 AlreadyComputed = true;
412 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
413 AU.setPreservesAll();
414 MachineFunctionPass::getAnalysisUsage(AU);
417 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {