Make this const.
[oota-llvm.git] / lib / CodeGen / TwoAddressInstructionPass.cpp
index 4aa143ea58c815eda2a6ca8d9009678069f7a1e8..3c404046f15e49e875ccde2756fb780bd8b33bce 100644 (file)
@@ -88,6 +88,9 @@ namespace {
     bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist,
                            unsigned &LastDef);
 
+    MachineInstr *FindLastUseInMBB(unsigned Reg, MachineBasicBlock *MBB,
+                                   unsigned Dist);
+
     bool isProfitableToCommute(unsigned regB, unsigned regC,
                                MachineInstr *MI, MachineBasicBlock *MBB,
                                unsigned Dist);
@@ -96,6 +99,13 @@ namespace {
                             MachineFunction::iterator &mbbi,
                             unsigned RegB, unsigned RegC, unsigned Dist);
 
+    bool isProfitableToConv3Addr(unsigned RegA);
+
+    bool ConvertInstTo3Addr(MachineBasicBlock::iterator &mi,
+                            MachineBasicBlock::iterator &nmi,
+                            MachineFunction::iterator &mbbi,
+                            unsigned RegB, unsigned Dist);
+
     void ProcessCopy(MachineInstr *MI, MachineBasicBlock *MBB,
                      SmallPtrSet<MachineInstr*, 8> &Processed);
   public:
@@ -170,7 +180,7 @@ bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
     break;
   }
 
-  if (!KillMI || KillMI->getParent() != MBB)
+  if (!KillMI || KillMI->getParent() != MBB || KillMI == MI)
     return false;
 
   // If any of the definitions are used by another instruction between the
@@ -303,6 +313,31 @@ bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg,
   return !(LastUse > LastDef && LastUse < Dist);
 }
 
+MachineInstr *TwoAddressInstructionPass::FindLastUseInMBB(unsigned Reg,
+                                                         MachineBasicBlock *MBB,
+                                                         unsigned Dist) {
+  unsigned LastUseDist = 0;
+  MachineInstr *LastUse = 0;
+  for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
+         E = MRI->reg_end(); I != E; ++I) {
+    MachineOperand &MO = I.getOperand();
+    MachineInstr *MI = MO.getParent();
+    if (MI->getParent() != MBB)
+      continue;
+    DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
+    if (DI == DistanceMap.end())
+      continue;
+    if (DI->second >= Dist)
+      continue;
+
+    if (MO.isUse() && DI->second > LastUseDist) {
+      LastUse = DI->first;
+      LastUseDist = DI->second;
+    }
+  }
+  return LastUse;
+}
+
 /// isCopyToReg - Return true if the specified MI is a copy instruction or
 /// a extract_subreg instruction. It also returns the source and destination
 /// registers and whether they are physical registers by reference.
@@ -319,6 +354,9 @@ static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII,
     } else if (MI.getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
       DstReg = MI.getOperand(0).getReg();
       SrcReg = MI.getOperand(2).getReg();
+    } else if (MI.getOpcode() == TargetInstrInfo::SUBREG_TO_REG) {
+      DstReg = MI.getOperand(0).getReg();
+      SrcReg = MI.getOperand(2).getReg();
     }
   }
 
@@ -330,11 +368,53 @@ static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII,
   return false;
 }
 
