I see there is no -march=generic option, which is unfortunate because I figured there would be an instruction set that is supported by a majority of CPUs.
If you think for a moment about what a CPU is and how it works, you'll realise what you're suggesting makes absolutely no sense. Every CPU has a single instruction set, and cannot use any other. IA-32 (i386) is a subset of all the various instruction sets used in x86-32 CPUs, and that's about a close as you're ever going to get to one instruction set being supported by a majority of CPUs. The instruction sets of other CPUs such as PowerPC, ARM, et al, are all totally incompatible with each other and with IA-32, so there's absolutely no way to compile code so that it works on all of them.
It looks like, just not using the -march option at all is what I want, and -mtune=generic.
Actually, that may be what broke it in the first place. Specifying the target architecture is
mandatory for the above reason. If you don't, the compiler will use the system default, which may not always be what you want. You
must always specify what architecture you're compiling for if you want it to work on systems other than your own. I strongly recommend that you use
-march=i386 -mtune=generic to avoid any future surprises.
-mtune doesn't actually have anything to do with what instruction set your target architecture uses - instead it just optimises your code for things like the cache size of a particular CPU and so on. Setting it to the wrong CPU (even a CPU that doesn't use the same instruction set as the one you're compiling for) won't ever break anything, but it can have a detrimental effect on your code's performance. Always set it to "generic" unless you have a specific CPU in mind.
Does this also mean that I can use "-march=i386 -m32" to compile the 32-bit binaries on my 64-bit system? It would be nice to be able to cross-compile, but I never bothered to figure out how, and have a separate VM for each .deb file...
I've never cross-compiled either, but yes, that should work. Let me know how it goes.