[SimplifyCFG] Fix for non-determinism in codegen

[mgrang]

Summary

This patch fixes issues in codegen uncovered due to https://reviews.llvm.org/D26718

[mgrang]

Ping.

[mgrang]

This patch fixes the non-determinism caused due to iterating SmallSet which was uncovered due to the experimenatal "reverse iteration order " patch: https://reviews.llvm.org/D26718

The following unit test fails because of the undefined order of iteration.
LLVM :: Transforms/SimplifyCFG/bug-25299.ll

This is fixed here by changing SmallSet to SmallSetVector so that the iteration order is defined.

[mgrang]

Ping for reviews please.

[arsenm]

Testcase?

[davide]

Having fixed the very same problem in LCSSA yesterday, I have some sympathy for this.
I think the fix is fine, but I'd appreciate if you can take some measurements and make sure this doesn't impact compile time.

[davide]

In D26726#728357, @arsenm wrote:

Testcase?

It's very hard to craft testcases for these order of iterations issues. They generally show up in very lovely situations, e.g. stage3 builds, and they break the bot anyway.
So, if it's easy to find a testcase, works for me, otherwise I wouldn't worry too much.

[mgrang]

@arsenm @davide Yes, it's difficult to make a test case for this. I uncovered this issue by turning ON reverse iteration of SmallPtrSet and finding that the following unit test failed:

test/Transforms/SimplifyCFG/bug-25299.ll

It failed because it expects:
continue: ; preds = %entry, %continue

But due to reverse iteration we get:
continue: ; preds = %continue, %entry

So, isn't the failing of this test case in itself sufficient to demonstrate the validity/correctness of this patch?

As far as the compile time is concerned, let me try building some tests and measure the effect on compile time.

[mgrang]

I built the llvm unit tests and the test suite and can see no measurable difference in compile time with and w/o my patch.

For ninja check-all:

Expected Passes    : 21902
Expected Failures  : 68
Unsupported Tests  : 9820
Unexpected Failures: 40

For ninja check-llvm-unit:

Expected Passes    : 2286
Unexpected Failures: 34

 Compile times            | without my patch | with my patch
ninja check-all             | real 1m29.448s     | real 1m28.608s
ninja check-llvm-unit  | real 0m4.553s       | real 0m4.540s

I am also trying to build LNT tests locally and will post the results when I have them.

Thanks!

[mgrang]

I built the LNT test-suite with and without my patch by turning on -flto and here are the compile time results:

Run Duration
With my patch 5:03:00
Baseline 5:05:26

I tried uploading my report.json to http://llvm.org/perf/submitRun but it always errors out:
"must provide input file or data"

Can someone please tell me how I can upload my test-suite json report files to llvm.org?

I am also attaching the reports in json and csv format here.

baseline_report.json188 KBDownload

run_report.json188 KBDownload

run_report.simple.csv58 KBDownload

baseline_report.simple.csv58 KBDownload

--Mandeep

lib/Transforms/Utils/SimplifyCFG.cpp

bool SimplifyCFGOpt::SimplifyCommonResume(ResumeInst *RI) {
   // Check that there are no other instructions except for debug intrinsics
   // between the phi of landing pads (RI->getValue()) and resume instruction.
   BasicBlock::iterator I = cast<Instruction>(RI->getValue())->getIterator(),
                        E = RI->getIterator();
   while (++I != E)
     if (!isa<DbgInfoIntrinsic>(I))
       return false;
 
-  SmallSet<BasicBlock *, 4> TrivialUnwindBlocks;
+  SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
   auto *PhiLPInst = cast<PHINode>(RI->getValue());
 
   // Check incoming blocks to see if any of them are trivial.
   for (unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
        Idx++) {
     auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
     auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);