TwoAddressInstructionPass.cpp

        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;
            }
          }
        }
          
        MadeChange = true;

        DEBUG(dbgs() << "\t\trewrite 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 SrcIdx,
                                  MachineRegisterInfo *MRI) {
  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg),
         RE = MRI->reg_end(); RI != RE; ) {
    MachineOperand &MO = RI.getOperand();
    ++RI;
    MO.setReg(DstReg);
    assert(MO.getSubReg() == 0);
    MO.setSubReg(SrcIdx);
  }
}

/// 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);
    }

    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;
      }

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

      if (!Seen.insert(SrcReg) || MI->getParent() != DefMI->getParent()) {
        // REG_SEQUENCE cannot have duplicated operands, add a copy.
        // Also add an copy if the source if 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.
        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 SrcIdx = MI->getOperand(i+1).getImm();
      UpdateRegSequenceSrcs(SrcReg, DstReg, SrcIdx, MRI);
    }

    DEBUG(dbgs() << "Eliminated: " << *MI);
    MI->eraseFromParent();

    // Try coalescing some EXTRACT_SUBREG instructions.
    Seen.clear();
    for (unsigned i = 0, e = RealSrcs.size(); i != e; ++i) {
      unsigned SrcReg = RealSrcs[i];
      if (!Seen.insert(SrcReg))
        continue;

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

      if (!CanCoalesce)
        continue;

      // %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.
      std::sort(SubIndices.begin(), SubIndices.end());
      unsigned NewSubIdx = 0;
      if (TRI->canCombinedSubRegIndex(MRI->getRegClass(SrcReg), SubIndices,
                                      NewSubIdx))
        UpdateRegSequenceSrcs(SrcReg, DstReg, NewSubIdx, MRI);
    }
  }

  RegSequences.clear();
  return true;
}