some thoughts on the semantics of !fpmath

I realize that some of these thoughts apply equally to the
prior !fpaccuracy metadata that's been around a while, but I
hadn't looked at it closely until now.

The !fpmath metadata violates the original spirit of
metadata, which is that metadata is only supposed to exclude
possible runtime conditions, rather than to introduce new
possible runtime possibilities. The motivation for this is
that optimizers that ignore metadata should always be safe.
With !fpmath, theoretically there are ways this can fail.

It also has the problem that there's nothing preventing a
pass like GVN from merging a !fpmath-decorated operation with an
undecorated operation, and nothing requiring it to strip
the !fpmath tag when it does so. (This is a general problem
with LLVM metadata semantics.)

The current definition of !fpmath does not appear to require
operations to return the same result each time they are
evaluated. This fits with the way the optimizer works, because
optimizations like inlining can duplicate code, and it's
impractical to guarantee that each instance of a duplicated
instruction will be subsequently optimized in the same way.
However, what's not obvious is that this implies that
operations tagged with !fpmath actually return values that are
effectively constrained undef. That's interesting, though it's
not actually fundamentally new, since constrained undef is
already a fairly well established concept in LLVM.

The current definition of !fpmath does not specify whether
the ULPs refers to error with respect to infinitely precise
results or rounded results.

Dan

Hi Dan,

I realize that some of these thoughts apply equally to the
prior !fpaccuracy metadata that's been around a while, but I
hadn't looked at it closely until now.

The !fpmath metadata violates the original spirit of
metadata, which is that metadata is only supposed to exclude
possible runtime conditions, rather than to introduce new
possible runtime possibilities. The motivation for this is
that optimizers that ignore metadata should always be safe.
With !fpmath, theoretically there are ways this can fail.

I don't understand how it can not be safe: if the metadata is dropped
then the optimizers have to be more strict, thus it is safe.

It also has the problem that there's nothing preventing a
pass like GVN from merging a !fpmath-decorated operation with an
undecorated operation, and nothing requiring it to strip
the !fpmath tag when it does so. (This is a general problem
with LLVM metadata semantics.)

This is true, what do you suggest as a solution?

The current definition of !fpmath does not appear to require
operations to return the same result each time they are
evaluated. This fits with the way the optimizer works, because
optimizations like inlining can duplicate code, and it's
impractical to guarantee that each instance of a duplicated
instruction will be subsequently optimized in the same way.
However, what's not obvious is that this implies that
operations tagged with !fpmath actually return values that are
effectively constrained undef. That's interesting, though it's
not actually fundamentally new, since constrained undef is
already a fairly well established concept in LLVM.

I think something like this is inevitable in any system that allows fast math.

The current definition of !fpmath does not specify whether
the ULPs refers to error with respect to infinitely precise
results or rounded results.

Yes, this bothers me too. I've CC'd Peter since he added the definition.

Ciao, Duncan.

Hi Dan,

The !fpmath metadata violates the original spirit of
metadata, which is that metadata is only supposed to exclude
possible runtime conditions, rather than to introduce new
possible runtime possibilities.

This was already violated by objc-specific metadata and if I get Chris
right - this is the intended behavior.

It also has the problem that there's nothing preventing a
pass like GVN from merging a !fpmath-decorated operation with an
undecorated operation, and nothing requiring it to strip
the !fpmath tag when it does so. (This is a general problem
with LLVM metadata semantics.)

Can it? My impression from the last discussion on alias analysis is
that a pass can drop metadata it doesn't know, but it cannot ignore
it, so GVN would have to drop the metadata in this case.

Dan

Cheers,
Rafael

> It also has the problem that there's nothing preventing a
> pass like GVN from merging a !fpmath-decorated operation with an
> undecorated operation, and nothing requiring it to strip
> the !fpmath tag when it does so. (This is a general problem
> with LLVM metadata semantics.)

Can it? My impression from the last discussion on alias analysis is
that a pass can drop metadata it doesn't know, but it cannot ignore
it, so GVN would have to drop the metadata in this case.

I agree; I think that GVN should keep metadata that is the same and
drop metadata that differs. GVN might want to understand how to merge
certain kinds of metadata (line numbers in debug info?), but that is
not really necessary.

In reality, metadata might want to have merging rules and a defined API
so that metadata merging can be used by a number of passes
(vectorization will need this too). For example, merging fp-accuracy
data should choose the more-stringent bound, but not really be removed
all together.

-Hal

+1!

The original intent of metadata was to represent spurious concepts,
and the design was that is was always safe to ignore more to avoid the
complex semantics than specific intent.

Debug data should never be discarded if the user specified -g. It can
be merged, changed, but never discarded. Otherwise, what's the point?

Vectorisation the same, if you do some transformation based on one
information and need a subsequent pass to finish the same
transformation, and you destroy the metadata, you get incorrect
results.

