1 //===-- llvm/CodeGen/GlobalISel/Legalizer.cpp -----------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 /// \file This file implements the LegalizerHelper class to legalize individual
10 /// instructions and the LegalizePass wrapper pass for the primary
13 //===----------------------------------------------------------------------===//
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"
35 #define DEBUG_TYPE "legalizer"
40 EnableCSEInLegalizer("enable-cse-in-legalizer",
41 cl::desc("Should enable CSE in Legalizer"),
42 cl::Optional, cl::init(false));
44 char Legalizer::ID = 0;
45 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
46 "Legalize the Machine IR a function's Machine IR", 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,
54 Legalizer::Legalizer() : MachineFunctionPass(ID) { }
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);
64 void Legalizer::init(MachineFunction &MF) {
67 static bool isArtifact(const MachineInstr &MI) {
68 switch (MI.getOpcode()) {
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:
83 using InstListTy = GISelWorkList<256>;
84 using ArtifactListTy = GISelWorkList<128>;
87 class LegalizerWorkListManager : public GISelChangeObserver {
89 ArtifactListTy &ArtifactList;
91 SmallVector<MachineInstr *, 4> NewMIs;
95 LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
96 : InstList(Insts), ArtifactList(Arts) {}
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())) {
104 ArtifactList.insert(&MI);
106 InstList.insert(&MI);
110 void createdInstr(MachineInstr &MI) override {
111 LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
112 LLVM_DEBUG(NewMIs.push_back(&MI));
113 createdOrChangedInstr(MI);
116 void printNewInstrs() {
118 for (const auto *MI : NewMIs)
119 dbgs() << ".. .. New MI: " << *MI;
124 void erasingInstr(MachineInstr &MI) override {
125 LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
126 InstList.remove(&MI);
127 ArtifactList.remove(&MI);
130 void changingInstr(MachineInstr &MI) override {
131 LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
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);
144 Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,
145 ArrayRef<GISelChangeObserver *> AuxObservers,
146 MachineIRBuilder &MIRBuilder) {
147 MachineRegisterInfo &MRI = MF.getRegInfo();
149 // Populate worklists.
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) {
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()))
165 ArtifactList.deferred_insert(&MI);
167 InstList.deferred_insert(&MI);
170 ArtifactList.finalize();
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);
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);
189 bool Changed = false;
190 SmallVector<MachineInstr *, 128> RetryList;
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();
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");
220 RetryList.push_back(&MI);
223 Helper.MIRBuilder.stopObservingChanges();
224 return {Changed, &MI};
226 WorkListObserver.printNewInstrs();
227 Changed |= Res == LegalizerHelper::Legalized;
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());
236 LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n");
237 Helper.MIRBuilder.stopObservingChanges();
238 return {Changed, RetryList.front()};
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();
251 SmallVector<MachineInstr *, 4> DeadInstructions;
252 LLVM_DEBUG(dbgs() << "Trying to combine: " << MI);
253 if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
255 WorkListObserver.printNewInstrs();
256 for (auto *DeadMI : DeadInstructions) {
257 LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
258 RemoveDeadInstFromLists(DeadMI);
259 DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
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.
268 LLVM_DEBUG(dbgs() << ".. Not combined, moving to instructions list\n");
269 InstList.insert(&MI);
272 } while (!InstList.empty());
274 return {Changed, /*FailedOn*/ nullptr};
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))
282 LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
284 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
285 GISelCSEAnalysisWrapper &Wrapper =
286 getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
287 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
289 const size_t NumBlocks = MF.size();
291 std::unique_ptr<MachineIRBuilder> MIRBuilder;
292 GISelCSEInfo *CSEInfo = nullptr;
293 bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
294 ? EnableCSEInLegalizer
295 : TPC.isGISelCSEEnabled();
297 MIRBuilder = std::make_unique<CSEMIRBuilder>();
298 CSEInfo = &Wrapper.get(TPC.getCSEConfig());
299 MIRBuilder->setCSEInfo(CSEInfo);
301 MIRBuilder = std::make_unique<MachineIRBuilder>();
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);
309 const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();
310 MFResult Result = legalizeMachineFunction(MF, LI, AuxObservers, *MIRBuilder);
312 if (Result.FailedOn) {
313 reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
314 "unable to legalize instruction", *Result.FailedOn);
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(),
323 R << "inserting blocks is not supported yet";
324 reportGISelFailure(MF, TPC, MORE, R);
327 return Result.Changed;