TwoAddressInstructionPass.cpp

  }

  return false;
}

/// runOnMachineFunction - Reduce two-address instructions to two operands.
///
bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
  DEBUG(dbgs() << "Machine Function\n");
  const TargetMachine &TM = MF.getTarget();
  MRI = &MF.getRegInfo();
  TII = TM.getInstrInfo();
  TRI = TM.getRegisterInfo();
  LV = getAnalysisIfAvailable<LiveVariables>();
  AA = &getAnalysis<AliasAnalysis>();

  bool MadeChange = false;

  DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
  DEBUG(dbgs() << "********** Function: " 
        << MF.getFunction()->getName() << '\n');

  // ReMatRegs - Keep track of the registers whose def's are remat'ed.
  BitVector ReMatRegs;
  ReMatRegs.resize(MRI->getLastVirtReg()+1);

  typedef DenseMap<unsigned, SmallVector<std::pair<unsigned, unsigned>, 4> >
    TiedOperandMap;
  TiedOperandMap TiedOperands(4);

  SmallPtrSet<MachineInstr*, 8> Processed;
  for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
       mbbi != mbbe; ++mbbi) {
    unsigned Dist = 0;
    DistanceMap.clear();
    SrcRegMap.clear();
    DstRegMap.clear();
    Processed.clear();
    for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
         mi != me; ) {
      MachineBasicBlock::iterator nmi = llvm::next(mi);
      if (mi->isDebugValue()) {
        mi = nmi;
        continue;
      }

      // Remember REG_SEQUENCE instructions, we'll deal with them later.
      if (mi->isRegSequence())
        RegSequences.push_back(&*mi);

      const TargetInstrDesc &TID = mi->getDesc();
      bool FirstTied = true;

      DistanceMap.insert(std::make_pair(mi, ++Dist));

      ProcessCopy(&*mi, &*mbbi, Processed);

      // First scan through all the tied register uses in this instruction
      // and record a list of pairs of tied operands for each register.
      unsigned NumOps = mi->isInlineAsm()
        ? mi->getNumOperands() : TID.getNumOperands();
      for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
        unsigned DstIdx = 0;
        if (!mi->isRegTiedToDefOperand(SrcIdx, &DstIdx))
          continue;

        if (FirstTied) {
          FirstTied = false;
          ++NumTwoAddressInstrs;
          DEBUG(dbgs() << '\t' << *mi);
        }

        assert(mi->getOperand(SrcIdx).isReg() &&
               mi->getOperand(SrcIdx).getReg() &&
               mi->getOperand(SrcIdx).isUse() &&
               "two address instruction invalid");

        unsigned regB = mi->getOperand(SrcIdx).getReg();
        TiedOperandMap::iterator OI = TiedOperands.find(regB);
        if (OI == TiedOperands.end()) {
          SmallVector<std::pair<unsigned, unsigned>, 4> TiedPair;
          OI = TiedOperands.insert(std::make_pair(regB, TiedPair)).first;
        }
        OI->second.push_back(std::make_pair(SrcIdx, DstIdx));
      }

      // Now iterate over the information collected above.
      for (TiedOperandMap::iterator OI = TiedOperands.begin(),
             OE = TiedOperands.end(); OI != OE; ++OI) {
        SmallVector<std::pair<unsigned, unsigned>, 4> &TiedPairs = OI->second;

        // If the instruction has a single pair of tied operands, try some
        // transformations that may either eliminate the tied operands or
        // improve the opportunities for coalescing away the register copy.
        if (TiedOperands.size() == 1 && TiedPairs.size() == 1) {
          unsigned SrcIdx = TiedPairs[0].first;
          unsigned DstIdx = TiedPairs[0].second;

          // If the registers are already equal, nothing needs to be done.
          if (mi->getOperand(SrcIdx).getReg() ==
              mi->getOperand(DstIdx).getReg())
            break; // Done with this instruction.

          if (TryInstructionTransform(mi, nmi, mbbi, SrcIdx, DstIdx, Dist))
            break; // The tied operands have been eliminated.
        }

        bool RemovedKillFlag = false;
        bool AllUsesCopied = true;
        unsigned LastCopiedReg = 0;
        unsigned regB = OI->first;
        for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
          unsigned SrcIdx = TiedPairs[tpi].first;
          unsigned DstIdx = TiedPairs[tpi].second;
          unsigned regA = mi->getOperand(DstIdx).getReg();
          // Grab regB from the instruction because it may have changed if the
          // instruction was commuted.
          regB = mi->getOperand(SrcIdx).getReg();

          if (regA == regB) {
            // The register is tied to multiple destinations (or else we would
            // not have continued this far), but this use of the register
            // already matches the tied destination.  Leave it.
            AllUsesCopied = false;
            continue;
          }
          LastCopiedReg = regA;

          assert(TargetRegisterInfo::isVirtualRegister(regB) &&
                 "cannot make instruction into two-address form");

#ifndef NDEBUG
          // First, verify that we don't have a use of "a" in the instruction
          // (a = b + a for example) because our transformation will not
          // work. This should never occur because we are in SSA form.
          for (unsigned i = 0; i != mi->getNumOperands(); ++i)
            assert(i == DstIdx ||
                   !mi->getOperand(i).isReg() ||
                   mi->getOperand(i).getReg() != regA);
#endif

          // Emit a copy or rematerialize the definition.
          const TargetRegisterClass *rc = MRI->getRegClass(regB);
          MachineInstr *DefMI = MRI->getVRegDef(regB);
          // If it's safe and profitable, remat the definition instead of
          // copying it.
          if (DefMI &&
              DefMI->getDesc().isAsCheapAsAMove() &&
              DefMI->isSafeToReMat(TII, AA, regB) &&
              isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist)){
            DEBUG(dbgs() << "2addr: REMATTING : " << *DefMI << "\n");
            unsigned regASubIdx = mi->getOperand(DstIdx).getSubReg();
            TII->reMaterialize(*mbbi, mi, regA, regASubIdx, DefMI, *TRI);
            ReMatRegs.set(regB);
            ++NumReMats;
          } else {
            bool Emitted = TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc,
                                             mi->getDebugLoc());
            (void)Emitted;
            assert(Emitted && "Unable to issue a copy instruction!\n");
          }

          MachineBasicBlock::iterator prevMI = prior(mi);
          // Update DistanceMap.
          DistanceMap.insert(std::make_pair(prevMI, Dist));
          DistanceMap[mi] = ++Dist;

          DEBUG(dbgs() << "\t\tprepend:\t" << *prevMI);

          MachineOperand &MO = mi->getOperand(SrcIdx);
          assert(MO.isReg() && MO.getReg() == regB && MO.isUse() &&
                 "inconsistent operand info for 2-reg pass");
          if (MO.isKill()) {
            MO.setIsKill(false);
            RemovedKillFlag = true;
          }
          MO.setReg(regA);
        }

        if (AllUsesCopied) {
          // Replace other (un-tied) uses of regB with LastCopiedReg.
          for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
            MachineOperand &MO = mi->getOperand(i);
            if (MO.isReg() && MO.getReg() == regB && MO.isUse()) {
              if (MO.isKill()) {
                MO.setIsKill(false);
                RemovedKillFlag = true;
              }
              MO.setReg(LastCopiedReg);
            }
          }

          // Update live variables for regB.
          if (RemovedKillFlag && LV && LV->getVarInfo(regB).removeKill(mi))
            LV->addVirtualRegisterKilled(regB, prior(mi));

        } else if (RemovedKillFlag) {
          // Some tied uses of regB matched their destination registers, so
          // regB is still used in this instruction, but a kill flag was
          // removed from a different tied use of regB, so now we need to add
          // a kill flag to one of the remaining uses of regB.
          for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
            MachineOperand &MO = mi->getOperand(i);
            if (MO.isReg() && MO.getReg() == regB && MO.isUse()) {
              MO.setIsKill(true);
              break;
            }
          }
        }

        // Schedule the source copy / remat inserted to form two-address
        // instruction. FIXME: Does it matter the distance map may not be
        // accurate after it's scheduled?
        TII->scheduleTwoAddrSource(prior(mi), mi, *TRI);

        MadeChange = true;

        DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
      }

      // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form.
      if (mi->isInsertSubreg()) {
        // From %reg = INSERT_SUBREG %reg, %subreg, subidx
        // To   %reg:subidx = COPY %subreg
        unsigned SubIdx = mi->getOperand(3).getImm();
        mi->RemoveOperand(3);
        assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
        mi->getOperand(0).setSubReg(SubIdx);
        mi->RemoveOperand(1);
        mi->setDesc(TII->get(TargetOpcode::COPY));
        DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
      }

      // Clear TiedOperands here instead of at the top of the loop
      // since most instructions do not have tied operands.
      TiedOperands.clear();
      mi = nmi;
    }
  }

  // Some remat'ed instructions are dead.
  int VReg = ReMatRegs.find_first();
  while (VReg != -1) {
    if (MRI->use_nodbg_empty(VReg)) {
      MachineInstr *DefMI = MRI->getVRegDef(VReg);
      DefMI->eraseFromParent();
    }
    VReg = ReMatRegs.find_next(VReg);
  }

  // Eliminate REG_SEQUENCE instructions. Their whole purpose was to preseve
  // SSA form. It's now safe to de-SSA.
  MadeChange |= EliminateRegSequences();

  return MadeChange;
}

