LangRef.html

<h5>Semantics:</h5>
...<p>


<h5>Example:</h5>
<pre>
  &lt;result&gt; = or int 4, %var         <i>; yields {int}:result = 4 | %var</i>
  &lt;result&gt; = or int 15, 40          <i>; yields {int}:result = 47</i>
  &lt;result&gt; = or int 4, 8            <i>; yields {int}:result = 12</i>
</pre>


<!-- _______________________________________________________________________ -->
</ul><a name="i_xor"><h4><hr size=0>'<tt>xor</tt>' Instruction</h4><ul>

<h5>Syntax:</h5>
<pre>
  &lt;result&gt; = xor &lt;ty&gt; &lt;var1&gt;, &lt;var2&gt;   <i>; yields {ty}:result</i>
</pre>

<h5>Overview:</h5>

The '<tt>xor</tt>' instruction returns the bitwise logical exclusive or of its
two operands.<p>

<h5>Arguments:</h5>

The two arguments to the '<tt>xor</tt>' instruction must be either <a
href="#t_integral">integral</a> or <a href="#t_bool"><tt>bool</tt></a> values.
Both arguments must have identical types.<p>


<h5>Semantics:</h5>
...<p>


<h5>Example:</h5>
<pre>
  &lt;result&gt; = xor int 4, %var         <i>; yields {int}:result = 4 ^ %var</i>
  &lt;result&gt; = xor int 15, 40          <i>; yields {int}:result = 39</i>
  &lt;result&gt; = xor int 4, 8            <i>; yields {int}:result = 12</i>
</pre>


<!-- _______________________________________________________________________ -->
</ul><a name="i_shl"><h4><hr size=0>'<tt>shl</tt>' Instruction</h4><ul>

<h5>Syntax:</h5>
<pre>
  &lt;result&gt; = shl &lt;ty&gt; &lt;var1&gt;, ubyte &lt;var2&gt;   <i>; yields {ty}:result</i>
</pre>

<h5>Overview:</h5>

The '<tt>shl</tt>' instruction returns the first operand shifted to the left a
specified number of bits.

<h5>Arguments:</h5>

The first argument to the '<tt>shl</tt>' instruction must be an <a
href="#t_integral">integral</a> type.  The second argument must be an
'<tt>ubyte</tt>' type.<p>

<h5>Semantics:</h5>
... 0 bits are shifted into the emptied bit positions...<p>


<h5>Example:</h5>
<pre>
  &lt;result&gt; = shl int 4, ubyte %var   <i>; yields {int}:result = 4 << %var</i>
  &lt;result&gt; = shl int 4, ubyte 2      <i>; yields {int}:result = 16</i>
  &lt;result&gt; = shl int 1, ubyte 10     <i>; yields {int}:result = 1024</i>
</pre>


<!-- _______________________________________________________________________ -->
</ul><a name="i_shr"><h4><hr size=0>'<tt>shr</tt>' Instruction</h4><ul>


<h5>Syntax:</h5>
<pre>
  &lt;result&gt; = shr &lt;ty&gt; &lt;var1&gt;, ubyte &lt;var2&gt;   <i>; yields {ty}:result</i>
</pre>

<h5>Overview:</h5>
The '<tt>shr</tt>' instruction returns the first operand shifted to the right a specified number of bits.

<h5>Arguments:</h5>
The first argument to the '<tt>shr</tt>' instruction must be an  <a href="#t_integral">integral</a> type.  The second argument must be an '<tt>ubyte</tt>' type.<p>

<h5>Semantics:</h5>
... if the first argument is a <a href="#t_signed">signed</a> type, the most significant bit is duplicated in the newly free'd bit positions.  If the first argument is unsigned, zeros shall fill the empty positions...<p>

<h5>Example:</h5>
<pre>
  &lt;result&gt; = shr int 4, ubyte %var   <i>; yields {int}:result = 4 >> %var</i>
  &lt;result&gt; = shr int 4, ubyte 1      <i>; yields {int}:result = 2</i>
  &lt;result&gt; = shr int 4, ubyte 2      <i>; yields {int}:result = 1</i>
  &lt;result&gt; = shr int 4, ubyte 3      <i>; yields {int}:result = 0</i>
