[Loop Peeling] Fix idom detection algorithm.
authorSerguei Katkov <serguei.katkov@azul.com>
Thu, 25 Jul 2019 19:31:50 +0000 (19:31 +0000)
committerSerguei Katkov <serguei.katkov@azul.com>
Thu, 25 Jul 2019 19:31:50 +0000 (19:31 +0000)
commitcde00c02e11da2355ec715f571958fa180b17a43
treea3533f0325801d8089e27b25e15e483c4d0de5a6
parent8b288c7d11ccb43588fb8c14777a80d4d24c0858
[Loop Peeling] Fix idom detection algorithm.

We'd like to determine the idom of exit block after peeling one iteration.
Let Exit is exit block.
Let ExitingSet - is a set of predecessors of Exit block. They are exiting blocks.
Let Latch' and ExitingSet' are copies after a peeling.
We'd like to find an idom'(Exit) - idom of Exit after peeling.
It is an evident that idom'(Exit) will be the nearest common dominator of ExitingSet and ExitingSet'.
idom(Exit) is a nearest common dominator of ExitingSet.
idom(Exit)' is a nearest common dominator of ExitingSet'.
Taking into account that we have a single Latch, Latch' will dominate Header and idom(Exit).
So the idom'(Exit) is nearest common dominator of idom(Exit)' and Latch'.
All these basic blocks are in the same loop, so what we find is
(nearest common dominator of idom(Exit) and Latch)'.

Reviewers: reames, fhahn
Reviewed By: reames
Subscribers: hiraditya, zzheng, llvm-commits
Differential Revision: https://reviews.llvm.org/D65292

llvm-svn: 367044
llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp
llvm/test/Transforms/LoopUnroll/peel-loop-pgo-deopt-idom-2.ll [new file with mode: 0644]