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/Support/Debug.h"
30 #include "llvm/Target/TargetMachine.h"
34 #define DEBUG_TYPE "legalizer"
39 EnableCSEInLegalizer("enable-cse-in-legalizer",
40 cl::desc("Should enable CSE in Legalizer"),
41 cl::Optional, cl::init(false));
43 char Legalizer::ID = 0;
44 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
45 "Legalize the Machine IR a function's Machine IR", 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,
53 Legalizer::Legalizer() : MachineFunctionPass(ID) { }
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);
63 void Legalizer::init(MachineFunction &MF) {
66 static bool isArtifact(const MachineInstr &MI) {
67 switch (MI.getOpcode()) {
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:
82 using InstListTy = GISelWorkList<256>;
83 using ArtifactListTy = GISelWorkList<128>;
86 class LegalizerWorkListManager : public GISelChangeObserver {
88 ArtifactListTy &ArtifactList;
90 SmallVector<MachineInstr *, 4> NewMIs;
94 LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
95 : InstList(Insts), ArtifactList(Arts) {}
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())) {
103 ArtifactList.insert(&MI);
105 InstList.insert(&MI);
109 void createdInstr(MachineInstr &MI) override {
110 LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
111 LLVM_DEBUG(NewMIs.push_back(&MI));
112 createdOrChangedInstr(MI);
115 void printNewInstrs() {
117 for (const auto *MI : NewMIs)
118 dbgs() << ".. .. New MI: " << *MI;
123 void erasingInstr(MachineInstr &MI) override {
124 LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
125 InstList.remove(&MI);
126 ArtifactList.remove(&MI);
129 void changingInstr(MachineInstr &MI) override {
130 LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
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);
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))
147 LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
149 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
150 GISelCSEAnalysisWrapper &Wrapper =
151 getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
152 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
154 const size_t NumBlocks = MF.size();
155 MachineRegisterInfo &MRI = MF.getRegInfo();
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) {
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()))
173 ArtifactList.deferred_insert(&MI);
175 InstList.deferred_insert(&MI);
178 ArtifactList.finalize();
180 std::unique_ptr<MachineIRBuilder> MIRBuilder;
181 GISelCSEInfo *CSEInfo = nullptr;
182 bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
183 ? EnableCSEInLegalizer
184 : TPC.isGISelCSEEnabled();
187 MIRBuilder = make_unique<CSEMIRBuilder>();
188 CSEInfo = &Wrapper.get(TPC.getCSEConfig());
189 MIRBuilder->setCSEInfo(CSEInfo);
191 MIRBuilder = 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(),
206 auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
207 WrapperObserver.erasingInstr(*DeadMI);
209 bool Changed = false;
211 while (!InstList.empty()) {
212 MachineInstr &MI = *InstList.pop_back_val();
213 assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
214 if (isTriviallyDead(MI, MRI)) {
215 LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
216 MI.eraseFromParentAndMarkDBGValuesForRemoval();
220 // Do the legalization for this instruction.
221 auto Res = Helper.legalizeInstrStep(MI);
222 // Error out if we couldn't legalize this instruction. We may want to
223 // fall back to DAG ISel instead in the future.
224 if (Res == LegalizerHelper::UnableToLegalize) {
225 Helper.MIRBuilder.stopObservingChanges();
226 reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
227 "unable to legalize instruction", MI);
230 WorkListObserver.printNewInstrs();
231 Changed |= Res == LegalizerHelper::Legalized;
233 while (!ArtifactList.empty()) {
234 MachineInstr &MI = *ArtifactList.pop_back_val();
235 assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
236 if (isTriviallyDead(MI, MRI)) {
237 LLVM_DEBUG(dbgs() << MI << "Is dead\n");
238 RemoveDeadInstFromLists(&MI);
239 MI.eraseFromParentAndMarkDBGValuesForRemoval();
242 SmallVector<MachineInstr *, 4> DeadInstructions;
243 if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
245 WorkListObserver.printNewInstrs();
246 for (auto *DeadMI : DeadInstructions) {
247 LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
248 RemoveDeadInstFromLists(DeadMI);
249 DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
254 // If this was not an artifact (that could be combined away), this might
255 // need special handling. Add it to InstList, so when it's processed
256 // there, it has to be legal or specially handled.
258 InstList.insert(&MI);
260 } while (!InstList.empty());
262 // For now don't support if new blocks are inserted - we would need to fix the
263 // outerloop for that.
264 if (MF.size() != NumBlocks) {
265 MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
266 MF.getFunction().getSubprogram(),
268 R << "inserting blocks is not supported yet";
269 reportGISelFailure(MF, TPC, MORE, R);