HomePhabricator

[CloneFunction] Update loop headers after cloning all blocks in loop.

Authored by Whitney on Feb 21 2020, 2:15 PM.

Description

[CloneFunction] Update loop headers after cloning all blocks in loop.

Summary:
Blocks in a loop can be in any order as long as the loop header is the
first block in Blocks.
With some order of Blocks, cloneLoopWithPreheader would trigger the
assertion in addBasicBlockToLoop.

Example:

define void @test(i64 %N) {
preheader.i:

br label %header.i

header.i:

%i = phi i64 [ 0, %preheader.i ], [ %inc.i, %latch.i ]
br label %header.j

header.j:

%j = phi i64 [ 0, %header.i ], [ %inc.j, %latch.j ]
br label %header.k

header.k:

%k = phi i64 [ 0, %header.j ], [ %inc.k, %latch.k ]
call void @baz(i64 %i, i64 %j, i64 %k)
br label %latch.k

latch.k:

%inc.k = add nsw i64 %k, 1
%cmp.k = icmp slt i64 %inc.k, %N
br i1 %cmp.k, label %header.k, label %latch.j

latch.j:

%inc.j = add nsw i64 %j, 1
%cmp.j = icmp slt i64 %inc.j, %N
br i1 %cmp.j, label %header.j, label %latch.i

latch.i:

%inc.i = add nsw i64 %i, 1
%cmp.i = icmp slt i64 %inc.i, %N
br i1 %cmp.i, label %header.i, label %exit.i

exit.i:

ret void

}
declare void @baz(i64, i64, i64)
If the blocks of loop-i is in the order: header.i, latch.k, header.k,
header.j, latch.j, latch.i,
then cloneLoopWithPreheader would trigger the assertion in
addBasicBlockToLoop
assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
"Incorrect LI specified for this loop!");

As latch.k is in both loop-j and loop-k, it would be set as the header
of both loops after adding latch.k.
If we update loop headers during cloning blocks, then after adding
header.k,
the header of loop-k would be updated with header.k,
while the header of loop-j stays as latch.k.

When adding header.j, SameHeader is loop-k, SameHeader->getHeader() is
header.k, but getHeader() is latch.k, which trigger the assertion.
Reviewer: jdoerfert, Meinersbur, fhahn, kbarton, hfinkel, bmahjour,
etiotto
Reviewed By: Meinersbur
Subscribers: hiraditya, llvm-commits
Tag: LLVM
Differential Revision: https://reviews.llvm.org/D74382

Details

Committed
WhitneyFeb 21 2020, 2:18 PM
Reviewer
Meinersbur
Differential Revision
D74382: [CloneFunction] Update loop headers after cloning all blocks in loop.
Parents
rGd37cbda5f9a4: [Hexagon] Define __ELF__ by default.
Branches
Unknown
Tags
Unknown