Page MenuHomePhabricator

[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

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
a.sidorin added inline comments.Nov 15 2017, 5:19 AM
test/Analysis/diagnostics/goto-label-determinism.cpp
2 ↗(On Diff #123014)

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

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

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

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?

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!~

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

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