Page MenuHomePhabricator

[LoopInfo] Return conditional branch of preheader's predecessor if loop's exit has exactly two predecessors which are latch and guard
AbandonedPublic

Authored by vdsered on Sep 26 2021, 12:28 AM.

Details

Reviewers
Whitney
fhahn
Summary

While working on an optimization for DSE I've noticed that for an example like the one below we return getLoopGuardBranch == nullptr and isGuarded == false for both loops even if they are in rotated form. See IR in an example on godbolt.

Technically, entry block decides if both loops execute, but there is a block with br i1 %3, label %7, label %14 where %3 is a icmp in entry block, so it can be a guard for the second loop.

void func(int *P, int N) {
    for (int i = 0; i < N; ++i) {
        P[i] = 1;
    }
    for (int i = 0; i < N; ++i) {
        P[i] = 2;
    }
}

This happens because loops are not in canonical form (specifically, because of no dedicated exits). I suggest to relax a little this requirement to have dedicated exits and add a check for a case when there is an exit that has exactly two predecessors and both of them are latch from loop and the block whose branch instruction we return in getLoopGuardBranch. So, we find a guard in a case as in the example above.

Diff Detail

Unit TestsFailed

TimeTest
110 msx64 debian > ORC-x86_64-linux.TestCases/Linux/x86-64::trivial-cxa-atexit.S
Script: -- : 'RUN: at line 3'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -m64 -c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/orc/X86_64LinuxConfig/TestCases/Linux/x86-64/Output/trivial-cxa-atexit.S.tmp /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/orc/TestCases/Linux/x86-64/trivial-cxa-atexit.S
110 msx64 debian > ORC-x86_64-linux.TestCases/Linux/x86-64::trivial-static-initializer.S
Script: -- : 'RUN: at line 7'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -m64 -c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/orc/X86_64LinuxConfig/TestCases/Linux/x86-64/Output/trivial-static-initializer.S.tmp /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/orc/TestCases/Linux/x86-64/trivial-static-initializer.S
110 msx64 debian > ORC-x86_64-linux.TestCases/Linux/x86-64::trivial-tls.S
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -m64 -c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/orc/X86_64LinuxConfig/TestCases/Linux/x86-64/Output/trivial-tls.S.tmp /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/orc/TestCases/Linux/x86-64/trivial-tls.S

Event Timeline

vdsered created this revision.Sep 26 2021, 12:28 AM
vdsered requested review of this revision.Sep 26 2021, 12:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 26 2021, 12:28 AM
vdsered edited the summary of this revision. (Show Details)Sep 26 2021, 12:31 AM
vdsered edited the summary of this revision. (Show Details)Sep 26 2021, 12:42 AM
vdsered edited the summary of this revision. (Show Details)Sep 26 2021, 1:05 AM

Why is the input to DSE not in simplified form? By running -loop-simplify after the IR you provided resolves this problem.

llvm/lib/Analysis/LoopInfo.cpp
396

no need braces for single statement block.

llvm/unittests/Analysis/LoopInfoTest.cpp
1587

isn't it better to make sure is FI->getTerminator().

vdsered added a comment.EditedSep 27 2021, 9:04 AM

Loops lose simplify form in JumpThreading in default pipeline before DSE, for example. I don't know the details and if this is correct or not. There is currently no need for a loop to be in simplify form in DSE in order to work with it (except that it should be a natural loop). It became only required for my optimization.

I think now that it is probably be better to transform a loop to simplify form for this optimization in DSE than generalizing getLoopGuardBranch.

vdsered abandoned this revision.Nov 1 2021, 10:44 AM