</pre>





<!-- ======================================================================= -->
</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0><tr><td>&nbsp;</td><td width="100%">&nbsp; <font color="#EEEEFF" face="Georgia,Palatino"><b>
<a name="memoryops">Memory Access Operations
</b></font></td></tr></table><ul>

Accessing memory in SSA form is, well, sticky at best.  This section describes how to read and write memory in LLVM.<p>


<!-- _______________________________________________________________________ -->
</ul><a name="i_malloc"><h4><hr size=0>'<tt>malloc</tt>' Instruction</h4><ul>

<h5>Syntax:</h5>
<pre>
  &lt;result&gt; = malloc &lt;type&gt;, uint &lt;NumElements&gt;     <i>; yields {type*}:result</i>
  &lt;result&gt; = malloc &lt;type&gt;                         <i>; yields {type*}:result</i>
</pre>

<h5>Overview:</h5>
The '<tt>malloc</tt>' instruction allocates memory from the system heap and returns a pointer to it.<p>

<h5>Arguments:</h5>

The the '<tt>malloc</tt>' instruction allocates
<tt>sizeof(&lt;type&gt;)*NumElements</tt> bytes of memory from the operating
system, and returns a pointer of the appropriate type to the program.  The
second form of the instruction is a shorter version of the first instruction
that defaults to allocating one element.<p>

'<tt>type</tt>' must be a sized type<p>

<h5>Semantics:</h5>
Memory is allocated, a pointer is returned.<p>

<h5>Example:</h5>
<pre>
  %array  = malloc [4 x ubyte ]                    <i>; yields {[%4 x ubyte]*}:array</i>

  %size   = <a href="#i_add">add</a> uint 2, 2                          <i>; yields {uint}:size = uint 4</i>
  %array1 = malloc ubyte, uint 4                   <i>; yields {ubyte*}:array1</i>
  %array2 = malloc [12 x ubyte], uint %size        <i>; yields {[12 x ubyte]*}:array2</i>
</pre>


<!-- _______________________________________________________________________ -->
</ul><a name="i_free"><h4><hr size=0>'<tt>free</tt>' Instruction</h4><ul>

<h5>Syntax:</h5>
<pre>
  free &lt;type&gt; &lt;value&gt;                              <i>; yields {void}</i>
</pre>


<h5>Overview:</h5>
The '<tt>free</tt>' instruction returns memory back to the unused memory heap, to be reallocated in the future.<p>


<h5>Arguments:</h5>

'<tt>value</tt>' shall be a pointer value that points to a value that was allocated with the '<tt><a href="#i_malloc">malloc</a></tt>' instruction.<p>


<h5>Semantics:</h5>
Memory is available for use after this point.  The contents of the '<tt>value</tt>' pointer are undefined after this instruction.<p>


<h5>Example:</h5>
<pre>
  %array  = <a href="#i_malloc">malloc</a> [4 x ubyte]                    <i>; yields {[4 x ubyte]*}:array</i>
            free   [4 x ubyte]* %array
</pre>


<!-- _______________________________________________________________________ -->
</ul><a name="i_alloca"><h4><hr size=0>'<tt>alloca</tt>' Instruction</h4><ul>

<h5>Syntax:</h5>
<pre>
  &lt;result&gt; = alloca &lt;type&gt;, uint &lt;NumElements&gt;  <i>; yields {type*}:result</i>
  &lt;result&gt; = alloca &lt;type&gt;                      <i>; yields {type*}:result</i>
</pre>

<h5>Overview:</h5>

The '<tt>alloca</tt>' instruction allocates memory on the current stack frame of
the procedure that is live until the current function returns to its caller.<p>

<h5>Arguments:</h5>

The the '<tt>alloca</tt>' instruction allocates
<tt>sizeof(&lt;type&gt;)*NumElements</tt> bytes of memory on the runtime stack,
returning a pointer of the appropriate type to the program.  The second form of
the instruction is a shorter version of the first that defaults to allocating
one element.<p>

