text: //===-- DelaySlotFiller.cpp - Mips delay slot filler ---------------------===//
  //
  //                     The LLVM Compiler Infrastructure
  //
  // This file is distributed under the University of Illinois Open Source
  // License. See LICENSE.TXT for details.
  //
  //===----------------------------------------------------------------------===//
  //
  // Simple pass to fills delay slots with useful instructions.
  //
  //===----------------------------------------------------------------------===//
  
  #define DEBUG_TYPE "delay-slot-filler"
  
  #include "Mips.h"
  #include "MipsTargetMachine.h"
  #include "llvm/CodeGen/MachineFunctionPass.h"
  #include "llvm/CodeGen/MachineInstrBuilder.h"
  #include "llvm/Support/CommandLine.h"
  #include "llvm/Target/TargetMachine.h"
  #include "llvm/Target/TargetInstrInfo.h"
  #include "llvm/Target/TargetRegisterInfo.h"
  #include "llvm/ADT/SmallSet.h"
  #include "llvm/ADT/Statistic.h"
  
  using namespace llvm;
  
  STATISTIC(FilledSlots, "Number of delay slots filled");
  STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that"
                         " are not NOP.");
  
  static cl::opt<bool> EnableDelaySlotFiller(
    "enable-mips-delay-filler",
    cl::init(false),
    cl::desc("Fill the Mips delay slots useful instructions."),
    cl::Hidden);
  
  namespace {
    struct Filler : public MachineFunctionPass {
  
      TargetMachine &TM;
      const TargetInstrInfo *TII;
      MachineBasicBlock::iterator LastFiller;
  
      static char ID;
      Filler(TargetMachine &tm)
        : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
  
      virtual const char *getPassName() const {
        return "Mips Delay Slot Filler";
      }
  
      bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
      bool runOnMachineFunction(MachineFunction &F) {
        bool Changed = false;
        for (MachineFunction::iterator FI = F.begin(), FE = F.end();
             FI != FE; ++FI)
          Changed |= runOnMachineBasicBlock(*FI);
        return Changed;
      }
  
      bool isDelayFiller(MachineBasicBlock &MBB,
                         MachineBasicBlock::iterator candidate);
  
      void insertCallUses(MachineBasicBlock::iterator MI,
                          SmallSet<unsigned, 32>& RegDefs,
                          SmallSet<unsigned, 32>& RegUses);
  
      void insertDefsUses(MachineBasicBlock::iterator MI,
                          SmallSet<unsigned, 32>& RegDefs,
                          SmallSet<unsigned, 32>& RegUses);
  
      bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
                      unsigned Reg);
  
      bool delayHasHazard(MachineBasicBlock::iterator candidate,
                          bool &sawLoad, bool &sawStore,
                          SmallSet<unsigned, 32> &RegDefs,
                          SmallSet<unsigned, 32> &RegUses);
  
      bool
      findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot,
                     MachineBasicBlock::iterator &Filler);
  
  
    };
    char Filler::ID = 0;
  } // end of anonymous namespace
  
  /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
  /// We assume there is only one delay slot per delayed instruction.
  bool Filler::
  runOnMachineBasicBlock(MachineBasicBlock &MBB) {
    bool Changed = false;
    LastFiller = MBB.end();
  
    for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
      if (I->getDesc().hasDelaySlot()) {
        ++FilledSlots;
        Changed = true;
  
        MachineBasicBlock::iterator D;
  
        if (EnableDelaySlotFiller && findDelayInstr(MBB, I, D)) {
          MBB.splice(llvm::next(I), &MBB, D);
          ++UsefulSlots;
        }
        else 
          BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP));
  
        // Record the filler instruction that filled the delay slot.
        // The instruction after it will be visited in the next iteration.
        LastFiller = ++I;
       }
    return Changed;
  
  }
  
  /// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
  /// slots in Mips MachineFunctions
  FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) {
    return new Filler(tm);
  }
  
  bool Filler::findDelayInstr(MachineBasicBlock &MBB,
                              MachineBasicBlock::iterator slot,
                              MachineBasicBlock::iterator &Filler) {
    SmallSet<unsigned, 32> RegDefs;
    SmallSet<unsigned, 32> RegUses;
  
    insertDefsUses(slot, RegDefs, RegUses);
  
    bool sawLoad = false;
    bool sawStore = false;
  
    for (MachineBasicBlock::reverse_iterator I(slot); I != MBB.rend(); ++I) {
      // skip debug value
      if (I->isDebugValue())
        continue;
  
      // Convert to forward iterator.
      MachineBasicBlock::iterator FI(llvm::next(I).base());
  
      if (I->hasUnmodeledSideEffects()
          || I->isInlineAsm()
          || I->isLabel()
          || FI == LastFiller
          || I->getDesc().isPseudo()
          //
          // Should not allow:
          // ERET, DERET or WAIT, PAUSE. Need to add these to instruction
          // list. TBD.
          )
        break;
  
      if (delayHasHazard(FI, sawLoad, sawStore, RegDefs, RegUses)) {
        insertDefsUses(FI, RegDefs, RegUses);
        continue;
      }
  
      Filler = FI;
      return true;
    }
  
    return false;
  }
  
  bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate,
                              bool &sawLoad,
                              bool &sawStore,
                              SmallSet<unsigned, 32> &RegDefs,
                              SmallSet<unsigned, 32> &RegUses) {
    if (candidate->isImplicitDef() || candidate->isKill())
      return true;
  
    MCInstrDesc MCID = candidate->getDesc();
    // Loads or stores cannot be moved past a store to the delay slot
    // and stores cannot be moved past a load. 
    if (MCID.mayLoad()) {
      if (sawStore)
        return true;
      sawLoad = true;
    }
  
    if (MCID.mayStore()) {
      if (sawStore)
        return true;
      sawStore = true;
      if (sawLoad)
        return true;
    }
  
    assert((!MCID.isCall() && !MCID.isReturn()) &&
           "Cannot put calls or returns in delay slot.");
  
    for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
      const MachineOperand &MO = candidate->getOperand(i);
      unsigned Reg;
  
      if (!MO.isReg() || !(Reg = MO.getReg()))
        continue; // skip
  
      if (MO.isDef()) {
        // check whether Reg is defined or used before delay slot.
        if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
          return true;
      }
      if (MO.isUse()) {
        // check whether Reg is defined before delay slot.
        if (IsRegInSet(RegDefs, Reg))
          return true;
      }
    }
    return false;
  }
  
  // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
  void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
                              SmallSet<unsigned, 32>& RegDefs,
                              SmallSet<unsigned, 32>& RegUses) {
    // If MI is a call or return, just examine the explicit non-variadic operands.
    MCInstrDesc MCID = MI->getDesc();
    unsigned e = MCID.isCall() || MCID.isReturn() ? MCID.getNumOperands() :
                                                    MI->getNumOperands();
    
    // Add RA to RegDefs to prevent users of RA from going into delay slot. 
    if (MCID.isCall())
      RegDefs.insert(Mips::RA);
  
    for (unsigned i = 0; i != e; ++i) {
      const MachineOperand &MO = MI->getOperand(i);
      unsigned Reg;
  
      if (!MO.isReg() || !(Reg = MO.getReg()))
        continue;
  
      if (MO.isDef())
        RegDefs.insert(Reg);
      else if (MO.isUse())
        RegUses.insert(Reg);
    }
  }
  
  //returns true if the Reg or its alias is in the RegSet.
  bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) {
    if (RegSet.count(Reg))
      return true;
    // check Aliased Registers
    for (const unsigned *Alias = TM.getRegisterInfo()->getAliasSet(Reg);
         *Alias; ++Alias)
      if (RegSet.count(*Alias))
        return true;
  
    return false;
  }
  