1 //===- Localizer.cpp ---------------------- Localize some instrs -*- C++ -*-==// 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 /// \file 10 /// This file implements the Localizer class. 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/ADT/DenseMap.h" 14 #include "llvm/ADT/SmallPtrSet.h" 15 #include "llvm/CodeGen/GlobalISel/Localizer.h" 16 #include "llvm/CodeGen/MachineRegisterInfo.h" 17 #include "llvm/Support/Debug.h" 18 19 #define DEBUG_TYPE "localizer" 20 21 using namespace llvm; 22 23 char Localizer::ID = 0; 24 INITIALIZE_PASS(Localizer, DEBUG_TYPE, 25 "Move/duplicate certain instructions close to their use", 26 false, false); 27 28 Localizer::Localizer() : MachineFunctionPass(ID) { 29 initializeLocalizerPass(*PassRegistry::getPassRegistry()); 30 } 31 32 void Localizer::init(MachineFunction &MF) { 33 MRI = &MF.getRegInfo(); 34 } 35 36 bool Localizer::shouldLocalize(const MachineInstr &MI) { 37 switch(MI.getOpcode()) { 38 default: 39 return false; 40 // Constants-like instructions should be close to their users. 41 // We don't want long live-ranges for them. 42 case TargetOpcode::G_CONSTANT: 43 case TargetOpcode::G_FRAME_INDEX: 44 return true; 45 } 46 } 47 48 bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def, MachineBasicBlock **InsertMBB) { 49 MachineInstr &MIUse = *MOUse.getParent(); 50 *InsertMBB = MIUse.getParent(); 51 if (MIUse.isPHI()) 52 *InsertMBB = MIUse.getOperand(MIUse.getOperandNo(&MOUse) + 1).getMBB(); 53 return *InsertMBB == Def.getParent(); 54 } 55 56 bool Localizer::runOnMachineFunction(MachineFunction &MF) { 57 // If the ISel pipeline failed, do not bother running that pass. 58 if (MF.getProperties().hasProperty( 59 MachineFunctionProperties::Property::FailedISel)) 60 return false; 61 62 DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n'); 63 64 init(MF); 65 66 bool Changed = false; 67 // Keep track of the instructions we localized. 68 // We won't need to process them if we see them later in the CFG. 69 SmallPtrSet<MachineInstr *, 16> LocalizedInstrs; 70 DenseMap<std::pair<MachineBasicBlock *, unsigned>, unsigned> MBBWithLocalDef; 71 // TODO: Do bottom up traversal. 72 for (MachineBasicBlock &MBB : MF) { 73 for (MachineInstr &MI : MBB) { 74 if (LocalizedInstrs.count(&MI) || !shouldLocalize(MI)) 75 continue; 76 DEBUG(dbgs() << "Should localize: " << MI); 77 assert(MI.getDesc().getNumDefs() == 1 && "More than one definition not supported yet"); 78 unsigned Reg = MI.getOperand(0).getReg(); 79 // Check if all the users of MI are local. 80 // We are going to invalidation the list of use operands, so we 81 // can't use range iterator. 82 for (auto MOIt = MRI->use_begin(Reg), MOItEnd = MRI->use_end(); 83 MOIt != MOItEnd;) { 84 MachineOperand &MOUse = *MOIt++; 85 // Check if the use is already local. 86 MachineBasicBlock *InsertMBB; 87 DEBUG(MachineInstr &MIUse = *MOUse.getParent(); 88 dbgs() << "Checking use: " << MIUse << " #Opd: " << MIUse.getOperandNo(&MOUse) << '\n'); 89 if (isLocalUse(MOUse, MI, &InsertMBB)) 90 continue; 91 DEBUG(dbgs() << "Fixing non-local use\n"); 92 Changed = true; 93 auto MBBAndReg = std::make_pair(InsertMBB, Reg); 94 auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg); 95 if (NewVRegIt == MBBWithLocalDef.end()) { 96 // Create the localized instruction. 97 MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI); 98 LocalizedInstrs.insert(LocalizedMI); 99 // Move it at the right place. 100 MachineInstr &MIUse = *MOUse.getParent(); 101 if (MIUse.getParent() == InsertMBB) 102 InsertMBB->insert(MIUse, LocalizedMI); 103 else 104 InsertMBB->insert(InsertMBB->getFirstNonPHI(), LocalizedMI); 105 106 // Set a new register for the definition. 107 unsigned NewReg = MRI->createGenericVirtualRegister(MRI->getType(Reg)); 108 MRI->setRegClassOrRegBank(NewReg, MRI->getRegClassOrRegBank(Reg)); 109 LocalizedMI->getOperand(0).setReg(NewReg); 110 NewVRegIt = MBBWithLocalDef.insert(std::make_pair(MBBAndReg, NewReg)).first; 111 DEBUG(dbgs() << "Inserted: " << *LocalizedMI); 112 } 113 DEBUG(dbgs() << "Update use with: " << PrintReg(NewVRegIt->second) << '\n'); 114 // Update the user reg. 115 MOUse.setReg(NewVRegIt->second); 116 } 117 } 118 } 119 return Changed; 120 } 121