ilya-palachev created this revision.
Herald added subscribers: szepet, xazax.hun.
Current CFG is built in non-deterministic order due to the fact that indirect
goto labels' declarations (LabelDecl's) are stored in the llvm::SmallSet
container. LabelDecl's are pointers, whose order is not deterministic by
design, and llvm::SmallSet sorts them by their non-deterministic addresses
after "small" container is exceeded. This leads to non-deterministic processing
of the elements of the
container.
The fix is to use llvm::SmallSetVector, which is deterministic by design.
The introduced test case was creduce'd from Android5 source file.
The test file contains 100 runs, in order to make the testing stable: different
PLIST's are generated in 20% and 80% cases, correspondingly.
Repository:
rL LLVM
https://reviews.llvm.org/D40073
Files:
lib/Analysis/CFG.cpp
test/Analysis/diagnostics/goto-label-determinism.cpp
Index: test/Analysis/diagnostics/goto-label-determinism.cpp
===================================================================
--- /dev/null
+++ test/Analysis/diagnostics/goto-label-determinism.cpp
@@ -0,0 +1,254 @@
+// RUN: %clang_analyze_cc1 -triple arm-unknown-linux-gnueabi -w -analyzer-checker=debug.ExprInspection %s -verify
+// RUN: for i in {1..100}; do %clang_analyze_cc1 -triple arm-unknown-linux-gnueabi -w -analyzer-checker=debug.ExprInspection -analyzer-config max-nodes=10433 %s -analyzer-output=plist-multi-file -o %t.${i}.plist; done ; for i in {1..100}; do FileCheck --input-file=%t.${i}.plist %s; done ; if [ `md5sum %t.*.plist | awk '{print $1}' | sort -u | wc -l` -gt 1 ] ; then exit 1 ; fi
+
+int f();
+void clang_analyzer_warnIfReached();
+struct A {
+ void **t;
+ int recursion() {
+ &&L1;
+ &&L2;
+ &&L3;
+ &&L4;
+ &&L5;
+ &&L6;
+ &&L7;
+ &&L8;
+ &&L9;
+ L1:
+ f() > recursion();
+ L2:
+ goto *t[f()];
+ L3:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}};
+ L4:
+ L5:
+ L6:
+ L7:
+ L8:
+ L9:
+ return 0;
+ }
+};
+
+// CHECK: <key>diagnostics</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>path</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>kind</key><string>control</string>
+// CHECK-NEXT: <key>edges</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>start</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>9</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>9</integer>
+// CHECK-NEXT: <key>col</key><integer>6</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: <key>end</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>17</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>17</integer>
+// CHECK-NEXT: <key>col</key><integer>6</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>kind</key><string>control</string>
+// CHECK-NEXT: <key>edges</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>start</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>17</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>17</integer>
+// CHECK-NEXT: <key>col</key><integer>6</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: <key>end</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>19</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>19</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>kind</key><string>control</string>
+// CHECK-NEXT: <key>edges</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>start</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>19</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>19</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: <key>end</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>21</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>21</integer>
+// CHECK-NEXT: <key>col</key><integer>8</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>kind</key><string>control</string>
+// CHECK-NEXT: <key>edges</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>start</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>21</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>21</integer>
+// CHECK-NEXT: <key>col</key><integer>8</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: <key>end</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>21</integer>
+// CHECK-NEXT: <key>col</key><integer>11</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>21</integer>
+// CHECK-NEXT: <key>col</key><integer>11</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>kind</key><string>control</string>
+// CHECK-NEXT: <key>edges</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>start</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>21</integer>
+// CHECK-NEXT: <key>col</key><integer>11</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>21</integer>
+// CHECK-NEXT: <key>col</key><integer>11</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: <key>end</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>23</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>23</integer>
+// CHECK-NEXT: <key>col</key><integer>32</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>kind</key><string>event</string>
+// CHECK-NEXT: <key>location</key>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>23</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <key>ranges</key>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <array>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>23</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>23</integer>
+// CHECK-NEXT: <key>col</key><integer>34</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: <key>depth</key><integer>0</integer>
+// CHECK-NEXT: <key>extended_message</key>
+// CHECK-NEXT: <string>REACHABLE</string>
+// CHECK-NEXT: <key>message</key>
+// CHECK-NEXT: <string>REACHABLE</string>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
+// CHECK-NEXT: <key>description</key><string>REACHABLE</string>
+// CHECK-NEXT: <key>category</key><string>debug</string>
+// CHECK-NEXT: <key>type</key><string>Checking analyzer assumptions</string>
+// CHECK-NEXT: <key>check_name</key><string>debug.ExprInspection</string>
+// CHECK-NEXT: <!-- This hash is experimental and going to change! -->
+// CHECK-NEXT: <key>issue_hash_content_of_line_in_context</key><string>cc662faac3c6459edff9488dc1617213</string>
+// CHECK-NEXT: <key>issue_context_kind</key><string>C++ method</string>
+// CHECK-NEXT: <key>issue_context</key><string>int A::recursion()</string>
+// CHECK-NEXT: <key>location</key>
+// CHECK-NEXT: <dict>
+// CHECK-NEXT: <key>line</key><integer>23</integer>
+// CHECK-NEXT: <key>col</key><integer>5</integer>
+// CHECK-NEXT: <key>file</key><integer>0</integer>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </dict>
+// CHECK-NEXT: </array>
Index: lib/Analysis/CFG.cpp
===================================================================
--- lib/Analysis/CFG.cpp
+++ lib/Analysis/CFG.cpp
@@ -420,7 +420,7 @@
BackpatchBlocksTy BackpatchBlocks;
// A list of labels whose address has been taken (for indirect gotos).
- typedef llvm::SmallPtrSet<LabelDecl*, 5> LabelSetTy;
+ typedef llvm::SmallSetVector<LabelDecl*, 8> LabelSetTy;
LabelSetTy AddressTakenLabels;
bool badCFG;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
