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/PostOrderIterator.h" 18 #include "llvm/ADT/SetVector.h" 19 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h" 20 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h" 21 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h" 22 #include "llvm/CodeGen/GlobalISel/Utils.h" 23 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" 24 #include "llvm/CodeGen/MachineRegisterInfo.h" 25 #include "llvm/CodeGen/TargetPassConfig.h" 26 #include "llvm/CodeGen/TargetSubtargetInfo.h" 27 #include "llvm/Support/Debug.h" 28 29 #include <iterator> 30 31 #define DEBUG_TYPE "legalizer" 32 33 using namespace llvm; 34 35 char Legalizer::ID = 0; 36 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE, 37 "Legalize the Machine IR a function's Machine IR", false, 38 false) 39 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) 40 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE, 41 "Legalize the Machine IR a function's Machine IR", false, 42 false) 43 44 Legalizer::Legalizer() : MachineFunctionPass(ID) { 45 initializeLegalizerPass(*PassRegistry::getPassRegistry()); 46 } 47 48 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const { 49 AU.addRequired<TargetPassConfig>(); 50 getSelectionDAGFallbackAnalysisUsage(AU); 51 MachineFunctionPass::getAnalysisUsage(AU); 52 } 53 54 void Legalizer::init(MachineFunction &MF) { 55 } 56 57 static bool isArtifact(const MachineInstr &MI) { 58 switch (MI.getOpcode()) { 59 default: 60 return false; 61 case TargetOpcode::G_TRUNC: 62 case TargetOpcode::G_ZEXT: 63 case TargetOpcode::G_ANYEXT: 64 case TargetOpcode::G_SEXT: 65 case TargetOpcode::G_MERGE_VALUES: 66 case TargetOpcode::G_UNMERGE_VALUES: 67 return true; 68 } 69 } 70 71 bool Legalizer::runOnMachineFunction(MachineFunction &MF) { 72 // If the ISel pipeline failed, do not bother running that pass. 73 if (MF.getProperties().hasProperty( 74 MachineFunctionProperties::Property::FailedISel)) 75 return false; 76 LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n'); 77 init(MF); 78 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>(); 79 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr); 80 LegalizerHelper Helper(MF); 81 82 const size_t NumBlocks = MF.size(); 83 MachineRegisterInfo &MRI = MF.getRegInfo(); 84 85 // Populate Insts 86 GISelWorkList<256> InstList; 87 GISelWorkList<128> ArtifactList; 88 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF); 89 // Perform legalization bottom up so we can DCE as we legalize. 90 // Traverse BB in RPOT and within each basic block, add insts top down, 91 // so when we pop_back_val in the legalization process, we traverse bottom-up. 92 for (auto *MBB : RPOT) { 93 if (MBB->empty()) 94 continue; 95 for (MachineInstr &MI : *MBB) { 96 // Only legalize pre-isel generic instructions: others don't have types 97 // and are assumed to be legal. 98 if (!isPreISelGenericOpcode(MI.getOpcode())) 99 continue; 100 if (isArtifact(MI)) 101 ArtifactList.insert(&MI); 102 else 103 InstList.insert(&MI); 104 } 105 } 106 Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) { 107 // Only legalize pre-isel generic instructions. 108 // Legalization process could generate Target specific pseudo 109 // instructions with generic types. Don't record them 110 if (isPreISelGenericOpcode(MI->getOpcode())) { 111 if (isArtifact(*MI)) 112 ArtifactList.insert(MI); 113 else 114 InstList.insert(MI); 115 } 116 LLVM_DEBUG(dbgs() << ".. .. New MI: " << *MI;); 117 }); 118 const LegalizerInfo &LInfo(Helper.getLegalizerInfo()); 119 LegalizationArtifactCombiner ArtCombiner(Helper.MIRBuilder, MF.getRegInfo(), LInfo); 120 auto RemoveDeadInstFromLists = [&InstList, 121 &ArtifactList](MachineInstr *DeadMI) { 122 InstList.remove(DeadMI); 123 ArtifactList.remove(DeadMI); 124 }; 125 bool Changed = false; 126 do { 127 while (!InstList.empty()) { 128 MachineInstr &MI = *InstList.pop_back_val(); 129 assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode"); 130 if (isTriviallyDead(MI, MRI)) { 131 LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n"); 132 MI.eraseFromParentAndMarkDBGValuesForRemoval(); 133 continue; 134 } 135 136 // Do the legalization for this instruction. 137 auto Res = Helper.legalizeInstrStep(MI); 138 // Error out if we couldn't legalize this instruction. We may want to 139 // fall back to DAG ISel instead in the future. 140 if (Res == LegalizerHelper::UnableToLegalize) { 141 Helper.MIRBuilder.stopRecordingInsertions(); 142 reportGISelFailure(MF, TPC, MORE, "gisel-legalize", 143 "unable to legalize instruction", MI); 144 return false; 145 } 146 Changed |= Res == LegalizerHelper::Legalized; 147 } 148 while (!ArtifactList.empty()) { 149 MachineInstr &MI = *ArtifactList.pop_back_val(); 150 assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode"); 151 if (isTriviallyDead(MI, MRI)) { 152 LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n"); 153 RemoveDeadInstFromLists(&MI); 154 MI.eraseFromParentAndMarkDBGValuesForRemoval(); 155 continue; 156 } 157 SmallVector<MachineInstr *, 4> DeadInstructions; 158 if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) { 159 for (auto *DeadMI : DeadInstructions) { 160 LLVM_DEBUG(dbgs() << ".. Erasing Dead Instruction " << *DeadMI); 161 RemoveDeadInstFromLists(DeadMI); 162 DeadMI->eraseFromParentAndMarkDBGValuesForRemoval(); 163 } 164 Changed = true; 165 continue; 166 } 167 // If this was not an artifact (that could be combined away), this might 168 // need special handling. Add it to InstList, so when it's processed 169 // there, it has to be legal or specially handled. 170 else 171 InstList.insert(&MI); 172 } 173 } while (!InstList.empty()); 174 175 // For now don't support if new blocks are inserted - we would need to fix the 176 // outerloop for that. 177 if (MF.size() != NumBlocks) { 178 MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure", 179 MF.getFunction().getSubprogram(), 180 /*MBB=*/nullptr); 181 R << "inserting blocks is not supported yet"; 182 reportGISelFailure(MF, TPC, MORE, R); 183 return false; 184 } 185 186 return Changed; 187 } 188
