Non-deterministic results from MemorySSAUpdater due to iteration order

[mikaelholmen]

llvm commit: 6e66cfe

Build opt with and without LLVM_ENABLE_REVERSE_ITERATION and then do:

build-all/bin/opt "-passes=loop-mssa(licm<no-allowspeculation>,loop-rotate<header-duplication;no-prepare-for-lto>,licm<allowspeculation>)" bbi-104167.ll -o bbi-104167.norev.ll -S
build-all-reverse/bin/opt "-passes=loop-mssa(licm<no-allowspeculation>,loop-rotate<header-duplication;no-prepare-for-lto>,licm<allowspeculation>)" bbi-104167.ll -o bbi-104167.rev.ll -S

Then if we diff the two output files:

diff bbi-104167.norev.ll bbi-104167.rev.ll

we get

11d10
<   %0 = load ptr, ptr @ao, align 1
15c14
<   %1 = load volatile i32, ptr null, align 1
---
>   %0 = load volatile i32, ptr null, align 1
42c41
<   %2 = load volatile i16, ptr null, align 1
---
>   %1 = load volatile i16, ptr null, align 1
77c76,77
<   store double 0.000000e+00, ptr %0, align 1
---
>   %2 = load ptr, ptr @ao, align 1
>   store double 0.000000e+00, ptr %2, align 1

bbi-104167.ll.gz

[mikaelholmen]

This seems to be related to the PredMap map in MemorySSAUpdater::applyInsertUpdates:

  // Map a BB to its predecessors: added + previously existing. To get a
  // deterministic order, store predecessors as SetVectors. The order in each
  // will be defined by the order in Updates (fixed) and the order given by
  // children<> (also fixed). Since we further iterate over these ordered sets,
  // we lose the information of multiple edges possibly existing between two
  // blocks, so we'll keep and EdgeCount map for that.
  // An alternate implementation could keep unordered set for the predecessors,
  // traverse either Updates or children<> each time to get  the deterministic
  // order, and drop the usage of EdgeCount. This alternate approach would still
  // require querying the maps for each predecessor, and children<> call has
  // additional computation inside for creating the snapshot-graph predecessors.
  // As such, we favor using a little additional storage and less compute time.
  // This decision can be revisited if we find the alternative more favorable.

  struct PredInfo {
    SmallSetVector<BasicBlock *, 2> Added;
    SmallSetVector<BasicBlock *, 2> Prev;
  };
  SmallDenseMap<BasicBlock *, PredInfo> PredMap;

Changing PredMap to a MapVector instead makes the diff goes away.

[mikaelholmen]

The code in MemorySSAUpdater::applyInsertUpdates was added in 7980099

API to update MemorySSA for cloned blocks and added CFG edges.

Summary:
End goal is to update MemorySSA in all loop passes. LoopUnswitch clones all blocks in a loop. SimpleLoopUnswitch clones some blocks. LoopRotate clones some instructions.
Some of these loop passes also make CFG changes.
This is an API based on what I found needed in LoopUnswitch, SimpleLoopUnswitch, LoopRotate, LoopInstSimplify, LoopSimplifyCFG.
Adding dependent patches using this API for context.

Reviewers: george.burgess.iv, dberlin

Subscribers: sanjoy, jlebar, Prazek, llvm-commits

Differential Revision: https://reviews.llvm.org/D45299

llvm-svn: 341855