This is an archive of the discontinued LLVM Phabricator instance.

[GuardWidening] Use freeze to widen using possible poison value.
AbandonedPublic

Authored by skatkov on Jun 19 2022, 11:20 PM.

Details

Summary

During the guard widening we can add a poison use in the first guard which
can result in undefined behavior which were not before due to this guard could
guards us from it.

To avoid this behavior we can use freeze instruction.

Diff Detail

Event Timeline

skatkov created this revision.Jun 19 2022, 11:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 19 2022, 11:20 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
skatkov requested review of this revision.Jun 19 2022, 11:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 19 2022, 11:20 PM
fhahn added a subscriber: fhahn.Jun 20 2022, 12:51 AM
fhahn added inline comments.
llvm/test/Transforms/GuardWidening/basic.ll
379

It seems it would be sufficient to only freeze the final value?

skatkov updated this revision to Diff 438429.Jun 20 2022, 9:34 AM
skatkov marked an inline comment as done.
skatkov added inline comments.
llvm/test/Transforms/GuardWidening/basic.ll
379

Thanks for noting that.

nikic added a subscriber: nikic.Jun 20 2022, 9:56 AM

Does this actually need freeze, rather than just logical and instead of bitwise and?

RKSimon retitled this revision from [GuardWindening] Use freeze to widen using possible poison value. to [GuardWidening] Use freeze to widen using possible poison value..Jun 20 2022, 11:01 AM
skatkov marked an inline comment as done.Jun 20 2022, 8:04 PM

Does this actually need freeze, rather than just logical and instead of bitwise and?

Do we have logical and?

Logical and is select i1 %c1, i1 %c2, i1 false.

Logical and is select i1 %c1, i1 %c2, i1 false.

Also, IRBuilder::CreateLogicalAnd

I tend to re-write the patch and introduce the option to use freeze or logical and then choose the best one.
To have improved version of this patch for freeze and implement select solution I'll need to do some preparation work to know what condition comes from the widening guard (it should be first in logcal and and there is no need to freeze it) and what comes from other guard.
So, please be tuned.

Thank you, guys for suggestions.

skatkov planned changes to this revision.Jun 21 2022, 7:41 AM
skatkov updated this revision to Diff 441638.Jul 1 2022, 1:51 AM

I come up with this version of the solution.

Dear reviewers, I would appreciate the review.

Could you please give a brief outline of the approach?

Could you please give a brief outline of the approach?

Guard Widening uses two main ways to wide the current guard.
The second one is just combine conditions of two guards and apply it to the first one.
For this case we just use c1 & freeze(c2) in case we cannot prove that c2 is not a poison.
If we prove that c2 is not a poison the result is just c1& c2.

The first case is more complex.
First, it parses the conditions of first guard (guard to wide) and second one.
In case all conditions are and operation of "range checks" it will merge them.
Range check is a condition of the form base + offset unsigned less then length.
For each condition, case, offset and length can be different but offset must be an integer constant.
I try to reduce the number of freeze usages, so during the parsing we detect some facts.
While parsing the first guard we consider that all values do not require freeze due to if base or length were poison than
we had a UB(guard on poison value) in the original program so we do not care.
Parsing the second guard we conservatively suggest that freeze will be needed due to we will hoist the condition which potentially
may be a poison at the point of the first guard.
Also of we meet freeze instruction we go through it in parsing but consider that everything down require a freeze even if it comes from
the first guard (most probably it is a result of previous guard widening of the simple form).

Later optimization consider all Bi + OFFi < Li and split them into groups where Bi and Li are equal.
For each group it does the following:
if the size of the group is less then 3 then do not combine this group.
Otherwise if the OFFi from this group does not satisfy conditions required for this optimization Do not combine anything - just bailout.
Finally for this group combine all range checks and leave only B + OFFmin < L & B + OFFmax < L.
It is possible that both conditions comes from the second guard and will be hoisted so we need to freeze B and L.
However if B or L used in condition came from the first guard we can avoid freezing due to the same reason - we had UB in the original
program if B or L were poison.

After all groups are processed we combine all checks with arithmetic and operation but freeze those elements which require this.

I hope it helps.
the first guard

mkazantsev accepted this revision.Dec 8 2022, 9:04 PM
This revision is now accepted and ready to land.Dec 8 2022, 9:04 PM