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