1 //===-- llvm/CodeGen/GlobalISel/Legalizer.cpp -----------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file This file implements the LegalizerHelper class to legalize individual
11 /// instructions and the LegalizePass wrapper pass for the primary
12 /// legalization.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
17 #include "llvm/ADT/PostOrderIterator.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
20 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
21 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
22 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
23 #include "llvm/CodeGen/GlobalISel/Utils.h"
24 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
25 #include "llvm/CodeGen/MachineRegisterInfo.h"
26 #include "llvm/CodeGen/TargetPassConfig.h"
27 #include "llvm/CodeGen/TargetSubtargetInfo.h"
28 #include "llvm/Support/Debug.h"
29 
30 #include <iterator>
31 
32 #define DEBUG_TYPE "legalizer"
33 
34 using namespace llvm;
35 
36 char Legalizer::ID = 0;
37 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
38                       "Legalize the Machine IR a function's Machine IR", false,
39                       false)
40 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
41 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
42                     "Legalize the Machine IR a function's Machine IR", false,
43                     false)
44 
45 Legalizer::Legalizer() : MachineFunctionPass(ID) {
46   initializeLegalizerPass(*PassRegistry::getPassRegistry());
47 }
48 
49 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
50   AU.addRequired<TargetPassConfig>();
51   getSelectionDAGFallbackAnalysisUsage(AU);
52   MachineFunctionPass::getAnalysisUsage(AU);
53 }
54 
55 void Legalizer::init(MachineFunction &MF) {
56 }
57 
58 static bool isArtifact(const MachineInstr &MI) {
59   switch (MI.getOpcode()) {
60   default:
61     return false;
62   case TargetOpcode::G_TRUNC:
63   case TargetOpcode::G_ZEXT:
64   case TargetOpcode::G_ANYEXT:
65   case TargetOpcode::G_SEXT:
66   case TargetOpcode::G_MERGE_VALUES:
67   case TargetOpcode::G_UNMERGE_VALUES:
68   case TargetOpcode::G_CONCAT_VECTORS:
69   case TargetOpcode::G_BUILD_VECTOR:
70     return true;
71   }
72 }
73 using InstListTy = GISelWorkList<256>;
74 using ArtifactListTy = GISelWorkList<128>;
75 
76 class LegalizerWorkListManager : public GISelChangeObserver {
77   InstListTy &InstList;
78   ArtifactListTy &ArtifactList;
79 
80 public:
81   LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
82       : InstList(Insts), ArtifactList(Arts) {}
83 
84   void createdInstr(const MachineInstr &MI) override {
85     // Only legalize pre-isel generic instructions.
86     // Legalization process could generate Target specific pseudo
87     // instructions with generic types. Don't record them
88     if (isPreISelGenericOpcode(MI.getOpcode())) {
89       if (isArtifact(MI))
90         ArtifactList.insert(&MI);
91       else
92         InstList.insert(&MI);
93     }
94     LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
95   }
96 
97   void erasingInstr(const MachineInstr &MI) override {
98     LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
99     InstList.remove(&MI);
100     ArtifactList.remove(&MI);
101   }
102 
103   void changingInstr(const MachineInstr &MI) override {
104     LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
105   }
106 
107   void changedInstr(const MachineInstr &MI) override {
108     // When insts change, we want to revisit them to legalize them again.
109     // We'll consider them the same as created.
110     LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
111     createdInstr(MI);
112   }
113 };
114 
115 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
116   // If the ISel pipeline failed, do not bother running that pass.
117   if (MF.getProperties().hasProperty(
118           MachineFunctionProperties::Property::FailedISel))
119     return false;
120   LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
121   init(MF);
122   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
123   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
124 
125   const size_t NumBlocks = MF.size();
126   MachineRegisterInfo &MRI = MF.getRegInfo();
127 
128   // Populate Insts
129   InstListTy InstList(&MF);
130   ArtifactListTy ArtifactList(&MF);
131   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
132   // Perform legalization bottom up so we can DCE as we legalize.
133   // Traverse BB in RPOT and within each basic block, add insts top down,
134   // so when we pop_back_val in the legalization process, we traverse bottom-up.
135   for (auto *MBB : RPOT) {
136     if (MBB->empty())
137       continue;
138     for (MachineInstr &MI : *MBB) {
139       // Only legalize pre-isel generic instructions: others don't have types
140       // and are assumed to be legal.
141       if (!isPreISelGenericOpcode(MI.getOpcode()))
142         continue;
143       if (isArtifact(MI))
144         ArtifactList.insert(&MI);
145       else
146         InstList.insert(&MI);
147     }
148   }
149   LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
150   LegalizerHelper Helper(MF, WorkListObserver);
151   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
152   LegalizationArtifactCombiner ArtCombiner(Helper.MIRBuilder, MF.getRegInfo(), LInfo);
153   auto RemoveDeadInstFromLists = [&WorkListObserver](MachineInstr *DeadMI) {
154     WorkListObserver.erasingInstr(*DeadMI);
155   };
156   bool Changed = false;
157   do {
158     while (!InstList.empty()) {
159       MachineInstr &MI = *InstList.pop_back_val();
160       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
161       if (isTriviallyDead(MI, MRI)) {
162         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
163         MI.eraseFromParentAndMarkDBGValuesForRemoval();
164         continue;
165       }
166 
167       // Do the legalization for this instruction.
168       auto Res = Helper.legalizeInstrStep(MI);
169       // Error out if we couldn't legalize this instruction. We may want to
170       // fall back to DAG ISel instead in the future.
171       if (Res == LegalizerHelper::UnableToLegalize) {
172         Helper.MIRBuilder.stopObservingChanges();
173         reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
174                            "unable to legalize instruction", MI);
175         return false;
176       }
177       Changed |= Res == LegalizerHelper::Legalized;
178     }
179     while (!ArtifactList.empty()) {
180       MachineInstr &MI = *ArtifactList.pop_back_val();
181       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
182       if (isTriviallyDead(MI, MRI)) {
183         LLVM_DEBUG(dbgs() << MI << "Is dead\n");
184         RemoveDeadInstFromLists(&MI);
185         MI.eraseFromParentAndMarkDBGValuesForRemoval();
186         continue;
187       }
188       SmallVector<MachineInstr *, 4> DeadInstructions;
189       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) {
190         for (auto *DeadMI : DeadInstructions) {
191           LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
192           RemoveDeadInstFromLists(DeadMI);
193           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
194         }
195         Changed = true;
196         continue;
197       }
198       // If this was not an artifact (that could be combined away), this might
199       // need special handling. Add it to InstList, so when it's processed
200       // there, it has to be legal or specially handled.
201       else
202         InstList.insert(&MI);
203     }
204   } while (!InstList.empty());
205 
206   // For now don't support if new blocks are inserted - we would need to fix the
207   // outerloop for that.
208   if (MF.size() != NumBlocks) {
209     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
210                                       MF.getFunction().getSubprogram(),
211                                       /*MBB=*/nullptr);
212     R << "inserting blocks is not supported yet";
213     reportGISelFailure(MF, TPC, MORE, R);
214     return false;
215   }
216 
217   return Changed;
218 }
219