[LLVMdev] [global-isel] Random comments on Proposal for a global instruction selector

[Dean Sutherland]

This design does indeed appear generally cleaner than the current state of the world.  What follows is a bit long, so here's the tl;dr version:
You *really* want to support address types in your type system, even if you expand GEP-like operations into open arithmetic. This lets you produce good code for a wide variety of odd-ball architectures with relative ease. Failing to support address types makes it really difficult to support those odd-ball architectures.

On Aug 9, 2013, at 5:16 AM, David Chisnall <David.Chisnall at cl.cam.ac.uk>
 wrote:

>> 	• The getelementpointer instruction is too abstract. We want pointer arithmetic to be exposed as normal integer arithmetic in a type system without pointers. This would require a lot of awkward pointer-to-integer conversions in LLVM IR.
> 
> For our back end, we absolutely do not want a type system without pointers - not only do we have separate registers for pointers, we also have separate instructions for manipulating them and representing this in SelectionDAG requires some very ugly hacks.  This is also the case for several DSPs, which have separate address and data registers, and for upcoming Intel chips with MPX that have 4 hardware bounds registers that need keeping in sync with pointers.  Something like GEP is actually a very good model for these, because it allows the same bounds register to be used for a set of pointer operations, however it would be fine to have a single pointer type that was independent of its pointee type (or small set of different-sized ones, which will be useful for several GPUs) and a lower-level GEP that was just a byte offset.
> 
> For the architectures that don't distinguish between pointers and integers, there should be some option of lowering to integer types, however the information that a particular register contains an 


At Tartan Labs, we found it very useful to represent three different kinds of information: the type of each value, the result context of each operation, and whether operations required checks (or not).

The type system should absolutely know about addresses! At Tartan, the backend (Optimizer & code-gen) concept of "type" included more kinds of types than those described by the OP. Specifically, when compiling for various DSPs and other unusual architectures, we found it was crucial to know not only which values were "addresses", but also what specific kind of address they were. Specific kinds of addresses were used to support machines with multiple address spaces, fat pointers of various kinds (e.g., [pointer-to-array, pointer-to-bounds-info], [pointer, capability], or even [pointer, capability, bounds-info] tuples) and so on.  Consider, for example a machine with a split Harvard architecture, where there are separate buses for the Code, Data-A and Data-B address spaces. Given a "pointer" value, you must emit different instructions to load from one of those spaces; the same bit-pattern in the value references completely different memory.  On other architectures, you also had to use different registers to access the different address spaces. And you only get good performance by keeping all the code and data buses busy simultaneously.  The machine with fat-pointers-with-capabilities required the use of both special instructions and special registers for operations on those pointer-with-capa values. Using ordinary (e.g., non-capa) instructions or registers cleared the capability bits and so wiped out access to the protected resources. Generating good code for architectures like these requires richer knowledge of the types of the values the compiler is working with.

Result context may not matter for a 3-address IR such as LLVM uses.
The simplest result context system we used had three values: address, value, and flow. This mattered because we had a tree-based IR, in which expression temporaries were implicit. So we needed context information to guide allocation of expression temporaries.  Given a 3-address IR, I suspect that at least address and value context are redundant with the type information for the destination.  

That leaves only "flow" as an interesting concept.  It was useful to know when the result of an operation would be used for control flow (rather than being stored in some other variable). This helped us make better use of condition codes (for machines that have them), or even of multiple condition code registers. It also helped guide flow-targetted computations and temporaries to register/instruction combinations that also set condition codes (when relevant).  The usefulness of flow context across a very broad mix of architectures may suggest that one or more "flow"-like types could be useful. 

Finally, checked operations.
If you ever expect to support one or more languages that do overflow checking on arithmetic (or pointer deref, or array bounds, or address-sanitization, or ...), you may find it useful to know whether particular operations (a) require checks, (b) require lack-of-checks, or (c) don't care about checks -- all of these from the viewpoint of language semantics. In addition, when checks are required, it's really useful to distinguish the cases where the result of the check is statically known (e.g., guaranteed to succeed or to fail) -- we discovered this latter property in the optimizer, as part of removing unnecessary checks. The obvious alternative here is to require front-ends that need checks to generate the obvious IR to perform said check. However, it's rather more difficult to generate efficient code this way. For C & C++, I believe that unsigned requires lack-of-checks (because it's defined to wrap), but signed integers don't care for most implementations (wrapping or not is undefined).


Dean Sutherland
(a Tartan Labs alumnus)