This is an archive of the discontinued LLVM Phabricator instance.

Differential D40073

[Analyzer] Non-determinism: don't sort indirect goto LabelDecl's by addresses
ClosedPublic

Authored by ilya-palachev on Nov 15 2017, 5:11 AM.

Details

Reviewers
NoQ
dcoughlin
a.sidorin
Commits
rG124f5de84134: [Analyzer] Stable iteration on indirect goto LabelDecl's to avoid non…
rG3c3454b9d192: [Analyzer] Non-determinism: stable iteration on indirect goto LabelDecl's
rC318754: [Analyzer] Stable iteration on indirect goto LabelDecl's to avoid non…
rC318750: [Analyzer] Non-determinism: stable iteration on indirect goto LabelDecl's
rL318754: [Analyzer] Stable iteration on indirect goto LabelDecl's to avoid non…
rL318750: [Analyzer] Non-determinism: stable iteration on indirect goto LabelDecl's
Summary

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.

Diff Detail

Repository
rL LLVM

Event Timeline

ilya-palachev created this revision.Nov 15 2017, 5:11 AM
Herald added subscribers: szepet, xazax.hun. · View Herald TranscriptNov 15 2017, 5:11 AM
a.sidorin added inline comments.Nov 15 2017, 5:19 AM
test/Analysis/diagnostics/goto-label-determinism.cpp
3

This will not work on Windows. However, I don't know the common way of writing tests for determinism. Any ideas?

ilya-palachev updated this revision to Diff 123016.Nov 15 2017, 5:24 AM

Slightly changed the number of max-nodes, since previous one was maximum possible on my local branch, and it doesn't work for upstream. The behavior with number 500 seems more stable. With it, we have 4 different types of PLIST's being generated: 14, 54, 8 and 24 times, correspondingly.

ilya-palachev edited the summary of this revision. (Show Details)Nov 15 2017, 5:28 AM
dcoughlin accepted this revision.Nov 18 2017, 5:35 PM

Thanks for finding and fixing this!

This looks good, but since the nondeterminism is in CFG construction, I think it makes sense to create and dump the CFG rather than running the whole analyzer.

Here is a suggestion for a faster, more portable test.

// RUN: %clang_analyze_cc1 -analyzer-checker=debug.DumpCFG %s 2>&1 | FileCheck %s

void *target;
int indirectBlockSuccessorDeterminism() {
    (void)&&L1;
    (void)&&L2;
    (void)&&L3;
    (void)&&L4;
    (void)&&L5;
    (void)&&L6;
    (void)&&L7;
    (void)&&L8;
    (void)&&L9;
    (void)&&L10;
    (void)&&L11;
    (void)&&L12;
    (void)&&L13;
    (void)&&L14;
    (void)&&L15;
    (void)&&L16;
    (void)&&L17;
    (void)&&L18;
    (void)&&L19;
    (void)&&L20;
    (void)&&L21;
    (void)&&L22;
    (void)&&L23;
    (void)&&L24;
    (void)&&L25;
    (void)&&L26;
    (void)&&L27;
    (void)&&L28;
    (void)&&L29;
    (void)&&L30;
    (void)&&L31;
    (void)&&L32;
    (void)&&L33;
    (void)&&L34;
    (void)&&L35;
    (void)&&L36;
    (void)&&L37;
    (void)&&L38;
    (void)&&L39;
    (void)&&L40;

    goto *target;
  L1:
  L2:
  L3:
  L4:
  L5:
  L6:
  L7:
  L8:
  L9:
  L10:
  L11:
  L12:
  L13:
  L14:
  L15:
  L16:
  L17:
  L18:
  L19:
  L20:
  L21:
  L22:
  L23:
  L24:
  L25:
  L26:
  L27:
  L28:
  L29:
  L30:
  L31:
  L32:
  L33:
  L34:
  L35:
  L36:
  L37:
  L38:
  L39:
  L40:
    return 0;
}

