<li><a href="#targetimpls">Target-specific Implementation Notes</a>
<ul>
<li><a href="#tailcallopt">Tail call optimization</a></li>
+ <li><a href="#sibcallopt">Sibling call optimization</a></li>
<li><a href="#x86">The X86 backend</a></li>
<li><a href="#ppc">The PowerPC backend</a>
<ul>
<div class="doc_code">
<pre>
-MI.addReg(Reg, MachineOperand::Def);
+MI.addReg(Reg, RegState::Define);
</pre>
</div>
<div class="doc_code">
<pre>
-%t1 = add float %W, %X
-%t2 = mul float %t1, %Y
-%t3 = add float %t2, %Z
+%t1 = fadd float %W, %X
+%t2 = fmul float %t1, %Y
+%t3 = fadd float %t2, %Z
</pre>
</div>
<p>The portion of the instruction definition in bold indicates the pattern used
to match the instruction. The DAG operators
(like <tt>fmul</tt>/<tt>fadd</tt>) are defined in
- the <tt>lib/Target/TargetSelectionDAG.td</tt> file. "<tt>F4RC</tt>" is the
- register class of the input and result values.</p>
+ the <tt>include/llvm/Target/TargetSelectionDAG.td</tt> file. "
+ <tt>F4RC</tt>" is the register class of the input and result values.</p>
<p>The TableGen DAG instruction selector generator reads the instruction
patterns in the <tt>.td</tt> file and automatically builds parts of the
for <tt>RegisterClass</tt>, the last parameter of which is a list of
registers. Just commenting some out is one simple way to avoid them being
used. A more polite way is to explicitly exclude some registers from
- the <i>allocation order</i>. See the definition of the <tt>GR</tt> register
- class in <tt>lib/Target/IA64/IA64RegisterInfo.td</tt> for an example of this
- (e.g., <tt>numReservedRegs</tt> registers are hidden.)</p>
+ the <i>allocation order</i>. See the definition of the <tt>GR8</tt> register
+ class in <tt>lib/Target/X86/X86RegisterInfo.td</tt> for an example of this.
+ </p>
<p>Virtual registers are also denoted by integer numbers. Contrary to physical
registers, different virtual registers never share the same number. The
instruction,
use <tt>TargetInstrInfo::get(opcode)::ImplicitUses</tt>. Pre-colored
registers impose constraints on any register allocation algorithm. The
- register allocator must make sure that none of them is been overwritten by
+ register allocator must make sure that none of them are overwritten by
the values of virtual registers while still alive.</p>
</div>
different register allocators:</p>
<ul>
- <li><i>Simple</i> — This is a very simple implementation that does not
- keep values in registers across instructions. This register allocator
- immediately spills every value right after it is computed, and reloads all
- used operands from memory to temporary registers before each
- instruction.</li>
-
- <li><i>Local</i> — This register allocator is an improvement on the
- <i>Simple</i> implementation. It allocates registers on a basic block
- level, attempting to keep values in registers and reusing registers as
- appropriate.</li>
-
<li><i>Linear Scan</i> — <i>The default allocator</i>. This is the
well-know linear scan register allocator. Whereas the
<i>Simple</i> and <i>Local</i> algorithms use a direct mapping
implementation technique, the <i>Linear Scan</i> implementation
uses a spiller in order to place load and stores.</li>
+
+ <li><i>Fast</i> — This register allocator is the default for debug
+ builds. It allocates registers on a basic block level, attempting to keep
+ values in registers and reusing registers as appropriate.</li>
+
+ <li><i>PBQP</i> — A Partitioned Boolean Quadratic Programming (PBQP)
+ based register allocator. This allocator works by constructing a PBQP
+ problem representing the register allocation problem under consideration,
+ solving this using a PBQP solver, and mapping the solution back to a
+ register assignment.</li>
+
</ul>
<p>The type of register allocator used in <tt>llc</tt> can be chosen with the
<div class="doc_code">
<pre>
-$ llc -f -regalloc=simple file.bc -o sp.s;
-$ llc -f -regalloc=local file.bc -o lc.s;
-$ llc -f -regalloc=linearscan file.bc -o ln.s;
+$ llc -regalloc=linearscan file.bc -o ln.s;
+$ llc -regalloc=fast file.bc -o fa.s;
+$ llc -regalloc=pbqp file.bc -o pbqp.s;
</pre>
</div>
supported on x86/x86-64 and PowerPC. It is performed if:</p>
<ul>
- <li>Caller and callee have the calling convention <tt>fastcc</tt>.</li>
+ <li>Caller and callee have the calling convention <tt>fastcc</tt> or
+ <tt>cc 10</tt> (GHC call convention).</li>
<li>The call is a tail call - in tail position (ret immediately follows call
and ret uses value of call or is void).</li>
(because one or more of above constraints are not met) to be followed by a
readjustment of the stack. So performance might be worse in such cases.</p>
-<p>On x86 and x86-64 one register is reserved for indirect tail calls (e.g via a
- function pointer). So there is one less register for integer argument
- passing. For x86 this means 2 registers (if <tt>inreg</tt> parameter
- attribute is used) and for x86-64 this means 5 register are used.</p>
+</div>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="sibcallopt">Sibling call optimization</a>
+</div>
+
+<div class="doc_text">
+
+<p>Sibling call optimization is a restricted form of tail call optimization.
+ Unlike tail call optimization described in the previous section, it can be
+ performed automatically on any tail calls when <tt>-tailcallopt</tt> option
+ is not specified.</p>
+
+<p>Sibling call optimization is currently performed on x86/x86-64 when the
+ following constraints are met:</p>
+
+<ul>
+ <li>Caller and callee have the same calling convention. It can be either
+ <tt>c</tt> or <tt>fastcc</tt>.
+
+ <li>The call is a tail call - in tail position (ret immediately follows call
+ and ret uses value of call or is void).</li>
+
+ <li>Caller and callee have matching return type or the callee result is not
+ used.
+
+ <li>If any of the callee arguments are being passed in stack, they must be
+ available in caller's own incoming argument stack and the frame offsets
+ must be the same.
+</ul>
+
+<p>Example:</p>
+<div class="doc_code">
+<pre>
+declare i32 @bar(i32, i32)
+
+define i32 @foo(i32 %a, i32 %b, i32 %c) {
+entry:
+ %0 = tail call i32 @bar(i32 %a, i32 %b)
+ ret i32 %0
+}
+</pre>
+</div>
</div>
<!-- ======================================================================= -->
<li><b>i386-pc-mingw32msvc</b> — MingW crosscompiler on Linux</li>
<li><b>i686-apple-darwin*</b> — Apple Darwin on X86</li>
+
+ <li><b>x86_64-unknown-linux-gnu</b> — Linux</li>
</ul>
</div>
<div class="doc_code">
<pre>
-Base + [1,2,4,8] * IndexReg + Disp32
+SegmentReg: Base + [1,2,4,8] * IndexReg + Disp32
</pre>
</div>
-<p>In order to represent this, LLVM tracks no less than 4 operands for each
+<p>In order to represent this, LLVM tracks no less than 5 operands for each
memory operand of this form. This means that the "load" form of
'<tt>mov</tt>' has the following <tt>MachineOperand</tt>s in this order:</p>
<div class="doc_code">
<pre>
-Index: 0 | 1 2 3 4
-Meaning: DestReg, | BaseReg, Scale, IndexReg, Displacement
-OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg, SignExtImm
+Index: 0 | 1 2 3 4 5
+Meaning: DestReg, | BaseReg, Scale, IndexReg, Displacement Segment
+OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg, SignExtImm PhysReg
</pre>
</div>
<p>Stores, and all other instructions, treat the four memory operands in the
- same way and in the same order.</p>
+ same way and in the same order. If the segment register is unspecified
+ (regno = 0), then no segment override is generated. "Lea" operations do not
+ have a segment register specified, so they only have 4 operands for their
+ memory reference.</p>
</div>