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