Wnswl's blog

Category: Uncategorized

  • What is a Compiler Intrinsic?

    Disclaimer

    .It is completely fine if you do not understand this article all at once. It covers material you would usually encounter around the third or fourth year of a typical computer science or computer engineering program.

    Since it spans knowledge from programming languages, compilers, computer architecture, algorithms, and the theory of computation, it will be much easier to follow if you already have some background in those subjects.

    One-line summary

    An intrinsic is a function defined directly by the compiler and the architecture, even without any source implementation. All other functions are ultimately built on top of that foundation.

    What is a computer to you?

    That is a fairly abstract question. Some people might answer it by saying, “An electronic device made up of hardware and software, used to achieve a certain purpose.” Others might define it as “a category of devices including smartphones, desktop computers, tablets, gaming devices, laptops, and so on.” Those are all perfectly valid definitions, but from the perspective of mathematical and formal disciplines, a computer can be reduced to a single word:

    A prover.

    Seriously. From the perspective of formal language and logic, that one word is enough.

    That may be hard to accept at first, so let’s use programming — the thing people here deal with all the time — as an example.

    In most programming languages, addition is written like this:

    a + b

    That is because most programming languages define it roughly as follows:

    An operator that takes variables or constants of a real-number type on the left-hand side and right-hand side, and produces the result of real-number addition.

    The compiler proves this expression in roughly the following way:

    1. It finds the + operator. According to its definition, the left-hand side and right-hand side must be variables or constants, and their types must be real numbers.
    2. Neither side is a constant. Therefore, both must be interpreted as variables.
    3. It looks up the variables a and b in scope (I’ll talk about scope later in a different article on programming languages). If they cannot be found, or if their types do not match what is required, the proof fails. Therefore, the code does not compile.

    Actual compilers really do operate according to logic like this.

    So how does this work in JavaScript?

    Unlike strongly typed and non-implicit-conversion-friendly languages such as C++, JavaScript is very permissive about type conversion. JavaScript extends the definition of addition with more detailed rules:

    An operator that takes variables or constants of types such as real numbers, strings, arrays, and booleans on the left and right, and behaves as follows:

    1. If both sides are real numbers, it performs real-number addition.
    2. If one side is a real number and the other is a boolean, true is treated as 1 and false as 0.
    3. If both sides are booleans, true is treated as 1 and false as 0.
    4. If one side is a string and the other is a boolean or a real number, it concatenates the string with the other operand.

    …and so on.

    Now the problem becomes apparent. In a strongly typed language like C++, where type conversion is restricted, the proof process was relatively simple. But in JavaScript, a variable’s type can change freely within scope. So how do you prove anything in that situation?

    JavaScript is an interpreted language, which is why this is not a problem. In a statically compiled language like C++, the proof process above has to be completed before execution, which is why code in the style of JavaScript is not allowed. Logically speaking, there is no contradiction in allowing that style, but one reason C++ is used is that it aims to make memory usage as predictable as possible. That means the compiler should be able to infer memory requirements at compile time and minimize waste at runtime. A language could have been designed like JavaScript, with inefficiently sized variable storage, but C++ deliberately chose not to do that.

    JavaScript, instead, attempts this proof not at compile time but at runtime. As long as the program’s execution does not violate the runtime rules of the + operator defined above, it proceeds.

    Then what about the following example?

    function concatTest (input) {
  var a = '';
  for (var I = 0; I < input.length; I++) {
    a = a + input[I];
  }
  return a;
}

    input is probably an array. If so, each iteration of the for loop concatenates an element of input onto a, so a will always remain a string. According to the rules of the addition operator defined earlier, a will therefore always be a string. Once the loop finishes, a is still a string, so we can predict that this function will ultimately return a string.

    Now here is the real question:

    What if input is not an array at runtime?

    In that case, this code can no longer be proven at runtime. For the code to execute, input must be iterable — in other words, it must be something that can be iterated over, such as a map, dictionary, tuple, array, list, queue, or stack. In JavaScript, the length property is generally defined only for iterable types. So the proof fails on line 3, where it assumes that input has a property called length. Since the proof fails, the result is an exception.

    In other words, from the perspective of computer science, the exceptions we constantly encounter during programming can be defined as follows:

    A contradiction between the assumptions made by code that was presumed to be provable — that is, the code that was written — and the assumptions that hold at runtime.

    This conclusion may still feel hard to accept.

    • What about network failure?
    • What about I/O timeouts?
    • What about hardware failure?

    Those do not seem like logical contradictions, do they? Let’s rewrite those three examples like this:

    • Exception due to network failure: The program assumed that communication over the network would succeed, but that assumption was not satisfied. Therefore, a contradiction arises.
    • I/O timeout: The program assumed that the expected input would arrive within the time limit, but that assumption was not satisfied. Therefore, a contradiction arises.
    • Hardware failure: The program assumed that the hardware would operate normally, but that assumption was not satisfied. Therefore, a contradiction arises.

    In this way, every exceptional situation that exists in computing — errors, exceptions, failures, and so on — can be summarized as the occurrence of a contradiction.

    That is because a computer is, fundamentally, a prover.

    There may still be something unsatisfying about that idea. Suppose we accept that a computer is a prover. Then what about displaying something on a screen? Producing sound? A cash dispenser releasing bills after its processor finishes computation? A robot moving its motors after its processor completes a calculation? Do those things have anything to do with logic? Surely computers do not exist just to prove things.

    This also becomes easier to understand if you phrase it like this:

    Everything a computer does other than proving is a side effect.

    That is, dispensing cash, drawing to a monitor, outputting sound through speakers — all of these are, from a formal academic perspective, merely side effects unrelated to logical proof. They just happen to be extremely useful side effects from a human point of view.

    You can go even further and say that everything a computer does from the moment it powers on until the moment it shuts down is part of one overall proof process. Through firmware, bootloader, operating system, and application layers, it produces meaningful “side effects” for the user, and then eventually returns a normal shutdown to the firmware and ends the proof. That is the full behavior of a computer when viewed from a formal academic perspective.

    Note: If this interests you, look up the Halting Problem. It addresses the question of whether there exists a general method for predicting how long it will take to prove a given program. The most famous proof is Alan Turing’s, while the earliest proof was given by Alonzo Church.

    The proof has to reach the hardware too

    So far, I have shown why a computer is a prover from the software point of view. But a computer is made of both software and hardware. No matter how perfect a logical proof may be in software, it is meaningless if that proof does not actually execute on hardware. In other words, we need something that bridges the missing link between the conclusions reached in software and their realization in hardware.

    How is that logical gap filled?

    That gap is filled by the compiler.

    The actual agents that carry out logical proof in hardware are computation devices such as processors and controllers. They take executable binaries and operands from memory and signal connections, and produce results. Converting software into binaries that those devices can decode and execute — in other words, closing the logical gap between software and hardware execution — is precisely what the compiler does. You can think of an interpreter as a compiler that operates at runtime.

    Ultimately, a compiler consists of the following:

    • Code written directly in assembly
    • Functions implemented directly inside the compiler for each architecture

    Code written in assembly is easy enough to understand, but the phrase “functions implemented directly inside the compiler” sounds a bit strange. Are not all standard functions for a language implemented inside the compiler?

    Surprisingly, the answer is no.

    If you look at the actual implementation of functions defined in C/C++ headers such as stdio.h, you will see code full of names starting with __, as well as things like __asm or __asm__. Among these, __asm__ — in GCC; MSVC and Clang use __asm as an extension — refers to code written directly in architecture-specific machine instructions, which the compiler converts almost one-to-one into sequences of zeros and ones.

    Then what are the other functions?

    Functions whose names begin with __ are often functions that the compiler defines internally on its own, even without any header or source file. In other words, they are intrinsics. These functions are also almost converted one-to-one into machine code. But defining everything as inline assembly would destroy readability, so instead, they are exposed internally as if they were functions, and later translated one-to-one into machine instructions by the compiler. That is what an intrinsic is.

    These functions are defined per architecture. For example:

    • x86 / IA-32 and x64 / AMD64 are defined by Intel and AMD
    • ARMv7 and ARMv8 are defined by Arm

    Compilers implement these as standards for their respective targets. Of course, compilers may also define some of their own.

    This is why even with the same compiler, intrinsics differ depending on the architecture. Even stdio.h in C/C++ is written differently depending on the hardware vendors the compiler supports, using different inline assembly and intrinsics. Through this process, logically provable code finally becomes provable on actual hardware as well.

    But do we ever need to write this stuff ourselves?

    In most cases, no. The compiler handles it for you.

    However, when working on things like game development, operating systems, kernels, or other software that is very close to the hardware, there are times when you want to access processor features directly for performance reasons, without going through the abstractions of a programming language.

    A typical example is processing multiple operands with a single instruction, such as vector addition. SIMD-related instruction sets like Intel’s AVX or ARM’s NEON are well-known examples of this. When implementing features like that, you may end up writing intrinsics yourself.

    Note: Vector instructions are one of the representative examples of parallel processing, but they are conceptually different from multicore programming. Multicore programming distributes work across multiple cores, whereas vector instructions allow a single core to process multiple operands simultaneously.

    So where can you find the intrinsics defined for each architecture?

    One of the best-known references is MSDN’s Compiler Intrinsics documentation. It is probably the cleanest of the available sources. It describes the MSVC collection of intrinsics defined by various hardware vendors.

    Beyond that, there are also references from:

    • GCC: I will not bother linking it because their documentation is famously disorganized, and you can find it easily enough by searching.
    • LLVM / Clang: Since Clang uses the LLVM backend, which abstracts the logic of compiling all languages down to hardware assembly, you often need to consult LLVM and Clang documentation separately.
    • Intel: Intel documents the x86 family overall, and since Intel manages the architecture, AMD does not usually maintain separate documentation except for its own unique instructions.
    • Arm

    Between those sources, you can find essentially all the information you need.