+/// isKilled - Test if the given register value, which is used by the given
+/// instruction, is killed by the given instruction. This looks through
+/// coalescable copies to see if the original value is potentially not killed.
+///
+/// For example, in this code:
+///
+///   %reg1034 = copy %reg1024
+///   %reg1035 = copy %reg1025<kill>
+///   %reg1036 = add %reg1034<kill>, %reg1035<kill>
+///
+/// %reg1034 is not considered to be killed, since it is copied from a
+/// register which is not killed. Treating it as not killed lets the
+/// normal heuristics commute the (two-address) add, which lets
+/// coalescing eliminate the extra copy.
+///
+static bool isKilled(MachineInstr &MI, unsigned Reg,
+                     const MachineRegisterInfo *MRI,
+                     const TargetInstrInfo *TII) {
+  MachineInstr *DefMI = &MI;
+  for (;;) {
+    if (!DefMI->killsRegister(Reg))
+      return false;
+    if (TargetRegisterInfo::isPhysicalRegister(Reg))
+      return true;
+    MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg);
+    // If there are multiple defs, we can't do a simple analysis, so just
+    // go with what the kill flag says.
+    if (next(Begin) != MRI->def_end())
+      return true;
+    DefMI = &*Begin;
+    bool IsSrcPhys, IsDstPhys;
+    unsigned SrcReg,  DstReg;
+    // If the def is something other than a copy, then it isn't going to
+    // be coalesced, so follow the kill flag.
+    if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
+      return true;
+    Reg = SrcReg;
+  }
+}
+
 /// isTwoAddrUse - Return true if the specified MI uses the specified register
 /// as a two-address use. If so, return the destination register by reference.
 static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) {
   const TargetInstrDesc &TID = MI.getDesc();
-  for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
+  unsigned NumOps = (MI.getOpcode() == TargetInstrInfo::INLINEASM)
+    ? MI.getNumOperands() : TID.getNumOperands();
+  for (unsigned i = 0; i != NumOps; ++i) {
     const MachineOperand &MO = MI.getOperand(i);
     if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
       continue;
@@ -353,7 +433,7 @@ static
 MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB,
                                      MachineRegisterInfo *MRI,
                                      const TargetInstrInfo *TII,
-                                     bool &isCopy,
+                                     bool &IsCopy,
                                      unsigned &DstReg, bool &IsDstPhys) {
   MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg);
   if (UI == MRI->use_end())
@@ -366,11 +446,15 @@ MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB,
     return 0;
   unsigned SrcReg;
   bool IsSrcPhys;
-  if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
+  if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
+    IsCopy = true;
     return &UseMI;
+  }
   IsDstPhys = false;
-  if (isTwoAddrUse(UseMI, Reg, DstReg))
+  if (isTwoAddrUse(UseMI, Reg, DstReg)) {
+    IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
     return &UseMI;
+  }
   return 0;
 }
 
@@ -503,6 +587,53 @@ TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi,
   return true;
 }
 
+/// isProfitableToConv3Addr - Return true if it is profitable to convert the
+/// given 2-address instruction to a 3-address one.
+bool
+TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA) {
+  // Look for situations like this:
+  // %reg1024<def> = MOV r1
+  // %reg1025<def> = MOV r0
+  // %reg1026<def> = ADD %reg1024, %reg1025
+  // r2            = MOV %reg1026
+  // Turn ADD into a 3-address instruction to avoid a copy.
+  unsigned FromRegA = getMappedReg(RegA, SrcRegMap);
+  unsigned ToRegA = getMappedReg(RegA, DstRegMap);
+  return (FromRegA && ToRegA && !regsAreCompatible(FromRegA, ToRegA, TRI));
+}
+
+/// ConvertInstTo3Addr - Convert the specified two-address instruction into a
+/// three address one. Return true if this transformation was successful.
+bool
+TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi,
+                                              MachineBasicBlock::iterator &nmi,
+                                              MachineFunction::iterator &mbbi,
+                                              unsigned RegB, unsigned Dist) {
+  MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV);
+  if (NewMI) {
+    DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
+    DOUT << "2addr:         TO 3-ADDR: " << *NewMI;
+    bool Sunk = false;
+
+    if (NewMI->findRegisterUseOperand(RegB, false, TRI))
+      // FIXME: Temporary workaround. If the new instruction doesn't
+      // uses RegB, convertToThreeAddress must have created more
+      // then one instruction.
+      Sunk = Sink3AddrInstruction(mbbi, NewMI, RegB, mi);
+
+    mbbi->erase(mi); // Nuke the old inst.
+
+    if (!Sunk) {
+      DistanceMap.insert(std::make_pair(NewMI, Dist));
+      mi = NewMI;
+      nmi = next(mi);
+    }
+    return true;
+  }
+
+  return false;
+}
+
 /// ProcessCopy - If the specified instruction is not yet processed, process it
 /// if it's a copy. For a copy instruction, we find the physical registers the
 /// source and destination registers might be mapped to. These are kept in
