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/CodeGen/GlobalISel/CSEInfo.h"
17#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
18#include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
19#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
20#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
21#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
22#include "llvm/CodeGen/GlobalISel/Utils.h"
23#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
24#include "llvm/Support/Debug.h"
25
26#define DEBUG_TYPE "gi-combiner"
27
28using namespace llvm;
29
30namespace llvm {
31cl::OptionCategory GICombinerOptionCategory(
32 "GlobalISel Combiner",
33 "Control the rules which are enabled. These options all take a comma "
34 "separated list of rules to disable and may be specified by number "
35 "or number range (e.g. 1-10)."
36#ifndef NDEBUG
37 " They may also be specified by name."
38#endif
39);
40} // end namespace llvm
41
42/// This class acts as the glue the joins the CombinerHelper to the overall
43/// Combine algorithm. The CombinerHelper is intended to report the
44/// modifications it makes to the MIR to the GISelChangeObserver and the
45/// observer subclass will act on these events. In this case, instruction
46/// erasure will cancel any future visits to the erased instruction and
47/// instruction creation will schedule that instruction for a future visit.
48/// Other Combiner implementations may require more complex behaviour from
49/// their GISelChangeObserver subclass.
50class Combiner::WorkListMaintainer : public GISelChangeObserver {
51 using WorkListTy = GISelWorkList<512>;
52 WorkListTy &WorkList;
53 /// The instructions that have been created but we want to report once they
54 /// have their operands. This is only maintained if debug output is requested.
55#ifndef NDEBUG
56 SetVector<const MachineInstr *> CreatedInstrs;
57#endif
58
59public:
60 WorkListMaintainer(WorkListTy &WorkList) : WorkList(WorkList) {}
61 virtual ~WorkListMaintainer() = default;
62
63 void erasingInstr(MachineInstr &MI) override {
64 LLVM_DEBUG(dbgs() << "Erasing: " << MI << "\n");
65 WorkList.remove(I: &MI);
66 }
67 void createdInstr(MachineInstr &MI) override {
68 LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n");
69 WorkList.insert(I: &MI);
70 LLVM_DEBUG(CreatedInstrs.insert(&MI));
71 }
72 void changingInstr(MachineInstr &MI) override {
73 LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n");
74 WorkList.insert(I: &MI);
75 }
76 void changedInstr(MachineInstr &MI) override {
77 LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n");
78 WorkList.insert(I: &MI);
79 }
80
81 void reportFullyCreatedInstrs() {
82 LLVM_DEBUG(for (const auto *MI
83 : CreatedInstrs) {
84 dbgs() << "Created: ";
85 MI->print(dbgs());
86 });
87 LLVM_DEBUG(CreatedInstrs.clear());
88 }
89};
90
91Combiner::Combiner(MachineFunction &MF, CombinerInfo &CInfo,
92 const TargetPassConfig *TPC, GISelKnownBits *KB,
93 GISelCSEInfo *CSEInfo)
94 : Builder(CSEInfo ? std::make_unique<CSEMIRBuilder>()
95 : std::make_unique<MachineIRBuilder>()),
96 WLObserver(std::make_unique<WorkListMaintainer>(args&: WorkList)),
97 ObserverWrapper(std::make_unique<GISelObserverWrapper>()), CInfo(CInfo),
98 Observer(*ObserverWrapper), B(*Builder), MF(MF), MRI(MF.getRegInfo()),
99 KB(KB), TPC(TPC), CSEInfo(CSEInfo) {
100 (void)this->TPC; // FIXME: Remove when used.
101
102 // Setup builder.
103 B.setMF(MF);
104 if (CSEInfo)
105 B.setCSEInfo(CSEInfo);
106
107 // Setup observer.
108 ObserverWrapper->addObserver(O: WLObserver.get());
109 if (CSEInfo)
110 ObserverWrapper->addObserver(O: CSEInfo);
111
112 B.setChangeObserver(*ObserverWrapper);
113}
114
115Combiner::~Combiner() = default;
116
117bool Combiner::combineMachineInstrs() {
118 // If the ISel pipeline failed, do not bother running this pass.
119 // FIXME: Should this be here or in individual combiner passes.
120 if (MF.getProperties().hasProperty(
121 P: MachineFunctionProperties::Property::FailedISel))
122 return false;
123
124 // We can't call this in the constructor because the derived class is
125 // uninitialized at that time.
126 if (!HasSetupMF) {
127 HasSetupMF = true;
128 setupMF(mf&: MF, kb: KB);
129 }
130
131 LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
132
133 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
134
135 bool MFChanged = false;
136 bool Changed;
137
138 do {
139 WorkList.clear();
140
141 // Collect all instructions. Do a post order traversal for basic blocks and
142 // insert with list bottom up, so while we pop_back_val, we'll traverse top
143 // down RPOT.
144 Changed = false;
145
146 RAIIDelegateInstaller DelInstall(MF, ObserverWrapper.get());
147 for (MachineBasicBlock *MBB : post_order(G: &MF)) {
148 for (MachineInstr &CurMI :
149 llvm::make_early_inc_range(Range: llvm::reverse(C&: *MBB))) {
150 // Erase dead insts before even adding to the list.
151 if (isTriviallyDead(MI: CurMI, MRI)) {
152 LLVM_DEBUG(dbgs() << CurMI << "Is dead; erasing.\n");
153 llvm::salvageDebugInfo(MRI, MI&: CurMI);
154 CurMI.eraseFromParent();
155 continue;
156 }
157 WorkList.deferred_insert(I: &CurMI);
158 }
159 }
160 WorkList.finalize();
161 // Main Loop. Process the instructions here.
162 while (!WorkList.empty()) {
163 MachineInstr *CurrInst = WorkList.pop_back_val();
164 LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;);
165 Changed |= tryCombineAll(I&: *CurrInst);
166 WLObserver->reportFullyCreatedInstrs();
167 }
168 MFChanged |= Changed;
169 } while (Changed);
170
171#ifndef NDEBUG
172 if (CSEInfo) {
173 if (auto E = CSEInfo->verify()) {
174 errs() << E << '\n';
175 assert(false && "CSEInfo is not consistent. Likely missing calls to "
176 "observer on mutations.");
177 }
178 }
179#endif
180 return MFChanged;
181}
182

source code of llvm/lib/CodeGen/GlobalISel/Combiner.cpp