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(&MI);
66  }
67  void createdInstr(MachineInstr &MI) override {
68    LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n");
69    WorkList.insert(&MI);
70    LLVM_DEBUG(CreatedInstrs.insert(&MI));
71  }
72  void changingInstr(MachineInstr &MI) override {
73    LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n");
74    WorkList.insert(&MI);
75  }
76  void changedInstr(MachineInstr &MI) override {
77    LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n");
78    WorkList.insert(&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>(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(WLObserver.get());
109  if (CSEInfo)
110    ObserverWrapper->addObserver(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          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, 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(&MF)) {
148      for (MachineInstr &CurMI :
149           llvm::make_early_inc_range(llvm::reverse(*MBB))) {
150        // Erase dead insts before even adding to the list.
151        if (isTriviallyDead(CurMI, MRI)) {
152          LLVM_DEBUG(dbgs() << CurMI << "Is dead; erasing.\n");
153          llvm::salvageDebugInfo(MRI, CurMI);
154          CurMI.eraseFromParent();
155          continue;
156        }
157        WorkList.deferred_insert(&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(*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