VirtRegRewriter.cpp

          if (MR & VirtRegMap::isModRef) {
            unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
            SmallVector<MachineInstr*, 4> NewMIs;
            // We can reuse this physreg as long as we are allowed to clobber
            // the value and there isn't an earlier def that has already clobbered
            // the physreg.
            if (PhysReg &&
                !ReusedOperands.isClobbered(PhysReg) &&
                Spills.canClobberPhysReg(PhysReg) &&
                !TII->isStoreToStackSlot(&MI, SS)) { // Not profitable!
              MachineOperand *KillOpnd =
                DeadStore->findRegisterUseOperand(PhysReg, true);
              // Note, if the store is storing a sub-register, it's possible the
              // super-register is needed below.
              if (KillOpnd && !KillOpnd->getSubReg() &&
                  TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, true,NewMIs)){
                MBB.insert(MII, NewMIs[0]);
                NewStore = NewMIs[1];
                MBB.insert(MII, NewStore);
                VRM.addSpillSlotUse(SS, NewStore);
                InvalidateKills(MI, TRI, RegKills, KillOps);
                VRM.RemoveMachineInstrFromMaps(&MI);
                MBB.erase(&MI);
                Erased = true;
                --NextMII;
                --NextMII;  // backtrack to the unfolded instruction.
                BackTracked = true;
                isDead = true;
                ++NumSUnfold;
              }
            }
          }

          if (isDead) {  // Previous store is dead.
            // If we get here, the store is dead, nuke it now.
            DOUT << "Removed dead store:\t" << *DeadStore;
            InvalidateKills(*DeadStore, TRI, RegKills, KillOps);
            VRM.RemoveMachineInstrFromMaps(DeadStore);
            MBB.erase(DeadStore);
            if (!NewStore)
              ++NumDSE;
          }

          MaybeDeadStores[SS] = NULL;
          if (NewStore) {
            // Treat this store as a spill merged into a copy. That makes the
            // stack slot value available.
            VRM.virtFolded(VirtReg, NewStore, VirtRegMap::isMod);
            goto ProcessNextInst;
          }
        }

        // If the spill slot value is available, and this is a new definition of
        // the value, the value is not available anymore.
        if (MR & VirtRegMap::isMod) {
          // Notice that the value in this stack slot has been modified.
          Spills.ModifyStackSlotOrReMat(SS);
          
          // If this is *just* a mod of the value, check to see if this is just a
          // store to the spill slot (i.e. the spill got merged into the copy). If
          // so, realize that the vreg is available now, and add the store to the
          // MaybeDeadStore info.
          int StackSlot;
          if (!(MR & VirtRegMap::isRef)) {
            if (unsigned SrcReg = TII->isStoreToStackSlot(&MI, StackSlot)) {
              assert(TargetRegisterInfo::isPhysicalRegister(SrcReg) &&
                     "Src hasn't been allocated yet?");

              if (CommuteToFoldReload(MBB, MII, VirtReg, SrcReg, StackSlot,
                                      Spills, RegKills, KillOps, TRI, VRM)) {
                NextMII = next(MII);
                BackTracked = true;
                goto ProcessNextInst;
              }

              // Okay, this is certainly a store of SrcReg to [StackSlot].  Mark
              // this as a potentially dead store in case there is a subsequent
              // store into the stack slot without a read from it.
              MaybeDeadStores[StackSlot] = &MI;

              // If the stack slot value was previously available in some other
              // register, change it now.  Otherwise, make the register
              // available in PhysReg.
              Spills.addAvailable(StackSlot, SrcReg, MI.killsRegister(SrcReg));
            }
          }
        }
      }

      // Process all of the spilled defs.
      for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
        MachineOperand &MO = MI.getOperand(i);
        if (!(MO.isReg() && MO.getReg() && MO.isDef()))
          continue;

        unsigned VirtReg = MO.getReg();
        if (!TargetRegisterInfo::isVirtualRegister(VirtReg)) {
          // Check to see if this is a noop copy.  If so, eliminate the
          // instruction before considering the dest reg to be changed.
          unsigned Src, Dst, SrcSR, DstSR;
          if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst) {
            ++NumDCE;
            DOUT << "Removing now-noop copy: " << MI;
            SmallVector<unsigned, 2> KillRegs;
            InvalidateKills(MI, TRI, RegKills, KillOps, &KillRegs);
            if (MO.isDead() && !KillRegs.empty()) {
              // Source register or an implicit super/sub-register use is killed.
              assert(KillRegs[0] == Dst ||
                     TRI->isSubRegister(KillRegs[0], Dst) ||
                     TRI->isSuperRegister(KillRegs[0], Dst));
              // Last def is now dead.
              TransferDeadness(&MBB, Dist, Src, RegKills, KillOps, VRM);
            }
            VRM.RemoveMachineInstrFromMaps(&MI);
            MBB.erase(&MI);
            Erased = true;
            Spills.disallowClobberPhysReg(VirtReg);
            goto ProcessNextInst;
          }
            
          // If it's not a no-op copy, it clobbers the value in the destreg.
          Spills.ClobberPhysReg(VirtReg);
          ReusedOperands.markClobbered(VirtReg);
   
          // Check to see if this instruction is a load from a stack slot into
          // a register.  If so, this provides the stack slot value in the reg.
          int FrameIdx;
          if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) {
            assert(DestReg == VirtReg && "Unknown load situation!");

            // If it is a folded reference, then it's not safe to clobber.
            bool Folded = FoldedSS.count(FrameIdx);
            // Otherwise, if it wasn't available, remember that it is now!
            Spills.addAvailable(FrameIdx, DestReg, !Folded);
            goto ProcessNextInst;
          }
              
          continue;
        }

        unsigned SubIdx = MO.getSubReg();
        bool DoReMat = VRM.isReMaterialized(VirtReg);
        if (DoReMat)
          ReMatDefs.insert(&MI);

        // The only vregs left are stack slot definitions.
        int StackSlot = VRM.getStackSlot(VirtReg);
        const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg);

        // If this def is part of a two-address operand, make sure to execute
        // the store from the correct physical register.
        unsigned PhysReg;
        unsigned TiedOp;
        if (MI.isRegTiedToUseOperand(i, &TiedOp)) {
          PhysReg = MI.getOperand(TiedOp).getReg();
          if (SubIdx) {
            unsigned SuperReg = findSuperReg(RC, PhysReg, SubIdx, TRI);
            assert(SuperReg && TRI->getSubReg(SuperReg, SubIdx) == PhysReg &&
                   "Can't find corresponding super-register!");
            PhysReg = SuperReg;
          }
        } else {
          PhysReg = VRM.getPhys(VirtReg);
          if (ReusedOperands.isClobbered(PhysReg)) {
            // Another def has taken the assigned physreg. It must have been a
            // use&def which got it due to reuse. Undo the reuse!
            PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI, 
                                 Spills, MaybeDeadStores, RegKills, KillOps, VRM);
          }
        }

        assert(PhysReg && "VR not assigned a physical register?");
        RegInfo->setPhysRegUsed(PhysReg);
        unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
        ReusedOperands.markClobbered(RReg);
        MI.getOperand(i).setReg(RReg);
        MI.getOperand(i).setSubReg(0);

        if (!MO.isDead()) {
          MachineInstr *&LastStore = MaybeDeadStores[StackSlot];
          SpillRegToStackSlot(MBB, MII, -1, PhysReg, StackSlot, RC, true,
                            LastStore, Spills, ReMatDefs, RegKills, KillOps, VRM);
          NextMII = next(MII);

          // Check to see if this is a noop copy.  If so, eliminate the
          // instruction before considering the dest reg to be changed.
          {
            unsigned Src, Dst, SrcSR, DstSR;
            if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst) {
              ++NumDCE;
              DOUT << "Removing now-noop copy: " << MI;
              InvalidateKills(MI, TRI, RegKills, KillOps);
              VRM.RemoveMachineInstrFromMaps(&MI);
              MBB.erase(&MI);
              Erased = true;
              UpdateKills(*LastStore, TRI, RegKills, KillOps);
              goto ProcessNextInst;
            }
          }
        }    
      }
    ProcessNextInst:
      DistanceMap.insert(std::make_pair(&MI, Dist++));
      if (!Erased && !BackTracked) {
        for (MachineBasicBlock::iterator II = &MI; II != NextMII; ++II)
          UpdateKills(*II, TRI, RegKills, KillOps);
      }
      MII = NextMII;
    }

  }

};

llvm::VirtRegRewriter* llvm::createVirtRegRewriter() {
  switch (RewriterOpt) {
  default: assert(0 && "Unreachable!");
  case local:
    return new LocalRewriter();
  case simple:
    return new SimpleRewriter();
  case trivial:
    return new TrivialRewriter();
  }
}