With FP precision, you might be able to use different instructions or
ignore specific traps on more relaxed models, and the back-end can
only know that if you kept the metadata until the end.

I appreciate the cost of strict metadata semantics to the IR, but I
think we're at a point that either we use a decent metadata engine or
none at all.

Here's an example:

  %z = fadd float %x, %y, !fpmath !{ float 1000.0 }
  %p = fcmp ogt %z, 0.0
  br i1 %p, label %true, label %false
true:
  %d = call float @llvm.sqrt.f32(float %z)

This ought to be safe, since no matter now imprecise the fadd is,
the compare and branch protects the sqrt.

Now suppose a metadata-unaware optimizer can do value-range analysis
and can prove that the fadd always produces a positive finite value.
Then it's safe to replace the fcmp with true and delete the branch.

Then a metadata-aware codegen translates the fadd with reduced
precision, as permitted by the metadata. At runtime, the fadd may
return a negative value sometimes, because that could well be within
1000.0 ULPs of an expected non-negative result. But the branch is
now gone, and undefined behavior sqrts out.

Dan

Hi Dan,

Hi Anton,

The !fpmath metadata violates the original spirit of
metadata, which is that metadata is only supposed to exclude
possible runtime conditions, rather than to introduce new
possible runtime possibilities.

This was already violated by objc-specific metadata

Well, ObjC violates a lot more of LLVM IR semantics than just metadata.
Whether this is a problem or not depends on your perspective, I guess.

and if I get Chris
right - this is the intended behavior.

In Chris' own blog post on the subject [0], the first design
goal of metadata is that:

"Optimizations shouldn't be affected by metadata unless they explicitly try to look at it."

Now, it is debatable whether this is actually feasible. Maybe it
is too restrictive, and that it would be better to just require
every pass and every backend to be aware of every kind of
officially recognized metadata, as needed. It seems that several
people are starting to think this way.

[0] Extensible Metadata in LLVM IR - The LLVM Project Blog

Dan

The point isn't whether it's a good idea to discard FP precision data
(or vectorization data, or debug data), but rather whether IR
transformations are allowed to treat a meta-data annotated instruction
as having the same semantics as an unannotated instruction. If
transformation passes which aren't metadata aware aren't allowed to
reason about an annotated instruction, there's no point to metadata in
the first place: we can just introduce new intrinsics/instructions, or
change the definition of an existing instruction/intrinsic.

-Eli

The point isn't whether it's a good idea to discard FP precision data
(or vectorization data, or debug data), but rather whether IR
transformations are allowed to treat a meta-data annotated instruction
as having the same semantics as an unannotated instruction. If
transformation passes which aren't metadata aware aren't allowed to
reason about an annotated instruction, there's no point to metadata in
the first place: we can just introduce new intrinsics/instructions, or
change the definition of an existing instruction/intrinsic.

I am also not sure if it is at all possible to design a metadata
system that allows passes to ignore it. I don't think that is true for
any metadata we have other than debug info (if you don't consider
broken debug info).

IMHO the advantage that is still left in using metadata is that it is
easier to implement gradually, since passes are allowed to drop it.

Without metadata, changing the IL is an atomic operation where every
pass has to be audited for correctness. If we insist that passes must
drop metadata that they don't know about, support can be added one
pass at a time.

-Eli

Cheers,
Rafael

Okay... that could make sense. So under this system, each pass would
declare what kinds of metadata it supports, and the PassManager would
automatically drop all other instruction-level metadata from the
current module/function/loop?

-Eli

Okay... that could make sense. So under this system, each pass would
declare what kinds of metadata it supports, and the PassManager would
automatically drop all other instruction-level metadata from the
current module/function/loop?

I didn't think about using the pass manager, but that would be a way to do it.

-Eli

Cheers,
Rafael

>> The point isn't whether it's a good idea to discard FP precision
>> data (or vectorization data, or debug data), but rather whether IR
>> transformations are allowed to treat a meta-data annotated
>> instruction as having the same semantics as an unannotated
>> instruction. If transformation passes which aren't metadata aware
>> aren't allowed to reason about an annotated instruction, there's
>> no point to metadata in the first place: we can just introduce new
>> intrinsics/instructions, or change the definition of an existing
>> instruction/intrinsic.
>
> I am also not sure if it is at all possible to design a metadata
> system that allows passes to ignore it. I don't think that is true
> for any metadata we have other than debug info (if you don't
> consider broken debug info).
>
> IMHO the advantage that is still left in using metadata is that it
> is easier to implement gradually, since passes are allowed to drop
> it.
>
> Without metadata, changing the IL is an atomic operation where every
> pass has to be audited for correctness. If we insist that passes
> must drop metadata that they don't know about, support can be added
> one pass at a time.