@@ -529,18 +660,18 @@ void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI,
   if (IsDstPhys && !IsSrcPhys)
     DstRegMap.insert(std::make_pair(SrcReg, DstReg));
   else if (!IsDstPhys && IsSrcPhys) {
-    bool isNew =
-      SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
-    isNew = isNew; // Silence compiler warning.
-    assert(isNew && "Can't map to two src physical registers!");
+    bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
+    if (!isNew)
+      assert(SrcRegMap[DstReg] == SrcReg &&
+             "Can't map to two src physical registers!");
 
     SmallVector<unsigned, 4> VirtRegPairs;
-    bool isCopy = false;
+    bool IsCopy = false;
     unsigned NewReg = 0;
     while (MachineInstr *UseMI = findOnlyInterestingUse(DstReg, MBB, MRI,TII,
-                                                   isCopy, NewReg, IsDstPhys)) {
-      if (isCopy) {
-        if (Processed.insert(UseMI))
+                                                   IsCopy, NewReg, IsDstPhys)) {
+      if (IsCopy) {
+        if (!Processed.insert(UseMI))
           break;
       }
 
@@ -554,8 +685,9 @@ void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI,
         break;
       }
       bool isNew = SrcRegMap.insert(std::make_pair(NewReg, DstReg)).second;
-      isNew = isNew; // Silence compiler warning.
-      assert(isNew && "Can't map to two src physical registers!");
+      if (!isNew)
+        assert(SrcRegMap[NewReg] == DstReg &&
+               "Can't map to two src physical registers!");
       VirtRegPairs.push_back(NewReg);
       DstReg = NewReg;
     }
@@ -567,8 +699,9 @@ void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI,
         unsigned FromReg = VirtRegPairs.back();
         VirtRegPairs.pop_back();
         bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
-        isNew = isNew; // Silence compiler warning.
-        assert(isNew && "Can't map to two dst physical registers!");
+        if (!isNew)
+          assert(DstRegMap[FromReg] == ToReg &&
+                 "Can't map to two dst physical registers!");
         ToReg = FromReg;
       }
     }
@@ -579,7 +712,9 @@ void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI,
 
 /// isSafeToDelete - If the specified instruction does not produce any side
 /// effects and all of its defs are dead, then it's safe to delete.
