1 //===-- lib/CodeGen/GlobalISel/Combiner.cpp -------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file constains common code to combine machine functions at generic
11 // level.
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/CodeGen/GlobalISel/Combiner.h"
15 #include "llvm/ADT/PostOrderIterator.h"
16 #include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
17 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
18 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
19 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
20 #include "llvm/CodeGen/GlobalISel/Utils.h"
21 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/Support/Debug.h"
24 
25 #define DEBUG_TYPE "gi-combiner"
26 
27 using namespace llvm;
28 
29 namespace {
30 /// This class acts as the glue the joins the CombinerHelper to the overall
31 /// Combine algorithm. The CombinerHelper is intended to report the
32 /// modifications it makes to the MIR to the GISelChangeObserver and the
33 /// observer subclass will act on these events. In this case, instruction
34 /// erasure will cancel any future visits to the erased instruction and
35 /// instruction creation will schedule that instruction for a future visit.
36 /// Other Combiner implementations may require more complex behaviour from
37 /// their GISelChangeObserver subclass.
38 class WorkListMaintainer : public GISelChangeObserver,
39                            public MachineFunction::Delegate {
40   using WorkListTy = GISelWorkList<512>;
41   MachineFunction &MF;
42   WorkListTy &WorkList;
43   /// The instructions that have been created but we want to report once they
44   /// have their operands. This is only maintained if debug output is requested.
45   SmallPtrSet<const MachineInstr *, 4> CreatedInstrs;
46 
47 public:
48   WorkListMaintainer(MachineFunction &MF, WorkListTy &WorkList)
49       : GISelChangeObserver(), MF(MF), WorkList(WorkList) {
50     MF.setDelegate(this);
51   }
52   virtual ~WorkListMaintainer() {
53     MF.resetDelegate(this);
54   }
55 
56   void erasingInstr(const MachineInstr &MI) override {
57     LLVM_DEBUG(dbgs() << "Erased: " << MI << "\n");
58     WorkList.remove(&MI);
59   }
60   void createdInstr(const MachineInstr &MI) override {
61     LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n");
62     WorkList.insert(&MI);
63     LLVM_DEBUG(CreatedInstrs.insert(&MI));
64   }
65   void changingInstr(const MachineInstr &MI) override {
66     LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n");
67     WorkList.insert(&MI);
68   }
69   void changedInstr(const MachineInstr &MI) override {
70     LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n");
71     WorkList.insert(&MI);
72   }
73 
74   void reportFullyCreatedInstrs() {
75     LLVM_DEBUG(for (const auto *MI
76                     : CreatedInstrs) {
77       dbgs() << "Created: ";
78       MI->print(dbgs());
79     });
80     LLVM_DEBUG(CreatedInstrs.clear());
81   }
82 
83   void MF_HandleInsertion(const MachineInstr &MI) override {
84     createdInstr(MI);
85   }
86   void MF_HandleRemoval(const MachineInstr &MI) override {
87     erasingInstr(MI);
88   }
89 };
90 }
91 
92 Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC)
93     : CInfo(Info), TPC(TPC) {
94   (void)this->TPC; // FIXME: Remove when used.
95 }
96 
97 bool Combiner::combineMachineInstrs(MachineFunction &MF) {
98   // If the ISel pipeline failed, do not bother running this pass.
99   // FIXME: Should this be here or in individual combiner passes.
100   if (MF.getProperties().hasProperty(
101           MachineFunctionProperties::Property::FailedISel))
102     return false;
103 
104   MRI = &MF.getRegInfo();
105   Builder.setMF(MF);
106 
107   LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
108 
109   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
110 
111   bool MFChanged = false;
112   bool Changed;
113 
114   do {
115     // Collect all instructions. Do a post order traversal for basic blocks and
116     // insert with list bottom up, so while we pop_back_val, we'll traverse top
117     // down RPOT.
118     Changed = false;
119     GISelWorkList<512> WorkList(&MF);
120     WorkListMaintainer Observer(MF, WorkList);
121     for (MachineBasicBlock *MBB : post_order(&MF)) {
122       if (MBB->empty())
123         continue;
124       for (auto MII = MBB->rbegin(), MIE = MBB->rend(); MII != MIE;) {
125         MachineInstr *CurMI = &*MII;
126         ++MII;
127         // Erase dead insts before even adding to the list.
128         if (isTriviallyDead(*CurMI, *MRI)) {
129           LLVM_DEBUG(dbgs() << *CurMI << "Is dead; erasing.\n");
130           CurMI->eraseFromParentAndMarkDBGValuesForRemoval();
131           continue;
132         }
133         WorkList.insert(CurMI);
134       }
135     }
136     // Main Loop. Process the instructions here.
137     while (!WorkList.empty()) {
138       MachineInstr *CurrInst = WorkList.pop_back_val();
139       LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;);
140       Changed |= CInfo.combine(Observer, *CurrInst, Builder);
141       Observer.reportFullyCreatedInstrs();
142     }
143     MFChanged |= Changed;
144   } while (Changed);
145 
146   return MFChanged;
147 }
148