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

[fhahn]

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

[nikic]

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]

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]

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]

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–1372

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.

[fhahn]

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]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

1369–1372

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

[nikic]

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]

Check for FPMathOperator.

[fhahn]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

1376

fixed, thanks!

[nikic]

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.

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

if (SimpleValue::canHandle(&Inst)) {
       // See if the instruction has an available value.  If so, use it.
       if (Value *V = AvailableValues.lookup(&Inst)) {
         LLVM_DEBUG(dbgs() << "EarlyCSE CSE: " << Inst << "  to: " << *V
                           << '\n');
         if (!DebugCounter::shouldExecute(CSECounter)) {
           LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
           continue;
         }
-        if (auto *I = dyn_cast<Instruction>(V))
+        if (auto *I = dyn_cast<Instruction>(V)) {
+          if (!I->hasPoisonGeneratingFlags() || !programUndefinedIfPoison(I))
             I->andIRFlags(&Inst);
+        }
         Inst.replaceAllUsesWith(V);
         salvageKnowledge(&Inst, &AC);
         removeMSSA(Inst);
         Inst.eraseFromParent();
         Changed = true;
         ++NumCSE;
         continue;
       }
 
       // Otherwise, just remember that this value is available.
       AvailableValues.insert(&Inst, &Inst);
       continue;

llvm/test/Transforms/EarlyCSE/flags.ll

;
   call void @use(i1 %cmp2)
   ret void
 }
 
 declare void @use.i8(i8*)
 
 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-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* [[ADD_PTR_1]])
 ; CHECK-NEXT:    ret void
 ;
   %add.ptr.1 = getelementptr inbounds i8, i8* %ptr, i64 %n
   call void @use.i8(i8* noundef %add.ptr.1)
   %add.ptr.2 = getelementptr i8, i8* %ptr, i64 %n
   call void @use.i8(i8* %add.ptr.2)