static void UpdateRegSequenceSrcs(unsigned SrcReg,
                                  unsigned DstReg, unsigned SubIdx,
                                  MachineRegisterInfo *MRI,
                                  const TargetRegisterInfo &TRI) {
  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg),
         RE = MRI->reg_end(); RI != RE; ) {
    MachineOperand &MO = RI.getOperand();
    ++RI;
    MO.substVirtReg(DstReg, SubIdx, TRI);
  }
}

/// CoalesceExtSubRegs - If a number of sources of the REG_SEQUENCE are
/// EXTRACT_SUBREG from the same register and to the same virtual register
/// with different sub-register indices, attempt to combine the
/// EXTRACT_SUBREGs and pre-coalesce them. e.g.
/// %reg1026<def> = VLDMQ %reg1025<kill>, 260, pred:14, pred:%reg0
/// %reg1029:6<def> = EXTRACT_SUBREG %reg1026, 6
/// %reg1029:5<def> = EXTRACT_SUBREG %reg1026<kill>, 5
/// Since D subregs 5, 6 can combine to a Q register, we can coalesce
/// reg1026 to reg1029.
void
TwoAddressInstructionPass::CoalesceExtSubRegs(SmallVector<unsigned,4> &Srcs,
                                              unsigned DstReg) {
  SmallSet<unsigned, 4> Seen;
  for (unsigned i = 0, e = Srcs.size(); i != e; ++i) {
    unsigned SrcReg = Srcs[i];
    if (!Seen.insert(SrcReg))
      continue;

    // Check that the instructions are all in the same basic block.
    MachineInstr *SrcDefMI = MRI->getVRegDef(SrcReg);
    MachineInstr *DstDefMI = MRI->getVRegDef(DstReg);
    if (SrcDefMI->getParent() != DstDefMI->getParent())
      continue;

    // If there are no other uses than copies which feed into
    // the reg_sequence, then we might be able to coalesce them.
    bool CanCoalesce = true;
    SmallVector<unsigned, 4> SrcSubIndices, DstSubIndices;
    for (MachineRegisterInfo::use_nodbg_iterator
           UI = MRI->use_nodbg_begin(SrcReg),
           UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
      MachineInstr *UseMI = &*UI;
      if (!UseMI->isCopy() || UseMI->getOperand(0).getReg() != DstReg) {
        CanCoalesce = false;
        break;
      }
      SrcSubIndices.push_back(UseMI->getOperand(1).getSubReg());
      DstSubIndices.push_back(UseMI->getOperand(0).getSubReg());
    }

    if (!CanCoalesce || SrcSubIndices.size() < 2)
      continue;

    // Check that the source subregisters can be combined.
    std::sort(SrcSubIndices.begin(), SrcSubIndices.end());
    unsigned NewSrcSubIdx = 0;
    if (!TRI->canCombineSubRegIndices(MRI->getRegClass(SrcReg), SrcSubIndices,
                                      NewSrcSubIdx))
      continue;

    // Check that the destination subregisters can also be combined.
    std::sort(DstSubIndices.begin(), DstSubIndices.end());
    unsigned NewDstSubIdx = 0;
    if (!TRI->canCombineSubRegIndices(MRI->getRegClass(DstReg), DstSubIndices,
                                      NewDstSubIdx))
      continue;

    // If neither source nor destination can be combined to the full register,
    // just give up.  This could be improved if it ever matters.
    if (NewSrcSubIdx != 0 && NewDstSubIdx != 0)
      continue;

    // Now that we know that all the uses are extract_subregs and that those
    // subregs can somehow be combined, scan all the extract_subregs again to
    // make sure the subregs are in the right order and can be composed.
    MachineInstr *SomeMI = 0;
    CanCoalesce = true;
    for (MachineRegisterInfo::use_nodbg_iterator
           UI = MRI->use_nodbg_begin(SrcReg),
           UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
      MachineInstr *UseMI = &*UI;
      assert(UseMI->isCopy());
      unsigned DstSubIdx = UseMI->getOperand(0).getSubReg();
      unsigned SrcSubIdx = UseMI->getOperand(1).getSubReg();
      assert(DstSubIdx != 0 && "missing subreg from RegSequence elimination");
      if ((NewDstSubIdx == 0 &&
           TRI->composeSubRegIndices(NewSrcSubIdx, DstSubIdx) != SrcSubIdx) ||
          (NewSrcSubIdx == 0 &&
           TRI->composeSubRegIndices(NewDstSubIdx, SrcSubIdx) != DstSubIdx)) {
        CanCoalesce = false;
        break;
      }
      // Keep track of one of the uses.
      SomeMI = UseMI;
    }
    if (!CanCoalesce)
      continue;

    // Insert a copy to replace the original.
    MachineBasicBlock::iterator InsertLoc = SomeMI;
    MachineInstr *CopyMI = BuildMI(*SomeMI->getParent(), SomeMI,
                                   SomeMI->getDebugLoc(),
                                   TII->get(TargetOpcode::COPY))
      .addReg(DstReg, RegState::Define, NewDstSubIdx)
      .addReg(SrcReg, 0, NewSrcSubIdx);

    // Remove all the old extract instructions.
    for (MachineRegisterInfo::use_nodbg_iterator
           UI = MRI->use_nodbg_begin(SrcReg),
           UE = MRI->use_nodbg_end(); UI != UE; ) {
      MachineInstr *UseMI = &*UI;
      ++UI;
      if (UseMI == CopyMI)
        continue;
      assert(UseMI->isCopy());
      // Move any kills to the new copy or extract instruction.
      if (UseMI->getOperand(1).isKill()) {
        CopyMI->getOperand(1).setIsKill();
        if (LV)
          // Update live variables
          LV->replaceKillInstruction(SrcReg, UseMI, &*CopyMI);
      }
      UseMI->eraseFromParent();
    }
  }
}

