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