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/GISelWorkList.h"
20 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
21 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
22 #include "llvm/CodeGen/GlobalISel/Utils.h"
23 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/TargetPassConfig.h"
26 #include "llvm/CodeGen/TargetSubtargetInfo.h"
27 #include "llvm/Support/Debug.h"
28 
29 #include <iterator>
30 
31 #define DEBUG_TYPE "legalizer"
32 
33 using namespace llvm;
34 
35 char Legalizer::ID = 0;
36 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
37                       "Legalize the Machine IR a function's Machine IR", false,
38                       false)
39 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
40 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
41                     "Legalize the Machine IR a function's Machine IR", false,
42                     false)
43 
44 Legalizer::Legalizer() : MachineFunctionPass(ID) {
45   initializeLegalizerPass(*PassRegistry::getPassRegistry());
46 }
47 
48 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
49   AU.addRequired<TargetPassConfig>();
50   MachineFunctionPass::getAnalysisUsage(AU);
51 }
52 
53 void Legalizer::init(MachineFunction &MF) {
54 }
55 
56 static bool isArtifact(const MachineInstr &MI) {
57   switch (MI.getOpcode()) {
58   default:
59     return false;
60   case TargetOpcode::G_TRUNC:
61   case TargetOpcode::G_ZEXT:
62   case TargetOpcode::G_ANYEXT:
63   case TargetOpcode::G_SEXT:
64   case TargetOpcode::G_MERGE_VALUES:
65   case TargetOpcode::G_UNMERGE_VALUES:
66     return true;
67   }
68 }
69 
70 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
71   // If the ISel pipeline failed, do not bother running that pass.
72   if (MF.getProperties().hasProperty(
73           MachineFunctionProperties::Property::FailedISel))
74     return false;
75   DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
76   init(MF);
77   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
78   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
79   LegalizerHelper Helper(MF);
80 
81   const size_t NumBlocks = MF.size();
82   MachineRegisterInfo &MRI = MF.getRegInfo();
83 
84   // Populate Insts
85   GISelWorkList<256> InstList;
86   GISelWorkList<128> ArtifactList;
87   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
88   // Perform legalization bottom up so we can DCE as we legalize.
89   // Traverse BB in RPOT and within each basic block, add insts top down,
90   // so when we pop_back_val in the legalization process, we traverse bottom-up.
91   for (auto *MBB : RPOT) {
92     if (MBB->empty())
93       continue;
94     for (MachineInstr &MI : *MBB) {
95       // Only legalize pre-isel generic instructions: others don't have types
96       // and are assumed to be legal.
97       if (!isPreISelGenericOpcode(MI.getOpcode()))
98         continue;
99       if (isArtifact(MI))
100         ArtifactList.insert(&MI);
101       else
102         InstList.insert(&MI);
103     }
104   }
105   Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
106     // Only legalize pre-isel generic instructions.
107     // Legalization process could generate Target specific pseudo
108     // instructions with generic types. Don't record them
109     if (isPreISelGenericOpcode(MI->getOpcode())) {
110       if (isArtifact(*MI))
111         ArtifactList.insert(MI);
112       else
113         InstList.insert(MI);
114     }
115     DEBUG(dbgs() << ".. .. New MI: " << *MI;);
116   });
117   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
118   LegalizationArtifactCombiner ArtCombiner(Helper.MIRBuilder, MF.getRegInfo(), LInfo);
119   auto RemoveDeadInstFromLists = [&InstList,
120                                   &ArtifactList](MachineInstr *DeadMI) {
121     InstList.remove(DeadMI);
122     ArtifactList.remove(DeadMI);
123   };
124   bool Changed = false;
125   do {
126     while (!InstList.empty()) {
127       MachineInstr &MI = *InstList.pop_back_val();
128       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
129       if (isTriviallyDead(MI, MRI)) {
130         DEBUG(dbgs() << MI << "Is dead; erasing.\n");
131         MI.eraseFromParentAndMarkDBGValuesForRemoval();
132         continue;
133       }
134 
135       // Do the legalization for this instruction.
136       auto Res = Helper.legalizeInstrStep(MI);
137       // Error out if we couldn't legalize this instruction. We may want to
138       // fall back to DAG ISel instead in the future.
139       if (Res == LegalizerHelper::UnableToLegalize) {
140         Helper.MIRBuilder.stopRecordingInsertions();
141         reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
142                            "unable to legalize instruction", MI);
143         return false;
144       }
145       Changed |= Res == LegalizerHelper::Legalized;
146     }
147     while (!ArtifactList.empty()) {
148       MachineInstr &MI = *ArtifactList.pop_back_val();
149       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
150       if (isTriviallyDead(MI, MRI)) {
151         DEBUG(dbgs() << MI << "Is dead; erasing.\n");
152         RemoveDeadInstFromLists(&MI);
153         MI.eraseFromParentAndMarkDBGValuesForRemoval();
154         continue;
155       }
156       SmallVector<MachineInstr *, 4> DeadInstructions;
157       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) {
158         for (auto *DeadMI : DeadInstructions) {
159           DEBUG(dbgs() << ".. Erasing Dead Instruction " << *DeadMI);
160           RemoveDeadInstFromLists(DeadMI);
161           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
162         }
163         Changed = true;
164         continue;
165       }
166       // If this was not an artifact (that could be combined away), this might
167       // need special handling. Add it to InstList, so when it's processed
168       // there, it has to be legal or specially handled.
169       else
170         InstList.insert(&MI);
171     }
172   } while (!InstList.empty());
173 
174   // For now don't support if new blocks are inserted - we would need to fix the
175   // outerloop for that.
176   if (MF.size() != NumBlocks) {
177     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
178                                       MF.getFunction().getSubprogram(),
179                                       /*MBB=*/nullptr);
180     R << "inserting blocks is not supported yet";
181     reportGISelFailure(MF, TPC, MORE, R);
182     return false;
183   }
184 
185   return Changed;
186 }
187