static bool HasOtherRegSequenceUses(unsigned Reg, MachineInstr *RegSeq,
                                    MachineRegisterInfo *MRI) {
  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
         UE = MRI->use_end(); UI != UE; ++UI) {
    MachineInstr *UseMI = &*UI;
    if (UseMI != RegSeq && UseMI->isRegSequence())
      return true;
  }
  return false;
}

/// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as part
/// of the de-ssa process. This replaces sources of REG_SEQUENCE as
/// sub-register references of the register defined by REG_SEQUENCE. e.g.
///
/// %reg1029<def>, %reg1030<def> = VLD1q16 %reg1024<kill>, ...
/// %reg1031<def> = REG_SEQUENCE %reg1029<kill>, 5, %reg1030<kill>, 6
/// =>
/// %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
bool TwoAddressInstructionPass::EliminateRegSequences() {
  if (RegSequences.empty())
    return false;

  for (unsigned i = 0, e = RegSequences.size(); i != e; ++i) {
    MachineInstr *MI = RegSequences[i];
    unsigned DstReg = MI->getOperand(0).getReg();
    if (MI->getOperand(0).getSubReg() ||
        TargetRegisterInfo::isPhysicalRegister(DstReg) ||
        !(MI->getNumOperands() & 1)) {
      DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI);
      llvm_unreachable(0);
    }

    bool IsImpDef = true;
    SmallVector<unsigned, 4> RealSrcs;
    SmallSet<unsigned, 4> Seen;
    for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) {
      unsigned SrcReg = MI->getOperand(i).getReg();
      if (MI->getOperand(i).getSubReg() ||
          TargetRegisterInfo::isPhysicalRegister(SrcReg)) {
        DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI);
        llvm_unreachable(0);
      }

      MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
      if (DefMI->isImplicitDef()) {
        DefMI->eraseFromParent();
        continue;
      }
      IsImpDef = false;

      // Remember COPY sources. These might be candidate for coalescing.
      if (DefMI->isCopy())
        RealSrcs.push_back(DefMI->getOperand(1).getReg());

      if (!Seen.insert(SrcReg) ||
          MI->getParent() != DefMI->getParent() ||
          !MI->getOperand(i).isKill() ||
          HasOtherRegSequenceUses(SrcReg, MI, MRI)) {
        // REG_SEQUENCE cannot have duplicated operands, add a copy.
        // Also add an copy if the source is live-in the block. We don't want
        // to end up with a partial-redef of a livein, e.g.
        // BB0:
        // reg1051:10<def> =
        // ...
        // BB1:
        // ... = reg1051:10
        // BB2:
        // reg1051:9<def> =
        // LiveIntervalAnalysis won't like it.
        //
        // If the REG_SEQUENCE doesn't kill its source, keeping live variables
        // correctly up to date becomes very difficult. Insert a copy.
        //
        const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
        unsigned NewReg = MRI->createVirtualRegister(RC);
        MachineBasicBlock::iterator InsertLoc = MI;
        bool Emitted =
          TII->copyRegToReg(*MI->getParent(), InsertLoc, NewReg, SrcReg, RC, RC,
                            MI->getDebugLoc());
        (void)Emitted;
        assert(Emitted && "Unable to issue a copy instruction!\n");
        MI->getOperand(i).setReg(NewReg);
        if (MI->getOperand(i).isKill()) {
          MachineBasicBlock::iterator CopyMI = prior(InsertLoc);
          MachineOperand *KillMO = CopyMI->findRegisterUseOperand(SrcReg);
          KillMO->setIsKill();
          if (LV)
            // Update live variables
            LV->replaceKillInstruction(SrcReg, MI, &*CopyMI);
        }
      }
    }

    for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) {
      unsigned SrcReg = MI->getOperand(i).getReg();
      unsigned SubIdx = MI->getOperand(i+1).getImm();
      UpdateRegSequenceSrcs(SrcReg, DstReg, SubIdx, MRI, *TRI);
    }

    if (IsImpDef) {
      DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF");
      MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
      for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
        MI->RemoveOperand(j);      
    } else {
      DEBUG(dbgs() << "Eliminated: " << *MI);
      MI->eraseFromParent();
    }

    // Try coalescing some EXTRACT_SUBREG instructions. This can create
    // INSERT_SUBREG instructions that must have <undef> flags added by
    // LiveIntervalAnalysis, so only run it when LiveVariables is available.
    if (LV)
      CoalesceExtSubRegs(RealSrcs, DstReg);
  }

  RegSequences.clear();
  return true;
}