Subzero: Improve LoopAnalyzer Interface

src/IceLoopAnalyzer.cpp

Index: src/IceLoopAnalyzer.cpp
diff --git a/src/IceLoopAnalyzer.cpp b/src/IceLoopAnalyzer.cpp
index 344ffcea6f534278956f022404e3f830075cf625..5355cf10548052e2b1048b7d4159a8a1ce467000 100644
--- a/src/IceLoopAnalyzer.cpp
+++ b/src/IceLoopAnalyzer.cpp
@@ -16,6 +16,8 @@
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 
+#include <algorithm>
+
 namespace Ice {
 
 void LoopAnalyzer::LoopNode::reset() {
@@ -142,12 +144,12 @@ LoopAnalyzer::processNode(LoopAnalyzer::LoopNode &Node) {
     if (*It == &Node) {
       (*It)->setDeleted();
       ++NumDeletedNodes;
-      CfgVector<SizeT> LoopNodes;
+      CfgUnorderedSet<SizeT> LoopNodes;
       for (auto LoopIter = It.base() - 1; LoopIter != LoopStack.end();
            ++LoopIter) {
-        LoopNodes.push_back((*LoopIter)->getNode()->getIndex());
+        LoopNodes.insert((*LoopIter)->getNode()->getIndex());
       }
-      Loops[(*It)->getNode()->getIndex()] = LoopNodes;
+      Loops.push_back(LoopNodes);

[John, 2016/07/15 21:13:30]

this is awfully inefficient! you're copying LoopNodes here, and you probably
don't want to do that. Instead, do

Loops.emplace_back(std::move(LoopNode));

Alternatively (I prefer this approach), do

Loop.emplace_back({});  // pushes a new, empty loop in Loops
auto* LoopNodes = &Loop.back();

and then s/LoopNodes./LoopNodes->/

       LoopStack.erase(It.base() - 1, LoopStack.end());
       break;
     }
@@ -155,5 +157,70 @@ LoopAnalyzer::processNode(LoopAnalyzer::LoopNode &Node) {
 
   return nullptr;
 }
+void LoopAnalyzer::LoopInfo::computeLoopMetaData() {

[John, 2016/07/15 21:13:30]

Why do you need this method? where was it defined before?

[John, 2016/07/18 15:25:36]

nevermind.

[manasijm, 2016/07/18 22:27:47]

It was not there.
I am computing headers and pre-headers (if any) for loops here.

+  std::sort(Loops.begin(), Loops.end(), [](const CfgUnorderedSet<SizeT> &A,
+                                           const CfgUnorderedSet<SizeT> &B) {
+    return A.size() > B.size();
+  });
+  for (SizeT i = 0; i < Loops.size(); ++i) {
+    auto &Loop = Loops[i];
+    CfgNode *Header = nullptr;
+    bool IsSimpleLoop = true;
+    for (auto NodeIndex : Loop) {
+      CfgNode *Cur = Func->getNodes()[NodeIndex];
+      for (auto *Prev : Cur->getInEdges()) {
+        if (Loop.find(Prev->getIndex()) == Loop.end()) { // coming from outside
+          if (Header == nullptr) {
+            Header = Cur;
+          } else {
+            Header = nullptr;
+            IsSimpleLoop = false;
+            break;
+          }
+        }
+      }
+      if (!IsSimpleLoop) {
+        break;
+      }
+    }
+    if (!IsSimpleLoop)
+      continue; // To next potential loop
+
+    LoopIndexForHeader[Header->getIndex()] = i;
+
+    for (auto NodeIndex : Loop) {
+      //       CfgNode *Cur = Func->getNodes()[NodeIndex];

[Jim Stichnoth, 2016/07/15 22:14:33]

Remove this?

[manasijm, 2016/07/18 22:27:47]

Done.

+      HeaderForNode[NodeIndex] = Header->getIndex();
+    }
+
+    CfgNode *PreHeader = nullptr;
+    for (auto *Prev : Header->getInEdges()) {
+      if (Loop.find(Prev->getIndex()) == Loop.end()) {
+        if (PreHeader == nullptr) {
+          PreHeader = Prev;
+        } else {
+          PreHeader = nullptr;
+          break;
+        }
+      }
+    }
+    if (PreHeader != nullptr) {
+      PreheaderForHeader[Header->getIndex()] = PreHeader->getIndex();
+    }
+  }
+}
+
+CfgNode *LoopAnalyzer::LoopInfo::getHeader(CfgNode *Node) {
+  return Func->getNodes()[HeaderForNode[Node->getIndex()]];
+}
+
+CfgNode *LoopAnalyzer::LoopInfo::getPreHeader(CfgNode *Node) {
+  return Func->getNodes()[PreheaderForHeader[Node->getIndex()]];
+}
+const CfgUnorderedSet<SizeT> &LoopAnalyzer::LoopInfo::getBody(CfgNode *Header) {
+  auto Iter = LoopIndexForHeader.find(Header->getIndex());
+  assert(Iter != LoopIndexForHeader.end());
+  return Loops[Iter->second];
+}
 
 } // end of namespace Ice