This is an archive of the discontinued LLVM Phabricator instance.

Differential D115247

[EarlyCSE] Retain poison flags, if program is UB if poison.
ClosedPublic

Authored by fhahn on Dec 7 2021, 5:52 AM.

Details

Reviewers
nikic
reames
nlopes
spatel
Commits
rG361111906ba4: [EarlyCSE] Retain poison flags, if program is UB if poison.
Summary

Poison-generating flags can be retained during CSE on the earlier
instruction , *if* the earlier instruction being poison causes UB.

Note that the code as written assumes that an instruction cannot have
poison-generating flags and fast-math flags, but I am not sure this is
always true. Should we add a version of andIRFlags that selectively
allows AND'ing fast-math flags only?

https://alive2.llvm.org/ce/z/4K3D7P

Diff Detail

Unit TestsFailed

TimeTest
680 msx64 debian > AddressSanitizer-x86_64-linux.TestCases::non-executable-pc.cpp
810 msx64 debian > HWAddressSanitizer-x86_64.TestCases::build-ids.c

Event Timeline

fhahn created this revision.Dec 7 2021, 5:52 AM
Herald added a subscriber: hiraditya. · View Herald TranscriptDec 7 2021, 5:52 AM
fhahn requested review of this revision.Dec 7 2021, 5:52 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 7 2021, 5:52 AM
Harbormaster completed remote builds in B137890: Diff 392374.Dec 7 2021, 6:33 AM
nikic added a comment.Dec 8 2021, 12:14 AM

Note that the code as written assumes that an instruction cannot have
poison-generating flags and fast-math flags, but I am not sure this is
always true. Should we add a version of andIRFlags that selectively
allows AND'ing fast-math flags only?

Yes, I think so. Or more specifically, to only and the non-poison-generating flags. There are some FMF that are poison generating, but we don't currently treat them as such in various "poison generating" queries. If that changed in the future, we should still handle it correctly.

fhahn mentioned this in D115527: [Instruction] Split out 'and' of non-poison generating flags (NFC)..Dec 10 2021, 8:05 AM
fhahn added a parent revision: D115527: [Instruction] Split out 'and' of non-poison generating flags (NFC)..Dec 10 2021, 8:05 AM
fhahn updated this revision to Diff 393497.Dec 10 2021, 8:06 AM
In D115247#3178708, @nikic wrote:

Note that the code as written assumes that an instruction cannot have
poison-generating flags and fast-math flags, but I am not sure this is
always true. Should we add a version of andIRFlags that selectively
allows AND'ing fast-math flags only?

Yes, I think so. Or more specifically, to only and the non-poison-generating flags. There are some FMF that are poison generating, but we don't currently treat them as such in various "poison generating" queries. If that changed in the future, we should still handle it correctly.

I split out the code to 'and' non-poison generating flags in D115527 and update the patch to use it in case the program is not UB if I is poison.

spatel added a comment.Dec 10 2021, 8:14 AM
In D115247#3178708, @nikic wrote:

Note that the code as written assumes that an instruction cannot have
poison-generating flags and fast-math flags, but I am not sure this is
always true. Should we add a version of andIRFlags that selectively
allows AND'ing fast-math flags only?

Yes, I think so. Or more specifically, to only and the non-poison-generating flags. There are some FMF that are poison generating, but we don't currently treat them as such in various "poison generating" queries. If that changed in the future, we should still handle it correctly.

We have a few poison-related patches in progress currently, so there may be some interaction between these:
D115460 would add ninf/nnan to the list of poison-generating flags.
D115526 would remove a demanded elements restriction for propagation of flags

reames requested changes to this revision.Dec 10 2021, 8:26 AM

Conceptually this is clear enough, but I'm worried about compile time impact. Do you have any numbers to share? This looks potentially quite expensive as the analysis to prove UB if poison is not really cacheable.

We can improve compile time by e.g. only doing the search on things which might produce poison flags, but the first step is knowing if we have a problem.

llvm/lib/Transforms/Scalar/EarlyCSE.cpp
1369–1379

Per LangRef, nnan and ninf are poison generating. The handling on the other FMF flags is unclear to me. I'd suggest as a stepping stone restricting the preservation of flags to non-float instructions while leaving a clear TODO.

