This is an archive of the discontinued LLVM Phabricator instance.

[SimplifyCFG] Allow SimplifyCFG hoisting to skip over non-matching instructions
ClosedPublic

Authored by chill on Jul 8 2022, 6:47 AM.

Details

Summary

SimplifyCFG does some common code hoisting, which is limited to hoisting a
sequence of identical instruction in identical order and stops at the first
non-identical instruction.

This patch allows hoisting instruction pairs over same-length sequences of
non-matching instructions. The linear asymptotic complexity of the algorithm
stays the same, there's an extra parameter simplifycfg-hoist-common-skip-limit
serving to limit compilation time and/or the size of the hoisted live ranges.

The patch improves SPECv6/525.x264_r by about 10%.

Diff Detail

Event Timeline

chill created this revision.Jul 8 2022, 6:47 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 8 2022, 6:47 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
chill requested review of this revision.Jul 8 2022, 6:47 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 8 2022, 6:47 AM
nikic added a comment.Jul 8 2022, 7:46 AM

I think you need to be more careful about the side effects here. You generally need to distinguish control flow effects from memory effects. For example, if you skip over an instruction that is not must-exec (i.e. not nothrow or not willreturn), and then want to hoist a udiv (which is side-effect free, but not generally speculatable), then that is illegal and I don't think you currently handle this correctly.

On a more general note, this skipping of non-identical instructions in lock-step seems kind of ... random? It isn't obvious to me why we would typically expect there to be sequences of different instructions that just happen to have the same length.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
1446

Why can Instruction::mayHaveSideEffects() not be used?

1456

Wrong comment indentation here and below.

1463

What does this have to do with the single predecessor? Doesn't this generally hold?

chill marked 3 inline comments as done.Jul 12 2022, 2:56 AM
chill added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
1463

Indeed.

chill marked an inline comment as done.Jul 12 2022, 3:02 AM

I think you need to be more careful about the side effects here. You generally need to distinguish control flow effects from memory effects. For example, if you skip over an instruction that is not must-exec (i.e. not nothrow or not willreturn), and then want to hoist a udiv (which is side-effect free, but not generally speculatable), then that is illegal and I don't think you currently handle this correctly.

Thanks for the review, I think I have fixed those issues.

On a more general note, this skipping of non-identical instructions in lock-step seems kind of ... random? It isn't obvious to me why we would typically expect there to be sequences of different instructions that just happen to have the same length.

Indeed, it relies on ... luck, but that applies to the original function as well, isn't it ?

