462 lines · cpp
1//===- CSEInfo.cpp ------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9//10//===----------------------------------------------------------------------===//11#include "llvm/CodeGen/GlobalISel/CSEInfo.h"12#include "llvm/CodeGen/MachineRegisterInfo.h"13#include "llvm/InitializePasses.h"14#include "llvm/Support/Error.h"15 16#define DEBUG_TYPE "cseinfo"17 18using namespace llvm;19char llvm::GISelCSEAnalysisWrapperPass::ID = 0;20GISelCSEAnalysisWrapperPass::GISelCSEAnalysisWrapperPass()21 : MachineFunctionPass(ID) {22 initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry());23}24INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,25 "Analysis containing CSE Info", false, true)26INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,27 "Analysis containing CSE Info", false, true)28 29/// -------- UniqueMachineInstr -------------//30 31void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {32 GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);33}34/// -----------------------------------------35 36/// --------- CSEConfigFull ---------- ///37bool CSEConfigFull::shouldCSEOpc(unsigned Opc) {38 switch (Opc) {39 default:40 break;41 case TargetOpcode::G_ADD:42 case TargetOpcode::G_AND:43 case TargetOpcode::G_ASHR:44 case TargetOpcode::G_LSHR:45 case TargetOpcode::G_MUL:46 case TargetOpcode::G_OR:47 case TargetOpcode::G_SHL:48 case TargetOpcode::G_SUB:49 case TargetOpcode::G_XOR:50 case TargetOpcode::G_UDIV:51 case TargetOpcode::G_SDIV:52 case TargetOpcode::G_UREM:53 case TargetOpcode::G_SREM:54 case TargetOpcode::G_CONSTANT:55 case TargetOpcode::G_FCONSTANT:56 case TargetOpcode::G_IMPLICIT_DEF:57 case TargetOpcode::G_ZEXT:58 case TargetOpcode::G_SEXT:59 case TargetOpcode::G_ANYEXT:60 case TargetOpcode::G_UNMERGE_VALUES:61 case TargetOpcode::G_TRUNC:62 case TargetOpcode::G_PTR_ADD:63 case TargetOpcode::G_EXTRACT:64 case TargetOpcode::G_SELECT:65 case TargetOpcode::G_BUILD_VECTOR:66 case TargetOpcode::G_BUILD_VECTOR_TRUNC:67 case TargetOpcode::G_SEXT_INREG:68 case TargetOpcode::G_FADD:69 case TargetOpcode::G_FSUB:70 case TargetOpcode::G_FMUL:71 case TargetOpcode::G_FDIV:72 case TargetOpcode::G_FABS:73 // TODO: support G_FNEG.74 case TargetOpcode::G_FMAXNUM:75 case TargetOpcode::G_FMINNUM:76 case TargetOpcode::G_FMAXNUM_IEEE:77 case TargetOpcode::G_FMINNUM_IEEE:78 return true;79 }80 return false;81}82 83bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {84 return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_FCONSTANT ||85 Opc == TargetOpcode::G_IMPLICIT_DEF;86}87 88std::unique_ptr<CSEConfigBase>89llvm::getStandardCSEConfigForOpt(CodeGenOptLevel Level) {90 std::unique_ptr<CSEConfigBase> Config;91 if (Level == CodeGenOptLevel::None)92 Config = std::make_unique<CSEConfigConstantOnly>();93 else94 Config = std::make_unique<CSEConfigFull>();95 return Config;96}97 98/// -----------------------------------------99 100/// -------- GISelCSEInfo -------------//101void GISelCSEInfo::setMF(MachineFunction &MF) {102 this->MF = &MF;103 this->MRI = &MF.getRegInfo();104}105 106GISelCSEInfo::~GISelCSEInfo() = default;107 108bool GISelCSEInfo::isUniqueMachineInstValid(109 const UniqueMachineInstr &UMI) const {110 // Should we check here and assert that the instruction has been fully111 // constructed?112 // FIXME: Any other checks required to be done here? Remove this method if113 // none.114 return true;115}116 117void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {118 bool Removed = CSEMap.RemoveNode(UMI);119 (void)Removed;120 assert(Removed && "Invalidation called on invalid UMI");121 // FIXME: Should UMI be deallocated/destroyed?122}123 124UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,125 MachineBasicBlock *MBB,126 void *&InsertPos) {127 auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);128 if (Node) {129 if (!isUniqueMachineInstValid(*Node)) {130 invalidateUniqueMachineInstr(Node);131 return nullptr;132 }133 134 if (Node->MI->getParent() != MBB)135 return nullptr;136 }137 return Node;138}139 140void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {141 handleRecordedInsts();142 assert(UMI);143 UniqueMachineInstr *MaybeNewNode = UMI;144 if (InsertPos)145 CSEMap.InsertNode(UMI, InsertPos);146 else147 MaybeNewNode = CSEMap.GetOrInsertNode(UMI);148 if (MaybeNewNode != UMI) {149 // A similar node exists in the folding set. Let's ignore this one.150 return;151 }152 assert(InstrMapping.count(UMI->MI) == 0 &&153 "This instruction should not be in the map");154 InstrMapping[UMI->MI] = MaybeNewNode;155}156 157UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {158 assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");159 auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);160 return Node;161}162 163void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) {164 assert(MI);165 // If it exists in temporary insts, remove it.166 TemporaryInsts.remove(MI);167 auto *Node = getUniqueInstrForMI(MI);168 insertNode(Node, InsertPos);169}170 171MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,172 MachineBasicBlock *MBB,173 void *&InsertPos) {174 handleRecordedInsts();175 if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) {176 LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI);177 return const_cast<MachineInstr *>(Inst->MI);178 }179 return nullptr;180}181 182void GISelCSEInfo::countOpcodeHit(unsigned Opc) {183#ifndef NDEBUG184 ++OpcodeHitTable[Opc];185#endif186 // Else do nothing.187}188 189void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) {190 if (shouldCSE(MI->getOpcode())) {191 TemporaryInsts.insert(MI);192 LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);193 }194}195 196void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) {197 assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");198 auto *UMI = InstrMapping.lookup(MI);199 LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);200 if (UMI) {201 // Invalidate this MI.202 invalidateUniqueMachineInstr(UMI);203 InstrMapping.erase(MI);204 }205 /// Now insert the new instruction.206 if (UMI) {207 /// We'll reuse the same UniqueMachineInstr to avoid the new208 /// allocation.209 *UMI = UniqueMachineInstr(MI);210 insertNode(UMI, nullptr);211 } else {212 /// This is a new instruction. Allocate a new UniqueMachineInstr and213 /// Insert.214 insertInstr(MI);215 }216}217 218void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) {219 if (auto *UMI = InstrMapping.lookup(MI)) {220 invalidateUniqueMachineInstr(UMI);221 InstrMapping.erase(MI);222 }223 TemporaryInsts.remove(MI);224}225 226void GISelCSEInfo::handleRecordedInsts() {227 if (HandlingRecordedInstrs)228 return;229 HandlingRecordedInstrs = true;230 while (!TemporaryInsts.empty()) {231 auto *MI = TemporaryInsts.pop_back_val();232 handleRecordedInst(MI);233 }234 HandlingRecordedInstrs = false;235}236 237bool GISelCSEInfo::shouldCSE(unsigned Opc) const {238 assert(CSEOpt.get() && "CSEConfig not set");239 return CSEOpt->shouldCSEOpc(Opc);240}241 242void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }243void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }244void GISelCSEInfo::changingInstr(MachineInstr &MI) {245 // For now, perform erase, followed by insert.246 erasingInstr(MI);247 createdInstr(MI);248}249void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }250 251void GISelCSEInfo::analyze(MachineFunction &MF) {252 setMF(MF);253 for (auto &MBB : MF) {254 for (MachineInstr &MI : MBB) {255 if (!shouldCSE(MI.getOpcode()))256 continue;257 LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);258 insertInstr(&MI);259 }260 }261}262 263void GISelCSEInfo::releaseMemory() {264 print();265 CSEMap.clear();266 InstrMapping.clear();267 UniqueInstrAllocator.Reset();268 TemporaryInsts.clear();269 CSEOpt.reset();270 MRI = nullptr;271 MF = nullptr;272#ifndef NDEBUG273 OpcodeHitTable.clear();274#endif275}276 277#ifndef NDEBUG278static const char *stringify(const MachineInstr *MI, std::string &S) {279 raw_string_ostream OS(S);280 OS << *MI;281 return OS.str().c_str();282}283#endif284 285Error GISelCSEInfo::verify() {286#ifndef NDEBUG287 std::string S1, S2;288 handleRecordedInsts();289 // For each instruction in map from MI -> UMI,290 // Profile(MI) and make sure UMI is found for that profile.291 for (auto &It : InstrMapping) {292 FoldingSetNodeID TmpID;293 GISelInstProfileBuilder(TmpID, *MRI).addNodeID(It.first);294 void *InsertPos;295 UniqueMachineInstr *FoundNode =296 CSEMap.FindNodeOrInsertPos(TmpID, InsertPos);297 if (FoundNode != It.second)298 return createStringError(std::errc::not_supported,299 "CSEMap mismatch, InstrMapping has MIs without "300 "corresponding Nodes in CSEMap:\n%s",301 stringify(It.second->MI, S1));302 }303 304 // For every node in the CSEMap, make sure that the InstrMapping305 // points to it.306 for (const UniqueMachineInstr &UMI : CSEMap) {307 if (!InstrMapping.count(UMI.MI))308 return createStringError(std::errc::not_supported,309 "Node in CSE without InstrMapping:\n%s",310 stringify(UMI.MI, S1));311 312 if (InstrMapping[UMI.MI] != &UMI)313 return createStringError(std::make_error_code(std::errc::not_supported),314 "Mismatch in CSE mapping:\n%s\n%s",315 stringify(InstrMapping[UMI.MI]->MI, S1),316 stringify(UMI.MI, S2));317 }318#endif319 return Error::success();320}321 322void GISelCSEInfo::print() {323 LLVM_DEBUG({324 for (auto &It : OpcodeHitTable)325 dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second326 << "\n";327 });328}329/// -----------------------------------------330// ---- Profiling methods for FoldingSetNode --- //331const GISelInstProfileBuilder &332GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const {333 addNodeIDMBB(MI->getParent());334 addNodeIDOpcode(MI->getOpcode());335 for (const auto &Op : MI->operands())336 addNodeIDMachineOperand(Op);337 addNodeIDFlag(MI->getFlags());338 return *this;339}340 341const GISelInstProfileBuilder &342GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {343 ID.AddInteger(Opc);344 return *this;345}346 347const GISelInstProfileBuilder &348GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const {349 uint64_t Val = Ty.getUniqueRAWLLTData();350 ID.AddInteger(Val);351 return *this;352}353 354const GISelInstProfileBuilder &355GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {356 ID.AddPointer(RC);357 return *this;358}359 360const GISelInstProfileBuilder &361GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {362 ID.AddPointer(RB);363 return *this;364}365 366const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDRegType(367 MachineRegisterInfo::VRegAttrs Attrs) const {368 addNodeIDRegType(Attrs.Ty);369 370 const RegClassOrRegBank &RCOrRB = Attrs.RCOrRB;371 if (RCOrRB) {372 if (const auto *RB = dyn_cast_if_present<const RegisterBank *>(RCOrRB))373 addNodeIDRegType(RB);374 else375 addNodeIDRegType(cast<const TargetRegisterClass *>(RCOrRB));376 }377 return *this;378}379 380const GISelInstProfileBuilder &381GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {382 ID.AddInteger(Imm);383 return *this;384}385 386const GISelInstProfileBuilder &387GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const {388 ID.AddInteger(Reg.id());389 return *this;390}391 392const GISelInstProfileBuilder &393GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const {394 addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));395 return *this;396}397 398const GISelInstProfileBuilder &399GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {400 ID.AddPointer(MBB);401 return *this;402}403 404const GISelInstProfileBuilder &405GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {406 if (Flag)407 ID.AddInteger(Flag);408 return *this;409}410 411const GISelInstProfileBuilder &412GISelInstProfileBuilder::addNodeIDReg(Register Reg) const {413 addNodeIDRegType(MRI.getVRegAttrs(Reg));414 return *this;415}416 417const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(418 const MachineOperand &MO) const {419 if (MO.isReg()) {420 Register Reg = MO.getReg();421 if (!MO.isDef())422 addNodeIDRegNum(Reg);423 424 // Profile the register properties.425 addNodeIDReg(Reg);426 assert(!MO.isImplicit() && "Unhandled case");427 } else if (MO.isImm())428 ID.AddInteger(MO.getImm());429 else if (MO.isCImm())430 ID.AddPointer(MO.getCImm());431 else if (MO.isFPImm())432 ID.AddPointer(MO.getFPImm());433 else if (MO.isPredicate())434 ID.AddInteger(MO.getPredicate());435 else436 llvm_unreachable("Unhandled operand type");437 // Handle other types438 return *this;439}440 441GISelCSEInfo &442GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,443 bool Recompute) {444 if (!AlreadyComputed || Recompute) {445 Info.releaseMemory();446 Info.setCSEConfig(std::move(CSEOpt));447 Info.analyze(*MF);448 AlreadyComputed = true;449 }450 return Info;451}452void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {453 AU.setPreservesAll();454 MachineFunctionPass::getAnalysisUsage(AU);455}456 457bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {458 releaseMemory();459 Wrapper.setMF(MF);460 return false;461}462