Then add the assembler code inlined into the C function implementing the algorithm guarded by compiler macros so that the asm version is used on the platforms supporting it (i.e. x86_64) and the pure C on those that doesn't.

Another approach is to include the asm version of the function in its own .S file, but then you will have to add the rules for its compilation into the Makefile. Nowadays, most perls are compiled with gcc which can also be used to compile assembler code, so it should be a relatively easy task!

In order to detect when to use the C version or the asm version you can access the perl build configuration using Config, or in case that's not enough, you can go for Config::AutoConf.

It's more complicated than you need, but there is some inline assembly in Math::Prime::Util. See mulmod.h and montmath.h. Basically just C code with preprocessor wrappers for different platforms.

You can use Devel::CheckLib or similar packages for build time configuration as well.

For testing, I recommend Linux / Unix x86 machines that match your target, an x86 that doesn't (e.g. x86 non-64), a Mac especially since they use clang which acts slightly differently than gcc (different preprocessor defines), Windows. If you're ambitious, Cygwin and a non-x86 machine.

Is there a specific reason for it to be perl-only? Tight integration with perl internal structures?

I would recommend rolling this up as an independent library first, if possible. Or even just a separate translation unit. The XS is best used as a thin glue.

Are you sure that assembly is a requirement for this algorithm? Modern C compilers can autovectorize code; intrinsics are also available where needed. Furthermore, x86_64 CPUs span a number of feature-sets, beginning with just SSE3 (or is it SSE2?), going up to AVX2, and further, with miscellaneous extensions like POPCNT, BMI, FMA, and so on. Major speedups are often obtained by targeting the best feature-set.

So it comes down the particulars of your algorithm, and how it relates to perl.