This is an archive of the discontinued LLVM Phabricator instance.

[InstSimplify] remove quadratic time looping (PR42771)
ClosedPublic

Authored by spatel on Jul 26 2019, 9:07 AM.

Details

Summary

The test case from:
https://bugs.llvm.org/show_bug.cgi?id=42771
...shows a ~30x slowdown caused by the awkward loop iteration (rL207302) that is seemingly done just to avoid invalidating the instruction iterator. We can instead delay instruction deletion until we reach the end of the block (or we could delay until we reach the end of all blocks).

There's a test diff here for a degenerate case with llvm.assume that I didn't step through, but I think that's caused because isInstructionTriviallyDead() may not be true for a function call even if that call has no uses.

This change probably doesn't result in much overall compile-time improvement because we call -instsimplify as a standalone pass only once in the standard -O2 opt pipeline from what I see.

Diff Detail

Event Timeline

spatel created this revision.Jul 26 2019, 9:07 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 26 2019, 9:07 AM
foad added a comment.Jul 26 2019, 9:14 AM

There's a test diff here for a degenerate case with llvm.assume that I didn't step through, but I think that's caused because isInstructionTriviallyDead() may not be true for a function call even if that call has no uses.

The old code would visit %cond1, notice the @llvm.assume, record an assumption that %x==3, and then (because of the "When instructions get deleted re-iterate instead" case) *revisit* the %add and find that it can now be simplified using the assumption. I don't know how important it is to preserve this kind of behaviour.

There's a test diff here for a degenerate case with llvm.assume that I didn't step through, but I think that's caused because isInstructionTriviallyDead() may not be true for a function call even if that call has no uses.

The old code would visit %cond1, notice the @llvm.assume, record an assumption that %x==3, and then (because of the "When instructions get deleted re-iterate instead" case) *revisit* the %add and find that it can now be simplified using the assumption. I don't know how important it is to preserve this kind of behaviour.

It's not important IMO. That test has conflicting assumptions, so we're really just making sure we don't crash. If we're still propagating info from legitimate assumptions, we should be fine.

foad added inline comments.Jul 26 2019, 9:25 AM
llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp
45–48

Why did you change the logic here? Now we might try to simplify an instruction that has no uses but is not trivially dead, which at least makes the comment on L45 slightly wrong.

spatel marked an inline comment as done.Jul 26 2019, 9:46 AM
spatel added inline comments.
llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp
45–48

See comment at line 55 - just because an instruction (a call at least) has no uses does not mean it can not be simplified. I think we should use isInstructionTriviallyDead() as our point of truth here rather than mixing that with a use check.

I'll update the comment at line 45 if you agree.

foad added inline comments.Jul 26 2019, 10:05 AM
llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp
45–48

just because an instruction (a call at least) has no uses does not mean it can not be simplified

As I understand it, there is no point simplifying an instruction that has no uses. "Simplifying" does not change the instruction at all, it just returns a pointer to another (simpler) Value that users of the original instruction could use instead. If there are no users, there is no point doing this.

spatel marked 2 inline comments as done.Jul 26 2019, 12:23 PM
spatel added inline comments.
llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp
45–48

Ok, that sounds good. So let's only try to simplify if an instruction is not trivially dead *and* it has uses. We can only delete the trivially dead, so we only add those to the dead instructions list.

spatel updated this revision to Diff 211982.Jul 26 2019, 12:25 PM
spatel marked an inline comment as done.

Patch updated:
Don't bother trying to simplify an instruction if it has no uses (restores the previous logic).

foad added a comment.Jul 26 2019, 12:59 PM

Looks OK to me now, thanks.

As a follow-up I might try rewriting the whole thing as a worklist algorithm. At the moment it'll do another pass through the whole function even if there is only one instruction left on the ToSimplify list, which seems pretty wasteful. Although as you say, it might not make any difference to overall compile time.

This revision was not accepted when it landed; it landed in state Needs Review.Jul 27 2019, 7:05 AM
This revision was automatically updated to reflect the committed changes.
bjope added a subscriber: bjope.Aug 8 2019, 1:42 PM
bjope added inline comments.
llvm/trunk/lib/Transforms/Scalar/InstSimplifyPass.cpp
47 ↗(On Diff #212054)

I think we need to set Changed = true here as well.

I've got a test case like this:

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -instsimplify -S -o /dev/null -debug-pass=Details 2>&1 | FileCheck --check-prefix DETAILS %s
; RUN: opt < %s -instsimplify -S -o - | FileCheck %s

; Verify that InstSimplifyLegacyPass notifies the pass manager about changes
; being made (when a call is removed CGSCC must be updated).
;
; DETAILS: Made Modification 'Remove redundant instructions' on Function 'main'

define internal void @func_1(i64* nocapture readnone %0) #0 {
; CHECK-LABEL: @func_1(
; CHECK-NEXT:    unreachable
;
  unreachable
}

define i16 @main(i16 %0, i16** nocapture readnone %1) #1 {
; CHECK-LABEL: @main(
; CHECK-NEXT:  bb1:
; CHECK-NEXT:    unreachable
;
bb1:
  call void @func_1(i64* undef)
  unreachable
}

attributes #0 = { noinline norecurse nounwind readnone }
attributes #1 = { norecurse nounwind readnone }

that show that we do not propagate to pass managers that we have removed a call otherwise.

My original reproducer ended up with

opt: ../include/llvm/Analysis/CallGraph.h:180: llvm::CallGraphNode::~CallGraphNode(): Assertion `NumReferences == 0 && "Node deleted while references remain"' failed.

due to not cleaning up the call graph after removing the call.

I'll upload a patch for this (assuming it is the correct solution).

Although, I've also noticed that the same assert was seen in https://bugs.llvm.org/show_bug.cgi?id=42751, and https://bugs.llvm.org/show_bug.cgi?id=42787 is also related to calls being optimized away (afaict). InstSimpllify is not involved in those two PRs. So it might be something else that makes isInstructionTriviallyDead returning that certain calls can be removed nowadays (such as recent changes regarding functions attributes). It should be valid for a FunctionPass to delete a call right, or is it interprocedural to for example look at function attributes to determine that the callee has no side effects? It is illegal for a FunctionPass to inspect a function other than the one being optimized. Is looking at function attributes the same as "inspecting" the callee?

bjope added inline comments.Aug 8 2019, 2:13 PM
llvm/trunk/lib/Transforms/Scalar/InstSimplifyPass.cpp
47 ↗(On Diff #212054)

Suggested fixup is up for review here: https://reviews.llvm.org/D65973