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/Utils.h" 25 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" 26 #include "llvm/CodeGen/MachineRegisterInfo.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/Target/TargetMachine.h" 32 33 #include <iterator> 34 35 #define DEBUG_TYPE "legalizer" 36 37 using namespace llvm; 38 39 static cl::opt<bool> 40 EnableCSEInLegalizer("enable-cse-in-legalizer", 41 cl::desc("Should enable CSE in Legalizer"), 42 cl::Optional, cl::init(false)); 43 44 char Legalizer::ID = 0; 45 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE, 46 "Legalize the Machine IR a function's Machine IR", false, 47 false) 48 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) 49 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass) 50 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE, 51 "Legalize the Machine IR a function's Machine IR", false, 52 false) 53 54 Legalizer::Legalizer() : MachineFunctionPass(ID) { } 55 56 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const { 57 AU.addRequired<TargetPassConfig>(); 58 AU.addRequired<GISelCSEAnalysisWrapperPass>(); 59 AU.addPreserved<GISelCSEAnalysisWrapperPass>(); 60 getSelectionDAGFallbackAnalysisUsage(AU); 61 MachineFunctionPass::getAnalysisUsage(AU); 62 } 63 64 void Legalizer::init(MachineFunction &MF) { 65 } 66 67 static bool isArtifact(const MachineInstr &MI) { 68 switch (MI.getOpcode()) { 69 default: 70 return false; 71 case TargetOpcode::G_TRUNC: 72 case TargetOpcode::G_ZEXT: 73 case TargetOpcode::G_ANYEXT: 74 case TargetOpcode::G_SEXT: 75 case TargetOpcode::G_MERGE_VALUES: 76 case TargetOpcode::G_UNMERGE_VALUES: 77 case TargetOpcode::G_CONCAT_VECTORS: 78 case TargetOpcode::G_BUILD_VECTOR: 79 case TargetOpcode::G_EXTRACT: 80 return true; 81 } 82 } 83 using InstListTy = GISelWorkList<256>; 84 using ArtifactListTy = GISelWorkList<128>; 85 86 namespace { 87 class LegalizerWorkListManager : public GISelChangeObserver { 88 InstListTy &InstList; 89 ArtifactListTy &ArtifactList; 90 #ifndef NDEBUG 91 SmallVector<MachineInstr *, 4> NewMIs; 92 #endif 93 94 public: 95 LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts) 96 : InstList(Insts), ArtifactList(Arts) {} 97 98 void createdOrChangedInstr(MachineInstr &MI) { 99 // Only legalize pre-isel generic instructions. 100 // Legalization process could generate Target specific pseudo 101 // instructions with generic types. Don't record them 102 if (isPreISelGenericOpcode(MI.getOpcode())) { 103 if (isArtifact(MI)) 104 ArtifactList.insert(&MI); 105 else 106 InstList.insert(&MI); 107 } 108 } 109 110 void createdInstr(MachineInstr &MI) override { 111 LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI); 112 LLVM_DEBUG(NewMIs.push_back(&MI)); 113 createdOrChangedInstr(MI); 114 } 115 116 void printNewInstrs() { 117 LLVM_DEBUG({ 118 for (const auto *MI : NewMIs) 119 dbgs() << ".. .. New MI: " << *MI; 120 NewMIs.clear(); 121 }); 122 } 123 124 void erasingInstr(MachineInstr &MI) override { 125 LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI); 126 InstList.remove(&MI); 127 ArtifactList.remove(&MI); 128 } 129 130 void changingInstr(MachineInstr &MI) override { 131 LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI); 132 } 133 134 void changedInstr(MachineInstr &MI) override { 135 // When insts change, we want to revisit them to legalize them again. 136 // We'll consider them the same as created. 137 LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI); 138 createdOrChangedInstr(MI); 139 } 140 }; 141 } // namespace 142 143 Legalizer::MFResult 144 Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI, 145 ArrayRef<GISelChangeObserver *> AuxObservers, 146 MachineIRBuilder &MIRBuilder) { 147 MachineRegisterInfo &MRI = MF.getRegInfo(); 148 149 // Populate worklists. 150 InstListTy InstList; 151 ArtifactListTy ArtifactList; 152 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF); 153 // Perform legalization bottom up so we can DCE as we legalize. 154 // Traverse BB in RPOT and within each basic block, add insts top down, 155 // so when we pop_back_val in the legalization process, we traverse bottom-up. 156 for (auto *MBB : RPOT) { 157 if (MBB->empty()) 158 continue; 159 for (MachineInstr &MI : *MBB) { 160 // Only legalize pre-isel generic instructions: others don't have types 161 // and are assumed to be legal. 162 if (!isPreISelGenericOpcode(MI.getOpcode())) 163 continue; 164 if (isArtifact(MI)) 165 ArtifactList.deferred_insert(&MI); 166 else 167 InstList.deferred_insert(&MI); 168 } 169 } 170 ArtifactList.finalize(); 171 InstList.finalize(); 172 173 // This observer keeps the worklists updated. 174 LegalizerWorkListManager WorkListObserver(InstList, ArtifactList); 175 // We want both WorkListObserver as well as all the auxiliary observers (e.g. 176 // CSEInfo) to observe all changes. Use the wrapper observer. 177 GISelObserverWrapper WrapperObserver(&WorkListObserver); 178 for (GISelChangeObserver *Observer : AuxObservers) 179 WrapperObserver.addObserver(Observer); 180 181 // Now install the observer as the delegate to MF. 182 // This will keep all the observers notified about new insertions/deletions. 183 RAIIDelegateInstaller DelInstall(MF, &WrapperObserver); 184 LegalizerHelper Helper(MF, LI, WrapperObserver, MIRBuilder); 185 LegalizationArtifactCombiner ArtCombiner(MIRBuilder, MRI, LI); 186 auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) { 187 WrapperObserver.erasingInstr(*DeadMI); 188 }; 189 bool Changed = false; 190 SmallVector<MachineInstr *, 128> RetryList; 191 do { 192 LLVM_DEBUG(dbgs() << "=== New Iteration ===\n"); 193 assert(RetryList.empty() && "Expected no instructions in RetryList"); 194 unsigned NumArtifacts = ArtifactList.size(); 195 while (!InstList.empty()) { 196 MachineInstr &MI = *InstList.pop_back_val(); 197 assert(isPreISelGenericOpcode(MI.getOpcode()) && 198 "Expecting generic opcode"); 199 if (isTriviallyDead(MI, MRI)) { 200 LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n"); 201 MI.eraseFromParentAndMarkDBGValuesForRemoval(); 202 continue; 203 } 204 205 // Do the legalization for this instruction. 206 auto Res = Helper.legalizeInstrStep(MI); 207 // Error out if we couldn't legalize this instruction. We may want to 208 // fall back to DAG ISel instead in the future. 209 if (Res == LegalizerHelper::UnableToLegalize) { 210 // Move illegal artifacts to RetryList instead of aborting because 211 // legalizing InstList may generate artifacts that allow 212 // ArtifactCombiner to combine away them. 213 if (isArtifact(MI)) { 214 LLVM_DEBUG(dbgs() << ".. Not legalized, moving to artifacts retry\n"); 215 assert(NumArtifacts == 0 && 216 "Artifacts are only expected in instruction list starting the " 217 "second iteration, but each iteration starting second must " 218 "start with an empty artifacts list"); 219 (void)NumArtifacts; 220 RetryList.push_back(&MI); 221 continue; 222 } 223 Helper.MIRBuilder.stopObservingChanges(); 224 return {Changed, &MI}; 225 } 226 WorkListObserver.printNewInstrs(); 227 Changed |= Res == LegalizerHelper::Legalized; 228 } 229 // Try to combine the instructions in RetryList again if there 230 // are new artifacts. If not, stop legalizing. 231 if (!RetryList.empty()) { 232 if (!ArtifactList.empty()) { 233 while (!RetryList.empty()) 234 ArtifactList.insert(RetryList.pop_back_val()); 235 } else { 236 LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n"); 237 Helper.MIRBuilder.stopObservingChanges(); 238 return {Changed, RetryList.front()}; 239 } 240 } 241 while (!ArtifactList.empty()) { 242 MachineInstr &MI = *ArtifactList.pop_back_val(); 243 assert(isPreISelGenericOpcode(MI.getOpcode()) && 244 "Expecting generic opcode"); 245 if (isTriviallyDead(MI, MRI)) { 246 LLVM_DEBUG(dbgs() << MI << "Is dead\n"); 247 RemoveDeadInstFromLists(&MI); 248 MI.eraseFromParentAndMarkDBGValuesForRemoval(); 249 continue; 250 } 251 SmallVector<MachineInstr *, 4> DeadInstructions; 252 LLVM_DEBUG(dbgs() << "Trying to combine: " << MI); 253 if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions, 254 WrapperObserver)) { 255 WorkListObserver.printNewInstrs(); 256 for (auto *DeadMI : DeadInstructions) { 257 LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n"); 258 RemoveDeadInstFromLists(DeadMI); 259 DeadMI->eraseFromParentAndMarkDBGValuesForRemoval(); 260 } 261 Changed = true; 262 continue; 263 } 264 // If this was not an artifact (that could be combined away), this might 265 // need special handling. Add it to InstList, so when it's processed 266 // there, it has to be legal or specially handled. 267 else { 268 LLVM_DEBUG(dbgs() << ".. Not combined, moving to instructions list\n"); 269 InstList.insert(&MI); 270 } 271 } 272 } while (!InstList.empty()); 273 274 return {Changed, /*FailedOn*/ nullptr}; 275 } 276 277 bool Legalizer::runOnMachineFunction(MachineFunction &MF) { 278 // If the ISel pipeline failed, do not bother running that pass. 279 if (MF.getProperties().hasProperty( 280 MachineFunctionProperties::Property::FailedISel)) 281 return false; 282 LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n'); 283 init(MF); 284 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>(); 285 GISelCSEAnalysisWrapper &Wrapper = 286 getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper(); 287 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr); 288 289 const size_t NumBlocks = MF.size(); 290 291 std::unique_ptr<MachineIRBuilder> MIRBuilder; 292 GISelCSEInfo *CSEInfo = nullptr; 293 bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences() 294 ? EnableCSEInLegalizer 295 : TPC.isGISelCSEEnabled(); 296 if (EnableCSE) { 297 MIRBuilder = std::make_unique<CSEMIRBuilder>(); 298 CSEInfo = &Wrapper.get(TPC.getCSEConfig()); 299 MIRBuilder->setCSEInfo(CSEInfo); 300 } else 301 MIRBuilder = std::make_unique<MachineIRBuilder>(); 302 303 SmallVector<GISelChangeObserver *, 1> AuxObservers; 304 if (EnableCSE && CSEInfo) { 305 // We want CSEInfo in addition to WorkListObserver to observe all changes. 306 AuxObservers.push_back(CSEInfo); 307 } 308 309 const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo(); 310 MFResult Result = legalizeMachineFunction(MF, LI, AuxObservers, *MIRBuilder); 311 312 if (Result.FailedOn) { 313 reportGISelFailure(MF, TPC, MORE, "gisel-legalize", 314 "unable to legalize instruction", *Result.FailedOn); 315 return false; 316 } 317 // For now don't support if new blocks are inserted - we would need to fix the 318 // outer loop for that. 319 if (MF.size() != NumBlocks) { 320 MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure", 321 MF.getFunction().getSubprogram(), 322 /*MBB=*/nullptr); 323 R << "inserting blocks is not supported yet"; 324 reportGISelFailure(MF, TPC, MORE, R); 325 return false; 326 } 327 return Result.Changed; 328 } 329