From 3b8d35fb8d38022700dc565a26da4d24cf5e61c7 Mon Sep 17 00:00:00 2001
From: "Arnaud A. de Grandmaison" <arnaud.degrandmaison@arm.com>
Date: Thu, 11 Jun 2015 07:50:21 +0000
Subject: [PATCH] [LiveVariables] Improve isLiveOut runtime performances. NFC.

On large goto table based interpreters, where phi nodes can have (very) large
fan-ins, isLiveOut exhibited poor performances: about 40% of the full
codegen time was spent in PHIElim, sorting MachineBasicBlock addresses.

This patch improve the performances for such cases, and does not show
compile time regressions on the LNT, at bootstrap (llvm+clang+lldb) or
any other benchmarks we have in-house.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@239510 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/LiveVariables.cpp | 39 +++++++----------------------------
 1 file changed, 8 insertions(+), 31 deletions(-)

diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp
index 11deb813dde..b355393e76f 100644
--- a/lib/CodeGen/LiveVariables.cpp
+++ b/lib/CodeGen/LiveVariables.cpp
@@ -738,45 +738,22 @@ bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB,
 bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) {
   LiveVariables::VarInfo &VI = getVarInfo(Reg);
 
+  SmallPtrSet<const MachineBasicBlock *, 8> Kills;
+  for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
+    Kills.insert(VI.Kills[i]->getParent());
+
   // Loop over all of the successors of the basic block, checking to see if
   // the value is either live in the block, or if it is killed in the block.
-  SmallVector<MachineBasicBlock*, 8> OpSuccBlocks;
-  for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),
-         E = MBB.succ_end(); SI != E; ++SI) {
-    MachineBasicBlock *SuccMBB = *SI;
-
+  for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
     // Is it alive in this successor?
     unsigned SuccIdx = SuccMBB->getNumber();
     if (VI.AliveBlocks.test(SuccIdx))
       return true;
-    OpSuccBlocks.push_back(SuccMBB);
+    // Or is it live because there is a use in a successor that kills it?
+    if (Kills.count(SuccMBB))
+      return true;
   }
 
-  // Check to see if this value is live because there is a use in a successor
-  // that kills it.
-  switch (OpSuccBlocks.size()) {
-  case 1: {
-    MachineBasicBlock *SuccMBB = OpSuccBlocks[0];
-    for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
-      if (VI.Kills[i]->getParent() == SuccMBB)
-        return true;
-    break;
-  }
-  case 2: {
-    MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1];
-    for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
-      if (VI.Kills[i]->getParent() == SuccMBB1 ||
-          VI.Kills[i]->getParent() == SuccMBB2)
-        return true;
-    break;
-  }
-  default:
-    std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end());
-    for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
-      if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(),
-                             VI.Kills[i]->getParent()))
-        return true;
-  }
   return false;
 }
 
-- 
2.34.1