[PATCH] D62619: [analyzer][Dominators] Add a control dependency tree builder + a new debug checker

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus added a comment.

While I managed to create a version of `llvm::IDFCalculator` that both compiles 
and works well with `clang::CFGBlock *`, I'm a little unsure about the 
specifics. I sent out a mail to reach a wider audience about the next steps: 
http://lists.llvm.org/pipermail/llvm-dev/2019-June/132786.html


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62619/new/

https://reviews.llvm.org/D62619



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62619: [analyzer][Dominators] Add a control dependency tree builder + a new debug checker

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun added a comment.

I did not check the algorithm as you planned changes to that. I only did a 
quick review of the interface which might also be rendered obsolete once you 
update this patch.




Comment at: clang/include/clang/Analysis/Analyses/Dominators.h:191
+
+  CFGDomTree () { return DomTree; }
+  const CFGDomTree () const { return DomTree; }

Is it sensible to have a non-const reference to the DomTree? Why would the user 
want to modify this? I think do not really do transformations on the CFG once 
it is built.



Comment at: clang/include/clang/Analysis/Analyses/Dominators.h:193
+  const CFGDomTree () const { return DomTree; }
+  CFGPostDomTree () { return PostDomTree; }
+  const CFGPostDomTree () const { return PostDomTree; }

Same as above.


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62619/new/

https://reviews.llvm.org/D62619



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62619: [analyzer][Dominators] Add a control dependency tree builder + a new debug checker

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus added a comment.

Also, I read some of the article you showed as well as the one I found on the 
dominance frontier file documentation[1], and I feel a lot more enlightened 
about the subject, thanks! I'll spend more time on them before wrapping this up.

[1]
Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of 
Programming Languages
POPL '95. ACM, New York, NY, 62-73.


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62619/new/

https://reviews.llvm.org/D62619



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62619: [analyzer][Dominators] Add a control dependency tree builder + a new debug checker

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus added a comment.

I seem to have made good progress on this, although it did require a lot of 
code changes on LLVM side (basically turning `BasicBlock *` to template 
arguments). Here's a sample:

  //   <--
  //  /  <-   \
  // /  /  \   \
  // [B12 (ENTRY)] -> [B11] -> [B10]-> [B9] -> [B8] ---> [B7] -> [B6]  |
  // |  \\ /
  // |   \-> [B2] /
  // |\  /
  // |  -> [B5] -> [B4] -> [B3]
  // |   \  /
  // |<
  //  \
  //   -> [B1] -> [B0 (EXIT)]
  
  Control dependencies  (Node, Dependency):
  (2,10)
  (3,5)
  (3,9)
  (3,10)
  (4,5)
  (4,9)
  (4,10)
  (5,9)
  (5,5)
  (5,10)
  (6,8)
  (6,9)
  (6,10)
  (7,8)
  (7,9)
  (7,10)
  (8,9)
  (8,8)
  (8,10)
  (9,10)
  (10,10)

My solution is inspired by

In D62619#1521824 , @kuhar wrote:

> - 
> https://github.com/seahorn/seahorn/blob/deep-dev-5.0/include/seahorn/Analysis/ControlDependenceAnalysis.hh
> - 
> https://github.com/seahorn/seahorn/blob/deep-dev-5.0/lib/Analysis/ControlDependenceAnalysis.cc


, and I really like where this is going. I am yet to figure out how to deal 
with Clang's CFG containing null pointers in a not-too-invasive way (will 
probably end up doing something similar to `ChildrenGetter`), as it currently 
crashes.


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62619/new/

https://reviews.llvm.org/D62619



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62619: [analyzer][Dominators] Add a control dependency tree builder + a new debug checker

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus added a comment.

In D62619#1521824 , @kuhar wrote:

> You can easily get CD by calculating the PostDominanceFrontier. LLVM 
> implements a templated IDF (Iterated Dominance Frontier) construction.
>  A native implementation for llvm ir for reference, if you need:
>
> - 
> https://github.com/seahorn/seahorn/blob/deep-dev-5.0/include/seahorn/Analysis/ControlDependenceAnalysis.hh
> - 
> https://github.com/seahorn/seahorn/blob/deep-dev-5.0/lib/Analysis/ControlDependenceAnalysis.cc
>
>   Paper: R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. 
> Efficiently computing static single assignment form and the control 
> dependence graph. ACM Trans. Program. Lang. Syst., 13(4):451–490, Oct. 1991.


Wow, thank you so much! This looks like a far superior but not a much more 
complicated solution then my own :) And I came to realize it may not even be 
correct.


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62619/new/

https://reviews.llvm.org/D62619



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62619: [analyzer][Dominators] Add a control dependency tree builder + a new debug checker

[Jakub Kuderski via Phabricator via cfe-commits]

kuhar added a comment.

You can easily get CD by calculating the PostDominanceFrontier. LLVM implements 
a templated IDF (Iterated Dominance Frontier) construction.
A native implementation for llvm ir for reference, if you need:

- 
https://github.com/seahorn/seahorn/blob/deep-dev-5.0/include/seahorn/Analysis/ControlDependenceAnalysis.hh
- 
https://github.com/seahorn/seahorn/blob/deep-dev-5.0/lib/Analysis/ControlDependenceAnalysis.cc