'<tt>type</tt>' may be any sized type.<p>

<h5>Semantics:</h5>

Memory is allocated, a pointer is returned.  '<tt>alloca</tt>'d memory is
automatically released when the function returns.  The '<tt>alloca</tt>'
instruction is commonly used to represent automatic variables that must have an
address available, as well as spilled variables.<p>

<h5>Example:</h5>
<pre>
  %ptr = alloca int                              <i>; yields {int*}:ptr</i>
  %ptr = alloca int, uint 4                      <i>; yields {int*}:ptr</i>
</pre>


<!-- _______________________________________________________________________ -->
</ul><a name="i_getelementptr"><h4><hr size=0>'<tt>getelementptr</tt>' Instruction</h4><ul>

<h5>Syntax:</h5>
<pre>
  &lt;result&gt; = getelementptr &lt;ty&gt;* &lt;ptrval&gt;{, uint &lt;aidx&gt;|, ubyte &lt;sidx&gt;}*
</pre>

<h5>Overview:</h5>

The '<tt>getelementptr</tt>' instruction is used to get the address of a
subelement of an aggregate data structure.  In addition to being present as an
explicit instruction, the '<tt>getelementptr</tt>' functionality is present in
both the '<tt><a href="#i_load">load</a></tt>' and '<tt><a
href="#i_store">store</a></tt>' instructions to allow more compact specification
of common expressions.<p>

<h5>Arguments:</h5>

This instruction takes a list of <tt>uint</tt> values and <tt>ubyte</tt>
constants that indicate what form of addressing to perform.  The actual types of
the arguments provided depend on the type of the first pointer argument.  The
'<tt>getelementptr</tt>' instruction is used to index down through the type
levels of a structure.<p>

TODO.

<h5>Semantics:</h5>


<h5>Example:</h5>
<pre>
  %aptr = getelementptr {int, [12 x ubyte]}* %sptr, 1   <i>; yields {[12 x ubyte]*}:aptr</i>
  %ub   = load [12x ubyte]* %aptr, 4                    <i>;yields {ubyte}:ub</i>
</pre>



<!-- _______________________________________________________________________ -->
</ul><a name="i_load"><h4><hr size=0>'<tt>load</tt>' Instruction</h4><ul>

<h5>Syntax:</h5>
<pre>
  &lt;result&gt; = load &lt;ty&gt;* &lt;pointer&gt;
  &lt;result&gt; = load &lt;ty&gt;* &lt;pointer&gt; &lt;index list&gt;
</pre>

<h5>Overview:</h5>
The '<tt>load</tt>' instruction is used to read from memory.<p>

<h5>Arguments:</h5>

There are three forms of the '<tt>load</tt>' instruction: one for reading from a general pointer, one for reading from a pointer to an array, and one for reading from a pointer to a structure.<p>

In the first form, '<tt>&lt;ty&gt;</tt>' must be a pointer to a simple type (a primitive type or another pointer).<p>

In the second form, '<tt>&lt;ty&gt;</tt>' must be a pointer to an array, and a list of one or more indices is provided as indexes into the (possibly multidimensional) array.  No bounds checking is performed on array reads.<p>

In the third form, the pointer must point to a (possibly nested) structure.  There shall be one ubyte argument for each level of dereferencing involved.<p>

<h5>Semantics:</h5>
...

<h5>Examples:</h5>
<pre>
  %ptr = <a href="#i_alloca">alloca</a> int                               <i>; yields {int*}:ptr</i>
  <a href="#i_store">store</a> int 3, int* %ptr                          <i>; yields {void}</i>
  %val = load int* %ptr                           <i>; yields {int}:val = int 3</i>

  %array = <a href="#i_malloc">malloc</a> [4 x ubyte]                     <i>; yields {[4 x ubyte]*}:array</i>
  <a href="#i_store">store</a> ubyte 124, [4 x ubyte]* %array, uint 4
  %val   = load [4 x ubyte]* %array, uint 4       <i>; yields {ubyte}:val = ubyte 124</i>
  %val   = load {{int, float}}* %stptr, 0, 1      <i>; yields {float}:val</i>