And it turns out, it happens: when compiling llvm-test-suite, the HoistThenElseCodeToIf triggers 3206 times, of these
722 times at least one instruction pair was hoisted over at least one non-matching pair (stats collected as in https://reviews.llvm.org/D129551)

chill added a comment.Jul 12 2022, 3:25 AM

And it turns out, it happens: when compiling llvm-test-suite, the HoistThenElseCodeToIf triggers 3206 times, of these
722 times at least one instruction pair was hoisted over at least one non-matching pair (stats collected as in https://reviews.llvm.org/D129551)

TBH, some of those might be identical pairs of debug intrinsics, which aren't very interesting.

fhahn added a comment.Jul 19 2022, 3:07 AM

I think you need to be more careful about the side effects here. You generally need to distinguish control flow effects from memory effects. For example, if you skip over an instruction that is not must-exec (i.e. not nothrow or not willreturn), and then want to hoist a udiv (which is side-effect free, but not generally speculatable), then that is illegal and I don't think you currently handle this correctly.

Thanks for the review, I think I have fixed those issues.

It looks like we are missing test-coverage for at least some of those case. Could you add extra tests to cover the checks you added?

llvm/test/Transforms/SimplifyCFG/hoist-common-skip.ll
76

the test case can be further simplified, e.g. there's no need to load & compare here. instead the condition can simplify be passed as argument.

Similarly, there's no need to return an i32 from the function or have multiple diverging instructions in the blocks.

chill updated this revision to Diff 446393.Jul 21 2022, 2:08 AM
chill marked an inline comment as done.
dmgreen accepted this revision.Jul 28 2022, 2:16 AM

I would probably have just bailed out if it reached an instruction with side-effects, but as far as I can see this seems like it should be OK.

LGMT

This revision is now accepted and ready to land.Jul 28 2022, 2:16 AM
This revision was landed with ongoing or failed builds.Jul 31 2022, 11:56 PM
This revision was automatically updated to reflect the committed changes.
nikic added inline comments.Aug 1 2022, 12:15 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
1558

This check should not be present (likely rebase mistake).

1638

This check is still incorrect. Consider this example:

define i16 @f7(i1 %c, ptr %a, ptr %b) {
; CHECK-LABEL: @f7(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    store i16 0, ptr [[B:%.*]], align 2
; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    [[VA:%.*]] = load i16, ptr [[A:%.*]], align 2
; CHECK-NEXT:    br label [[IF_END:%.*]]
; CHECK:       if.else:
; CHECK-NEXT:    [[VB:%.*]] = load i16, ptr [[B]], align 2
; CHECK-NEXT:    br label [[IF_END]]
; CHECK:       if.end:
; CHECK-NEXT:    [[V:%.*]] = phi i16 [ [[VA]], [[IF_THEN]] ], [ [[VB]], [[IF_ELSE]] ]
; CHECK-NEXT:    ret i16 [[V]]
;
entry:
  br i1 %c, label %if.then, label %if.else

if.then:
  %va = load i16, ptr %a, align 2
  store i16 0, ptr %b, align 2
  br label %if.end

if.else:
  %vb = load i16, ptr %b, align 2
  store i16 0, ptr %b, align 2
  br label %if.end

if.end:
  %v = phi i16 [ %va, %if.then ], [ %vb, %if.else ]
  ret i16 %v
}

You are currently hoisting the store above the loads.

What you want to check here is mayReadOrWriteMemory, not mayHaveSideEffects. (The non-memory effects are modeled by the other check now).

chill added a comment.Aug 1 2022, 12:38 AM

Thanks, I'll have look.

chill reopened this revision.Aug 2 2022, 2:09 AM
This revision is now accepted and ready to land.Aug 2 2022, 2:09 AM
chill planned changes to this revision.Aug 2 2022, 2:10 AM
chill updated this revision to Diff 449592.Aug 3 2022, 1:54 AM
This revision is now accepted and ready to land.Aug 3 2022, 1:54 AM
chill requested review of this revision.Aug 3 2022, 1:55 AM
chill marked 2 inline comments as done.
nikic accepted this revision.Aug 30 2022, 1:43 AM

LGTM

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
1440

instructins -> instructions

This revision is now accepted and ready to land.Aug 30 2022, 1:43 AM
chill updated this revision to Diff 457931.Sep 5 2022, 4:21 AM
chill marked an inline comment as done.

Thanks!

This revision was landed with ongoing or failed builds.Sep 5 2022, 7:14 AM
This revision was automatically updated to reflect the committed changes.
hans added a subscriber: hans.Sep 9 2022, 9:51 AM

Heads up that we're seeing test failures in Chromium that bisect to this: https://bugs.chromium.org/p/chromium/issues/detail?id=1361629

We're still investigating, just adding an early note in case others have also hit problems.

this looks to be hoisting llvm.stacksave past a previous alloca inalloca which breaks win32 (inalloca docs). trying to come up with a reduced repro

this looks to be hoisting llvm.stacksave past a previous alloca inalloca which breaks win32 (inalloca docs). trying to come up with a reduced repro

https://reviews.llvm.org/D133730

foad added a subscriber: foad.Apr 27 2023, 7:40 AM
foad added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
1576

Leaving these return instructions in the isIdenticalToWhenDefined case seems wrong, since it means that instructions that are identical but fail this check are treated more pessimistically than instructions that are not identical.

chill added inline comments.Apr 27 2023, 8:00 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
1576

You mean ,in that case we should enter that part where we skip over those calls, increment
NumSkipped and continue (i.e. the part that starts at line 1638 below)?

Yeah, makes sense.

chill added inline comments.Apr 28 2023, 2:07 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
1576

OTOH, a musttail call can only be followed by a ret or a bitcast.

I guess I don't understand what we are missing here ...

foad added inline comments.Apr 28 2023, 3:09 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
1576

I didn't really mean this specific return, I meant all of the returns from here down to line 1595. D149365 fixes them all and shows a case where it improves handling of convergent calls.

chill marked 2 inline comments as done.Apr 28 2023, 3:17 AM
chill added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
1576

Yeah, I saw the other patch. Thanks!