Okay... that could make sense. So under this system, each pass would
declare what kinds of metadata it supports, and the PassManager would
automatically drop all other instruction-level metadata from the
current module/function/loop?

For a transformation pass, should we do this only if the pass actually
changed something?

-Hal

For a transformation pass, should we do this only if the pass actually
changed something?

In the pass manager? That is interesting. What I had in mind was just
changing the passes to only copy the metadata info they know about.
The problem is that in examples like the one Dan created. The pass
would have to delete metadata in an instruction it reasoned about but
didn't otherwise modify, which is fairly error prone.

-Hal

Cheers,
Rafael

> For a transformation pass, should we do this only if the pass
> actually changed something?

In the pass manager? That is interesting. What I had in mind was just
changing the passes to only copy the metadata info they know about.
The problem is that in examples like the one Dan created. The pass
would have to delete metadata in an instruction it reasoned about but
didn't otherwise modify, which is fairly error prone.

My thought was that if the pass manager is going to go through every
instruction in the block/loop/function, etc. and remove metadata
incompatible with the pass, then I think the effect is same if the pass
manager does this before the pass runs or after (so long as the pass
does not retain state like an analysis pass). If I'm correct, then it
seems unnecessarily conservative to remove the metadata even if the
pass made no changes.

-Hal

Hi,

I am also not sure if it is at all possible to design a metadata
system that allows passes to ignore it. I don't think that is true for
any metadata we have other than debug info (if you don't consider
broken debug info).

IMHO the advantage that is still left in using metadata is that it is
easier to implement gradually, since passes are allowed to drop it.

Without metadata, changing the IL is an atomic operation where every
pass has to be audited for correctness. If we insist that passes must
drop metadata that they don't know about, support can be added one
pass at a time.

Okay... that could make sense. So under this system, each pass would
declare what kinds of metadata it supports, and the PassManager would
automatically drop all other instruction-level metadata from the
current module/function/loop?

what?! This seems like huge overkill to me. As far as I can see main problem
currently is that some passes *add* metadata to instructions that didn't have
any. That's one way of viewing the problem with GVN: it can take an
instruction A without metadata and identify it with an instruction B with
metadata, so in effect GVN has added metadata to A. Any pass that blatantly
went around adding random metadata (eg: tbaa metadata) to instructions would be
considered to be obviously buggy. I think GVN and EarlyCSE or whoever should
be fixed not to do this, or rather to tag the unified instruction with the
least common denominator of the metadata on the original instructions (and thus
in effect it will only ever drop metadata rather than adding it).

Ciao, Duncan.

Hi,

>> I am also not sure if it is at all possible to design a metadata
>> system that allows passes to ignore it. I don't think that is true
>> for any metadata we have other than debug info (if you don't
>> consider broken debug info).
>>
>> IMHO the advantage that is still left in using metadata is that it
>> is easier to implement gradually, since passes are allowed to drop
>> it.
>>
>> Without metadata, changing the IL is an atomic operation where
>> every pass has to be audited for correctness. If we insist that
>> passes must drop metadata that they don't know about, support can
>> be added one pass at a time.
>
> Okay... that could make sense. So under this system, each pass
> would declare what kinds of metadata it supports, and the
> PassManager would automatically drop all other instruction-level
> metadata from the current module/function/loop?

what?! This seems like huge overkill to me. As far as I can see
main problem currently is that some passes *add* metadata to
instructions that didn't have any. That's one way of viewing the
problem with GVN: it can take an instruction A without metadata and
identify it with an instruction B with metadata, so in effect GVN has
added metadata to A. Any pass that blatantly went around adding
random metadata (eg: tbaa metadata) to instructions would be
considered to be obviously buggy. I think GVN and EarlyCSE or
whoever should be fixed not to do this, or rather to tag the unified
instruction with the least common denominator of the metadata on the
original instructions (and thus in effect it will only ever drop
metadata rather than adding it).

This makes sense to me. Does anyone have a counterexample? And this is
exactly why I think we should have a mergeMetadata API -- I need this for the
vectorization passes as well.

-Hal

Hi Dan,

I don't understand how it can not be safe: if the metadata is dropped
then the optimizers have to be more strict, thus it is safe.

Here's an example:

   %z = fadd float %x, %y, !fpmath !{ float 1000.0 }
   %p = fcmp ogt %z, 0.0
   br i1 %p, label %true, label %false
true:
   %d = call float @llvm.sqrt.f32(float %z)

This ought to be safe, since no matter now imprecise the fadd is,
the compare and branch protects the sqrt.

Now suppose a metadata-unaware optimizer can do value-range analysis
and can prove that the fadd always produces a positive finite value.

this just means that passes doing floating point value-range analysis
need to be metadata aware.

Ciao, Duncan.