Fix quadratic LexicalScopes::constructScopeNest(...), NFC

[jmaessen]

Summary

NO FUNCTIONAL CHANGE. Algorithmic complexity fix.

Our team at Facebook is currently constructing a compile backended by
LLVM. We sometimes have functions with large numbers of sibling basic
blocks (usually with an error path exit from each one). This was
triggering the qudratic behavior in this function - after visiting
each child llvm would re-scan the parent from the beginning again. We
modify the work stack to record the next index to be worked on
alongside the pointer. This avoids the need to linearly search for
the next unfinished child.

Note that I am not a committer at present, and will need the help of a committer to land this.

Test Plan:
cmake -G Ninja ...x86... -DLLVM_ENABLE_PROJECTS="clang;clang-tools-extra;debuginfo-tests;lld;opt" ...
ninja check

[dblaikie]

Looks good - once the variable names are fixed up to match LLVM conventions. Thanks!

llvm/lib/CodeGen/LexicalScopes.cpp

241–243

Please fix/ensure the names of variables conform with the LLVM naming conventions (Upper case-starting camelcase)

[jmorse]

LGTM with one nit inline and Davids recommendations done. Thanks for finding this! I can land it when you're ready, please provide a name and email to be set as the git commit author.

llvm/lib/CodeGen/LexicalScopes.cpp

247

IMO this comment isn't necessary, because it's describing the relationship between the new code and old code, which is best put in a commit message. After this lands, the DFSIn / DFSOut values of an unvisited scope shouldn't be something a reader would consider at all.

That being said, would you be able to add a comment about the overall purpose of the function somewhere, i.e. "Visit each scope in depth-first order, with the current exploration state kept as a tree in WorkStack", or similar.

[dblaikie]

llvm/lib/CodeGen/LexicalScopes.cpp

247

+1

[jmaessen]

Address review comments

[jmaessen]

Name: Jan-Willem Maessen
email: <llvm phabricator username>@fb.com

[jmaessen]

Fix non-compliant var name i and remove useless comment.

[jmorse]

Sorry for the delay, I've just pushed this up in rG3610d31e7a366, Phab should automagically close this in a moment. You might get emails from the CI buildbots as your email address is in the author field; I'll keep an eye on them in case something goes wrong and it needs reverting. LLVMs buildbots roll multiple commits together for testing, so it's a noisy process.

Many thanks for the patch!

llvm/lib/CodeGen/LexicalScopes.cpp

I = AbstractScopeMap.emplace(std::piecewise_construct,
                                std::forward_as_tuple(Scope),
                                std::forward_as_tuple(Parent, Scope,
                                                      nullptr, true)).first;
   if (isa<DISubprogram>(Scope))
     AbstractScopesList.push_back(&I->second);
   return &I->second;
 }
 
-/// constructScopeNest
+/// constructScopeNest - Traverse the Scope tree depth-first, storing
+/// traversal state in WorkStack and recording the depth-first
+/// numbering (setDFSIn, setDFSOut) for edge classification.
 void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
   assert(Scope && "Unable to calculate scope dominance graph!");
-  SmallVector<LexicalScope *, 4> WorkStack;
-  WorkStack.push_back(Scope);
+  SmallVector<std::pair<LexicalScope *, size_t>, 4> WorkStack;
+  WorkStack.push_back(std::make_pair(Scope, 0));
   unsigned Counter = 0;
   while (!WorkStack.empty()) {
-    LexicalScope *WS = WorkStack.back();
+    auto &ScopePosition = WorkStack.back();
+    LexicalScope *WS = ScopePosition.first;
+    size_t ChildNum = ScopePosition.second++;
     const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
-    bool visitedChildren = false;
-    for (auto &ChildScope : Children)
-      if (!ChildScope->getDFSOut()) {
-        WorkStack.push_back(ChildScope);
-        visitedChildren = true;
-        ChildScope->setDFSIn(++Counter);
-        break;
-      }
-    if (!visitedChildren) {
+    if (ChildNum < Children.size()) {
+      auto &ChildScope = Children[ChildNum];
+      WorkStack.push_back(std::make_pair(ChildScope, 0));
+    } else {
       WorkStack.pop_back();
       WS->setDFSOut(++Counter);
     }
   }
 }
 
 /// assignInstructionRanges - Find ranges of instructions covered by each
 /// lexical scope.