</pre>




<!-- _______________________________________________________________________ -->
</ul><a name="i_store"><h4><hr size=0>'<tt>store</tt>' Instruction</h4><ul>

<h5>Syntax:</h5>
<pre>
  store &lt;ty&gt; &lt;value&gt;, &lt;ty&gt;* &lt;pointer&gt;                   <i>; yields {void}</i>
  store &lt;ty&gt; &lt;value&gt;, &lt;ty&gt;* &lt;arrayptr&gt;{, uint &lt;idx&gt;}+   <i>; yields {void}</i>
  store &lt;ty&gt; &lt;value&gt;, &lt;ty&gt;* &lt;structptr&gt;{, ubyte &lt;idx&gt;}+ <i>; yields {void}e</i>
</pre>

<h5>Overview:</h5>
The '<tt>store</tt>' instruction is used to write to memory.<p>

<h5>Arguments:</h5>
There are three forms of the '<tt>store</tt>' instruction: one for writing through a general pointer, one for writing through a pointer to a (possibly multidimensional) array, and one for writing to an element of a (potentially nested) structure.<p>

The semantics of this instruction closely match that of the <a href="#i_load">load</a> instruction, except that memory is written to, not read from.

<h5>Semantics:</h5>
...

<h5>Example:</h5>
<pre>
  %ptr = <a href="#i_alloca">alloca</a> int                               <i>; yields {int*}:ptr</i>
  <a href="#i_store">store</a> int 3, int* %ptr                          <i>; yields {void}</i>
  %val = load int* %ptr                           <i>; yields {int}:val = int 3</i>

  %array = <a href="#i_malloc">malloc</a> [4 x ubyte]                     <i>; yields {[4 x ubyte]*}:array</i>
  <a href="#i_store">store</a> ubyte 124, [4 x ubyte]* %array, uint 4
  %val   = load [4 x ubyte]* %array, uint 4       <i>; yields {ubyte}:val = ubyte 124</i>
  %val   = load {{int, float}}* %stptr, 0, 1      <i>; yields {float}:val</i>
</pre>




<!-- ======================================================================= -->
</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0><tr><td>&nbsp;</td><td width="100%">&nbsp; <font color="#EEEEFF" face="Georgia,Palatino"><b>
<a name="otherops">Other Operations
</b></font></td></tr></table><ul>

The instructions in this catagory are the "miscellaneous" functions, that defy better classification.<p>


<!-- _______________________________________________________________________ -->
</ul><a name="i_cast"><h4><hr size=0>'<tt>cast .. to</tt>' Instruction</h4><ul>

<h1>TODO</h1>

<a name="logical_integrals">
  Talk about what is considered true or false for integrals.



<h5>Syntax:</h5>
<pre>
</pre>

<h5>Overview:</h5>


<h5>Arguments:</h5>


<h5>Semantics:</h5>


<h5>Example:</h5>
<pre>
</pre>



<!-- _______________________________________________________________________ -->
</ul><a name="i_call"><h4><hr size=0>'<tt>call</tt>' Instruction</h4><ul>

<h5>Syntax:</h5>
<pre>

</pre>

<h5>Overview:</h5>


<h5>Arguments:</h5>


<h5>Semantics:</h5>


<h5>Example:</h5>
<pre>
  %retval = call int %test(int %argc)
</pre>


<!-- _______________________________________________________________________ --></ul><a name="i_icall"><h3><hr size=0>'<tt>icall</tt>' Instruction</h3><ul>

Indirect calls are desperately needed to implement virtual function tables (C++, java) and function pointers (C, C++, ...).<p>

A new instruction <tt>icall</tt> or similar should be introduced to represent an indirect call.<p>

Example:
<pre>
  %retval = icall int %funcptr(int %arg1)          <i>; yields {int}:%retval</i>
</pre>



