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/CodeGen/GlobalISel/CSEInfo.h"
16#include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
17#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
18#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
19#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
20#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
21#include "llvm/CodeGen/GlobalISel/Utils.h"
22#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
23#include "llvm/CodeGen/MachineRegisterInfo.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
42namespace {
43/// This class acts as the glue the joins the CombinerHelper to the overall
44/// Combine algorithm. The CombinerHelper is intended to report the
45/// modifications it makes to the MIR to the GISelChangeObserver and the
46/// observer subclass will act on these events. In this case, instruction
47/// erasure will cancel any future visits to the erased instruction and
48/// instruction creation will schedule that instruction for a future visit.
49/// Other Combiner implementations may require more complex behaviour from
50/// their GISelChangeObserver subclass.
51class WorkListMaintainer : public GISelChangeObserver {
52  using WorkListTy = GISelWorkList<512>;
53  WorkListTy &WorkList;
54  /// The instructions that have been created but we want to report once they
55  /// have their operands. This is only maintained if debug output is requested.
56  SmallPtrSet<const MachineInstr *, 4> CreatedInstrs;
57
58public:
59  WorkListMaintainer(WorkListTy &WorkList)
60      : GISelChangeObserver(), WorkList(WorkList) {}
61  virtual ~WorkListMaintainer() {
62  }
63
64  void erasingInstr(MachineInstr &MI) override {
65    LLVM_DEBUG(dbgs() << "Erasing: " << MI << "\n");
66    WorkList.remove(&MI);
67  }
68  void createdInstr(MachineInstr &MI) override {
69    LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n");
70    WorkList.insert(&MI);
71    LLVM_DEBUG(CreatedInstrs.insert(&MI));
72  }
73  void changingInstr(MachineInstr &MI) override {
74    LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n");
75    WorkList.insert(&MI);
76  }
77  void changedInstr(MachineInstr &MI) override {
78    LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n");
79    WorkList.insert(&MI);
80  }
81
82  void reportFullyCreatedInstrs() {
83    LLVM_DEBUG(for (const auto *MI
84                    : CreatedInstrs) {
85      dbgs() << "Created: ";
86      MI->print(dbgs());
87    });
88    LLVM_DEBUG(CreatedInstrs.clear());
89  }
90};
91}
92
93Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC)
94    : CInfo(Info), TPC(TPC) {
95  (void)this->TPC; // FIXME: Remove when used.
96}
97
98bool Combiner::combineMachineInstrs(MachineFunction &MF,
99                                    GISelCSEInfo *CSEInfo) {
100  // If the ISel pipeline failed, do not bother running this pass.
101  // FIXME: Should this be here or in individual combiner passes.
102  if (MF.getProperties().hasProperty(
103          MachineFunctionProperties::Property::FailedISel))
104    return false;
105
106  Builder =
107      CSEInfo ? std::make_unique<CSEMIRBuilder>() : std::make_unique<MachineIRBuilder>();
108  MRI = &MF.getRegInfo();
109  Builder->setMF(MF);
110  if (CSEInfo)
111    Builder->setCSEInfo(CSEInfo);
112
113  LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
114
115  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
116
117  bool MFChanged = false;
118  bool Changed;
119  MachineIRBuilder &B = *Builder.get();
120
121  do {
122    // Collect all instructions. Do a post order traversal for basic blocks and
123    // insert with list bottom up, so while we pop_back_val, we'll traverse top
124    // down RPOT.
125    Changed = false;
126    GISelWorkList<512> WorkList;
127    WorkListMaintainer Observer(WorkList);
128    GISelObserverWrapper WrapperObserver(&Observer);
129    if (CSEInfo)
130      WrapperObserver.addObserver(CSEInfo);
131    RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
132    for (MachineBasicBlock *MBB : post_order(&MF)) {
133      if (MBB->empty())
134        continue;
135      for (auto MII = MBB->rbegin(), MIE = MBB->rend(); MII != MIE;) {
136        MachineInstr *CurMI = &*MII;
137        ++MII;
138        // Erase dead insts before even adding to the list.
139        if (isTriviallyDead(*CurMI, *MRI)) {
140          LLVM_DEBUG(dbgs() << *CurMI << "Is dead; erasing.\n");
141          CurMI->eraseFromParentAndMarkDBGValuesForRemoval();
142          continue;
143        }
144        WorkList.deferred_insert(CurMI);
145      }
146    }
147    WorkList.finalize();
148    // Main Loop. Process the instructions here.
149    while (!WorkList.empty()) {
150      MachineInstr *CurrInst = WorkList.pop_back_val();
151      LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;);
152      Changed |= CInfo.combine(WrapperObserver, *CurrInst, B);
153      Observer.reportFullyCreatedInstrs();
154    }
155    MFChanged |= Changed;
156  } while (Changed);
157
158  return MFChanged;
159}
160