1//===-- lib/CodeGen/GlobalISel/Combiner.cpp -------------------------------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This file constains common code to combine machine functions at generic
10// level.
11//===----------------------------------------------------------------------===//
12
13#include "llvm/CodeGen/GlobalISel/Combiner.h"
14#include "llvm/ADT/PostOrderIterator.h"
15#include "llvm/ADT/SetVector.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
18#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
19#include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
20#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
21#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
22#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
23#include "llvm/CodeGen/GlobalISel/Utils.h"
24#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
25#include "llvm/Support/Debug.h"
26
27#define DEBUG_TYPE "gi-combiner"
28
29using namespace llvm;
30
31STATISTIC(NumOneIteration, "Number of functions with one iteration");
32STATISTIC(NumTwoIterations, "Number of functions with two iterations");
33STATISTIC(NumThreeOrMoreIterations,
34 "Number of functions with three or more iterations");
35
36namespace llvm {
37cl::OptionCategory GICombinerOptionCategory(
38 "GlobalISel Combiner",
39 "Control the rules which are enabled. These options all take a comma "
40 "separated list of rules to disable and may be specified by number "
41 "or number range (e.g. 1-10)."
42#ifndef NDEBUG
43 " They may also be specified by name."
44#endif
45);
46} // end namespace llvm
47
48/// This class acts as the glue that joins the CombinerHelper to the overall
49/// Combine algorithm. The CombinerHelper is intended to report the
50/// modifications it makes to the MIR to the GISelChangeObserver and the
51/// observer subclass will act on these events.
52class Combiner::WorkListMaintainer : public GISelChangeObserver {
53protected:
54#ifndef NDEBUG
55 /// The instructions that have been created but we want to report once they
56 /// have their operands. This is only maintained if debug output is requested.
57 SmallSetVector<const MachineInstr *, 32> CreatedInstrs;
58#endif
59 using Level = CombinerInfo::ObserverLevel;
60
61public:
62 static std::unique_ptr<WorkListMaintainer>
63 create(Level Lvl, WorkListTy &WorkList, MachineRegisterInfo &MRI);
64
65 ~WorkListMaintainer() override = default;
66
67 void reportFullyCreatedInstrs() {
68 LLVM_DEBUG({
69 for (auto *MI : CreatedInstrs) {
70 dbgs() << "Created: " << *MI;
71 }
72 CreatedInstrs.clear();
73 });
74 }
75
76 virtual void reset() = 0;
77 virtual void appliedCombine() = 0;
78};
79
80/// A configurable WorkListMaintainer implementation.
81/// The ObserverLevel determines how the WorkListMaintainer reacts to MIR
82/// changes.
83template <CombinerInfo::ObserverLevel Lvl>
84class Combiner::WorkListMaintainerImpl : public Combiner::WorkListMaintainer {
85 WorkListTy &WorkList;
86 MachineRegisterInfo &MRI;
87
88 // Defer handling these instructions until the combine finishes.
89 SmallSetVector<MachineInstr *, 32> DeferList;
90
91 // Track VRegs that (might) have lost a use.
92 SmallSetVector<Register, 32> LostUses;
93
94public:
95 WorkListMaintainerImpl(WorkListTy &WorkList, MachineRegisterInfo &MRI)
96 : WorkList(WorkList), MRI(MRI) {}
97
98 ~WorkListMaintainerImpl() override = default;
99
100 void reset() override {
101 DeferList.clear();
102 LostUses.clear();
103 }
104
105 void erasingInstr(MachineInstr &MI) override {
106 // MI will become dangling, remove it from all lists.
107 LLVM_DEBUG(dbgs() << "Erasing: " << MI; CreatedInstrs.remove(&MI));
108 WorkList.remove(I: &MI);
109 if constexpr (Lvl != Level::Basic) {
110 DeferList.remove(X: &MI);
111 noteLostUses(MI);
112 }
113 }
114
115 void createdInstr(MachineInstr &MI) override {
116 LLVM_DEBUG(dbgs() << "Creating: " << MI; CreatedInstrs.insert(&MI));
117 if constexpr (Lvl == Level::Basic)
118 WorkList.insert(I: &MI);
119 else
120 // Defer handling newly created instructions, because they don't have
121 // operands yet. We also insert them into the WorkList in reverse
122 // order so that they will be combined top down.
123 DeferList.insert(X: &MI);
124 }
125
126 void changingInstr(MachineInstr &MI) override {
127 LLVM_DEBUG(dbgs() << "Changing: " << MI);
128 // Some uses might get dropped when MI is changed.
129 // For now, overapproximate by assuming all uses will be dropped.
130 // TODO: Is a more precise heuristic or manual tracking of use count
131 // decrements worth it?
132 if constexpr (Lvl != Level::Basic)
133 noteLostUses(MI);
134 }
135
136 void changedInstr(MachineInstr &MI) override {
137 LLVM_DEBUG(dbgs() << "Changed: " << MI);
138 if constexpr (Lvl == Level::Basic)
139 WorkList.insert(I: &MI);
140 else
141 // Defer this for DCE
142 DeferList.insert(X: &MI);
143 }
144
145 // Only track changes during the combine and then walk the def/use-chains once
146 // the combine is finished, because:
147 // - instructions might have multiple defs during the combine.
148 // - use counts aren't accurate during the combine.
149 void appliedCombine() override {
150 if constexpr (Lvl == Level::Basic)
151 return;
152
153 // DCE deferred instructions and add them to the WorkList bottom up.
154 while (!DeferList.empty()) {
155 MachineInstr &MI = *DeferList.pop_back_val();
156 if (tryDCE(MI, MRI))
157 continue;
158
159 if constexpr (Lvl >= Level::SinglePass)
160 addUsersToWorkList(MI);
161
162 WorkList.insert(I: &MI);
163 }
164
165 // Handle instructions that have lost a user.
166 while (!LostUses.empty()) {
167 Register Use = LostUses.pop_back_val();
168 MachineInstr *UseMI = MRI.getVRegDef(Reg: Use);
169 if (!UseMI)
170 continue;
171
172 // If DCE succeeds, UseMI's uses are added back to LostUses by
173 // erasingInstr.
174 if (tryDCE(MI&: *UseMI, MRI))
175 continue;
176
177 if constexpr (Lvl >= Level::SinglePass) {
178 // OneUse checks are relatively common, so we might be able to combine
179 // the single remaining user of this Reg.
180 if (MRI.hasOneNonDBGUser(RegNo: Use))
181 WorkList.insert(I: &*MRI.use_instr_nodbg_begin(RegNo: Use));
182
183 WorkList.insert(I: UseMI);
184 }
185 }
186 }
187
188 void noteLostUses(MachineInstr &MI) {
189 for (auto &Use : MI.explicit_uses()) {
190 if (!Use.isReg() || !Use.getReg().isVirtual())
191 continue;
192 LostUses.insert(X: Use.getReg());
193 }
194 }
195
196 void addUsersToWorkList(MachineInstr &MI) {
197 for (auto &Def : MI.defs()) {
198 Register DefReg = Def.getReg();
199 if (!DefReg.isVirtual())
200 continue;
201 for (auto &UseMI : MRI.use_nodbg_instructions(Reg: DefReg)) {
202 WorkList.insert(I: &UseMI);
203 }
204 }
205 }
206};
207
208std::unique_ptr<Combiner::WorkListMaintainer>
209Combiner::WorkListMaintainer::create(Level Lvl, WorkListTy &WorkList,
210 MachineRegisterInfo &MRI) {
211 switch (Lvl) {
212 case Level::Basic:
213 return std::make_unique<WorkListMaintainerImpl<Level::Basic>>(args&: WorkList,
214 args&: MRI);
215 case Level::DCE:
216 return std::make_unique<WorkListMaintainerImpl<Level::DCE>>(args&: WorkList, args&: MRI);
217 case Level::SinglePass:
218 return std::make_unique<WorkListMaintainerImpl<Level::SinglePass>>(args&: WorkList,
219 args&: MRI);
220 }
221 llvm_unreachable("Illegal ObserverLevel");
222}
223
224Combiner::Combiner(MachineFunction &MF, const CombinerInfo &CInfo,
225 GISelValueTracking *VT, GISelCSEInfo *CSEInfo)
226 : Builder(CSEInfo ? std::make_unique<CSEMIRBuilder>()
227 : std::make_unique<MachineIRBuilder>()),
228 WLObserver(WorkListMaintainer::create(Lvl: CInfo.ObserverLvl, WorkList,
229 MRI&: MF.getRegInfo())),
230 ObserverWrapper(std::make_unique<GISelObserverWrapper>()), CInfo(CInfo),
231 Observer(*ObserverWrapper), B(*Builder), MF(MF), MRI(MF.getRegInfo()),
232 VT(VT), CSEInfo(CSEInfo) {
233 // Setup builder.
234 B.setMF(MF);
235 if (CSEInfo)
236 B.setCSEInfo(CSEInfo);
237
238 B.setChangeObserver(*ObserverWrapper);
239}
240
241Combiner::~Combiner() = default;
242
243bool Combiner::tryDCE(MachineInstr &MI, MachineRegisterInfo &MRI) {
244 if (!isTriviallyDead(MI, MRI))
245 return false;
246 LLVM_DEBUG(dbgs() << "Dead: " << MI);
247 llvm::salvageDebugInfo(MRI, MI);
248 MI.eraseFromParent();
249 return true;
250}
251
252bool Combiner::combineMachineInstrs() {
253 // If the ISel pipeline failed, do not bother running this pass.
254 // FIXME: Should this be here or in individual combiner passes.
255 if (MF.getProperties().hasFailedISel())
256 return false;
257
258 // We can't call this in the constructor because the derived class is
259 // uninitialized at that time.
260 if (!HasSetupMF) {
261 HasSetupMF = true;
262 setupMF(mf&: MF, vt: VT);
263 }
264
265 LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
266
267 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
268
269 bool MFChanged = false;
270 bool Changed;
271
272 unsigned Iteration = 0;
273 while (true) {
274 ++Iteration;
275 LLVM_DEBUG(dbgs() << "\n\nCombiner iteration #" << Iteration << '\n');
276
277 Changed = false;
278 WorkList.clear();
279 WLObserver->reset();
280 ObserverWrapper->clearObservers();
281 if (CSEInfo)
282 ObserverWrapper->addObserver(O: CSEInfo);
283
284 // If Observer-based DCE is enabled, perform full DCE only before the first
285 // iteration.
286 bool EnableDCE = CInfo.ObserverLvl >= CombinerInfo::ObserverLevel::DCE
287 ? CInfo.EnableFullDCE && Iteration == 1
288 : CInfo.EnableFullDCE;
289
290 // Collect all instructions. Do a post order traversal for basic blocks and
291 // insert with list bottom up, so while we pop_back_val, we'll traverse top
292 // down RPOT.
293 RAIIMFObsDelInstaller DelInstall(MF, *ObserverWrapper);
294 for (MachineBasicBlock *MBB : post_order(G: &MF)) {
295 for (MachineInstr &CurMI :
296 llvm::make_early_inc_range(Range: llvm::reverse(C&: *MBB))) {
297 // Erase dead insts before even adding to the list.
298 if (EnableDCE && tryDCE(MI&: CurMI, MRI))
299 continue;
300 WorkList.deferred_insert(I: &CurMI);
301 }
302 }
303 WorkList.finalize();
304
305 // Only notify WLObserver during actual combines
306 ObserverWrapper->addObserver(O: WLObserver.get());
307 // Main Loop. Process the instructions here.
308 while (!WorkList.empty()) {
309 MachineInstr &CurrInst = *WorkList.pop_back_val();
310 LLVM_DEBUG(dbgs() << "\nTry combining " << CurrInst);
311 bool AppliedCombine = tryCombineAll(I&: CurrInst);
312 LLVM_DEBUG(WLObserver->reportFullyCreatedInstrs());
313 Changed |= AppliedCombine;
314 if (AppliedCombine)
315 WLObserver->appliedCombine();
316 }
317 MFChanged |= Changed;
318
319 if (!Changed) {
320 LLVM_DEBUG(dbgs() << "\nCombiner reached fixed-point after iteration #"
321 << Iteration << '\n');
322 break;
323 }
324 // Iterate until a fixed-point is reached if MaxIterations == 0,
325 // otherwise limit the number of iterations.
326 if (CInfo.MaxIterations && Iteration >= CInfo.MaxIterations) {
327 LLVM_DEBUG(
328 dbgs() << "\nCombiner reached iteration limit after iteration #"
329 << Iteration << '\n');
330 break;
331 }
332 }
333
334 if (Iteration == 1)
335 ++NumOneIteration;
336 else if (Iteration == 2)
337 ++NumTwoIterations;
338 else
339 ++NumThreeOrMoreIterations;
340
341#ifndef NDEBUG
342 if (CSEInfo) {
343 if (auto E = CSEInfo->verify()) {
344 errs() << E << '\n';
345 assert(false && "CSEInfo is not consistent. Likely missing calls to "
346 "observer on mutations.");
347 }
348 }
349#endif
350 return MFChanged;
351}
352