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 the 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. In this case, instruction
52/// erasure will cancel any future visits to the erased instruction and
53/// instruction creation will schedule that instruction for a future visit.
54/// Other Combiner implementations may require more complex behaviour from
55/// their GISelChangeObserver subclass.
56class Combiner::WorkListMaintainer : public GISelChangeObserver {
57 using WorkListTy = GISelWorkList<512>;
58 WorkListTy &WorkList;
59 /// The instructions that have been created but we want to report once they
60 /// have their operands. This is only maintained if debug output is requested.
61#ifndef NDEBUG
62 SetVector<const MachineInstr *> CreatedInstrs;
63#endif
64
65public:
66 WorkListMaintainer(WorkListTy &WorkList) : WorkList(WorkList) {}
67 virtual ~WorkListMaintainer() = default;
68
69 void erasingInstr(MachineInstr &MI) override {
70 LLVM_DEBUG(dbgs() << "Erasing: " << MI << "\n");
71 WorkList.remove(I: &MI);
72 }
73 void createdInstr(MachineInstr &MI) override {
74 LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n");
75 WorkList.insert(I: &MI);
76 LLVM_DEBUG(CreatedInstrs.insert(&MI));
77 }
78 void changingInstr(MachineInstr &MI) override {
79 LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n");
80 WorkList.insert(I: &MI);
81 }
82 void changedInstr(MachineInstr &MI) override {
83 LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n");
84 WorkList.insert(I: &MI);
85 }
86
87 void reportFullyCreatedInstrs() {
88 LLVM_DEBUG(for (const auto *MI
89 : CreatedInstrs) {
90 dbgs() << "Created: ";
91 MI->print(dbgs());
92 });
93 LLVM_DEBUG(CreatedInstrs.clear());
94 }
95};
96
97Combiner::Combiner(MachineFunction &MF, CombinerInfo &CInfo,
98 const TargetPassConfig *TPC, GISelKnownBits *KB,
99 GISelCSEInfo *CSEInfo)
100 : Builder(CSEInfo ? std::make_unique<CSEMIRBuilder>()
101 : std::make_unique<MachineIRBuilder>()),
102 WLObserver(std::make_unique<WorkListMaintainer>(args&: WorkList)),
103 ObserverWrapper(std::make_unique<GISelObserverWrapper>()), CInfo(CInfo),
104 Observer(*ObserverWrapper), B(*Builder), MF(MF), MRI(MF.getRegInfo()),
105 KB(KB), TPC(TPC), CSEInfo(CSEInfo) {
106 (void)this->TPC; // FIXME: Remove when used.
107
108 // Setup builder.
109 B.setMF(MF);
110 if (CSEInfo)
111 B.setCSEInfo(CSEInfo);
112
113 // Setup observer.
114 ObserverWrapper->addObserver(O: WLObserver.get());
115 if (CSEInfo)
116 ObserverWrapper->addObserver(O: CSEInfo);
117
118 B.setChangeObserver(*ObserverWrapper);
119}
120
121Combiner::~Combiner() = default;
122
123bool Combiner::combineMachineInstrs() {
124 // If the ISel pipeline failed, do not bother running this pass.
125 // FIXME: Should this be here or in individual combiner passes.
126 if (MF.getProperties().hasProperty(
127 P: MachineFunctionProperties::Property::FailedISel))
128 return false;
129
130 // We can't call this in the constructor because the derived class is
131 // uninitialized at that time.
132 if (!HasSetupMF) {
133 HasSetupMF = true;
134 setupMF(mf&: MF, kb: KB);
135 }
136
137 LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
138
139 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
140
141 bool MFChanged = false;
142 bool Changed;
143
144 unsigned Iteration = 0;
145 while (true) {
146 ++Iteration;
147 LLVM_DEBUG(dbgs() << "\n\nCombiner iteration #" << Iteration << '\n');
148
149 WorkList.clear();
150
151 // Collect all instructions. Do a post order traversal for basic blocks and
152 // insert with list bottom up, so while we pop_back_val, we'll traverse top
153 // down RPOT.
154 Changed = false;
155
156 RAIIDelegateInstaller DelInstall(MF, ObserverWrapper.get());
157 for (MachineBasicBlock *MBB : post_order(G: &MF)) {
158 for (MachineInstr &CurMI :
159 llvm::make_early_inc_range(Range: llvm::reverse(C&: *MBB))) {
160 // Erase dead insts before even adding to the list.
161 if (isTriviallyDead(MI: CurMI, MRI)) {
162 LLVM_DEBUG(dbgs() << CurMI << "Is dead; erasing.\n");
163 llvm::salvageDebugInfo(MRI, MI&: CurMI);
164 CurMI.eraseFromParent();
165 continue;
166 }
167 WorkList.deferred_insert(I: &CurMI);
168 }
169 }
170 WorkList.finalize();
171 // Main Loop. Process the instructions here.
172 while (!WorkList.empty()) {
173 MachineInstr *CurrInst = WorkList.pop_back_val();
174 LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;);
175 Changed |= tryCombineAll(I&: *CurrInst);
176 WLObserver->reportFullyCreatedInstrs();
177 }
178 MFChanged |= Changed;
179
180 if (!Changed) {
181 LLVM_DEBUG(dbgs() << "\nCombiner reached fixed-point after iteration #"
182 << Iteration << '\n');
183 break;
184 }
185 // Iterate until a fixed-point is reached if MaxIterations == 0,
186 // otherwise limit the number of iterations.
187 if (CInfo.MaxIterations && Iteration >= CInfo.MaxIterations) {
188 LLVM_DEBUG(
189 dbgs() << "\nCombiner reached iteration limit after iteration #"
190 << Iteration << '\n');
191 break;
192 }
193 }
194
195 if (Iteration == 1)
196 ++NumOneIteration;
197 else if (Iteration == 2)
198 ++NumTwoIterations;
199 else
200 ++NumThreeOrMoreIterations;
201
202#ifndef NDEBUG
203 if (CSEInfo) {
204 if (auto E = CSEInfo->verify()) {
205 errs() << E << '\n';
206 assert(false && "CSEInfo is not consistent. Likely missing calls to "
207 "observer on mutations.");
208 }
209 }
210#endif
211 return MFChanged;
212}
213