1 //===-- llvm/CodeGen/GlobalISel/Legalizer.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 /// \file This file implements the LegalizerHelper class to legalize individual 11 /// instructions and the LegalizePass wrapper pass for the primary 12 /// legalization. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/CodeGen/GlobalISel/Legalizer.h" 17 #include "llvm/ADT/SetVector.h" 18 #include "llvm/CodeGen/GlobalISel/LegalizerCombiner.h" 19 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h" 20 #include "llvm/CodeGen/GlobalISel/Utils.h" 21 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" 22 #include "llvm/CodeGen/MachineRegisterInfo.h" 23 #include "llvm/CodeGen/TargetInstrInfo.h" 24 #include "llvm/CodeGen/TargetPassConfig.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Target/TargetSubtargetInfo.h" 27 28 #include <iterator> 29 30 #define DEBUG_TYPE "legalizer" 31 32 using namespace llvm; 33 34 char Legalizer::ID = 0; 35 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE, 36 "Legalize the Machine IR a function's Machine IR", false, 37 false) 38 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) 39 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE, 40 "Legalize the Machine IR a function's Machine IR", false, 41 false) 42 43 Legalizer::Legalizer() : MachineFunctionPass(ID) { 44 initializeLegalizerPass(*PassRegistry::getPassRegistry()); 45 } 46 47 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const { 48 AU.addRequired<TargetPassConfig>(); 49 MachineFunctionPass::getAnalysisUsage(AU); 50 } 51 52 void Legalizer::init(MachineFunction &MF) { 53 } 54 55 bool Legalizer::runOnMachineFunction(MachineFunction &MF) { 56 // If the ISel pipeline failed, do not bother running that pass. 57 if (MF.getProperties().hasProperty( 58 MachineFunctionProperties::Property::FailedISel)) 59 return false; 60 DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n'); 61 init(MF); 62 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>(); 63 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr); 64 LegalizerHelper Helper(MF); 65 66 // FIXME: an instruction may need more than one pass before it is legal. For 67 // example on most architectures <3 x i3> is doubly-illegal. It would 68 // typically proceed along a path like: <3 x i3> -> <3 x i8> -> <8 x i8>. We 69 // probably want a worklist of instructions rather than naive iterate until 70 // convergence for performance reasons. 71 bool Changed = false; 72 MachineBasicBlock::iterator NextMI; 73 using VecType = SmallSetVector<MachineInstr *, 8>; 74 VecType WorkList; 75 VecType CombineList; 76 for (auto &MBB : MF) { 77 for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) { 78 // Get the next Instruction before we try to legalize, because there's a 79 // good chance MI will be deleted. 80 NextMI = std::next(MI); 81 82 // Only legalize pre-isel generic instructions: others don't have types 83 // and are assumed to be legal. 84 if (!isPreISelGenericOpcode(MI->getOpcode())) 85 continue; 86 unsigned NumNewInsns = 0; 87 WorkList.clear(); 88 CombineList.clear(); 89 Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) { 90 // Only legalize pre-isel generic instructions. 91 // Legalization process could generate Target specific pseudo 92 // instructions with generic types. Don't record them 93 if (isPreISelGenericOpcode(MI->getOpcode())) { 94 ++NumNewInsns; 95 WorkList.insert(MI); 96 CombineList.insert(MI); 97 } 98 }); 99 WorkList.insert(&*MI); 100 LegalizerCombiner C(Helper.MIRBuilder, MF.getRegInfo(), 101 Helper.getLegalizerInfo()); 102 bool Changed = false; 103 LegalizerHelper::LegalizeResult Res; 104 do { 105 assert(!WorkList.empty() && "Expecting illegal ops"); 106 while (!WorkList.empty()) { 107 NumNewInsns = 0; 108 MachineInstr *CurrInst = WorkList.pop_back_val(); 109 Res = Helper.legalizeInstrStep(*CurrInst); 110 // Error out if we couldn't legalize this instruction. We may want to 111 // fall back to DAG ISel instead in the future. 112 if (Res == LegalizerHelper::UnableToLegalize) { 113 Helper.MIRBuilder.stopRecordingInsertions(); 114 if (Res == LegalizerHelper::UnableToLegalize) { 115 reportGISelFailure(MF, TPC, MORE, "gisel-legalize", 116 "unable to legalize instruction", *CurrInst); 117 return false; 118 } 119 } 120 Changed |= Res == LegalizerHelper::Legalized; 121 // If CurrInst was legalized, there's a good chance that it might have 122 // been erased. So remove it from the Combine List. 123 if (Res == LegalizerHelper::Legalized) 124 CombineList.remove(CurrInst); 125 126 #ifndef NDEBUG 127 if (NumNewInsns) 128 for (unsigned I = WorkList.size() - NumNewInsns, 129 E = WorkList.size(); 130 I != E; ++I) 131 DEBUG(dbgs() << ".. .. New MI: " << *WorkList[I];); 132 #endif 133 } 134 // Do the combines. 135 while (!CombineList.empty()) { 136 NumNewInsns = 0; 137 MachineInstr *CurrInst = CombineList.pop_back_val(); 138 SmallVector<MachineInstr *, 4> DeadInstructions; 139 Changed |= C.tryCombineInstruction(*CurrInst, DeadInstructions); 140 for (auto *DeadMI : DeadInstructions) { 141 DEBUG(dbgs() << ".. Erasing Dead Instruction " << *DeadMI); 142 CombineList.remove(DeadMI); 143 WorkList.remove(DeadMI); 144 DeadMI->eraseFromParent(); 145 } 146 #ifndef NDEBUG 147 if (NumNewInsns) 148 for (unsigned I = CombineList.size() - NumNewInsns, 149 E = CombineList.size(); 150 I != E; ++I) 151 DEBUG(dbgs() << ".. .. Combine New MI: " << *CombineList[I];); 152 #endif 153 } 154 } while (!WorkList.empty()); 155 156 Helper.MIRBuilder.stopRecordingInsertions(); 157 } 158 } 159 160 MachineRegisterInfo &MRI = MF.getRegInfo(); 161 MachineIRBuilder MIRBuilder(MF); 162 LegalizerCombiner C(MIRBuilder, MRI, Helper.getLegalizerInfo()); 163 for (auto &MBB : MF) { 164 for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) { 165 // Get the next Instruction before we try to legalize, because there's a 166 // good chance MI will be deleted. 167 // TOOD: Perhaps move this to a combiner pass later?. 168 NextMI = std::next(MI); 169 SmallVector<MachineInstr *, 4> DeadInsts; 170 Changed |= C.tryCombineMerges(*MI, DeadInsts); 171 for (auto *DeadMI : DeadInsts) 172 DeadMI->eraseFromParent(); 173 } 174 } 175 176 return Changed; 177 } 178