Subzero: Improve LoopAnalyzer Interface

src/IceLoopAnalyzer.cpp

 //===- subzero/src/IceLoopAnalyzer.cpp - Loop Analysis --------------------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief Implements the loop analysis on the CFG.
 ///
 //===----------------------------------------------------------------------===//
 #include "IceLoopAnalyzer.h"
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 
+#include <algorithm>
+
 namespace Ice {
 
 void LoopAnalyzer::LoopNode::reset() {
   if (Deleted)
     return;
   Succ = BB->getOutEdges().begin();
   Index = LowLink = UndefinedIndex;
   OnStack = false;
 }
 
@@ skipping 106 matching lines @@
   // Reaching here means a loop has been found! It consists of the nodes on the
   // top of the stack, down until the current node being processed, Node, is
   // found.
   for (auto It = LoopStack.rbegin(); It != LoopStack.rend(); ++It) {
     (*It)->setOnStack(false);
     (*It)->incrementLoopNestDepth();
     // Remove the loop from the stack and delete the head 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;
     }
   }
 
   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