Examples of specialized instructions of assembly language not available in compilers?

Question

In my CS computer organization textbook, there's this blurb on the advantage of assembly over a high-level language.

Another major advantage of assembly language is the ability to exploit specialized instructions - for example, string copy or pattern-matching instructions. Compilers, in most cases, cannot determine that a program loop can be replaced by a single instruction. However, the programmer who wrote the loop can replace it easily with a single instruction.

How can a loop be replaced by string copy or pattern matching? Can somebody give an example on specialized instructions that are not available in a high-level language and how a specialized instruction can replace a loop?

Answer 1

Some machines have complex processor instructions that can do the same job as a loop with a simple body. For example, x86 processors have an instruction scasb instruction that searches for a byte value; the C strlen function, which searches for a null byte and can be written in C as

while (*p != 0) p++;

can be written in x86 assembly as

repne scasb

Another example is bit counting. Many processors have instructions to do things like finding the number of bits that are set in a word, or finding the index of the lowest-order set bit in a word. However, most programming languages have no operator or function for that, so the programmer has to write a loop like

bit_count = 0;
while (n != 0) {
    if (n & 1) ++bit_count;
    n = n >> 1;
}

whereas recent x86_64 processors have an instruction for that:

popcnt

Some C compilers provide extensions to the standard language that give access to this instruction (and compile to a loop-based form if such an instruction doesn't exist on the target machine).

Yet another example is instructions that accelerate some common cryptographic algorithms (e.g. AES-NI on recent x86 processors). Unlike the previous two, this example is of interest only to the rarefied world of cryptography implementers, so compiler writers are less inclined to provide ways to generate those instructions apart from inline assembly.

Your textbook seems somewhat dated to me. Loop instructions hard-wired in processors are a very CISC feature that most modern processors don't have, the notable exception being the x86 architecture where it is implemented in microcode for backward compatibility. Compilers have become better at understanding what a piece of code including a simple loop does, and converting them to optimized machine instructions. The statement “Compilers, in most cases, cannot determine that a program loop can be replaced by a single instruction” is not always true for 21st century compilers. It is sometimes true; for example I can't seem to get GCC to recognize my naive popcnt implementation above.

Answer 2

Counting bits set, Brian Kernighan's way

unsigned int v; // count bits set (1)
unsigned int c; // result
for (c = 0; v; ++c)
{
  v &= v - 1;
}

This code becomes popcnt

Answer 3

Modern CPUs include specialized instructions (mostly privileged ones, i.e., only the operating system kernel is allowed to use them) to do Input/Output, messing with table pages, flushing the various CPU caches, return from an interrupt. The operations invoked make no sense in regular code (and wouldn't be allowed in the first place), so they aren't in the repertoire of instructions emitted by the compiler. To allow their use, most C compilers (C is often used to write operating system kernels) have ways to include assembly snippets inline.

If you look at the discussions on languages in StackOverflow, you'll see that the compiler is required to emit code that just behaves "as if" it was doing the operations written by the programmer. The instructions used to "fake" what you request can very well be quite different from what you'd expect, computations might be done in wildly different orders, useless computation silently elided, and so on. In the case of C, the compiler is allowed to use knowledge of what standard library functions do, and replace e.g. printf("%s", string) with puts(string), and sin(x) * sin(x) + cos(x) * cos(x) with 1.0. Take some (not too complex) code, and ask to compile with maximal optimization to assembly language (ask for debugging, that'll add some comments that help referencing back to the source). You'll be surprised.