diff options
Diffstat (limited to 'docs/AdvancedGetElementPtr.html')
| -rw-r--r-- | docs/AdvancedGetElementPtr.html | 362 |
1 files changed, 0 insertions, 362 deletions
diff --git a/docs/AdvancedGetElementPtr.html b/docs/AdvancedGetElementPtr.html deleted file mode 100644 index 1d37278..0000000 --- a/docs/AdvancedGetElementPtr.html +++ /dev/null @@ -1,362 +0,0 @@ -<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" - "http://www.w3.org/TR/html4/strict.dtd"> -<html> -<head> - <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> - <title>The Revenge Of The Often Misunderstood GEP Instruction</title> - <link rel="stylesheet" href="llvm.css" type="text/css"> - <style type="text/css"> - TABLE { text-align: left; border: 1px solid black; border-collapse: collapse; margin: 0 0 0 0; } - </style> -</head> -<body> - -<div class="doc_title"> - The Revenge Of The Often Misunderstood GEP Instruction -</div> - -<!-- *********************************************************************** --> -<div class="doc_section"><a name="intro"><b>Introduction</b></a></div> -<!-- *********************************************************************** --> -<div class="doc_text"> - <p>GEP was mysterious and wily at first, but it turned out that the basic - workings were fairly comprehensible. However the dragon was merely subdued; - now it's back, and it has more fundamental complexity to confront. This - document seeks to uncover misunderstandings of the GEP operator that tend - to persist past initial confusion about the funky "extra 0" thing. Here we - show that the GEP instruction is really not quite as simple as it seems, - even after the initial confusion is overcome.</p> -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>How is GEP different from ptrtoint, arithmetic, - and inttoptr?</b></a> -</div> -<div class="doc_text"> - <p>It's very similar; there are only subtle differences.</p> - - <p>With ptrtoint, you have to pick an integer type. One approach is to pick i64; - this is safe on everything LLVM supports (LLVM internally assumes pointers - are never wider than 64 bits in many places), and the optimizer will actually - narrow the i64 arithmetic down to the actual pointer size on targets which - don't support 64-bit arithmetic in most cases. However, there are some cases - where it doesn't do this. With GEP you can avoid this problem. - - <p>Also, GEP carries additional pointer aliasing rules. It's invalid to take a - GEP from one object, address into a different separately allocated - object, and dereference it. IR producers (front-ends) must follow this rule, - and consumers (optimizers, specifically alias analysis) benefit from being - able to rely on it.</p> - - <p>And, GEP is more concise in common cases.</p> - - <p>However, for the underlying integer computation implied, there - is no difference.</p> - -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>I'm writing a backend for a target which needs custom - lowering for GEP. How do I do this?</b></a> -</div> -<div class="doc_text"> - <p>You don't. The integer computation implied by a GEP is target-independent. - Typically what you'll need to do is make your backend pattern-match - expressions trees involving ADD, MUL, etc., which are what GEP is lowered - into. This has the advantage of letting your code work correctly in more - cases.</p> - - <p>GEP does use target-dependent parameters for the size and layout of data - types, which targets can customize.</p> - - <p>If you require support for addressing units which are not 8 bits, you'll - need to fix a lot of code in the backend, with GEP lowering being only a - small piece of the overall picture.</p> - -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>Why do struct member indices always use i32?</b></a> -</div> -<div class="doc_text"> - <p>The specific type i32 is probably just a historical artifact, however it's - wide enough for all practical purposes, so there's been no need to change it. - It doesn't necessarily imply i32 address arithmetic; it's just an identifier - which identifies a field in a struct. Requiring that all struct indices be - the same reduces the range of possibilities for cases where two GEPs are - effectively the same but have distinct operand types.</p> - -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>How does VLA addressing work with GEPs?</b></a> -</div> -<div class="doc_text"> - <p>GEPs don't natively support VLAs. LLVM's type system is entirely static, - and GEP address computations are guided by an LLVM type.</p> - - <p>VLA indices can be implemented as linearized indices. For example, an - expression like X[a][b][c], must be effectively lowered into a form - like X[a*m+b*n+c], so that it appears to the GEP as a single-dimensional - array reference.</p> - - <p>This means if you want to write an analysis which understands array - indices and you want to support VLAs, your code will have to be - prepared to reverse-engineer the linearization. One way to solve this - problem is to use the ScalarEvolution library, which always presents - VLA and non-VLA indexing in the same manner.</p> - -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>What happens if an array index is out of bounds?</b></a> -</div> -<div class="doc_text"> - <p>There are two senses in which an array index can be out of bounds.</p> - - <p>First, there's the array type which comes from the (static) type of - the first operand to the GEP. Indices greater than the number of elements - in the corresponding static array type are valid. There is no problem with - out of bounds indices in this sense. Indexing into an array only depends - on the size of the array element, not the number of elements.</p> - - <p>A common example of how this is used is arrays where the size is not known. - It's common to use array types with zero length to represent these. The - fact that the static type says there are zero elements is irrelevant; it's - perfectly valid to compute arbitrary element indices, as the computation - only depends on the size of the array element, not the number of - elements. Note that zero-sized arrays are not a special case here.</p> - - <p>This sense is unconnected with <tt>inbounds</tt> keyword. The - <tt>inbounds</tt> keyword is designed to describe low-level pointer - arithmetic overflow conditions, rather than high-level array - indexing rules. - - <p>Analysis passes which wish to understand array indexing should not - assume that the static array type bounds are respected.</p> - - <p>The second sense of being out of bounds is computing an address that's - beyond the actual underlying allocated object.</p> - - <p>With the <tt>inbounds</tt> keyword, the result value of the GEP is - undefined if the address is outside the actual underlying allocated - object and not the address one-past-the-end.</p> - - <p>Without the <tt>inbounds</tt> keyword, there are no restrictions - on computing out-of-bounds addresses. Obviously, performing a load or - a store requires an address of allocated and sufficiently aligned - memory. But the GEP itself is only concerned with computing addresses.</p> - -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>Can array indices be negative?</b></a> -</div> -<div class="doc_text"> - <p>Yes. This is basically a special case of array indices being out - of bounds.</p> - -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>Can I compare two values computed with GEPs?</b></a> -</div> -<div class="doc_text"> - <p>Yes. If both addresses are within the same allocated object, or - one-past-the-end, you'll get the comparison result you expect. If either - is outside of it, integer arithmetic wrapping may occur, so the - comparison may not be meaningful.</p> - -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>Can I do GEP with a different pointer type than the type of - the underlying object?</b></a> -</div> -<div class="doc_text"> - <p>Yes. There are no restrictions on bitcasting a pointer value to an arbitrary - pointer type. The types in a GEP serve only to define the parameters for the - underlying integer computation. They need not correspond with the actual - type of the underlying object.</p> - - <p>Furthermore, loads and stores don't have to use the same types as the type - of the underlying object. Types in this context serve only to specify - memory size and alignment. Beyond that there are merely a hint to the - optimizer indicating how the value will likely be used.</p> - -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>Can I cast an object's address to integer and add it - to null?</b></a> -</div> -<div class="doc_text"> - <p>You can compute an address that way, but if you use GEP to do the add, - you can't use that pointer to actually access the object, unless the - object is managed outside of LLVM.</p> - - <p>The underlying integer computation is sufficiently defined; null has a - defined value -- zero -- and you can add whatever value you want to it.</p> - - <p>However, it's invalid to access (load from or store to) an LLVM-aware - object with such a pointer. This includes GlobalVariables, Allocas, and - objects pointed to by noalias pointers.</p> - - <p>If you really need this functionality, you can do the arithmetic with - explicit integer instructions, and use inttoptr to convert the result to - an address. Most of GEP's special aliasing rules do not apply to pointers - computed from ptrtoint, arithmetic, and inttoptr sequences.</p> - -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>Can I compute the distance between two objects, and add - that value to one address to compute the other address?</b></a> -</div> -<div class="doc_text"> - <p>As with arithmetic on null, You can use GEP to compute an address that - way, but you can't use that pointer to actually access the object if you - do, unless the object is managed outside of LLVM.</p> - - <p>Also as above, ptrtoint and inttoptr provide an alternative way to do this - which do not have this restriction.</p> - -</div> - -<!-- *********************************************************************** --> -<div class="doc_subsection"> - <a name="lead0"><b>Can I do type-based alias analysis on LLVM IR?</b></a> -</div> -<div class="doc_text"> - <p>You can't do type-based alias analysis using LLVM's built-in type system, - because LLVM has no restrictions on mixing types in addressing, loads or - stores.</p> - - <p>It would be possible to add special annotations to the IR, probably using - metadata, to describe a different type system (such as the C type system), - and do type-based aliasing on top of that. This is a much bigger - undertaking though.</p> - -</div> - -<!-- *********************************************************************** --> - -<div class="doc_subsection"> - <a name="lead0"><b>What's an uglygep?</b></a> -</div> -<div class="doc_text"> - <p>Some LLVM optimizers operate on GEPs by internally lowering them into - more primitive integer expressions, which allows them to be combined - with other integer expressions and/or split into multiple separate - integer expressions. If they've made non-trivial changes, translating - back into LLVM IR can involve reverse-engineering the structure of - the addressing in order to fit it into the static type of the original - first operand. It isn't always possibly to fully reconstruct this - structure; sometimes the underlying addressing doesn't correspond with - the static type at all. In such cases the optimizer instead will emit - a GEP with the base pointer casted to a simple address-unit pointer, - using the name "uglygep". This isn't pretty, but it's just as - valid, and it's sufficient to preserve the pointer aliasing guarantees - that GEP provides.</p> - -</div> - -<!-- *********************************************************************** --> - -<div class="doc_subsection"> - <a name="lead0"><b>Can GEP index into vector elements?</b></a> -</div> -<div class="doc_text"> - <p>Sort of. This hasn't always been forcefully disallowed, though it's - not recommended. It leads to awkward special cases in the optimizers. - In the future, it may be outright disallowed.</p> - - <p>Instead, you should cast your pointer types and use arrays instead of - vectors for addressing. Arrays have the same in-memory representation - as vectors, so the addressing is interchangeable.</p> - -</div> - -<!-- *********************************************************************** --> - -<div class="doc_subsection"> - <a name="lead0"><b>Can GEP index into unions?</b></a> -</div> -<div class="doc_text"> - <p>Unknown.</p> - -</div> - -<!-- *********************************************************************** --> - -<div class="doc_subsection"> - <a name="lead0"><b>What happens if a GEP computation overflows?</b></a> -</div> -<div class="doc_text"> - <p>If the GEP has the <tt>inbounds</tt> keyword, the result value is - undefined.</p> - - <p>Otherwise, the result value is the result from evaluating the implied - two's complement integer computation. However, since there's no - guarantee of where an object will be allocated in the address space, - such values have limited meaning.</p> - -</div> - -<!-- *********************************************************************** --> - -<div class="doc_subsection"> - <a name="lead0"><b>What effect do address spaces have on GEPs?</b></a> -</div> -<div class="doc_text"> - <p>None, except that the address space qualifier on the first operand pointer - type always matches the address space qualifier on the result type.</p> - -</div> - -<!-- *********************************************************************** --> - -<div class="doc_subsection"> - <a name="lead0"><b>Why is GEP designed this way?</b></a> -</div> -<div class="doc_text"> - <p>The design of GEP has the following goals, in rough unofficial - order of priority:</p> - <ul> - <li>Support C, C-like languages, and languages which can be - conceptually lowered into C (this covers a lot).</li> - <li>Support optimizations such as those that are common in - C compilers.</li> - <li>Provide a consistent method for computing addresses so that - address computations don't need to be a part of load and - store instructions in the IR.</li> - <li>Support non-C-like languages, to the extent that it doesn't - interfere with other goals.</li> - <li>Minimize target-specific information in the IR.</li> - </ul> -</div> - -<!-- *********************************************************************** --> - -<hr> -<address> - <a href="http://jigsaw.w3.org/css-validator/check/referer"><img - src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a> - <a href="http://validator.w3.org/check/referer"><img - src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a> - <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/> - Last modified: $Date: 2010-02-18 19:40:29 +0100 (Thu, 18 Feb 2010) $ -</address> -</body> -</html> - |
