From e52a693787df6de250456a71c361d9c91fc40fd7 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sun, 19 Apr 2009 01:32:00 +0000 Subject: [PATCH] rewrite an O(N^2) algorithm to be O(n). git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@69500 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Sema/SemaDecl.cpp | 37 ++++++++++++++++++------------------- 1 file changed, 18 insertions(+), 19 deletions(-) diff --git a/lib/Sema/SemaDecl.cpp b/lib/Sema/SemaDecl.cpp index 3a1217a839..2f57a49f9e 100644 --- a/lib/Sema/SemaDecl.cpp +++ b/lib/Sema/SemaDecl.cpp @@ -3150,26 +3150,25 @@ void JumpScopeChecker::CheckJump(Stmt *From, Stmt *To, // and then emit a note at each VLA being jumped out of. S.Diag(DiagLoc, JumpDiag); - // FIXME: This is N^2 and silly. - while (1) { - // Diagnose that the jump jumps over this declaration. - const GotoScope &TargetScope = Scopes[ToScope]; - S.Diag(TargetScope.Loc, TargetScope.Diag); - - // Walk out one level. - ToScope = Scopes[ToScope].ParentScope; - assert(ToScope != ~0U && "Didn't find top-level function scope?"); - - // Check to see if the jump is valid now. - unsigned TestScope = FromScope; - while (TestScope != ~0U) { - // If we found the jump target, the the jump became valid. - if (TestScope == ToScope) return; - - // Otherwise, scan up the hierarchy. - TestScope = Scopes[TestScope].ParentScope; - } + // Eliminate the common prefix of the jump and the target. Start by + // linearizing both scopes, reversing them as we go. + std::vector FromScopes, ToScopes; + for (TestScope = FromScope; TestScope != ~0U; + TestScope = Scopes[TestScope].ParentScope) + FromScopes.push_back(TestScope); + for (TestScope = ToScope; TestScope != ~0U; + TestScope = Scopes[TestScope].ParentScope) + ToScopes.push_back(TestScope); + + // Remove any common entries (such as the top-level function scope). + while (!FromScopes.empty() && FromScopes.back() == ToScopes.back()) { + FromScopes.pop_back(); + ToScopes.pop_back(); } + + // Emit diagnostics for whatever is left in ToScopes. + for (unsigned i = 0, e = ToScopes.size(); i != e; ++i) + S.Diag(Scopes[ToScopes[i]].Loc, Scopes[ToScopes[i]].Diag); } -- 2.40.0