385 lines · cpp
1//===-- llvm/CodeGen/GlobalISel/Legalizer.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/// \file This file implements the LegalizerHelper class to legalize individual10/// instructions and the LegalizePass wrapper pass for the primary11/// legalization.12//13//===----------------------------------------------------------------------===//14 15#include "llvm/CodeGen/GlobalISel/Legalizer.h"16#include "llvm/ADT/PostOrderIterator.h"17#include "llvm/Analysis/OptimizationRemarkEmitter.h"18#include "llvm/CodeGen/GlobalISel/CSEInfo.h"19#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"20#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"21#include "llvm/CodeGen/GlobalISel/GISelValueTracking.h"22#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"23#include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"24#include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"25#include "llvm/CodeGen/GlobalISel/LostDebugLocObserver.h"26#include "llvm/CodeGen/GlobalISel/Utils.h"27#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"28#include "llvm/CodeGen/TargetPassConfig.h"29#include "llvm/CodeGen/TargetSubtargetInfo.h"30#include "llvm/Support/Debug.h"31#include "llvm/Support/Error.h"32 33#define DEBUG_TYPE "legalizer"34 35using namespace llvm;36 37static cl::opt<bool>38 EnableCSEInLegalizer("enable-cse-in-legalizer",39 cl::desc("Should enable CSE in Legalizer"),40 cl::Optional, cl::init(false));41 42// This is a temporary hack, should be removed soon.43static cl::opt<bool> AllowGInsertAsArtifact(44 "allow-ginsert-as-artifact",45 cl::desc("Allow G_INSERT to be considered an artifact. Hack around AMDGPU "46 "test infinite loops."),47 cl::Optional, cl::init(true));48 49enum class DebugLocVerifyLevel {50 None,51 Legalizations,52 LegalizationsAndArtifactCombiners,53};54#ifndef NDEBUG55static cl::opt<DebugLocVerifyLevel> VerifyDebugLocs(56 "verify-legalizer-debug-locs",57 cl::desc("Verify that debug locations are handled"),58 cl::values(59 clEnumValN(DebugLocVerifyLevel::None, "none", "No verification"),60 clEnumValN(DebugLocVerifyLevel::Legalizations, "legalizations",61 "Verify legalizations"),62 clEnumValN(DebugLocVerifyLevel::LegalizationsAndArtifactCombiners,63 "legalizations+artifactcombiners",64 "Verify legalizations and artifact combines")),65 cl::init(DebugLocVerifyLevel::Legalizations));66#else67// Always disable it for release builds by preventing the observer from being68// installed.69static const DebugLocVerifyLevel VerifyDebugLocs = DebugLocVerifyLevel::None;70#endif71 72char Legalizer::ID = 0;73INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,74 "Legalize the Machine IR a function's Machine IR", false,75 false)76INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)77INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)78INITIALIZE_PASS_DEPENDENCY(GISelValueTrackingAnalysisLegacy)79INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,80 "Legalize the Machine IR a function's Machine IR", false,81 false)82 83Legalizer::Legalizer() : MachineFunctionPass(ID) { }84 85void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {86 AU.addRequired<TargetPassConfig>();87 AU.addRequired<GISelCSEAnalysisWrapperPass>();88 AU.addPreserved<GISelCSEAnalysisWrapperPass>();89 AU.addRequired<GISelValueTrackingAnalysisLegacy>();90 AU.addPreserved<GISelValueTrackingAnalysisLegacy>();91 getSelectionDAGFallbackAnalysisUsage(AU);92 MachineFunctionPass::getAnalysisUsage(AU);93}94 95void Legalizer::init(MachineFunction &MF) {96}97 98static bool isArtifact(const MachineInstr &MI) {99 switch (MI.getOpcode()) {100 default:101 return false;102 case TargetOpcode::G_TRUNC:103 case TargetOpcode::G_ZEXT:104 case TargetOpcode::G_ANYEXT:105 case TargetOpcode::G_SEXT:106 case TargetOpcode::G_MERGE_VALUES:107 case TargetOpcode::G_UNMERGE_VALUES:108 case TargetOpcode::G_CONCAT_VECTORS:109 case TargetOpcode::G_BUILD_VECTOR:110 case TargetOpcode::G_EXTRACT:111 return true;112 case TargetOpcode::G_INSERT:113 return AllowGInsertAsArtifact;114 }115}116using InstListTy = GISelWorkList<256>;117using ArtifactListTy = GISelWorkList<128>;118 119namespace {120class LegalizerWorkListManager : public GISelChangeObserver {121 InstListTy &InstList;122 ArtifactListTy &ArtifactList;123#ifndef NDEBUG124 SmallVector<MachineInstr *, 4> NewMIs;125#endif126 127public:128 LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)129 : InstList(Insts), ArtifactList(Arts) {}130 131 void createdOrChangedInstr(MachineInstr &MI) {132 // Only legalize pre-isel generic instructions.133 // Legalization process could generate Target specific pseudo134 // instructions with generic types. Don't record them135 if (isPreISelGenericOpcode(MI.getOpcode())) {136 if (isArtifact(MI))137 ArtifactList.insert(&MI);138 else139 InstList.insert(&MI);140 }141 }142 143 void createdInstr(MachineInstr &MI) override {144 LLVM_DEBUG(NewMIs.push_back(&MI));145 createdOrChangedInstr(MI);146 }147 148 void printNewInstrs() {149 LLVM_DEBUG({150 for (const auto *MI : NewMIs)151 dbgs() << ".. .. New MI: " << *MI;152 NewMIs.clear();153 });154 }155 156 void erasingInstr(MachineInstr &MI) override {157 LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);158 InstList.remove(&MI);159 ArtifactList.remove(&MI);160 }161 162 void changingInstr(MachineInstr &MI) override {163 LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);164 }165 166 void changedInstr(MachineInstr &MI) override {167 // When insts change, we want to revisit them to legalize them again.168 // We'll consider them the same as created.169 LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);170 createdOrChangedInstr(MI);171 }172};173} // namespace174 175Legalizer::MFResult176Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,177 ArrayRef<GISelChangeObserver *> AuxObservers,178 LostDebugLocObserver &LocObserver,179 MachineIRBuilder &MIRBuilder,180 GISelValueTracking *VT) {181 MIRBuilder.setMF(MF);182 MachineRegisterInfo &MRI = MF.getRegInfo();183 184 // Populate worklists.185 InstListTy InstList;186 ArtifactListTy ArtifactList;187 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);188 // Perform legalization bottom up so we can DCE as we legalize.189 // Traverse BB in RPOT and within each basic block, add insts top down,190 // so when we pop_back_val in the legalization process, we traverse bottom-up.191 for (auto *MBB : RPOT) {192 if (MBB->empty())193 continue;194 for (MachineInstr &MI : *MBB) {195 // Only legalize pre-isel generic instructions: others don't have types196 // and are assumed to be legal.197 if (!isPreISelGenericOpcode(MI.getOpcode()))198 continue;199 if (isArtifact(MI))200 ArtifactList.deferred_insert(&MI);201 else202 InstList.deferred_insert(&MI);203 }204 }205 ArtifactList.finalize();206 InstList.finalize();207 208 // This observer keeps the worklists updated.209 LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);210 // We want both WorkListObserver as well as all the auxiliary observers (e.g.211 // CSEInfo) to observe all changes. Use the wrapper observer.212 GISelObserverWrapper WrapperObserver(&WorkListObserver);213 for (GISelChangeObserver *Observer : AuxObservers)214 WrapperObserver.addObserver(Observer);215 216 // Now install the observer as the delegate to MF.217 // This will keep all the observers notified about new insertions/deletions.218 RAIIMFObsDelInstaller Installer(MF, WrapperObserver);219 LegalizerHelper Helper(MF, LI, WrapperObserver, MIRBuilder, VT);220 LegalizationArtifactCombiner ArtCombiner(MIRBuilder, MRI, LI, VT);221 bool Changed = false;222 SmallVector<MachineInstr *, 128> RetryList;223 do {224 LLVM_DEBUG(dbgs() << "=== New Iteration ===\n");225 assert(RetryList.empty() && "Expected no instructions in RetryList");226 unsigned NumArtifacts = ArtifactList.size();227 while (!InstList.empty()) {228 MachineInstr &MI = *InstList.pop_back_val();229 assert(isPreISelGenericOpcode(MI.getOpcode()) &&230 "Expecting generic opcode");231 if (isTriviallyDead(MI, MRI)) {232 salvageDebugInfo(MRI, MI);233 eraseInstr(MI, MRI, &LocObserver);234 continue;235 }236 237 // Do the legalization for this instruction.238 auto Res = Helper.legalizeInstrStep(MI, LocObserver);239 // Error out if we couldn't legalize this instruction. We may want to240 // fall back to DAG ISel instead in the future.241 if (Res == LegalizerHelper::UnableToLegalize) {242 // Move illegal artifacts to RetryList instead of aborting because243 // legalizing InstList may generate artifacts that allow244 // ArtifactCombiner to combine away them.245 if (isArtifact(MI)) {246 LLVM_DEBUG(dbgs() << ".. Not legalized, moving to artifacts retry\n");247 assert(NumArtifacts == 0 &&248 "Artifacts are only expected in instruction list starting the "249 "second iteration, but each iteration starting second must "250 "start with an empty artifacts list");251 (void)NumArtifacts;252 RetryList.push_back(&MI);253 continue;254 }255 Helper.MIRBuilder.stopObservingChanges();256 return {Changed, &MI};257 }258 WorkListObserver.printNewInstrs();259 LocObserver.checkpoint();260 Changed |= Res == LegalizerHelper::Legalized;261 }262 // Try to combine the instructions in RetryList again if there263 // are new artifacts. If not, stop legalizing.264 if (!RetryList.empty()) {265 if (!ArtifactList.empty()) {266 while (!RetryList.empty())267 ArtifactList.insert(RetryList.pop_back_val());268 } else {269 LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n");270 Helper.MIRBuilder.stopObservingChanges();271 return {Changed, RetryList.front()};272 }273 }274 LocObserver.checkpoint();275 while (!ArtifactList.empty()) {276 MachineInstr &MI = *ArtifactList.pop_back_val();277 assert(isPreISelGenericOpcode(MI.getOpcode()) &&278 "Expecting generic opcode");279 if (isTriviallyDead(MI, MRI)) {280 salvageDebugInfo(MRI, MI);281 eraseInstr(MI, MRI, &LocObserver);282 continue;283 }284 SmallVector<MachineInstr *, 4> DeadInstructions;285 LLVM_DEBUG(dbgs() << "Trying to combine: " << MI);286 if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,287 WrapperObserver)) {288 WorkListObserver.printNewInstrs();289 eraseInstrs(DeadInstructions, MRI, &LocObserver);290 LocObserver.checkpoint(291 VerifyDebugLocs ==292 DebugLocVerifyLevel::LegalizationsAndArtifactCombiners);293 Changed = true;294 continue;295 }296 // If this was not an artifact (that could be combined away), this might297 // need special handling. Add it to InstList, so when it's processed298 // there, it has to be legal or specially handled.299 else {300 LLVM_DEBUG(dbgs() << ".. Not combined, moving to instructions list\n");301 InstList.insert(&MI);302 }303 }304 } while (!InstList.empty());305 306 return {Changed, /*FailedOn*/ nullptr};307}308 309bool Legalizer::runOnMachineFunction(MachineFunction &MF) {310 // If the ISel pipeline failed, do not bother running that pass.311 if (MF.getProperties().hasFailedISel())312 return false;313 LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');314 init(MF);315 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();316 GISelCSEAnalysisWrapper &Wrapper =317 getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();318 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);319 320 std::unique_ptr<MachineIRBuilder> MIRBuilder;321 GISelCSEInfo *CSEInfo = nullptr;322 bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()323 ? EnableCSEInLegalizer324 : TPC.isGISelCSEEnabled();325 if (EnableCSE) {326 MIRBuilder = std::make_unique<CSEMIRBuilder>();327 CSEInfo = &Wrapper.get(TPC.getCSEConfig());328 MIRBuilder->setCSEInfo(CSEInfo);329 } else330 MIRBuilder = std::make_unique<MachineIRBuilder>();331 332 SmallVector<GISelChangeObserver *, 1> AuxObservers;333 if (EnableCSE && CSEInfo) {334 // We want CSEInfo in addition to WorkListObserver to observe all changes.335 AuxObservers.push_back(CSEInfo);336 }337 assert(!CSEInfo || !errorToBool(CSEInfo->verify()));338 LostDebugLocObserver LocObserver(DEBUG_TYPE);339 if (VerifyDebugLocs > DebugLocVerifyLevel::None)340 AuxObservers.push_back(&LocObserver);341 342 // This allows Known Bits Analysis in the legalizer.343 GISelValueTracking *VT =344 &getAnalysis<GISelValueTrackingAnalysisLegacy>().get(MF);345 346 const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();347 MFResult Result = legalizeMachineFunction(MF, LI, AuxObservers, LocObserver,348 *MIRBuilder, VT);349 350 if (Result.FailedOn) {351 reportGISelFailure(MF, TPC, MORE, "gisel-legalize",352 "unable to legalize instruction", *Result.FailedOn);353 return false;354 }355 356 if (LocObserver.getNumLostDebugLocs()) {357 MachineOptimizationRemarkMissed R("gisel-legalize", "LostDebugLoc",358 MF.getFunction().getSubprogram(),359 /*MBB=*/&*MF.begin());360 R << "lost "361 << ore::NV("NumLostDebugLocs", LocObserver.getNumLostDebugLocs())362 << " debug locations during pass";363 reportGISelWarning(MF, TPC, MORE, R);364 // Example remark:365 // --- !Missed366 // Pass: gisel-legalize367 // Name: GISelFailure368 // DebugLoc: { File: '.../legalize-urem.mir', Line: 1, Column: 0 }369 // Function: test_urem_s32370 // Args:371 // - String: 'lost '372 // - NumLostDebugLocs: '1'373 // - String: ' debug locations during pass'374 // ...375 }376 377 // If for some reason CSE was not enabled, make sure that we invalidate the378 // CSEInfo object (as we currently declare that the analysis is preserved).379 // The next time get on the wrapper is called, it will force it to recompute380 // the analysis.381 if (!EnableCSE)382 Wrapper.setComputed(false);383 return Result.Changed;384}385