Update LLVM to r98164.

1 files changed, 109 insertions, 11 deletions

diff --git a/lib/CodeGen/MachineCSE.cpp b/lib/CodeGen/MachineCSE.cpp
index b376e3d..ce95d8d 100644
--- a/lib/CodeGen/MachineCSE.cpp
+++ b/lib/CodeGen/MachineCSE.cpp
@@ -33,9 +33,9 @@ namespace {
   class MachineCSE : public MachineFunctionPass {
     const TargetInstrInfo *TII;
     const TargetRegisterInfo *TRI;
-    MachineRegisterInfo  *MRI;
-    MachineDominatorTree *DT;
     AliasAnalysis *AA;
+    MachineDominatorTree *DT;
+    MachineRegisterInfo *MRI;
   public:
     static char ID; // Pass identification
     MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {}
@@ -61,6 +61,8 @@ namespace {
                                 MachineBasicBlock::const_iterator E);
     bool hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB);
     bool isCSECandidate(MachineInstr *MI);
+    bool isProfitableToCSE(unsigned CSReg, unsigned Reg,
+                           MachineInstr *CSMI, MachineInstr *MI);
     bool ProcessBlock(MachineDomTreeNode *Node);
   };
 } // end anonymous namespace
@@ -92,7 +94,16 @@ bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI,
     if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
         TargetRegisterInfo::isVirtualRegister(SrcReg) &&
         !SrcSubIdx && !DstSubIdx) {
+      const TargetRegisterClass *SRC   = MRI->getRegClass(SrcReg);
+      const TargetRegisterClass *RC    = MRI->getRegClass(Reg);
+      const TargetRegisterClass *NewRC = getCommonSubClass(RC, SRC);
+      if (!NewRC)
+        continue;
+      DEBUG(dbgs() << "Coalescing: " << *DefMI);
+      DEBUG(dbgs() << "*** to: " << *MI);
       MO.setReg(SrcReg);
+      if (NewRC != SRC)
+        MRI->setRegClass(SrcReg, NewRC);
       DefMI->eraseFromParent();
       ++NumCoalesces;
       Changed = true;
@@ -133,6 +144,8 @@ bool MachineCSE::isPhysDefTriviallyDead(unsigned Reg,
   return false;
 }
 
+/// hasLivePhysRegDefUse - Return true if the specified instruction read / write
+/// physical registers (except for dead defs of physical registers).
 bool MachineCSE::hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB){
   unsigned PhysDef = 0;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
@@ -167,12 +180,19 @@ bool MachineCSE::hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB){
   return false;
 }
 
-bool MachineCSE::isCSECandidate(MachineInstr *MI) {
-  // Ignore copies or instructions that read / write physical registers
-  // (except for dead defs of physical registers).
+static bool isCopy(const MachineInstr *MI, const TargetInstrInfo *TII) {
   unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
-  if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
-      MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg())
+  return TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
+    MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg();
+}
+
+bool MachineCSE::isCSECandidate(MachineInstr *MI) {
+  if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() ||
+      MI->isKill() || MI->isInlineAsm())
+    return false;
+
+  // Ignore copies.
+  if (isCopy(MI, TII))
     return false;
 
   // Ignore stuff that we obviously can't move.
@@ -194,9 +214,69 @@ bool MachineCSE::isCSECandidate(MachineInstr *MI) {
   return true;
 }
 