This revision now requires changes to proceed.Dec 10 2021, 8:26 AM
Harbormaster completed remote builds in B138673: Diff 393497.Dec 10 2021, 9:14 AM
fhahn updated this revision to Diff 393563.Dec 10 2021, 11:56 AM

Updated again to be independet of D115527 again, always use 'and' of flags for floating point insts.

In D115247#3185627, @spatel wrote:

We have a few poison-related patches in progress currently, so there may be some interaction between these:
D115460 would add ninf/nnan to the list of poison-generating flags.
D115526 would remove a demanded elements restriction for propagation of flags

Thanks for those references. I think D115460 would impact D115527, but not this patch directly. I went ahead and applied Philip's suggestion to always take the 'and' for floating point instructions.

In D115247#3185688, @reames wrote:

Conceptually this is clear enough, but I'm worried about compile time impact. Do you have any numbers to share? This looks potentially quite expensive as the analysis to prove UB if poison is not really cacheable.

We can improve compile time by e.g. only doing the search on things which might produce poison flags, but the first step is knowing if we have a problem.

Compile-time looks neutral when limiting the UB check to instructions with poison-generating flags, as in the original version, with the highest geoman increase of +0.04%. Note that SPASS for NewPM-ReleaseThinLTO has an increase of +0.17% and is highlighted red. For that workload, there's also a +0.16% size increase, so the increase is likely from additional transformations.

http://llvm-compile-time-tracker.com/compare.php?from=2a31b240df1ce1724960fd7cf98f673064b44206&to=e3d5cc5e3011f38eb95dc60f4a4762a40a7031a7&stat=instructions

fhahn marked an inline comment as done.Dec 10 2021, 11:58 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/EarlyCSE.cpp
1369–1379

Update and added todo. D115527 still seems helpful, but probably only once the poison-generating FMFs are explicitly handled.

nikic added inline comments.Dec 10 2021, 11:59 AM
llvm/lib/Transforms/Scalar/EarlyCSE.cpp
1376

This should be checking isa<FPMathOperator> instead. It's not necessarily the result type that's a float (e.g. fcmp).

fhahn updated this revision to Diff 393567.Dec 10 2021, 12:21 PM
fhahn marked an inline comment as done.

Check for FPMathOperator.

fhahn marked an inline comment as done.Dec 10 2021, 12:21 PM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/EarlyCSE.cpp
1376

fixed, thanks!

nikic accepted this revision.Dec 10 2021, 12:25 PM

LG

llvm/lib/Transforms/Scalar/EarlyCSE.cpp
1376

I think this would be more obvious as isa<FPMathOperator>(I) || (I->hasPoisonGeneratingFlags() && !programUndefindeIfPoison(I)), though in practice it's the same.

Harbormaster completed remote builds in B138716: Diff 393567.Dec 10 2021, 1:17 PM
This revision was not accepted when it landed; it landed in state Needs Review.Dec 11 2021, 7:12 AM
This revision was landed with ongoing or failed builds.
Closed by commit rG361111906ba4: [EarlyCSE] Retain poison flags, if program is UB if poison. (authored by fhahn). · Explain Why
This revision was automatically updated to reflect the committed changes.
fhahn marked an inline comment as done.
fhahn added a commit: rG361111906ba4: [EarlyCSE] Retain poison flags, if program is UB if poison..

Revision Contents

PathSize
llvm/
lib/
Transforms/
Scalar/
13 lines
test/
Transforms/
EarlyCSE/
2 lines

Diff 393567

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

