This is an archive of the discontinued LLVM Phabricator instance.

Differential D59312

AMDGPU: Fix a SIAnnotateControlFlow issue when there are multiple backedges.
ClosedPublic

Authored by cfang on Mar 13 2019, 10:50 AM.

Details

Reviewers
msearles
nhaehnle
arsenm
Commits
rG989ec59c9f04: AMDGPU: Fix a SIAnnotateControlFlow issue when there are multiple backedges.
rL356298: AMDGPU: Fix a SIAnnotateControlFlow issue when there are multiple backedges.
Summary

At the exit of the loop, the compiler uses a register to remember and accumulate the number of threads that have already exited. When all active threads exit the loop, this register is used to restore the exec mask, and the execution continues for the post loop code.

When there is a "continue" in the loop, the compiler made a mistake to reset the register to 0 when the "continue" backedge is taken. This will result in some threads not executing the post loop code as they are supposed to.

This patch fixed the issue ( the test is yet to be developed).

Diff Detail

Repository
rL LLVM

Event Timeline

cfang created this revision.Mar 13 2019, 10:50 AM
Herald added subscribers: jdoerfert, t-tye, tpr and 5 others. · View Herald TranscriptMar 13 2019, 10:50 AM
msearles added inline comments.Mar 13 2019, 10:53 AM
lib/Target/AMDGPU/SIAnnotateControlFlow.cpp
272 ↗(On Diff #190450)

Typo in comment: shouldl

arsenm added a comment.Mar 13 2019, 10:56 AM

Definitely needs several tests

cfang updated this revision to Diff 190658.Mar 14 2019, 10:18 AM

Fix a typo and add a test.

arsenm added inline comments.Mar 14 2019, 4:42 PM
lib/Target/AMDGPU/SIAnnotateControlFlow.cpp
274 ↗(On Diff #190658)

Could this still break for some block that is in the loop, but doesn't dominate BB?

test/CodeGen/AMDGPU/si-annotatecfg-multiple-backedges.ll
2 ↗(On Diff #190658)

I kind of think we should just start generating the checks for any test that deals with control flow

cfang marked 2 inline comments as done.Mar 14 2019, 9:19 PM
cfang added inline comments.
lib/Target/AMDGPU/SIAnnotateControlFlow.cpp
274 ↗(On Diff #190658)

I don’t think so. Given single entry single exit regions, and inside the loop, when BB and Pred are both backedge blocks, either Pred dominates BB or BB dominates Pred.

test/CodeGen/AMDGPU/si-annotatecfg-multiple-backedges.ll
2 ↗(On Diff #190658)

What do you want me to do here?

cfang marked 2 inline comments as done.Mar 14 2019, 9:22 PM
arsenm added inline comments.Mar 15 2019, 9:39 AM
test/CodeGen/AMDGPU/si-annotatecfg-multiple-backedges.ll
2 ↗(On Diff #190658)

Use utils/update_test_checks.py instead of the manually write checks. You just copied the output anyway, just for a subset of the function

cfang updated this revision to Diff 190857.Mar 15 2019, 11:12 AM

update the test with update_test_checks.py

arsenm added a comment.Mar 15 2019, 12:38 PM

The test needs an expansive comment describing what this is testing.

LGTM, but it would be better if Nicolai also looked at this

cfang updated this revision to Diff 190891.Mar 15 2019, 1:27 PM

Add comment to the test

nhaehnle added a comment.Mar 15 2019, 1:28 PM

Hmm, this is fragile -- I think your reasoning about domination is mostly sound, except when there's uniform control flow inside the loop itself, in which case I'm not sure. That said, it seems to me that the domination check is conservative, and your change shouldn't break anything that wasn't broken before, and a proper fix is potentially much more difficult.

Agree with Matt that using update_test_checks.py is a good idea, apart from that I think this can go in.

nhaehnle accepted this revision.Mar 15 2019, 1:28 PM

LGTM

This revision is now accepted and ready to land.Mar 15 2019, 1:28 PM
Closed by commit rL356298: AMDGPU: Fix a SIAnnotateControlFlow issue when there are multiple backedges. (authored by chfang). · Explain WhyMar 15 2019, 2:02 PM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptMar 15 2019, 2:02 PM

Revision Contents

PathSize
llvm/
trunk/
lib/
Target/
AMDGPU/
13 lines
test/
CodeGen/
AMDGPU/
61 lines

Diff 190894

llvm/trunk/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp

Show First 20 Lines • Show All 258 Lines • ▼ Show 20 Linesvoid SIAnnotateControlFlow::handleLoop(BranchInst *Term) {
BasicBlock *Target = Term->getSuccessor(1); BasicBlock *Target = Term->getSuccessor(1);
PHINode *Broken = PHINode::Create(Int64, 0, "phi.broken", &Target->front()); PHINode *Broken = PHINode::Create(Int64, 0, "phi.broken", &Target->front());
Value *Cond = Term->getCondition(); Value *Cond = Term->getCondition();
Term->setCondition(BoolTrue); Term->setCondition(BoolTrue);
Value *Arg = handleLoopCondition(Cond, Broken, L, Term); Value *Arg = handleLoopCondition(Cond, Broken, L, Term);
for (BasicBlock *Pred : predecessors(Target)) for (BasicBlock *Pred : predecessors(Target)) {
Broken->addIncoming(Pred == BB ? Arg : Int64Zero, Pred); Value *PHIValue = Int64Zero;
if (Pred == BB) // Remember the value of the previous iteration.
PHIValue = Arg;
// If the backedge from Pred to Target could be executed before the exit
// of the loop at BB, it should not reset or change "Broken", which keeps
// track of the number of threads exited the loop at BB.
else if (L->contains(Pred) && DT->dominates(Pred, BB))
PHIValue = Broken;
Broken->addIncoming(PHIValue, Pred);
}
Term->setCondition(CallInst::Create(Loop, Arg, "", Term)); Term->setCondition(CallInst::Create(Loop, Arg, "", Term));
push(Term->getSuccessor(0), Arg); push(Term->getSuccessor(0), Arg);
} }
/// Close the last opened control flow /// Close the last opened control flow
void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) { void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) {
▲ Show 20 Lines • Show All 80 Lines • Show Last 20 Lines

llvm/trunk/test/CodeGen/AMDGPU/si-annotatecfg-multiple-backedges.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -mtriple=amdgcn-- -S -structurizecfg -si-annotate-control-flow %s | FileCheck -check-prefix=OPT %s
; This test is designed to check that the backedge from a prior block won't
; reset the variable introduced to record and accumulate the number of threads
; which have already exited the loop.
define amdgpu_kernel void @multiple_backedges(i32 %arg, i32* %arg1) {
; OPT-LABEL: @multiple_backedges(
; OPT-NEXT: entry:
; OPT-NEXT: [[TMP:%.*]] = tail call i32 @llvm.amdgcn.workitem.id.x()
; OPT-NEXT: [[TMP2:%.*]] = shl nsw i32 [[ARG:%.*]], 1
; OPT-NEXT: br label [[LOOP:%.*]]
; OPT: loop:
; OPT-NEXT: [[PHI_BROKEN1:%.*]] = phi i64 [ [[TMP7:%.*]], [[LOOP_END:%.*]] ], [ [[PHI_BROKEN1]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
; OPT-NEXT: [[PHI_BROKEN:%.*]] = phi i64 [ 0, [[LOOP_END]] ], [ [[TMP0:%.*]], [[LOOP]] ], [ 0, [[ENTRY]] ]
; OPT-NEXT: [[TMP4:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[TMP5:%.*]], [[LOOP]] ], [ 0, [[LOOP_END]] ]
; OPT-NEXT: [[TMP5]] = add nsw i32 [[TMP4]], [[TMP]]
; OPT-NEXT: [[TMP6:%.*]] = icmp slt i32 [[ARG]], [[TMP5]]
; OPT-NEXT: [[TMP0]] = call i64 @llvm.amdgcn.if.break(i1 [[TMP6]], i64 [[PHI_BROKEN]])
; OPT-NEXT: [[TMP1:%.*]] = call i1 @llvm.amdgcn.loop(i64 [[TMP0]])
; OPT-NEXT: br i1 [[TMP1]], label [[LOOP_END]], label [[LOOP]]
; OPT: loop_end:
; OPT-NEXT: call void @llvm.amdgcn.end.cf(i64 [[TMP0]])
; OPT-NEXT: [[EXIT:%.*]] = icmp sgt i32 [[TMP5]], [[TMP2]]
; OPT-NEXT: [[TMP7]] = call i64 @llvm.amdgcn.if.break(i1 [[EXIT]], i64 [[PHI_BROKEN1]])
; OPT-NEXT: [[TMP3:%.*]] = call i1 @llvm.amdgcn.loop(i64 [[TMP7]])
; OPT-NEXT: br i1 [[TMP3]], label [[LOOP_EXIT:%.*]], label [[LOOP]]
; OPT: loop_exit:
; OPT-NEXT: call void @llvm.amdgcn.end.cf(i64 [[TMP7]])
; OPT-NEXT: [[TMP12:%.*]] = zext i32 [[TMP]] to i64
; OPT-NEXT: [[TMP13:%.*]] = getelementptr inbounds i32, i32* [[ARG1:%.*]], i64 [[TMP12]]
; OPT-NEXT: [[TMP14:%.*]] = addrspacecast i32* [[TMP13]] to i32 addrspace(1)*
; OPT-NEXT: store i32 [[TMP5]], i32 addrspace(1)* [[TMP14]], align 4
; OPT-NEXT: ret void
;
entry:
%tmp = tail call i32 @llvm.amdgcn.workitem.id.x()
%tmp2 = shl nsw i32 %arg, 1
br label %loop
loop:
%tmp4 = phi i32 [ 0, %entry ], [ %tmp5, %loop ], [ 0, %loop_end ]
%tmp5 = add nsw i32 %tmp4, %tmp
%tmp6 = icmp slt i32 %arg, %tmp5
br i1 %tmp6, label %loop_end, label %loop
loop_end:
%exit = icmp sgt i32 %tmp5, %tmp2
br i1 %exit, label %loop_exit, label %loop
loop_exit:
%tmp12 = zext i32 %tmp to i64
%tmp13 = getelementptr inbounds i32, i32* %arg1, i64 %tmp12
%tmp14 = addrspacecast i32* %tmp13 to i32 addrspace(1)*
store i32 %tmp5, i32 addrspace(1)* %tmp14, align 4
ret void
}
; Function Attrs: nounwind readnone speculatable
declare i32 @llvm.amdgcn.workitem.id.x()