• Rebase
• Simplified this patch

Just JFYI :)
Yes, probably not worth it

JFYI @spatel As I see this is quite similar to issue 53482. I remember some efforts to move out marking tail calls to a separate pass so this should be cheaper to do marking once again (not sure to what extent). It was not landed earlier, but it was ready to land as I understand :)

1. Rebased
2. If EnableOptimizationAcrossLoops is false, then DSE does not run twice
3. Added two more negative tests cases
4. Removed loop transformations from this pass
5. Skip killing store which is not guaranteed to execute

In D109280#3291535, @fhahn wrote:

@vdsered are you still planning on pushing this forward?

In D109280#3043563, @nikic wrote:

In D109280#3043179, @xbolva00 wrote:

I think this would have nontrivial impact on compile time (@nikic ?) and the results from testsuite do not look so promising - I would expect more “hits” to justify (small if possible) compile time regression.

Yes, this has a large negative effect: https://llvm-compile-time-tracker.com/compare.php?from=64eaffb613d0cb7fa7542fa48281a2e617ad8ee9&to=6e7452757e16c4260fa9a5862761a68ed778dbf9&stat=instructions

Agreed that the compile-time impact looks very large, but I *think* it may not be as bad as it looks at the moment. There seems to be a bug in the code that means we effectively run the main DSE loop twice if EnableOptimizationAcrossLoops = false (as in this patch).

Thee patch unconditionally runs the whole main DSE loop again, as below. prepareStateForAcrossLoopOptimization has en early exit if !EnableOptimizationAcrossLoops. Otherwise clears MemDeps and roughly only adds MemDeps with loop ranges. So as a consequence, if !EnableOptimizationAcrossLoops we process *all* MemoryDeps again.

MadeChange |= State.prepareStateForAcrossLoopOptimization();
MadeChange |= runDSEOptimizationLoop(State);

I tried to rebase the patches and collect compile-time numbers with that issue fixed: https://llvm-compile-time-tracker.com/compare.php?from=f622c7b7d33b211517d8fe4f725d1028d786fc08&to=00a8810b123e606c19d9926d11183318323a8752&stat=instructions

NewPM-O3: +0.24%
NewPM-ReleaseThinLTO: +0.39%
NewPM-ReleaseLTO-g: +0.26%

We should still see if we can get those down further, but I think they look more encouraging to start with.

In D115602#3195463, @spatel wrote:

I don't remember seeing this part of x86 codegen before, so adding some more reviewers. I'm also not sure what is recommended as the best perf x86 asm on recent CPUs. Should we be using this for "optsize" too?

Hi, @xbolva00. Are you sure that we can use loop idiom and transform arbitrary loop with a store into let's a memset?

Results for current patch for SingleSource/MultiSource are in the table below. Other don't show any different. Metric is dse.RemainingNumStores

• Transform loops into loop rotated simplify form
• Use guards instead of directly finding icmps
• Implemented optimization for loop + loop
• Decreased the number of times when we compute range for memory intrinsics
• Running DSE loop twice, 1 as it was before and 2 for optimization across loops

Loops lose simplify form in JumpThreading in default pipeline before DSE, for example. I don't know the details and if this is correct or not. There is currently no need for a loop to be in simplify form in DSE in order to work with it (except that it should be a natural loop). It became only required for my optimization.

1. Simplified code by removing unnecessary if-statements
2. Turned AddMemRange lambda to a method
3. memset can be eliminated when memset has constant length and loop has constant iteration count + added a test for this

@ebrevnov I see that in memoryIsNotModifiedBetween function and there is some sort of a local phi-translation (I mean it is used only inside this function) as I understand. Do we need to update this function somehow?

Rebase + fixed opt-pipeline.ll tests for AMDGPU

1. Added one test for a loop with several latches where we don't always overwrite the region where memory intrinsic writes to
2. Fixed formatting
3. Replaced typed pointers with opaque pointers (--force-opaque-pointers is used in tests)
4. Fixed crash caused by an assertion for multiplication of operands with different types
5. Optimized ContinuousMemoryRegion and removed one field from there
6. Added a feature flag EnableMemIntrinsicEliminationByStores to enable/disable this feature at runtime (probably not the best naming)

@ebrevnov
Hi, any progress on the patch? I'd like to work on it if you agreed to that.

@lebedev.ri I don't have commit access

We're going to see difference only in tests @mul_bool_sext_one_extra_user and mul_bool_sext_one_user as other transformations are performed even without the change in the patch. Can someone push baseline tests to show that in the diff?

1. Added an equality check of operands (previously checked if they have exactly one user)
2. Added more tests

I think I should update the patch because LLVM already handles zext

%sx = zext i1 %x to i32
%r = mul i32 %sx, %sx
ret i32 %r

In D104193#2815644, @lebedev.ri wrote:

Correction: what i meant to say is, there are two cases:

1. X == Y, in which case we do not care about use count. this implicitly handles the case where both operands are the same instruction
2. either operand is one-use

Sorry, I didn't see you have already committed :)

Removed name diff in tests

@spatel Done

@spatel you mentioned one more optimization with sext that we miss because of too strict use-constraint here. I'll create another patch for that. I think, it's going to be the last one. I don't know any other transformations for mul/fmul that would benefit from the new method.

1. Replaced hasOneUse + equality of operands with isOnlyUserOfAnyOperand
2. FMF are added to produced fadd
3. Added negative tests

I ask someone to commit the patch if there are no any barriers left for that (Roman's agreement?). I don't have commit access.

Waiting for approval of other reviewers

Rebasing + updated tests with multiple uses in fmul

isOnlyUserOfAnyOperand uses hasOneUser to figure out if at least one of ops has only one user

Moved isOnlyUserOfAnyOperand to Instruction class

As I understand it

Removed irrelevant comments

Replaced std::any_of with llvm::any_of and used I->operands() instead of making range directly via begin/end

Updating diff

1. Fixed warnings of clang-tidy
2. Refactored implementation for this patch

I created a new patch https://reviews.llvm.org/D102698. I will update the current patch when we close the new one.

In D102574#2763320, @spatel wrote:

In D102574#2763294, @vdsered wrote:

I have noticed that there are two similiar transformations below exp2(X) * exp2(Y) -> exp2(X + Y) and exp(X) * exp(Y) -> exp(X + Y) that are done when each operand of multiplication has exactly one use which is n't true if, for example, there is exp2(X) * exp2(X) where exp2(X) is the same instruction, so it can be improved a little. I'm going to update the patch

I recommend that you make that use-check logic into a helper function as a preliminary step, so it can be be accessed from other places. For example, we miss this transform too because the use check is too restrictive:
https://alive2.llvm.org/ce/z/27ryac

I have noticed that there are two similiar transformations below exp2(X) * exp2(Y) -> exp2(X + Y) and exp(X) * exp(Y) -> exp(X + Y) that are done when each operand of multiplication has exactly one use which is n't true if, for example, there is exp2(X) * exp2(X) where exp2(X) is the same instruction, so it can be improved a little. I'm going to update the patch

Calling CreateBinaryIntrinsic instead of CreateIntrinsic for better readability

@reames, I don't have commit access. Can you commit the patch?