-static bool isSafeToDelete(MachineInstr *MI, const TargetInstrInfo *TII) {
+static bool isSafeToDelete(MachineInstr *MI, unsigned Reg,
+                           const TargetInstrInfo *TII,
+                           SmallVector<unsigned, 4> &Kills) {
   const TargetInstrDesc &TID = MI->getDesc();
   if (TID.mayStore() || TID.isCall())
     return false;
@@ -588,10 +723,12 @@ static bool isSafeToDelete(MachineInstr *MI, const TargetInstrInfo *TII) {
 
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg() || !MO.isDef())
+    if (!MO.isReg())
       continue;
-    if (!MO.isDead())
+    if (MO.isDef() && !MO.isDead())
       return false;
+    if (MO.isUse() && MO.getReg() != Reg && MO.isKill())
+      Kills.push_back(MO.getReg());
   }
 
   return true;
@@ -679,14 +816,62 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
           // rearrange the code to make it so.  Making it the killing user will
           // allow us to coalesce A and B together, eliminating the copy we are
           // about to insert.
-          if (!mi->killsRegister(regB)) {
+          if (!isKilled(*mi, regB, MRI, TII)) {
             // If regA is dead and the instruction can be deleted, just delete
             // it so it doesn't clobber regB.
-            if (mi->getOperand(ti).isDead() && isSafeToDelete(mi, TII)) {
-              mbbi->erase(mi); // Nuke the old inst.
-              mi = nmi;
-              ++NumDeletes;
-              break; // Done with this instruction.
+            SmallVector<unsigned, 4> Kills;
+            if (mi->getOperand(ti).isDead() &&
+                isSafeToDelete(mi, regB, TII, Kills)) {
+              SmallVector<std::pair<std::pair<unsigned, bool>
+                ,MachineInstr*>, 4> NewKills;
+              bool ReallySafe = true;
+              // If this instruction kills some virtual registers, we need
+              // update the kill information. If it's not possible to do so,
+              // then bail out.
+              while (!Kills.empty()) {
+                unsigned Kill = Kills.back();
+                Kills.pop_back();
+                if (TargetRegisterInfo::isPhysicalRegister(Kill)) {
+                  ReallySafe = false;
+                  break;
+                }
+                MachineInstr *LastKill = FindLastUseInMBB(Kill, &*mbbi, Dist);
+                if (LastKill) {
+                  bool isModRef = LastKill->modifiesRegister(Kill);
+                  NewKills.push_back(std::make_pair(std::make_pair(Kill,isModRef),
+                                                    LastKill));
+                } else {
+                  ReallySafe = false;
+                  break;
+                }
+              }
+
+              if (ReallySafe) {
+                if (LV) {
+                  while (!NewKills.empty()) {
+                    MachineInstr *NewKill = NewKills.back().second;
+                    unsigned Kill = NewKills.back().first.first;
+                    bool isDead = NewKills.back().first.second;
+                    NewKills.pop_back();
+                    if (LV->removeVirtualRegisterKilled(Kill,  mi)) {
+                      if (isDead)
+                        LV->addVirtualRegisterDead(Kill, NewKill);
+                      else
+                        LV->addVirtualRegisterKilled(Kill, NewKill);
+                    }
+                  }
+                }
+
+                // We're really going to nuke the old inst. If regB was marked
+                // as a kill we need to update its Kills list.
+                if (mi->getOperand(si).isKill())
+                  LV->removeVirtualRegisterKilled(regB, mi);
+
+                mbbi->erase(mi); // Nuke the old inst.
+                mi = nmi;
+                ++NumDeletes;
+                break; // Done with this instruction.
+              }
             }
 
             // If this instruction is commutative, check to see if C dies.  If
@@ -697,7 +882,7 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
               assert(mi->getOperand(3-si).isReg() &&
                      "Not a proper commutative instruction!");
               unsigned regC = mi->getOperand(3-si).getReg();
-              if (mi->killsRegister(regC)) {
+              if (isKilled(*mi, regC, MRI, TII)) {
                 if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) {
                   ++NumCommuted;
                   regB = regC;
@@ -716,26 +901,7 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
                 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
 #endif
 
-              MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV);
-              if (NewMI) {
-                DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
-                DOUT << "2addr:         TO 3-ADDR: " << *NewMI;
-                bool Sunk = false;
-
-                if (NewMI->findRegisterUseOperand(regB, false, TRI))
-                  // FIXME: Temporary workaround. If the new instruction doesn't
-                  // uses regB, convertToThreeAddress must have created more
-                  // then one instruction.
-                  Sunk = Sink3AddrInstruction(mbbi, NewMI, regB, mi);
-
-                mbbi->erase(mi); // Nuke the old inst.
-
-                if (!Sunk) {
-                  DistanceMap.insert(std::make_pair(NewMI, Dist));
-                  mi = NewMI;
-                  nmi = next(mi);
-                }
-
+              if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) {
                 ++NumConvertedTo3Addr;
                 break; // Done with this instruction.
               }
@@ -750,9 +916,19 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
                 ++NumAggrCommuted;
                 ++NumCommuted;
                 regB = regC;
+                goto InstructionRearranged;
               }
           }
 
+          // If it's profitable to convert the 2-address instruction to a
+          // 3-address one, do so.
+          if (TID.isConvertibleTo3Addr() && isProfitableToConv3Addr(regA)) {
+            if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) {
+              ++NumConvertedTo3Addr;
+              break; // Done with this instruction.
+            }
+          }
+
         InstructionRearranged:
           const TargetRegisterClass* rc = MRI->getRegClass(regB);
           MachineInstr *DefMI = MRI->getVRegDef(regB);
@@ -767,7 +943,9 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
             ReMatRegs.set(regB);
             ++NumReMats;
           } else {
-            TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
+            bool Emitted = TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
+            (void)Emitted;
+            assert(Emitted && "Unable to issue a copy instruction!\n");
           }
 
           MachineBasicBlock::iterator prevMI = prior(mi);
@@ -777,11 +955,6 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
 
           // Update live variables for regB.
           if (LV) {
-            LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
-
-            // regB is used in this BB.
-            varInfoB.UsedBlocks[mbbi->getNumber()] = true;
-
             if (LV->removeVirtualRegisterKilled(regB,  mi))
               LV->addVirtualRegisterKilled(regB, prevMI);