This is an archive of the discontinued LLVM Phabricator instance.

[GuardWidening] Freeze the introduced use.
ClosedPublic

Authored by skatkov on Mar 23 2023, 1:20 AM.

Details

Summary

Guard widening optimization is able to move the condition from one
guard to the previous one. As a result if the condition is poison
and orginal second guard is never executed but the first one does,
we introduce undefined behavior which was not observed in original
program.

To resolve the issue we must freeze the condition we are moving.
However optimization itself does not know how to work with freeze.
Additionally optimization is written in incremental way.
For example we have three guards
G1(base + 8 < L)
G2(base + 16 < L)
G3(base + 24 < L)

On the first step GW will combine G1 and G2 as
G1(base + 8 < L && freeze(base + 16 < L))
G2(true)
G3(base + 24 < L)
while combining G1 and G3 base appears to be different.

To keep optimization enabled after freezing the moving condition, the
freeze instruction is pushed as much as possible and later all uses
of frozen values are replaced with frozen version.

This is similar what instruction combining does but more aggressively.

Diff Detail

Unit TestsFailed

Event Timeline

skatkov created this revision.Mar 23 2023, 1:20 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 23 2023, 1:20 AM
skatkov requested review of this revision.Mar 23 2023, 1:20 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 23 2023, 1:20 AM
skatkov updated this revision to Diff 507955.Mar 23 2023, 8:25 PM

Update test to specify that long of length is noundef.

mkazantsev added inline comments.Mar 24 2023, 3:49 AM
llvm/lib/Transforms/Scalar/GuardWidening.cpp
212–214

Can this be a part of some Utils maybe? It looks generic enough.

567

Add comment?

568

use another name here, overriden I is confusing.

601
  1. How can getFreezeInsertPt be null? Is there a test on that?
  2. Is isa<Instruction>(Op) check really needed here? You already do this check inside of getFreezeInsertPt, and I guess for it it never fails.
606

Do I understand correctly that if any of these instructions is a long chain of non-overflowing arithmetics, we will just wipe flags from all of them to the very roots. hypothetically even from entire function? Isn't it an overkill?

I think we should put a limit somewhere and do not go above it. Maybe the widened guard point should be this limit.

615

Maybe add statistic to count how many freezes we add?

618

Erase/mark trivially dead instructions for erasing?

Will update patch on Monday.

llvm/lib/Transforms/Scalar/GuardWidening.cpp
212–214

If there will be other users we can add this to utils.
At this moment it is similar what InstCombine does but a lot more aggressively.

567

will do

568

agreed

601

If Op is a result of invoke, and there is a critical edge, you have no place to put freeze.
In function getFreezeInsertPt, getInsertionPointAfterDef() may return false.

I will add a test.

Here. isa<Instruction>(Op) is just a quick check to avoid computation of first instruction in a function it is not an instruction. But we can safely remove this check.

606

You are correct. What limit do you propose, just arbitrary number of processed instructions?

615

ok, will do.

618

there is no dead instructions here. V will remains as it has FI as a user.

mkazantsev added inline comments.Mar 26 2023, 11:13 PM
llvm/lib/Transforms/Scalar/GuardWidening.cpp
212–214

Maybe add a TODO comment like "move to utils"?

601

For invoke, you can still freeze its result in normal path. But I see the point.

606

I dunno... Do you have data on downstream CT impact? Might not be a big deal, after all.

skatkov updated this revision to Diff 508512.Mar 27 2023, 12:50 AM

PTAL.

llvm/lib/Transforms/Scalar/GuardWidening.cpp
212–214

Let's keep it as is for a while.

601

Added a test and fixed a bug, thanks.

The test is added to posion.ll where for invoke we cannot insert it to normal path due to phi node user..

606

For a while, I do not see any problems. If they appear, we'll add some limit.

615

added

skatkov updated this revision to Diff 508892.Mar 27 2023, 10:02 PM

One more bug fixed. Additional test for the bug is added to posion.ll

mkazantsev added inline comments.Mar 28 2023, 5:49 AM
llvm/lib/Transforms/Scalar/GuardWidening.cpp
568

This is not true for Phis

569

non-alloca? Better say first available insertion point in the entry block...

571

could be const DominatorTree &DT

575

How is this possible?

581

I by default should dominate all its users. What am I missing here?

587

Maybe to reduce nest of code above, do

auto *I = dyn_cast<Instruction>(V);
if (!I)
  return &*DT.getRoot()->getFirstNonPHIOrDbgOrAlloca();
// code for instruction with 1 less nest
610

Why we can always cast this to operator? What if it's not?

skatkov added inline comments.Mar 28 2023, 8:43 PM
llvm/lib/Transforms/Scalar/GuardWidening.cpp
575

Invoke is in latch is used as a condition to go to header in normal path.
As a result getInsertionPointAfterDef() will return first non-phi instruction in header.

In this case I does not dominate Res. Actually it breaks SSA.

581

No, if the user is a phi node in header.

610

Any Instruction can be casted to Operator.

skatkov updated this revision to Diff 509211.Mar 28 2023, 9:16 PM
skatkov marked an inline comment as done.
skatkov added inline comments.
llvm/lib/Transforms/Scalar/GuardWidening.cpp
568

Doc is re-frased.

569

Doc is re-frased.

571

Changed.

587

Done

mkazantsev accepted this revision.Mar 28 2023, 9:43 PM
mkazantsev added inline comments.
llvm/lib/Transforms/Scalar/GuardWidening.cpp
581

Ok, got it.

610

Ok, I see how it works.

This revision is now accepted and ready to land.Mar 28 2023, 9:43 PM
This revision was landed with ongoing or failed builds.Mar 29 2023, 2:31 AM
This revision was automatically updated to reflect the committed changes.
skatkov marked an inline comment as done.

The patch has been reverted due to failures of CHECK-NEXT tests on buildbots due to it adds freeze instructions without any specific order by just iterating over SmallSet, need to fix it.