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