<!-- _______________________________________________________________________ -->
</ul><a name="i_phi"><h4><hr size=0>'<tt>phi</tt>' Instruction</h4><ul>

<h5>Syntax:</h5>
<pre>
</pre>

<h5>Overview:</h5>


<h5>Arguments:</h5>


<h5>Semantics:</h5>


<h5>Example:</h5>
<pre>
</pre>


<!-- ======================================================================= -->
</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0><tr><td>&nbsp;</td><td width="100%">&nbsp; <font color="#EEEEFF" face="Georgia,Palatino"><b>
<a name="builtinfunc">Builtin Functions
</b></font></td></tr></table><ul>

<b>Notice:</b> Preliminary idea!<p>

Builtin functions are very similar to normal functions, except they are defined by the implementation.  Invocations of these functions are very similar to function invocations, except that the syntax is a little less verbose.<p>

Builtin functions are useful to implement semi-high level ideas like a '<tt>min</tt>' or '<tt>max</tt>' operation that can have important properties when doing program analysis.  For example:

<ul>
<li>Some optimizations can make use of identities defined over the functions, 
    for example a parrallelizing compiler could make use of '<tt>min</tt>' 
    identities to parrellelize a loop.
<li>Builtin functions would have polymorphic types, where normal function calls
    may only have a single type.
<li>Builtin functions would be known to not have side effects, simplifying 
    analysis over straight function calls.
<li>The syntax of the builtin are cleaner than the syntax of the 
    '<a href="#i_call"><tt>call</tt></a>' instruction (very minor point).
</ul>

Because these invocations are explicit in the representation, the runtime can choose to implement these builtin functions any way that they want, including:

<ul>
<li>Inlining the code directly into the invocation
<li>Implementing the functions in some sort of Runtime class, convert invocation
    to a standard function call.
<li>Implementing the functions in some sort of Runtime class, and perform 
    standard inlining optimizations on it.
</ul>

Note that these builtins do not use quoted identifiers: the name of the builtin effectively becomes an identifier in the language.<p>

Example:
<pre>
  ; Example of a normal function call
  %maximum = call int %maximum(int %arg1, int %arg2)   <i>; yields {int}:%maximum</i>

  ; Examples of potential builtin functions
  %max = max(int %arg1, int %arg2)                     <i>; yields {int}:%max</i>
  %min = min(int %arg1, int %arg2)                     <i>; yields {int}:%min</i>
  %sin = sin(double %arg)                              <i>; yields {double}:%sin</i>
  %cos = cos(double %arg)                              <i>; yields {double}:%cos</i>

  ; Show that builtin's are polymorphic, like instructions
  %max = max(float %arg1, float %arg2)                 <i>; yields {float}:%max</i>
  %cos = cos(float %arg)                               <i>; yields {float}:%cos</i>
</pre>

The '<tt>maximum</tt>' vs '<tt>max</tt>' example illustrates the difference in calling semantics between a '<a href="#i_call"><tt>call</tt></a>' instruction and a builtin function invocation.  Notice that the '<tt>maximum</tt>' example assumes that the function is defined local to the caller.<p>




<!-- *********************************************************************** -->
</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0><tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
<a name="todo">TODO List
</b></font></td></tr></table><ul>
<!-- *********************************************************************** -->

This list of random topics includes things that will <b>need</b> to be addressed before the llvm may be used to implement a java like langauge.  Right now, it is pretty much useless for any language, given to unavailable of structure types<p>

<!-- _______________________________________________________________________ -->
</ul><a name="synchronization"><h3><hr size=0>Synchronization Instructions</h3><ul>

We will need some type of synchronization instructions to be able to implement stuff in Java well.  The way I currently envision doing this is to introduce a '<tt>lock</tt>' type, and then add two (builtin or instructions) operations to lock and unlock the lock.<p>


<!-- *********************************************************************** -->
</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0><tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
<a name="extensions">Possible Extensions
</b></font></td></tr></table><ul>
<!-- *********************************************************************** -->

These extensions are distinct from the TODO list, as they are mostly "interesting" ideas that could be implemented in the future by someone so motivated.  They are not directly required to get <a href="#rw_java">Java</a> like languages working.<p>

