Calling FFTW's in-place real-to-complex transform without violating strict aliasing rules

Question

I wish to call fftw's in-place real-to-complex transform function, which has the following signature:

fftw_plan fftw_plan_dft_r2c_1d(
    int n,             // transform length
    double* in,        // pointer to input array
    fftw_complex* out, // pointer to output array
    unsigned flags     // flags
);

The documentation says that I should indicate that I wish to perform an in-place transform by passing in aliasing pointers for the in and out parameters.

---

QUESTION: How can in and out alias without violating strict aliasing rules?

---

I am open to GCC-specific extensions (i.e., using unions to do type-punning, even though the standard declares this to be undefined behavior). Even if this extension is permitted, a union cannot contain dynamically-sized arrays (which is a must in this applications - I do not know the transform length in advance). Does anyone have any ideas? Thanks in advance.

Etheline

Where do you get the impression that the code in question doesn't violate the strict-aliasing rule? – Delrio

@Nicol Bolas: I suppose a rephrasing of my question might be: does FFTW’s interface force the caller to invoke undefined behavior? Or is there a way around it (besides compiling with -fno-strict-aliasing)? – Etheline

The strict aliasing rule has no official way around, unfortunately. The language is broken in that respect; there is no way (currently) to legally get a type alias from UB land into implementation-defined land, short of inline assembly or a compiler-specific switch like the one you mentioned. – Carpenter

Answer 1

According to this link fftw_complex is the following typedef:

typedef double fftw_complex[2];

And by the pre-C++20 rules fftw_complex* may alias double* because of this ([basic.lval]p8.6):

If a program attempts to access the stored value of an object through a glvalue of other than one of the following types the behavior is undefined:
...
— an aggregate or union type that includes one of the aforementioned types among its elements or nonstatic data members (including, recursively, an element or non-static data member of a subaggregate or contained union)

Array is an aggregate and our array contains doubles thus it is allowed to alias a double pointer. Hence, no strict aliasing rule violation happens in the fftw_plan_dft_r2c_1d function and you can safely use it.

Note, however, that this paragraph is removed from the C++20 standard and it is debated that it should be removed from the C standard as well. But since it is not removed yet and GCC & clang actually respect it I guess it is safe to assume that the behavior won't change with C++20 implementation. And MSVC, to my knowledge, doesn't take advantage of SAR at all.

Polyclitus

Huh, this link provides a different definition for fftw_complex. – Hecate

@HolyBlackCat, that's why I was asking what it actually is. But I went to their website and just used the latest doc version. Anyway, your link contains a structure which will work just as well. Because of the same paragraph from the standard. – Polyclitus

Do you (or does any one else) know the rationale for removing it from the standard? – Etheline

@Etheline it is deemed redundant.You see, what is described in my post (legality of the construction in your question) looks like a byproduct of a completely different intention. The said paragraph allows that aliasing but it seems it was created not to allow it but rather allow structure assignment in C. That said, this paragraph prevents aggressive compiler optimization in language fashion, so you can reason with language rules why it can't be UB. But you should understand that SAR is a contentious topic and it produces UB for a reason. – Polyclitus

The reason is optimization. And some compilers try to take advantage of it whenever they can but this code has parameters which will prevent the optimization in any case: it doesn't matter whether this paragraph is present or not. Compiler can't take advantage of this aliasing and reason that they can't alias thus producing a UB. The thing is that in will always be able to alias out because the latter consists of doubles and double can alias double any day and that won't change in C++20. So, I'd say that the code will stay correct anyway but the reasoning will become a bit murkier. – Polyclitus

And if you want to get some reading here is the paper for C and for C++ regarding this paragraph. – Polyclitus

Answer 2

I'll challenge the premise: Don't worry about strict aliasing too much.

Make an array of double and pass a pointer to it to in. reinterpret_cast the pointer to fftw_complex * and pass it to out.

Read the resulting doubles from this array (as pairs of real and imaginary components of complex numbers).

---

Yes, fftw_plan_dft_r2c_1d will probably break strict aliasing under the hood if called this way.

But since it's in a separate translation unit, and caller doesn't violate strict aliasing, your compiler has no way to tell if strict aliasing was indeed violated.