+/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
+/// common expression that defines Reg.
+bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg,
+                                   MachineInstr *CSMI, MachineInstr *MI) {
+  // FIXME: Heuristics that works around the lack the live range splitting.
+
+  // Heuristics #1: Don't cse "cheap" computating if the def is not local or in an
+  // immediate predecessor. We don't want to increase register pressure and end up
+  // causing other computation to be spilled.
+  if (MI->getDesc().isAsCheapAsAMove()) {
+    MachineBasicBlock *CSBB = CSMI->getParent();
+    MachineBasicBlock *BB = MI->getParent();
+    if (CSBB != BB && 
+        find(CSBB->succ_begin(), CSBB->succ_end(), BB) == CSBB->succ_end())
+      return false;
+  }
+
+  // Heuristics #2: If the expression doesn't not use a vr and the only use
+  // of the redundant computation are copies, do not cse.
+  bool HasVRegUse = false;
+  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+    const MachineOperand &MO = MI->getOperand(i);
+    if (MO.isReg() && MO.isUse() && MO.getReg() &&
+        TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
+      HasVRegUse = true;
+      break;
+    }
+  }
+  if (!HasVRegUse) {
+    bool HasNonCopyUse = false;
+    for (MachineRegisterInfo::use_nodbg_iterator I =  MRI->use_nodbg_begin(Reg),
+           E = MRI->use_nodbg_end(); I != E; ++I) {
+      MachineInstr *Use = &*I;
+      // Ignore copies.
+      if (!isCopy(Use, TII)) {
+        HasNonCopyUse = true;
+        break;
+      }
+    }
+    if (!HasNonCopyUse)
+      return false;
+  }
+
+  // Heuristics #3: If the common subexpression is used by PHIs, do not reuse
+  // it unless the defined value is already used in the BB of the new use.
+  bool HasPHI = false;
+  SmallPtrSet<MachineBasicBlock*, 4> CSBBs;
+  for (MachineRegisterInfo::use_nodbg_iterator I =  MRI->use_nodbg_begin(CSReg),
+       E = MRI->use_nodbg_end(); I != E; ++I) {
+    MachineInstr *Use = &*I;
+    HasPHI |= Use->isPHI();
+    CSBBs.insert(Use->getParent());
+  }
+
+  if (!HasPHI)
+    return true;
+  return CSBBs.count(MI->getParent());
+}
+
 bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
   bool Changed = false;
 
+  SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs;
   ScopedHashTableScope<MachineInstr*, unsigned,
     MachineInstrExpressionTrait> VNTS(VNT);
   MachineBasicBlock *MBB = Node->getBlock();
@@ -231,6 +311,9 @@ bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
     MachineInstr *CSMI = Exps[CSVN];
     DEBUG(dbgs() << "Examining: " << *MI);
     DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
+
+    // Check if it's profitable to perform this CSE.
+    bool DoCSE = true;
     unsigned NumDefs = MI->getDesc().getNumDefs();
     for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
       MachineOperand &MO = MI->getOperand(i);
@@ -243,11 +326,26 @@ bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
       assert(TargetRegisterInfo::isVirtualRegister(OldReg) &&
              TargetRegisterInfo::isVirtualRegister(NewReg) &&
              "Do not CSE physical register defs!");
-      MRI->replaceRegWith(OldReg, NewReg);
+      if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
+        DoCSE = false;
+        break;
+      }
+      CSEPairs.push_back(std::make_pair(OldReg, NewReg));
       --NumDefs;
     }
-    MI->eraseFromParent();
-    ++NumCSEs;
+
+    // Actually perform the elimination.
+    if (DoCSE) {
+      for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i)
+        MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second);
+      MI->eraseFromParent();
+      ++NumCSEs;
+    } else {
+      DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
+      VNT.insert(MI, CurrVN++);
+      Exps.push_back(MI);
+    }
+    CSEPairs.clear();
   }
 
   // Recursively call ProcessBlock with childred.
@@ -262,7 +360,7 @@ bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
   TII = MF.getTarget().getInstrInfo();
   TRI = MF.getTarget().getRegisterInfo();
   MRI = &MF.getRegInfo();
-  DT = &getAnalysis<MachineDominatorTree>();
   AA = &getAnalysis<AliasAnalysis>();
+  DT = &getAnalysis<MachineDominatorTree>();
   return ProcessBlock(DT->getRootNode());
 }