<!-- _______________________________________________________________________ -->
</ul><a name="i_tailcall"><h3><hr size=0>'<tt>tailcall</tt>' Instruction</h3><ul>

This could be useful.  Who knows.  '.net' does it, but is the optimization really worth the extra hassle?  Using strong typing would make this trivial to implement and a runtime could always callback to using downconverting this to a normal '<a href="#i_call"><tt>call</tt></a>' instruction.<p>


<!-- _______________________________________________________________________ -->
</ul><a name="globalvars"><h3><hr size=0>Global Variables</h3><ul>

In order to represent programs written in languages like C, we need to be able to support variables at the module (global) scope.  Perhaps they should be written outside of the module definition even.  Maybe global functions should be handled like this as well.<p>


<!-- _______________________________________________________________________ -->
</ul><a name="explicitparrellelism"><h3><hr size=0>Explicit Parrellelism</h3><ul>

With the rise of massively parrellel architectures (like <a href="#rw_ia64">the IA64 architecture</a>, multithreaded CPU cores, and SIMD data sets) it is becoming increasingly more important to extract all of the ILP from a code stream possible.  It would be interesting to research encoding functions that can explicitly represent this.  One straightforward way to do this would be to introduce a "stop" instruction that is equilivent to the IA64 stop bit.<p>



<!-- *********************************************************************** -->
</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0><tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
<a name="related">Related Work
</b></font></td></tr></table><ul>
<!-- *********************************************************************** -->


Codesigned virtual machines.<p>

<dl>
<a name="rw_safetsa">
<dt>SafeTSA
<DD>Description here<p>

<a name="rw_java">
<dt><a href="http://www.javasoft.com">Java</a>
<DD>Desciption here<p>

<a name="rw_net">
<dt><a href="http://www.microsoft.com/net">Microsoft .net</a>
<DD>Desciption here<p>

<a name="rw_gccrtl">
<dt><a href="http://www.math.umn.edu/systems_guide/gcc-2.95.1/gcc_15.html">GNU RTL Intermediate Representation</a>
<DD>Desciption here<p>

<a name="rw_ia64">
<dt><a href="http://developer.intel.com/design/ia-64/index.htm">IA64 Architecture &amp; Instruction Set</a>
<DD>Desciption here<p>

<a name="rw_mmix">
<dt><a href="http://www-cs-faculty.stanford.edu/~knuth/mmix-news.html">MMIX Instruction Set</a>
<DD>Desciption here<p>

<a name="rw_stroustrup">
<dt><a href="http://www.research.att.com/~bs/devXinterview.html">"Interview With Bjarne Stroustrup"</a>
<DD>This interview influenced the design and thought process behind LLVM in several ways, most notably the way that derived types are written in text format. See the question that starts with "you defined the C declarator syntax as an experiment that failed".<p>
</dl>

<!-- _______________________________________________________________________ -->
</ul><a name="rw_vectorization"><h3><hr size=0>Vectorized Architectures</h3><ul>

<dl>
<a name="rw_intel_simd">
<dt>Intel MMX, MMX2, SSE, SSE2
<DD>Description here<p>

<a name="rw_amd_simd">
<dt><a href="http://www.nondot.org/~sabre/os/H1ChipFeatures/3DNow!TechnologyManual.pdf">AMD 3Dnow!, 3Dnow! 2</a>
<DD>Desciption here<p>

<a name="rw_sun_simd">
<dt><a href="http://www.nondot.org/~sabre/os/H1ChipFeatures/VISInstructionSetUsersManual.pdf">Sun VIS ISA</a>
<DD>Desciption here<p>


</dl>

more...

<!-- *********************************************************************** -->
</ul>
<!-- *********************************************************************** -->


<hr>
<font size=-1>
<address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address>
<!-- Created: Tue Jan 23 15:19:28 CST 2001 -->
<!-- hhmts start -->
Last modified: Sun Apr 14 01:12:55 CDT 2002
<!-- hhmts end -->
</font>
</body></html>