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