// CHECK-LABEL:  [B41 (INDIRECT GOTO DISPATCH)]
// CHECK-NEXT:   Preds (1): B42
// CHECK-NEXT:  Succs (40): B1 B2 B3 B4 B5 B6 B7 B8
// CHECK-NEXT:       B9 B10 B11 B12 B13 B14 B15 B16 B17 B18
// CHECK-NEXT:       B19 B20 B21 B22 B23 B24 B25 B26 B27 B28
// CHECK-NEXT:       B29 B30 B31 B32 B33 B34 B35 B36 B37 B38
// CHECK-NEXT:       B39 B40
This revision is now accepted and ready to land.Nov 18 2017, 5:35 PM
ilya-palachev updated this revision to Diff 123558.Nov 20 2017, 3:35 AM

Ok, I agree, this test file is rather better.

dcoughlin added a comment.Nov 20 2017, 9:14 AM

Thanks! Do you have commit access, or do you need someone to commit this for you?

a.sidorin edited edge metadata.Nov 20 2017, 9:28 AM

Thank you, Devin!

Ilya doesn't have commit access so please commit the patch (or leave it for me, I'm going to commit some patches tomorrow).
By the way, is there a common way to write tests for non-determinism for LLVM test suite?

Closed by commit rL318750: [Analyzer] Non-determinism: stable iteration on indirect goto LabelDecl's (authored by a.sidorin). · Explain WhyNov 21 2017, 3:05 AM
This revision was automatically updated to reflect the committed changes.
NoQ edited edge metadata.Nov 21 2017, 3:19 AM

Thank you for the patch!~

In D40073#930470, @a.sidorin wrote:

By the way, is there a common way to write tests for non-determinism for LLVM test suite?

I guess the most recent update on this subject is in this thread: https://lists.llvm.org/pipermail/llvm-dev/2017-July/115025.html

dcoughlin added a comment.Nov 21 2017, 6:30 PM

For clang itself I think we also use a stage-2 clang to build the same version of clang and make sure that it matches the stage-2 clang. This doesn't help for the analyzer though.

mgrang added a subscriber: mgrang.Nov 21 2017, 6:54 PM

Revision Contents

PathSize
lib/
Analysis/
2 lines
test/
Analysis/
diagnostics/
254 lines

Diff 123016

lib/Analysis/CFG.cpp

Show First 20 Lines • Show All 414 Lines • ▼ Show 20 Linesclass CFGBuilder {
LabelMapTy LabelMap; LabelMapTy LabelMap;
// A list of blocks that end with a "goto" that must be backpatched to their // A list of blocks that end with a "goto" that must be backpatched to their
// resolved targets upon completion of CFG construction. // resolved targets upon completion of CFG construction.
typedef std::vector<JumpSource> BackpatchBlocksTy; typedef std::vector<JumpSource> BackpatchBlocksTy;
BackpatchBlocksTy BackpatchBlocks; BackpatchBlocksTy BackpatchBlocks;
// A list of labels whose address has been taken (for indirect gotos). // 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; LabelSetTy AddressTakenLabels;
bool badCFG; bool badCFG;
const CFG::BuildOptions &BuildOpts; const CFG::BuildOptions &BuildOpts;
// State to track for building switch statements. // State to track for building switch statements.
bool switchExclusivelyCovered; bool switchExclusivelyCovered;
Expr::EvalResult *switchCond; Expr::EvalResult *switchCond;
▲ Show 20 Lines • Show All 4,557 Lines • Show Last 20 Lines

test/Analysis/diagnostics/goto-label-determinism.cpp

  • This file was added.
// 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=500 %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
a.sidorinUnsubmitted
Not Done
ReplyInline Actions

This will not work on Windows. However, I don't know the common way of writing tests for determinism. Any ideas?

a.sidorin: This will not work on Windows. However, I don't know the common way of writing tests for…
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>