Show First 20 Lines • Show All 1,360 Lines • ▼ Show 20 Lines if (SimpleValue::canHandle(&Inst)) {
// See if the instruction has an available value. If so, use it. // See if the instruction has an available value. If so, use it.
if (Value *V = AvailableValues.lookup(&Inst)) { if (Value *V = AvailableValues.lookup(&Inst)) {
LLVM_DEBUG(dbgs() << "EarlyCSE CSE: " << Inst << " to: " << *V LLVM_DEBUG(dbgs() << "EarlyCSE CSE: " << Inst << " to: " << *V
<< '\n'); << '\n');
if (!DebugCounter::shouldExecute(CSECounter)) { if (!DebugCounter::shouldExecute(CSECounter)) {
LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n"); LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
continue; continue;
} }
if (auto *I = dyn_cast<Instruction>(V)) if (auto *I = dyn_cast<Instruction>(V)) {
// If I being poison triggers UB, there is no need to drop those
// flags. Otherwise, only retain flags present on both I and Inst.
// TODO: Currently some fast-math flags are not treated as
// poison-generating even though they should. Until this is fixed,
// always retain flags present on both I and Inst for floating point
// instructions.
if (isa<FPMathOperator>(I) || !I->hasPoisonGeneratingFlags() ||
nikicUnsubmitted
Done
ReplyInline Actions

This should be checking isa<FPMathOperator> instead. It's not necessarily the result type that's a float (e.g. fcmp).

nikic: This should be checking `isa<FPMathOperator>` instead. It's not necessarily the result type…
fhahnAuthorUnsubmitted
Done
ReplyInline Actions

fixed, thanks!

fhahn: fixed, thanks!
nikicUnsubmitted
Not Done
ReplyInline Actions

I think this would be more obvious as isa<FPMathOperator>(I) || (I->hasPoisonGeneratingFlags() && !programUndefindeIfPoison(I)), though in practice it's the same.

nikic: I think this would be more obvious as `isa<FPMathOperator>(I) || (I->hasPoisonGeneratingFlags()…
!programUndefinedIfPoison(I))
I->andIRFlags(&Inst); I->andIRFlags(&Inst);
}
reamesUnsubmitted
Done
ReplyInline Actions

Per LangRef, nnan and ninf are poison generating. The handling on the other FMF flags is unclear to me. I'd suggest as a stepping stone restricting the preservation of flags to non-float instructions while leaving a clear TODO.

reames: Per LangRef, nnan and ninf are poison generating. The handling on the other FMF flags is…
fhahnAuthorUnsubmitted
Done
ReplyInline Actions

Update and added todo. D115527 still seems helpful, but probably only once the poison-generating FMFs are explicitly handled.

fhahn: Update and added todo. D115527 still seems helpful, but probably only once the poison…
Inst.replaceAllUsesWith(V); Inst.replaceAllUsesWith(V);
salvageKnowledge(&Inst, &AC); salvageKnowledge(&Inst, &AC);
removeMSSA(Inst); removeMSSA(Inst);
Inst.eraseFromParent(); Inst.eraseFromParent();
Changed = true; Changed = true;
++NumCSE; ++NumCSE;
continue; continue;
} }
▲ Show 20 Lines • Show All 373 Lines • Show Last 20 Lines

llvm/test/Transforms/EarlyCSE/flags.ll

Show All 16 Lines;
call void @use(i1 %cmp2) call void @use(i1 %cmp2)
ret void ret void
} }
declare void @use.i8(i8*) declare void @use.i8(i8*)
define void @test_inbounds_program_ub_if_first_gep_poison(i8* %ptr, i64 %n) { define void @test_inbounds_program_ub_if_first_gep_poison(i8* %ptr, i64 %n) {
; CHECK-LABEL: @test_inbounds_program_ub_if_first_gep_poison( ; CHECK-LABEL: @test_inbounds_program_ub_if_first_gep_poison(
; CHECK-NEXT: [[ADD_PTR_1:%.*]] = getelementptr i8, i8* [[PTR:%.*]], i64 [[N:%.*]] ; CHECK-NEXT: [[ADD_PTR_1:%.*]] = getelementptr inbounds i8, i8* [[PTR:%.*]], i64 [[N:%.*]]
; CHECK-NEXT: call void @use.i8(i8* noundef [[ADD_PTR_1]]) ; CHECK-NEXT: call void @use.i8(i8* noundef [[ADD_PTR_1]])
; CHECK-NEXT: call void @use.i8(i8* [[ADD_PTR_1]]) ; CHECK-NEXT: call void @use.i8(i8* [[ADD_PTR_1]])
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
; ;
%add.ptr.1 = getelementptr inbounds i8, i8* %ptr, i64 %n %add.ptr.1 = getelementptr inbounds i8, i8* %ptr, i64 %n
call void @use.i8(i8* noundef %add.ptr.1) call void @use.i8(i8* noundef %add.ptr.1)
%add.ptr.2 = getelementptr i8, i8* %ptr, i64 %n %add.ptr.2 = getelementptr i8, i8* %ptr, i64 %n
call void @use.i8(i8* %add.ptr.2) call void @use.i8(i8* %add.ptr.2)
Show All 16 Lines