fftw_complex is essentially a struct fftw_complex {double re, im;};, so everything should work just fine.

For extra safety you can add:

static_assert(sizeof(fftw_complex) == 2 * sizeof(double) && alignof(fftw_complex) <= alignof(double));

Hecate

It is true that fftw’s UB is hidden in another translation unit, but for the caller to make any real-world use of the library, they must write to the in buffer and then read from the out buffer - thus violating the rules, likely in a single function. It seems reasonable to be concerned with compiler optimizations breaking the code in this case. In my application, it’s even worse - the code is part of a class template, so the compiler can see even more code, including code that I didn’t write, providing even more opportunities for the compiler to break the code. – Etheline

@Etheline No, the caller doesn't break strict aliasing. It simply works with an array of doubles. The only questionable thing the caller does in this case is reinterpret_cast, but by itself this cast doesn't cause UB. (From the point of view of the compiler, fftw_complex theoretically could cast the output pointer back to double * and write to this new pointer, thus not volating strict aliasing.) – Hecate

The caller does break strict aliasing, since the caller must fill an array of double (via a pointer-to-double), call fftw_execute, and then read an array of fftw_complex (via a pointer-to-fftw_complex). Because these two pointer actually point to the same memory, strict aliasing rules are violated. Any usage scheme that doesn’t break strict aliasing rules either doesn’t fill the input array or doesn’t read the output array. Any real usage on the caller’s side will both fill the input array and read the output array (via pointers to different types). – Etheline

@Etheline As the answer says, I don't suggest reading fftw_complex from the array. I suggest reading doubles from it (in pairs, where array[i*2] are real components and array[i*2+1] are imaginary components of those complex numbers). – Hecate

Ah, I see now. Yes, that could be safe, assuming no link-time-optimizations. – Etheline

@SumDood, There's a rather unusual description of the std::complex<T> type that specifies the structure of Ts apparently to deal with exactly this sort of thing where a return may be an array of Ts in a standard real/imaginary form. – Zettazeugma

@Etheline See en.cppreference.com/w/cpp/numeric/complex and the topic "Array-oriented access" – Zettazeugma

"your compiler has no way to tell if strict aliasing was indeed violated" It doesn't need to know if anything was violated. Compilers do not care about violations. They just act as no violations have ever happened, as they are not possible at all. So if the fftw_plan_dft_r2c_1d function is not compiled with -fno-strict-aliasing or specifically written the way that in no way it can cause any harm (I'm sincerely doubt it) you can assume no safety. UB is UB. – Polyclitus

@Polyclitus "sincerely doubt it" Note that the documentation for fftw_plan_dft_r2c_1d specifically permits passing the same pointer both to in and out. – Hecate

@Hecate doesn't matter what specification says. It might as well be lousy. Honestly, I suspect there is no SAR violation at all but it depends on what fftw_complex really is. But if there is a SAR violation than what spec says should not matter because it should explain why it is allowed in the first place. You can't just say "yeah, we have a UB here but worry not everything will be fine!". Why should anyone believe in it? – Polyclitus

@Polyclitus "doesn't matter what specification says" If the function doesn't behave as described in the docs, then there is nothing we can do and the whole question is moot. All we can do is eliminate UB in the caller, and hope for the best. "what fftw_complex really is" The link in the answer has the definition of fftw_complex. "why it is allowed in the first place" To save memory, I assume? If you don't need the original array, you can overwrite it with the results. – Hecate

@Hecate there is no UB on the caller side and can't be in this particular case. "hope for the best" doesn't sound like a good practice to me ;) By "why it is allowed in the first place" I meant aliasing. If the docs say that aliasing is fine and it contradicts the Standard then the doc should explicitly explain why it is fine. But since the definition of the fftw_complex is as simple as it is there is no SAR violation at all. – Polyclitus

Answer 3

This construct doesn't necessarily mean aliasing violation. Inside fftw_plan_dft_r2c_1d, there could be a placement new array call, which creates the out buffer properly.

With C++17, you may want to std::launder the out pointer after the call, just to be absolutely standard conformant.

Chetnik