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