1 //===-- lib/CodeGen/GlobalISel/GICombiner.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 CombinerChangeObserver 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 CombinerChangeObserver subclass.
38 class WorkListMaintainer : public GISelChangeObserver {
39   using WorkListTy = GISelWorkList<512>;
40   WorkListTy &WorkList;
41 
42 public:
43   WorkListMaintainer(WorkListTy &WorkList) : WorkList(WorkList) {}
44   virtual ~WorkListMaintainer() {}
45 
46   void erasingInstr(MachineInstr &MI) override {
47     LLVM_DEBUG(dbgs() << "Erased: " << MI << "\n");
48     WorkList.remove(&MI);
49   }
50   void createdInstr(MachineInstr &MI) override {
51     LLVM_DEBUG(dbgs() << "Created: " << MI << "\n");
52     WorkList.insert(&MI);
53   }
54   void changingInstr(MachineInstr &MI) override {
55     LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n");
56     WorkList.remove(&MI);
57   }
58   // Currently changed conservatively assumes erased.
59   void changedInstr(MachineInstr &MI) override {
60     LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n");
61     WorkList.remove(&MI);
62   }
63 };
64 }
65 
66 Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC)
67     : CInfo(Info), TPC(TPC) {
68   (void)this->TPC; // FIXME: Remove when used.
69 }
70 
71 bool Combiner::combineMachineInstrs(MachineFunction &MF) {
72   // If the ISel pipeline failed, do not bother running this pass.
73   // FIXME: Should this be here or in individual combiner passes.
74   if (MF.getProperties().hasProperty(
75           MachineFunctionProperties::Property::FailedISel))
76     return false;
77 
78   MRI = &MF.getRegInfo();
79   Builder.setMF(MF);
80 
81   LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
82 
83   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
84 
85   bool MFChanged = false;
86   bool Changed;
87 
88   do {
89     // Collect all instructions. Do a post order traversal for basic blocks and
90     // insert with list bottom up, so while we pop_back_val, we'll traverse top
91     // down RPOT.
92     Changed = false;
93     GISelWorkList<512> WorkList;
94     WorkListMaintainer Observer(WorkList);
95     for (MachineBasicBlock *MBB : post_order(&MF)) {
96       if (MBB->empty())
97         continue;
98       for (auto MII = MBB->rbegin(), MIE = MBB->rend(); MII != MIE;) {
99         MachineInstr *CurMI = &*MII;
100         ++MII;
101         // Erase dead insts before even adding to the list.
102         if (isTriviallyDead(*CurMI, *MRI)) {
103           LLVM_DEBUG(dbgs() << *CurMI << "Is dead; erasing.\n");
104           CurMI->eraseFromParentAndMarkDBGValuesForRemoval();
105           continue;
106         }
107         WorkList.insert(CurMI);
108       }
109     }
110     // Main Loop. Process the instructions here.
111     while (!WorkList.empty()) {
112       MachineInstr *CurrInst = WorkList.pop_back_val();
113       LLVM_DEBUG(dbgs() << "Try combining " << *CurrInst << "\n";);
114       Changed |= CInfo.combine(Observer, *CurrInst, Builder);
115     }
116     MFChanged |= Changed;
117   } while (Changed);
118 
119   return MFChanged;
120 }
121