Paper: R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. 
Efficiently
computing static single assignment form and the control dependence graph. ACM
Trans. Program. Lang. Syst., 13(4):451–490, Oct. 1991.


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62619/new/

https://reviews.llvm.org/D62619



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62619: [analyzer][Dominators] Add a control dependency tree builder + a new debug checker

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus created this revision.
Szelethus added reviewers: kuhar, NoQ, dcoughlin, xazax.hun, rnkovacs, 
baloghadamsoftware, Charusso.
Szelethus added a project: clang.
Herald added subscribers: cfe-commits, gamesh411, dkrupp, donat.nagy, 
mikhail.ramalho, a.sidorin, szepet, whisperity.
Szelethus added a parent revision: D62611: [analyzer][Dominators] Add unittests.

Block A is a control dependency of block B, is A dominates B but B doesn't post 
dominate A.

In detail:

- Create the `CFGControlDependencyTree`, which in fact stores both a dominator 
and a post dominator tree
- Add the new debug checker `debug.DumpControlDependencies`
- Add both lit and unit tests.

Now I'm not sure whether this is the optimal approach -- In fact I'm fairly 
certain that this isn't the most efficient way of calculating control 
dependencies, however, I'm not that concerned with performance just yet. This 
will be used to improve bug reports the static analyzer emits, and if this 
turns out to be useful, I might look enhancing this further.


Repository:
  rC Clang

https://reviews.llvm.org/D62619

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
  clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
  clang/test/Analysis/domtest.c
  clang/test/Analysis/domtest.cpp
  clang/unittests/Analysis/CFGDominatorTree.cpp

Index: clang/unittests/Analysis/CFGDominatorTree.cpp
===
--- clang/unittests/Analysis/CFGDominatorTree.cpp
+++ clang/unittests/Analysis/CFGDominatorTree.cpp
@@ -117,6 +117,105 @@
   EXPECT_TRUE(PostDom.dominates(nullptr, ExitBlock));
 }
 
+TEST(CFGDominatorTree, ControlDependency) {
+  const char *Code = R"(bool coin();
+
+void funcWithBranch() {
+  int x = 0;
+  if (coin()) {
+if (coin()) {
+  x = 5;
+}
+int j = 10 / x;
+(void)j;
+  }
+};)";
+  BuildResult Result = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+
+  //  1st if  2nd if
+  //  [B5 (ENTRY)]  -> [B4] -> [B3] -> [B2] -> [B1] -> [B0 (EXIT)]
+  //\\  / /
+  // \-> /
+  //  -->
+
+  CFG *cfg = Result.getCFG();
+
+  // Sanity checks.
+  EXPECT_EQ(cfg->size(), 6u);
+
+  CFGBlock *ExitBlock = *cfg->begin();
+  EXPECT_EQ(ExitBlock, >getExit());
+
+  CFGBlock *NullDerefBlock = *(cfg->begin() + 1);
+
+  CFGBlock *SecondThenBlock = *(cfg->begin() + 2);
+
+  CFGBlock *SecondIfBlock = *(cfg->begin() + 3);
+  EXPECT_TRUE(hasStmtType(SecondIfBlock));
+
+  CFGBlock *FirstIfBlock = *(cfg->begin() + 4);
+  EXPECT_TRUE(hasStmtType(FirstIfBlock));
+
+  CFGBlock *EntryBlock = *(cfg->begin() + 5);
+  EXPECT_EQ(EntryBlock, >getEntry());
+
+  CFGControlDependencyTree Control;
+  Control.buildDominatorTree(cfg);
+
+  EXPECT_TRUE(Control.isControlDependency(SecondIfBlock, SecondThenBlock));
+  EXPECT_TRUE(Control.isControlDependency(FirstIfBlock, SecondIfBlock));
+  EXPECT_FALSE(Control.isControlDependency(SecondIfBlock, NullDerefBlock));
+}
+
+TEST(CFGDominatorTree, ControlDependencyWithLoops) {
+  const char *Code = R"(int test3() {
+  int x,y,z;
+
+  x = y = z = 1;
+  if (x > 0) {
+while (x >= 0){
+  while (y >= x) {
+x = x-1;
+y = y/2;
+  }
+}
+  }
+  z = y;
+
+  return 0;
+})";
+  BuildResult Result = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+
+  //<-
+  //   /  \
+  //   |---> [B2]
+  //   |   /
+  // [B8 (ENTRY)] -> [B7] -> [B6] -> [B5] -> [B4] -> [B3]
+  //   \   |   \  /
+  //\  |<-
+  // \  \
+  //  > [B1] -> [B0 (EXIT)]
+
+  CFG *cfg = Result.getCFG();
+
+  CFGControlDependencyTree Control;
+  Control.buildDominatorTree(cfg);
+
+  auto GetBlock = [cfg] (unsigned Index) -> CFGBlock * {
+assert(Index < cfg->size());
+return *(cfg->begin() + Index);
+  };
+
+  // While not immediately obvious, the second block in fact post dominates the
+  // fifth, hence B5 is not a control dependency of 2.
+  EXPECT_FALSE(Control.isControlDependency(GetBlock(5), GetBlock(2)));