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