Page MenuHomePhabricator

[BPI] Handle incomplete state in BPI
AcceptedPublic

Authored by anna on Oct 8 2021, 11:05 AM.

Details

Summary

BPI has this inherent property that once it is computed for a block's
successor, Probs data exists for all successors of the block.

However, this is not true during lossy BPI preservation in loop passes,
where BPI is updated when a block is removed, but not when a block is
added (D110438).

This patch makes BPI more relaxed in the face of incomplete information:
removing an assertion that is no longer true and not relying on Probs
data to unconditionally have the information for a successor.

The unfortunate bit is that I cannot come up with any unit tests that
trigger the failure when we have lossy BPI (even downstream, the
failures are intemittent within the loop predication pass which uses
BPI). Upstream pipeline does not have a loop pass manager invocation
that uses lossy BPI preservation, but when it does, we will definitely
trip on these issues.

Diff Detail

Unit TestsFailed

TimeTest
80 msx64 debian > LLVM.CodeGen/X86::vector-interleaved-load-i8-stride-3.ll
Script: -- : 'RUN: at line 2'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/llc < /var/lib/buildkite-agent/builds/llvm-project/llvm/test/CodeGen/X86/vector-interleaved-load-i8-stride-3.ll -mtriple=x86_64-- -mattr=+avx2 | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck --check-prefixes=AVX2,AVX2-SLOW /var/lib/buildkite-agent/builds/llvm-project/llvm/test/CodeGen/X86/vector-interleaved-load-i8-stride-3.ll
60 msx64 debian > LLVM.CodeGen/X86::vector-interleaved-store-i8-stride-3.ll
Script: -- : 'RUN: at line 2'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/llc < /var/lib/buildkite-agent/builds/llvm-project/llvm/test/CodeGen/X86/vector-interleaved-store-i8-stride-3.ll -mtriple=x86_64-- -mattr=+avx2 | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck --check-prefixes=AVX2,AVX2-SLOW /var/lib/buildkite-agent/builds/llvm-project/llvm/test/CodeGen/X86/vector-interleaved-store-i8-stride-3.ll

Event Timeline

anna created this revision.Oct 8 2021, 11:05 AM
anna requested review of this revision.Oct 8 2021, 11:05 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 8 2021, 11:05 AM

I'm confused how the intermittent assert occurs. Is the compilation non-deterministic?

anna added a comment.Oct 8 2021, 11:35 AM

I'm confused how the intermittent assert occurs. Is the compilation non-deterministic?

Compilation is deterministic.

There can be couple of reasons (I couldn't find the reason for the intermittent failure) :

  1. Underlying data structure for Probs is DenseMap<Edge, BranchProbability>. Iteration through Probs is non-determistic, but I don't see us relying on that in BPI.
  2. It could also be that some pass within our LPM invocation has non-determinism in iteration through use-list or the way the successors are updated (this LPM is made up of all upstream passes: LoopPredication, LICM, LoopSimplifyCFG, LoopUnswitch<non-trivial>, GuardWidening).
anna added a reviewer: kazu.Oct 8 2021, 11:44 AM
asbirlea accepted this revision.Oct 18 2021, 11:38 AM

The question I was trying to get answer was: can there be the case where the probability is queried such that you can get different values based on when (what order) the blocks are removed or added? I think the answer is no, and I *think* I know why you're sometimes *not* triggering the assert: it's when IndexInSuccessors == 0. I suspect the successor order at the callsite in LoopPredication.cpp:947 is non-deterministic, so sometimes it's comparing against index 1, which does not have prob, and sometimes against itself, for which it does.

This revision is now accepted and ready to land.Oct 18 2021, 11:38 AM