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/CSEInfo.h" 17 #include "llvm/CodeGen/GlobalISel/CombinerInfo.h" 18 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.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/CodeGen/MachineRegisterInfo.h" 25 #include "llvm/Support/Debug.h" 26 27 #define DEBUG_TYPE "gi-combiner" 28 29 using namespace llvm; 30 31 namespace { 32 /// This class acts as the glue the joins the CombinerHelper to the overall 33 /// Combine algorithm. The CombinerHelper is intended to report the 34 /// modifications it makes to the MIR to the GISelChangeObserver and the 35 /// observer subclass will act on these events. In this case, instruction 36 /// erasure will cancel any future visits to the erased instruction and 37 /// instruction creation will schedule that instruction for a future visit. 38 /// Other Combiner implementations may require more complex behaviour from 39 /// their GISelChangeObserver subclass. 40 class WorkListMaintainer : public GISelChangeObserver { 41 using WorkListTy = GISelWorkList<512>; 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(WorkListTy &WorkList) 49 : GISelChangeObserver(), WorkList(WorkList) {} 50 virtual ~WorkListMaintainer() { 51 } 52 53 void erasingInstr(MachineInstr &MI) override { 54 LLVM_DEBUG(dbgs() << "Erased: " << MI << "\n"); 55 WorkList.remove(&MI); 56 } 57 void createdInstr(MachineInstr &MI) override { 58 LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n"); 59 WorkList.insert(&MI); 60 LLVM_DEBUG(CreatedInstrs.insert(&MI)); 61 } 62 void changingInstr(MachineInstr &MI) override { 63 LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n"); 64 WorkList.insert(&MI); 65 } 66 void changedInstr(MachineInstr &MI) override { 67 LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n"); 68 WorkList.insert(&MI); 69 } 70 71 void reportFullyCreatedInstrs() { 72 LLVM_DEBUG(for (const auto *MI 73 : CreatedInstrs) { 74 dbgs() << "Created: "; 75 MI->print(dbgs()); 76 }); 77 LLVM_DEBUG(CreatedInstrs.clear()); 78 } 79 }; 80 } 81 82 Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC) 83 : CInfo(Info), TPC(TPC) { 84 (void)this->TPC; // FIXME: Remove when used. 85 } 86 87 bool Combiner::combineMachineInstrs(MachineFunction &MF, 88 GISelCSEInfo *CSEInfo) { 89 // If the ISel pipeline failed, do not bother running this pass. 90 // FIXME: Should this be here or in individual combiner passes. 91 if (MF.getProperties().hasProperty( 92 MachineFunctionProperties::Property::FailedISel)) 93 return false; 94 95 Builder = 96 CSEInfo ? make_unique<CSEMIRBuilder>() : make_unique<MachineIRBuilder>(); 97 MRI = &MF.getRegInfo(); 98 Builder->setMF(MF); 99 if (CSEInfo) 100 Builder->setCSEInfo(CSEInfo); 101 102 LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n'); 103 104 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr); 105 106 bool MFChanged = false; 107 bool Changed; 108 MachineIRBuilder &B = *Builder.get(); 109 110 do { 111 // Collect all instructions. Do a post order traversal for basic blocks and 112 // insert with list bottom up, so while we pop_back_val, we'll traverse top 113 // down RPOT. 114 Changed = false; 115 GISelWorkList<512> WorkList; 116 WorkListMaintainer Observer(WorkList); 117 GISelObserverWrapper WrapperObserver(&Observer); 118 if (CSEInfo) 119 WrapperObserver.addObserver(CSEInfo); 120 RAIIDelegateInstaller DelInstall(MF, &WrapperObserver); 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(WrapperObserver, *CurrInst, B); 141 Observer.reportFullyCreatedInstrs(); 142 } 143 MFChanged |= Changed; 144 } while (Changed); 145 146 return MFChanged; 147 } 148