<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://www.cs.york.ac.uk/fp/darcs/hscolour/ -->
<title>nativeGen/RegAlloc/Linear/Main.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-comment'>{-# OPTIONS -fno-warn-missing-signatures #-}</span>
<a name="line-2"></a><span class='hs-comment'>-----------------------------------------------------------------------------</span>
<a name="line-3"></a><span class='hs-comment'>--</span>
<a name="line-4"></a><span class='hs-comment'>-- The register allocator</span>
<a name="line-5"></a><span class='hs-comment'>--</span>
<a name="line-6"></a><span class='hs-comment'>-- (c) The University of Glasgow 2004</span>
<a name="line-7"></a><span class='hs-comment'>--</span>
<a name="line-8"></a><span class='hs-comment'>-----------------------------------------------------------------------------</span>
<a name="line-9"></a>
<a name="line-10"></a><span class='hs-comment'>{-
<a name="line-11"></a>The algorithm is roughly:
<a name="line-12"></a>
<a name="line-13"></a> 1) Compute strongly connected components of the basic block list.
<a name="line-14"></a>
<a name="line-15"></a> 2) Compute liveness (mapping from pseudo register to
<a name="line-16"></a> point(s) of death?).
<a name="line-17"></a>
<a name="line-18"></a> 3) Walk instructions in each basic block. We keep track of
<a name="line-19"></a> (a) Free real registers (a bitmap?)
<a name="line-20"></a> (b) Current assignment of temporaries to machine registers and/or
<a name="line-21"></a> spill slots (call this the "assignment").
<a name="line-22"></a> (c) Partial mapping from basic block ids to a virt-to-loc mapping.
<a name="line-23"></a> When we first encounter a branch to a basic block,
<a name="line-24"></a> we fill in its entry in this table with the current mapping.
<a name="line-25"></a>
<a name="line-26"></a> For each instruction:
<a name="line-27"></a> (a) For each real register clobbered by this instruction:
<a name="line-28"></a> If a temporary resides in it,
<a name="line-29"></a> If the temporary is live after this instruction,
<a name="line-30"></a> Move the temporary to another (non-clobbered & free) reg,
<a name="line-31"></a> or spill it to memory. Mark the temporary as residing
<a name="line-32"></a> in both memory and a register if it was spilled (it might
<a name="line-33"></a> need to be read by this instruction).
<a name="line-34"></a> (ToDo: this is wrong for jump instructions?)
<a name="line-35"></a>
<a name="line-36"></a> (b) For each temporary *read* by the instruction:
<a name="line-37"></a> If the temporary does not have a real register allocation:
<a name="line-38"></a> - Allocate a real register from the free list. If
<a name="line-39"></a> the list is empty:
<a name="line-40"></a> - Find a temporary to spill. Pick one that is
<a name="line-41"></a> not used in this instruction (ToDo: not
<a name="line-42"></a> used for a while...)
<a name="line-43"></a> - generate a spill instruction
<a name="line-44"></a> - If the temporary was previously spilled,
<a name="line-45"></a> generate an instruction to read the temp from its spill loc.
<a name="line-46"></a> (optimisation: if we can see that a real register is going to
<a name="line-47"></a> be used soon, then don't use it for allocation).
<a name="line-48"></a>
<a name="line-49"></a> (c) Update the current assignment
<a name="line-50"></a>
<a name="line-51"></a> (d) If the intstruction is a branch:
<a name="line-52"></a> if the destination block already has a register assignment,
<a name="line-53"></a> Generate a new block with fixup code and redirect the
<a name="line-54"></a> jump to the new block.
<a name="line-55"></a> else,
<a name="line-56"></a> Update the block id->assignment mapping with the current
<a name="line-57"></a> assignment.
<a name="line-58"></a>
<a name="line-59"></a> (e) Delete all register assignments for temps which are read
<a name="line-60"></a> (only) and die here. Update the free register list.
<a name="line-61"></a>
<a name="line-62"></a> (f) Mark all registers clobbered by this instruction as not free,
<a name="line-63"></a> and mark temporaries which have been spilled due to clobbering
<a name="line-64"></a> as in memory (step (a) marks then as in both mem & reg).
<a name="line-65"></a>
<a name="line-66"></a> (g) For each temporary *written* by this instruction:
<a name="line-67"></a> Allocate a real register as for (b), spilling something
<a name="line-68"></a> else if necessary.
<a name="line-69"></a> - except when updating the assignment, drop any memory
<a name="line-70"></a> locations that the temporary was previously in, since
<a name="line-71"></a> they will be no longer valid after this instruction.
<a name="line-72"></a>
<a name="line-73"></a> (h) Delete all register assignments for temps which are
<a name="line-74"></a> written and die here (there should rarely be any). Update
<a name="line-75"></a> the free register list.
<a name="line-76"></a>
<a name="line-77"></a> (i) Rewrite the instruction with the new mapping.
<a name="line-78"></a>
<a name="line-79"></a> (j) For each spilled reg known to be now dead, re-add its stack slot
<a name="line-80"></a> to the free list.
<a name="line-81"></a>
<a name="line-82"></a>-}</span>
<a name="line-83"></a>
<a name="line-84"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>RegAlloc</span><span class='hs-varop'>.</span><span class='hs-conid'>Linear</span><span class='hs-varop'>.</span><span class='hs-conid'>Main</span> <span class='hs-layout'>(</span>
<a name="line-85"></a> <span class='hs-varid'>regAlloc</span><span class='hs-layout'>,</span>
<a name="line-86"></a> <span class='hs-keyword'>module</span> <span class='hs-conid'>RegAlloc</span><span class='hs-varop'>.</span><span class='hs-conid'>Linear</span><span class='hs-varop'>.</span><span class='hs-conid'>Base</span><span class='hs-layout'>,</span>
<a name="line-87"></a> <span class='hs-keyword'>module</span> <span class='hs-conid'>RegAlloc</span><span class='hs-varop'>.</span><span class='hs-conid'>Linear</span><span class='hs-varop'>.</span><span class='hs-conid'>Stats</span>
<a name="line-88"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-89"></a>
<a name="line-90"></a><span class='hs-cpp'>#include "HsVersions.h"</span>
<a name="line-91"></a>
<a name="line-92"></a>
<a name="line-93"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>RegAlloc</span><span class='hs-varop'>.</span><span class='hs-conid'>Linear</span><span class='hs-varop'>.</span><span class='hs-conid'>State</span>
<a name="line-94"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>RegAlloc</span><span class='hs-varop'>.</span><span class='hs-conid'>Linear</span><span class='hs-varop'>.</span><span class='hs-conid'>Base</span>
<a name="line-95"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>RegAlloc</span><span class='hs-varop'>.</span><span class='hs-conid'>Linear</span><span class='hs-varop'>.</span><span class='hs-conid'>StackMap</span>
<a name="line-96"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>RegAlloc</span><span class='hs-varop'>.</span><span class='hs-conid'>Linear</span><span class='hs-varop'>.</span><span class='hs-conid'>FreeRegs</span>
<a name="line-97"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>RegAlloc</span><span class='hs-varop'>.</span><span class='hs-conid'>Linear</span><span class='hs-varop'>.</span><span class='hs-conid'>Stats</span>
<a name="line-98"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>RegAlloc</span><span class='hs-varop'>.</span><span class='hs-conid'>Linear</span><span class='hs-varop'>.</span><span class='hs-conid'>JoinToTargets</span>
<a name="line-99"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>TargetReg</span>
<a name="line-100"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>RegAlloc</span><span class='hs-varop'>.</span><span class='hs-conid'>Liveness</span>
<a name="line-101"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Instruction</span>
<a name="line-102"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Reg</span>
<a name="line-103"></a>
<a name="line-104"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>BlockId</span>
<a name="line-105"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Cmm</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-conid'>RegSet</span><span class='hs-layout'>)</span>
<a name="line-106"></a>
<a name="line-107"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Digraph</span>
<a name="line-108"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Unique</span>
<a name="line-109"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>UniqSet</span>
<a name="line-110"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>UniqFM</span>
<a name="line-111"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>UniqSupply</span>
<a name="line-112"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Outputable</span>
<a name="line-113"></a>
<a name="line-114"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Maybe</span>
<a name="line-115"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>List</span>
<a name="line-116"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Monad</span>
<a name="line-117"></a>
<a name="line-118"></a><span class='hs-cpp'>#include "../includes/stg/MachRegs.h"</span>
<a name="line-119"></a>
<a name="line-120"></a>
<a name="line-121"></a><span class='hs-comment'>-- -----------------------------------------------------------------------------</span>
<a name="line-122"></a><span class='hs-comment'>-- Top level of the register allocator</span>
<a name="line-123"></a>
<a name="line-124"></a><a name="regAlloc"></a><span class='hs-comment'>-- Allocate registers</span>
<a name="line-125"></a><span class='hs-definition'>regAlloc</span>
<a name="line-126"></a> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>instr</span><span class='hs-layout'>,</span> <span class='hs-conid'>Instruction</span> <span class='hs-varid'>instr</span><span class='hs-layout'>)</span>
<a name="line-127"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>LiveCmmTop</span> <span class='hs-varid'>instr</span>
<a name="line-128"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>UniqSM</span> <span class='hs-layout'>(</span><span class='hs-conid'>NatCmmTop</span> <span class='hs-varid'>instr</span><span class='hs-layout'>,</span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>RegAllocStats</span><span class='hs-layout'>)</span>
<a name="line-129"></a>
<a name="line-130"></a><span class='hs-definition'>regAlloc</span> <span class='hs-layout'>(</span><span class='hs-conid'>CmmData</span> <span class='hs-varid'>sec</span> <span class='hs-varid'>d</span><span class='hs-layout'>)</span>
<a name="line-131"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span>
<a name="line-132"></a> <span class='hs-layout'>(</span> <span class='hs-conid'>CmmData</span> <span class='hs-varid'>sec</span> <span class='hs-varid'>d</span>
<a name="line-133"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Nothing</span> <span class='hs-layout'>)</span>
<a name="line-134"></a>
<a name="line-135"></a><span class='hs-definition'>regAlloc</span> <span class='hs-layout'>(</span><span class='hs-conid'>CmmProc</span> <span class='hs-layout'>(</span><span class='hs-conid'>LiveInfo</span> <span class='hs-varid'>info</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-varid'>lbl</span> <span class='hs-varid'>params</span> <span class='hs-layout'>(</span><span class='hs-conid'>ListGraph</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-136"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span> <span class='hs-conid'>CmmProc</span> <span class='hs-varid'>info</span> <span class='hs-varid'>lbl</span> <span class='hs-varid'>params</span> <span class='hs-layout'>(</span><span class='hs-conid'>ListGraph</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-137"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Nothing</span> <span class='hs-layout'>)</span>
<a name="line-138"></a>
<a name="line-139"></a><span class='hs-definition'>regAlloc</span> <span class='hs-layout'>(</span><span class='hs-conid'>CmmProc</span> <span class='hs-varid'>static</span> <span class='hs-varid'>lbl</span> <span class='hs-varid'>params</span> <span class='hs-layout'>(</span><span class='hs-conid'>ListGraph</span> <span class='hs-varid'>comps</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-140"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>LiveInfo</span> <span class='hs-varid'>info</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>first_id</span><span class='hs-layout'>)</span> <span class='hs-varid'>block_live</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>static</span>
<a name="line-141"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-142"></a> <span class='hs-comment'>-- do register allocation on each component.</span>
<a name="line-143"></a> <span class='hs-layout'>(</span><span class='hs-varid'>final_blocks</span><span class='hs-layout'>,</span> <span class='hs-varid'>stats</span><span class='hs-layout'>)</span>
<a name="line-144"></a> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>linearRegAlloc</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span>
<a name="line-145"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>case</span> <span class='hs-varid'>b</span> <span class='hs-keyword'>of</span>
<a name="line-146"></a> <span class='hs-conid'>BasicBlock</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>AcyclicSCC</span> <span class='hs-varid'>b</span>
<a name="line-147"></a> <span class='hs-conid'>BasicBlock</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>bs</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>CyclicSCC</span> <span class='hs-varid'>bs</span><span class='hs-layout'>)</span>
<a name="line-148"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>comps</span>
<a name="line-149"></a>
<a name="line-150"></a> <span class='hs-comment'>-- make sure the block that was first in the input list</span>
<a name="line-151"></a> <span class='hs-comment'>-- stays at the front of the output</span>
<a name="line-152"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>first'</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>rest'</span><span class='hs-layout'>)</span>
<a name="line-153"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>partition</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varop'>==</span> <span class='hs-varid'>first_id</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>blockId</span><span class='hs-layout'>)</span> <span class='hs-varid'>final_blocks</span>
<a name="line-154"></a>
<a name="line-155"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span> <span class='hs-conid'>CmmProc</span> <span class='hs-varid'>info</span> <span class='hs-varid'>lbl</span> <span class='hs-varid'>params</span> <span class='hs-layout'>(</span><span class='hs-conid'>ListGraph</span> <span class='hs-layout'>(</span><span class='hs-varid'>first'</span> <span class='hs-conop'>:</span> <span class='hs-varid'>rest'</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-156"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>stats</span><span class='hs-layout'>)</span>
<a name="line-157"></a>
<a name="line-158"></a><span class='hs-comment'>-- bogus. to make non-exhaustive match warning go away.</span>
<a name="line-159"></a><span class='hs-definition'>regAlloc</span> <span class='hs-layout'>(</span><span class='hs-conid'>CmmProc</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span>
<a name="line-160"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>panic</span> <span class='hs-str'>"RegAllocLinear.regAlloc: no match"</span>
<a name="line-161"></a>
<a name="line-162"></a>
<a name="line-163"></a><span class='hs-comment'>-- -----------------------------------------------------------------------------</span>
<a name="line-164"></a><span class='hs-comment'>-- Linear sweep to allocate registers</span>
<a name="line-165"></a>
<a name="line-166"></a>
<a name="line-167"></a><a name="linearRegAlloc"></a><span class='hs-comment'>-- | Do register allocation on some basic blocks.</span>
<a name="line-168"></a><span class='hs-comment'>-- But be careful to allocate a block in an SCC only if it has</span>
<a name="line-169"></a><span class='hs-comment'>-- an entry in the block map or it is the first block.</span>
<a name="line-170"></a><span class='hs-comment'>--</span>
<a name="line-171"></a><span class='hs-definition'>linearRegAlloc</span>
<a name="line-172"></a> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>instr</span><span class='hs-layout'>,</span> <span class='hs-conid'>Instruction</span> <span class='hs-varid'>instr</span><span class='hs-layout'>)</span>
<a name="line-173"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>BlockId</span> <span class='hs-comment'>-- ^ the first block</span>
<a name="line-174"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockMap</span> <span class='hs-conid'>RegSet</span> <span class='hs-comment'>-- ^ live regs on entry to each basic block</span>
<a name="line-175"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>SCC</span> <span class='hs-layout'>(</span><span class='hs-conid'>LiveBasicBlock</span> <span class='hs-varid'>instr</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ instructions annotated with "deaths"</span>
<a name="line-176"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>UniqSM</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-conid'>NatBasicBlock</span> <span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-conid'>RegAllocStats</span><span class='hs-layout'>)</span>
<a name="line-177"></a>
<a name="line-178"></a><span class='hs-definition'>linearRegAlloc</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>sccs</span>
<a name="line-179"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-varid'>us</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getUs</span>
<a name="line-180"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-varid'>stats</span><span class='hs-layout'>,</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-181"></a> <span class='hs-varid'>runR</span> <span class='hs-varid'>emptyBlockMap</span> <span class='hs-varid'>initFreeRegs</span> <span class='hs-varid'>emptyRegMap</span> <span class='hs-varid'>emptyStackMap</span> <span class='hs-varid'>us</span>
<a name="line-182"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>linearRA_SCCs</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>sccs</span>
<a name="line-183"></a>
<a name="line-184"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>blocks</span><span class='hs-layout'>,</span> <span class='hs-varid'>stats</span><span class='hs-layout'>)</span>
<a name="line-185"></a>
<a name="line-186"></a><a name="linearRA_SCCs"></a><span class='hs-definition'>linearRA_SCCs</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>blocksAcc</span> <span class='hs-conid'>[]</span>
<a name="line-187"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reverse</span> <span class='hs-varid'>blocksAcc</span>
<a name="line-188"></a>
<a name="line-189"></a><span class='hs-definition'>linearRA_SCCs</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>blocksAcc</span> <span class='hs-layout'>(</span><span class='hs-conid'>AcyclicSCC</span> <span class='hs-varid'>block</span> <span class='hs-conop'>:</span> <span class='hs-varid'>sccs</span><span class='hs-layout'>)</span>
<a name="line-190"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-varid'>blocks'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>processBlock</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>block</span>
<a name="line-191"></a> <span class='hs-varid'>linearRA_SCCs</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span>
<a name="line-192"></a> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>reverse</span> <span class='hs-varid'>blocks'</span><span class='hs-layout'>)</span> <span class='hs-varop'>++</span> <span class='hs-varid'>blocksAcc</span><span class='hs-layout'>)</span>
<a name="line-193"></a> <span class='hs-varid'>sccs</span>
<a name="line-194"></a>
<a name="line-195"></a><span class='hs-definition'>linearRA_SCCs</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>blocksAcc</span> <span class='hs-layout'>(</span><span class='hs-conid'>CyclicSCC</span> <span class='hs-varid'>blocks</span> <span class='hs-conop'>:</span> <span class='hs-varid'>sccs</span><span class='hs-layout'>)</span>
<a name="line-196"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-197"></a> <span class='hs-varid'>blockss'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>process</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>blocks</span> <span class='hs-conid'>[]</span> <span class='hs-layout'>(</span><span class='hs-varid'>return</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-198"></a> <span class='hs-varid'>linearRA_SCCs</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span>
<a name="line-199"></a> <span class='hs-layout'>(</span><span class='hs-varid'>reverse</span> <span class='hs-layout'>(</span><span class='hs-varid'>concat</span> <span class='hs-varid'>blockss'</span><span class='hs-layout'>)</span> <span class='hs-varop'>++</span> <span class='hs-varid'>blocksAcc</span><span class='hs-layout'>)</span>
<a name="line-200"></a> <span class='hs-varid'>sccs</span>
<a name="line-201"></a>
<a name="line-202"></a><span class='hs-comment'>{- from John Dias's patch 2008/10/16:
<a name="line-203"></a> The linear-scan allocator sometimes allocates a block
<a name="line-204"></a> before allocating one of its predecessors, which could lead to
<a name="line-205"></a> inconsistent allocations. Make it so a block is only allocated
<a name="line-206"></a> if a predecessor has set the "incoming" assignments for the block, or
<a name="line-207"></a> if it's the procedure's entry block.
<a name="line-208"></a>
<a name="line-209"></a> BL 2009/02: Careful. If the assignment for a block doesn't get set for
<a name="line-210"></a> some reason then this function will loop. We should probably do some
<a name="line-211"></a> more sanity checking to guard against this eventuality.
<a name="line-212"></a>-}</span>
<a name="line-213"></a>
<a name="line-214"></a><a name="process"></a><span class='hs-definition'>process</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>accum</span>
<a name="line-215"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reverse</span> <span class='hs-varid'>accum</span>
<a name="line-216"></a>
<a name="line-217"></a><span class='hs-definition'>process</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>next_round</span> <span class='hs-varid'>accum</span>
<a name="line-218"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>process</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>next_round</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>accum</span>
<a name="line-219"></a>
<a name="line-220"></a><span class='hs-definition'>process</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>BasicBlock</span> <span class='hs-varid'>id</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>blocks</span><span class='hs-layout'>)</span> <span class='hs-varid'>next_round</span> <span class='hs-varid'>accum</span>
<a name="line-221"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-222"></a> <span class='hs-varid'>block_assig</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getBlockAssigR</span>
<a name="line-223"></a>
<a name="line-224"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>isJust</span> <span class='hs-layout'>(</span><span class='hs-varid'>lookupBlockEnv</span> <span class='hs-varid'>block_assig</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span>
<a name="line-225"></a> <span class='hs-varop'>||</span> <span class='hs-varid'>id</span> <span class='hs-varop'>==</span> <span class='hs-varid'>first_id</span>
<a name="line-226"></a> <span class='hs-keyword'>then</span> <span class='hs-keyword'>do</span>
<a name="line-227"></a> <span class='hs-varid'>b'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>processBlock</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>b</span>
<a name="line-228"></a> <span class='hs-varid'>process</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>blocks</span> <span class='hs-varid'>next_round</span> <span class='hs-layout'>(</span><span class='hs-varid'>b'</span> <span class='hs-conop'>:</span> <span class='hs-varid'>accum</span><span class='hs-layout'>)</span>
<a name="line-229"></a>
<a name="line-230"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>process</span> <span class='hs-varid'>first_id</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>blocks</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span> <span class='hs-conop'>:</span> <span class='hs-varid'>next_round</span><span class='hs-layout'>)</span> <span class='hs-varid'>accum</span>
<a name="line-231"></a>
<a name="line-232"></a>
<a name="line-233"></a><a name="processBlock"></a><span class='hs-comment'>-- | Do register allocation on this basic block</span>
<a name="line-234"></a><span class='hs-comment'>--</span>
<a name="line-235"></a><span class='hs-definition'>processBlock</span>
<a name="line-236"></a> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>instr</span><span class='hs-layout'>,</span> <span class='hs-conid'>Instruction</span> <span class='hs-varid'>instr</span><span class='hs-layout'>)</span>
<a name="line-237"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>BlockMap</span> <span class='hs-conid'>RegSet</span> <span class='hs-comment'>-- ^ live regs on entry to each basic block</span>
<a name="line-238"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LiveBasicBlock</span> <span class='hs-varid'>instr</span> <span class='hs-comment'>-- ^ block to do register allocation on</span>
<a name="line-239"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>RegM</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>NatBasicBlock</span> <span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ block with registers allocated</span>
<a name="line-240"></a>
<a name="line-241"></a><span class='hs-definition'>processBlock</span> <span class='hs-varid'>block_live</span> <span class='hs-layout'>(</span><span class='hs-conid'>BasicBlock</span> <span class='hs-varid'>id</span> <span class='hs-varid'>instrs</span><span class='hs-layout'>)</span>
<a name="line-242"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-varid'>initBlock</span> <span class='hs-varid'>id</span>
<a name="line-243"></a> <span class='hs-layout'>(</span><span class='hs-varid'>instrs'</span><span class='hs-layout'>,</span> <span class='hs-varid'>fixups</span><span class='hs-layout'>)</span>
<a name="line-244"></a> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>linearRA</span> <span class='hs-varid'>block_live</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>id</span> <span class='hs-varid'>instrs</span>
<a name="line-245"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>BasicBlock</span> <span class='hs-varid'>id</span> <span class='hs-varid'>instrs'</span> <span class='hs-conop'>:</span> <span class='hs-varid'>fixups</span>
<a name="line-246"></a>
<a name="line-247"></a>
<a name="line-248"></a><a name="initBlock"></a><span class='hs-comment'>-- | Load the freeregs and current reg assignment into the RegM state</span>
<a name="line-249"></a><span class='hs-comment'>-- for the basic block with this BlockId.</span>
<a name="line-250"></a><span class='hs-definition'>initBlock</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>BlockId</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>RegM</span> <span class='hs-conid'>()</span>
<a name="line-251"></a><span class='hs-definition'>initBlock</span> <span class='hs-varid'>id</span>
<a name="line-252"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-varid'>block_assig</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getBlockAssigR</span>
<a name="line-253"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupBlockEnv</span> <span class='hs-varid'>block_assig</span> <span class='hs-varid'>id</span> <span class='hs-keyword'>of</span>
<a name="line-254"></a> <span class='hs-comment'>-- no prior info about this block: assume everything is</span>
<a name="line-255"></a> <span class='hs-comment'>-- free and the assignment is empty.</span>
<a name="line-256"></a> <span class='hs-conid'>Nothing</span>
<a name="line-257"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span> <span class='hs-comment'>-- pprTrace "initFreeRegs" (text $ show initFreeRegs) (return ())</span>
<a name="line-258"></a>
<a name="line-259"></a> <span class='hs-varid'>setFreeRegsR</span> <span class='hs-varid'>initFreeRegs</span>
<a name="line-260"></a> <span class='hs-varid'>setAssigR</span> <span class='hs-varid'>emptyRegMap</span>
<a name="line-261"></a>
<a name="line-262"></a> <span class='hs-comment'>-- load info about register assignments leading into this block.</span>
<a name="line-263"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>freeregs</span><span class='hs-layout'>,</span> <span class='hs-varid'>assig</span><span class='hs-layout'>)</span>
<a name="line-264"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span> <span class='hs-varid'>setFreeRegsR</span> <span class='hs-varid'>freeregs</span>
<a name="line-265"></a> <span class='hs-varid'>setAssigR</span> <span class='hs-varid'>assig</span>
<a name="line-266"></a>
<a name="line-267"></a>
<a name="line-268"></a><a name="linearRA"></a><span class='hs-comment'>-- | Do allocation for a sequence of instructions.</span>
<a name="line-269"></a><span class='hs-definition'>linearRA</span>
<a name="line-270"></a> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>instr</span><span class='hs-layout'>,</span> <span class='hs-conid'>Instruction</span> <span class='hs-varid'>instr</span><span class='hs-layout'>)</span>
<a name="line-271"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>BlockMap</span> <span class='hs-conid'>RegSet</span> <span class='hs-comment'>-- ^ map of what vregs are live on entry to each block.</span>
<a name="line-272"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ accumulator for instructions already processed.</span>
<a name="line-273"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>NatBasicBlock</span> <span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ accumulator for blocks of fixup code.</span>
<a name="line-274"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockId</span> <span class='hs-comment'>-- ^ id of the current block, for debugging.</span>
<a name="line-275"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>LiveInstr</span> <span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ liveness annotated instructions in this block.</span>
<a name="line-276"></a>
<a name="line-277"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>RegM</span> <span class='hs-layout'>(</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- instructions after register allocation</span>
<a name="line-278"></a> <span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>NatBasicBlock</span> <span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- fresh blocks of fixup code.</span>
<a name="line-279"></a>
<a name="line-280"></a>
<a name="line-281"></a><span class='hs-definition'>linearRA</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>accInstr</span> <span class='hs-varid'>accFixup</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span>
<a name="line-282"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span>
<a name="line-283"></a> <span class='hs-layout'>(</span> <span class='hs-varid'>reverse</span> <span class='hs-varid'>accInstr</span> <span class='hs-comment'>-- instrs need to be returned in the correct order.</span>
<a name="line-284"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>accFixup</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- it doesn't matter what order the fixup blocks are returned in.</span>
<a name="line-285"></a>
<a name="line-286"></a>
<a name="line-287"></a><span class='hs-definition'>linearRA</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>accInstr</span> <span class='hs-varid'>accFixups</span> <span class='hs-varid'>id</span> <span class='hs-layout'>(</span><span class='hs-varid'>instr</span><span class='hs-conop'>:</span><span class='hs-varid'>instrs</span><span class='hs-layout'>)</span>
<a name="line-288"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-289"></a> <span class='hs-layout'>(</span><span class='hs-varid'>accInstr'</span><span class='hs-layout'>,</span> <span class='hs-varid'>new_fixups</span><span class='hs-layout'>)</span>
<a name="line-290"></a> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>raInsn</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>accInstr</span> <span class='hs-varid'>id</span> <span class='hs-varid'>instr</span>
<a name="line-291"></a>
<a name="line-292"></a> <span class='hs-varid'>linearRA</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>accInstr'</span> <span class='hs-layout'>(</span><span class='hs-varid'>new_fixups</span> <span class='hs-varop'>++</span> <span class='hs-varid'>accFixups</span><span class='hs-layout'>)</span> <span class='hs-varid'>id</span> <span class='hs-varid'>instrs</span>
<a name="line-293"></a>
<a name="line-294"></a>
<a name="line-295"></a><a name="raInsn"></a><span class='hs-comment'>-- | Do allocation for a single instruction.</span>
<a name="line-296"></a><span class='hs-definition'>raInsn</span>
<a name="line-297"></a> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Outputable</span> <span class='hs-varid'>instr</span><span class='hs-layout'>,</span> <span class='hs-conid'>Instruction</span> <span class='hs-varid'>instr</span><span class='hs-layout'>)</span>
<a name="line-298"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>BlockMap</span> <span class='hs-conid'>RegSet</span> <span class='hs-comment'>-- ^ map of what vregs are love on entry to each block.</span>
<a name="line-299"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ accumulator for instructions already processed.</span>
<a name="line-300"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BlockId</span> <span class='hs-comment'>-- ^ the id of the current block, for debugging</span>
<a name="line-301"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LiveInstr</span> <span class='hs-varid'>instr</span> <span class='hs-comment'>-- ^ the instr to have its regs allocated, with liveness info.</span>
<a name="line-302"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>RegM</span>
<a name="line-303"></a> <span class='hs-layout'>(</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- new instructions</span>
<a name="line-304"></a> <span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>NatBasicBlock</span> <span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- extra fixup blocks</span>
<a name="line-305"></a>
<a name="line-306"></a><span class='hs-definition'>raInsn</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>new_instrs</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-conid'>Instr</span> <span class='hs-varid'>ii</span> <span class='hs-conid'>Nothing</span><span class='hs-layout'>)</span>
<a name="line-307"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>takeDeltaInstr</span> <span class='hs-varid'>ii</span>
<a name="line-308"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-varid'>setDeltaR</span> <span class='hs-varid'>n</span>
<a name="line-309"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>new_instrs</span><span class='hs-layout'>,</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-310"></a>
<a name="line-311"></a><span class='hs-definition'>raInsn</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>new_instrs</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-conid'>Instr</span> <span class='hs-varid'>ii</span> <span class='hs-conid'>Nothing</span><span class='hs-layout'>)</span>
<a name="line-312"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>isMetaInstr</span> <span class='hs-varid'>ii</span>
<a name="line-313"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>new_instrs</span><span class='hs-layout'>,</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-314"></a>
<a name="line-315"></a>
<a name="line-316"></a><span class='hs-definition'>raInsn</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>new_instrs</span> <span class='hs-varid'>id</span> <span class='hs-layout'>(</span><span class='hs-conid'>Instr</span> <span class='hs-varid'>instr</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>live</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-317"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-318"></a> <span class='hs-varid'>assig</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getAssigR</span>
<a name="line-319"></a>
<a name="line-320"></a> <span class='hs-comment'>-- If we have a reg->reg move between virtual registers, where the</span>
<a name="line-321"></a> <span class='hs-comment'>-- src register is not live after this instruction, and the dst</span>
<a name="line-322"></a> <span class='hs-comment'>-- register does not already have an assignment,</span>
<a name="line-323"></a> <span class='hs-comment'>-- and the source register is assigned to a register, not to a spill slot,</span>
<a name="line-324"></a> <span class='hs-comment'>-- then we can eliminate the instruction.</span>
<a name="line-325"></a> <span class='hs-comment'>-- (we can't eliminitate it if the source register is on the stack, because</span>
<a name="line-326"></a> <span class='hs-comment'>-- we do not want to use one spill slot for different virtual registers)</span>
<a name="line-327"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>takeRegRegMoveInstr</span> <span class='hs-varid'>instr</span> <span class='hs-keyword'>of</span>
<a name="line-328"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>src</span><span class='hs-layout'>,</span><span class='hs-varid'>dst</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>src</span> <span class='hs-varop'>`elementOfUniqSet`</span> <span class='hs-layout'>(</span><span class='hs-varid'>liveDieRead</span> <span class='hs-varid'>live</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span>
<a name="line-329"></a> <span class='hs-varid'>isVirtualReg</span> <span class='hs-varid'>dst</span><span class='hs-layout'>,</span>
<a name="line-330"></a> <span class='hs-varid'>not</span> <span class='hs-layout'>(</span><span class='hs-varid'>dst</span> <span class='hs-varop'>`elemUFM`</span> <span class='hs-varid'>assig</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span>
<a name="line-331"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-conid'>InReg</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-layout'>(</span><span class='hs-varid'>lookupUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>src</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-332"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>src</span> <span class='hs-keyword'>of</span>
<a name="line-333"></a> <span class='hs-layout'>(</span><span class='hs-conid'>RegReal</span> <span class='hs-varid'>rr</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>setAssigR</span> <span class='hs-layout'>(</span><span class='hs-varid'>addToUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>dst</span> <span class='hs-layout'>(</span><span class='hs-conid'>InReg</span> <span class='hs-varid'>rr</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-334"></a> <span class='hs-comment'>-- if src is a fixed reg, then we just map dest to this</span>
<a name="line-335"></a> <span class='hs-comment'>-- reg in the assignment. src must be an allocatable reg,</span>
<a name="line-336"></a> <span class='hs-comment'>-- otherwise it wouldn't be in r_dying.</span>
<a name="line-337"></a> <span class='hs-sel'>_virt</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>src</span> <span class='hs-keyword'>of</span>
<a name="line-338"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>panic</span> <span class='hs-str'>"raInsn"</span>
<a name="line-339"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>loc</span> <span class='hs-keyglyph'>-></span>
<a name="line-340"></a> <span class='hs-varid'>setAssigR</span> <span class='hs-layout'>(</span><span class='hs-varid'>addToUFM</span> <span class='hs-layout'>(</span><span class='hs-varid'>delFromUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>src</span><span class='hs-layout'>)</span> <span class='hs-varid'>dst</span> <span class='hs-varid'>loc</span><span class='hs-layout'>)</span>
<a name="line-341"></a>
<a name="line-342"></a> <span class='hs-comment'>-- we have eliminated this instruction</span>
<a name="line-343"></a> <span class='hs-comment'>{-
<a name="line-344"></a> freeregs <- getFreeRegsR
<a name="line-345"></a> assig <- getAssigR
<a name="line-346"></a> pprTrace "raInsn" (text "ELIMINATED: " <> docToSDoc (pprInstr instr)
<a name="line-347"></a> $$ ppr r_dying <+> ppr w_dying $$ text (show freeregs) $$ ppr assig) $ do
<a name="line-348"></a> -}</span>
<a name="line-349"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>new_instrs</span><span class='hs-layout'>,</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-350"></a>
<a name="line-351"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>genRaInsn</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>new_instrs</span> <span class='hs-varid'>id</span> <span class='hs-varid'>instr</span>
<a name="line-352"></a> <span class='hs-layout'>(</span><span class='hs-varid'>uniqSetToList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>liveDieRead</span> <span class='hs-varid'>live</span><span class='hs-layout'>)</span>
<a name="line-353"></a> <span class='hs-layout'>(</span><span class='hs-varid'>uniqSetToList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>liveDieWrite</span> <span class='hs-varid'>live</span><span class='hs-layout'>)</span>
<a name="line-354"></a>
<a name="line-355"></a>
<a name="line-356"></a><span class='hs-definition'>raInsn</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>instr</span>
<a name="line-357"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pprPanic</span> <span class='hs-str'>"raInsn"</span> <span class='hs-layout'>(</span><span class='hs-varid'>text</span> <span class='hs-str'>"no match for:"</span> <span class='hs-varop'><></span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>instr</span><span class='hs-layout'>)</span>
<a name="line-358"></a>
<a name="line-359"></a>
<a name="line-360"></a>
<a name="line-361"></a>
<a name="line-362"></a><a name="genRaInsn"></a><span class='hs-definition'>genRaInsn</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>new_instrs</span> <span class='hs-varid'>block_id</span> <span class='hs-varid'>instr</span> <span class='hs-varid'>r_dying</span> <span class='hs-varid'>w_dying</span> <span class='hs-keyglyph'>=</span>
<a name="line-363"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>regUsageOfInstr</span> <span class='hs-varid'>instr</span> <span class='hs-keyword'>of</span> <span class='hs-layout'>{</span> <span class='hs-conid'>RU</span> <span class='hs-varid'>read</span> <span class='hs-varid'>written</span> <span class='hs-keyglyph'>-></span>
<a name="line-364"></a> <span class='hs-keyword'>do</span>
<a name="line-365"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>real_written</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>rr</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-conid'>RegReal</span> <span class='hs-varid'>rr</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>written</span> <span class='hs-keyglyph'>]</span>
<a name="line-366"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>virt_written</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>vr</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-conid'>RegVirtual</span> <span class='hs-varid'>vr</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>written</span> <span class='hs-keyglyph'>]</span>
<a name="line-367"></a>
<a name="line-368"></a> <span class='hs-comment'>-- we don't need to do anything with real registers that are</span>
<a name="line-369"></a> <span class='hs-comment'>-- only read by this instr. (the list is typically ~2 elements,</span>
<a name="line-370"></a> <span class='hs-comment'>-- so using nub isn't a problem).</span>
<a name="line-371"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>virt_read</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nub</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>vr</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-conid'>RegVirtual</span> <span class='hs-varid'>vr</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>read</span> <span class='hs-keyglyph'>]</span>
<a name="line-372"></a>
<a name="line-373"></a> <span class='hs-comment'>-- (a) save any temporaries which will be clobbered by this instruction</span>
<a name="line-374"></a> <span class='hs-varid'>clobber_saves</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>saveClobberedTemps</span> <span class='hs-varid'>real_written</span> <span class='hs-varid'>r_dying</span>
<a name="line-375"></a>
<a name="line-376"></a> <span class='hs-comment'>-- debugging</span>
<a name="line-377"></a><span class='hs-comment'>{- freeregs <- getFreeRegsR
<a name="line-378"></a> assig <- getAssigR
<a name="line-379"></a> pprTrace "genRaInsn"
<a name="line-380"></a> (ppr instr
<a name="line-381"></a> $$ text "r_dying = " <+> ppr r_dying
<a name="line-382"></a> $$ text "w_dying = " <+> ppr w_dying
<a name="line-383"></a> $$ text "virt_read = " <+> ppr virt_read
<a name="line-384"></a> $$ text "virt_written = " <+> ppr virt_written
<a name="line-385"></a> $$ text "freeregs = " <+> text (show freeregs)
<a name="line-386"></a> $$ text "assig = " <+> ppr assig)
<a name="line-387"></a> $ do
<a name="line-388"></a>-}</span>
<a name="line-389"></a>
<a name="line-390"></a> <span class='hs-comment'>-- (b), (c) allocate real regs for all regs read by this instruction.</span>
<a name="line-391"></a> <span class='hs-layout'>(</span><span class='hs-varid'>r_spills</span><span class='hs-layout'>,</span> <span class='hs-varid'>r_allocd</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span>
<a name="line-392"></a> <span class='hs-varid'>allocateRegsAndSpill</span> <span class='hs-conid'>True</span><span class='hs-comment'>{-reading-}</span> <span class='hs-varid'>virt_read</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>virt_read</span>
<a name="line-393"></a>
<a name="line-394"></a> <span class='hs-comment'>-- (d) Update block map for new destinations</span>
<a name="line-395"></a> <span class='hs-comment'>-- NB. do this before removing dead regs from the assignment, because</span>
<a name="line-396"></a> <span class='hs-comment'>-- these dead regs might in fact be live in the jump targets (they're</span>
<a name="line-397"></a> <span class='hs-comment'>-- only dead in the code that follows in the current basic block).</span>
<a name="line-398"></a> <span class='hs-layout'>(</span><span class='hs-varid'>fixup_blocks</span><span class='hs-layout'>,</span> <span class='hs-varid'>adjusted_instr</span><span class='hs-layout'>)</span>
<a name="line-399"></a> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>joinToTargets</span> <span class='hs-varid'>block_live</span> <span class='hs-varid'>block_id</span> <span class='hs-varid'>instr</span>
<a name="line-400"></a>
<a name="line-401"></a> <span class='hs-comment'>-- (e) Delete all register assignments for temps which are read</span>
<a name="line-402"></a> <span class='hs-comment'>-- (only) and die here. Update the free register list.</span>
<a name="line-403"></a> <span class='hs-varid'>releaseRegs</span> <span class='hs-varid'>r_dying</span>
<a name="line-404"></a>
<a name="line-405"></a> <span class='hs-comment'>-- (f) Mark regs which are clobbered as unallocatable</span>
<a name="line-406"></a> <span class='hs-varid'>clobberRegs</span> <span class='hs-varid'>real_written</span>
<a name="line-407"></a>
<a name="line-408"></a> <span class='hs-comment'>-- (g) Allocate registers for temporaries *written* (only)</span>
<a name="line-409"></a> <span class='hs-layout'>(</span><span class='hs-varid'>w_spills</span><span class='hs-layout'>,</span> <span class='hs-varid'>w_allocd</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span>
<a name="line-410"></a> <span class='hs-varid'>allocateRegsAndSpill</span> <span class='hs-conid'>False</span><span class='hs-comment'>{-writing-}</span> <span class='hs-varid'>virt_written</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>virt_written</span>
<a name="line-411"></a>
<a name="line-412"></a> <span class='hs-comment'>-- (h) Release registers for temps which are written here and not</span>
<a name="line-413"></a> <span class='hs-comment'>-- used again.</span>
<a name="line-414"></a> <span class='hs-varid'>releaseRegs</span> <span class='hs-varid'>w_dying</span>
<a name="line-415"></a>
<a name="line-416"></a> <span class='hs-keyword'>let</span>
<a name="line-417"></a> <span class='hs-comment'>-- (i) Patch the instruction</span>
<a name="line-418"></a> <span class='hs-varid'>patch_map</span>
<a name="line-419"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>listToUFM</span>
<a name="line-420"></a> <span class='hs-keyglyph'>[</span> <span class='hs-layout'>(</span><span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>RegReal</span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span>
<a name="line-421"></a> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>zip</span> <span class='hs-varid'>virt_read</span> <span class='hs-varid'>r_allocd</span>
<a name="line-422"></a> <span class='hs-varop'>++</span> <span class='hs-varid'>zip</span> <span class='hs-varid'>virt_written</span> <span class='hs-varid'>w_allocd</span> <span class='hs-keyglyph'>]</span>
<a name="line-423"></a>
<a name="line-424"></a> <span class='hs-varid'>patched_instr</span>
<a name="line-425"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>patchRegsOfInstr</span> <span class='hs-varid'>adjusted_instr</span> <span class='hs-varid'>patchLookup</span>
<a name="line-426"></a>
<a name="line-427"></a> <span class='hs-varid'>patchLookup</span> <span class='hs-varid'>x</span>
<a name="line-428"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupUFM</span> <span class='hs-varid'>patch_map</span> <span class='hs-varid'>x</span> <span class='hs-keyword'>of</span>
<a name="line-429"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>x</span>
<a name="line-430"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>y</span>
<a name="line-431"></a>
<a name="line-432"></a>
<a name="line-433"></a> <span class='hs-comment'>-- (j) free up stack slots for dead spilled regs</span>
<a name="line-434"></a> <span class='hs-comment'>-- TODO (can't be bothered right now)</span>
<a name="line-435"></a>
<a name="line-436"></a> <span class='hs-comment'>-- erase reg->reg moves where the source and destination are the same.</span>
<a name="line-437"></a> <span class='hs-comment'>-- If the src temp didn't die in this instr but happened to be allocated</span>
<a name="line-438"></a> <span class='hs-comment'>-- to the same real reg as the destination, then we can erase the move anyway.</span>
<a name="line-439"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>squashed_instr</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>takeRegRegMoveInstr</span> <span class='hs-varid'>patched_instr</span> <span class='hs-keyword'>of</span>
<a name="line-440"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>src</span><span class='hs-layout'>,</span> <span class='hs-varid'>dst</span><span class='hs-layout'>)</span>
<a name="line-441"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>src</span> <span class='hs-varop'>==</span> <span class='hs-varid'>dst</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>[]</span>
<a name="line-442"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>patched_instr</span><span class='hs-keyglyph'>]</span>
<a name="line-443"></a>
<a name="line-444"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>code</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>squashed_instr</span> <span class='hs-varop'>++</span> <span class='hs-varid'>w_spills</span> <span class='hs-varop'>++</span> <span class='hs-varid'>reverse</span> <span class='hs-varid'>r_spills</span>
<a name="line-445"></a> <span class='hs-varop'>++</span> <span class='hs-varid'>clobber_saves</span> <span class='hs-varop'>++</span> <span class='hs-varid'>new_instrs</span>
<a name="line-446"></a>
<a name="line-447"></a><span class='hs-comment'>-- pprTrace "patched-code" ((vcat $ map (docToSDoc . pprInstr) code)) $ do</span>
<a name="line-448"></a><span class='hs-comment'>-- pprTrace "pached-fixup" ((ppr fixup_blocks)) $ do</span>
<a name="line-449"></a>
<a name="line-450"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>code</span><span class='hs-layout'>,</span> <span class='hs-varid'>fixup_blocks</span><span class='hs-layout'>)</span>
<a name="line-451"></a>
<a name="line-452"></a> <span class='hs-layout'>}</span>
<a name="line-453"></a>
<a name="line-454"></a><span class='hs-comment'>-- -----------------------------------------------------------------------------</span>
<a name="line-455"></a><span class='hs-comment'>-- releaseRegs</span>
<a name="line-456"></a>
<a name="line-457"></a><a name="releaseRegs"></a><span class='hs-definition'>releaseRegs</span> <span class='hs-varid'>regs</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-458"></a> <span class='hs-varid'>assig</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getAssigR</span>
<a name="line-459"></a> <span class='hs-varid'>free</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getFreeRegsR</span>
<a name="line-460"></a> <span class='hs-varid'>loop</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>free</span> <span class='hs-varid'>regs</span>
<a name="line-461"></a> <span class='hs-keyword'>where</span>
<a name="line-462"></a> <span class='hs-varid'>loop</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>free</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>free</span> <span class='hs-varop'>`seq`</span> <span class='hs-conid'>False</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>undefined</span>
<a name="line-463"></a> <span class='hs-varid'>loop</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>free</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-varid'>setAssigR</span> <span class='hs-varid'>assig</span><span class='hs-layout'>;</span> <span class='hs-varid'>setFreeRegsR</span> <span class='hs-varid'>free</span><span class='hs-layout'>;</span> <span class='hs-varid'>return</span> <span class='hs-conid'>()</span>
<a name="line-464"></a> <span class='hs-varid'>loop</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>free</span> <span class='hs-layout'>(</span><span class='hs-conid'>RegReal</span> <span class='hs-varid'>rr</span> <span class='hs-conop'>:</span> <span class='hs-varid'>rs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>loop</span> <span class='hs-varid'>assig</span> <span class='hs-layout'>(</span><span class='hs-varid'>releaseReg</span> <span class='hs-varid'>rr</span> <span class='hs-varid'>free</span><span class='hs-layout'>)</span> <span class='hs-varid'>rs</span>
<a name="line-465"></a> <span class='hs-varid'>loop</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>free</span> <span class='hs-layout'>(</span><span class='hs-varid'>r</span><span class='hs-conop'>:</span><span class='hs-varid'>rs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-466"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>r</span> <span class='hs-keyword'>of</span>
<a name="line-467"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-conid'>InBoth</span> <span class='hs-varid'>real</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>loop</span> <span class='hs-layout'>(</span><span class='hs-varid'>delFromUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>releaseReg</span> <span class='hs-varid'>real</span> <span class='hs-varid'>free</span><span class='hs-layout'>)</span> <span class='hs-varid'>rs</span>
<a name="line-468"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-conid'>InReg</span> <span class='hs-varid'>real</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>loop</span> <span class='hs-layout'>(</span><span class='hs-varid'>delFromUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>releaseReg</span> <span class='hs-varid'>real</span> <span class='hs-varid'>free</span><span class='hs-layout'>)</span> <span class='hs-varid'>rs</span>
<a name="line-469"></a> <span class='hs-sel'>_other</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>loop</span> <span class='hs-layout'>(</span><span class='hs-varid'>delFromUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span> <span class='hs-varid'>free</span> <span class='hs-varid'>rs</span>
<a name="line-470"></a>
<a name="line-471"></a>
<a name="line-472"></a><span class='hs-comment'>-- -----------------------------------------------------------------------------</span>
<a name="line-473"></a><span class='hs-comment'>-- Clobber real registers</span>
<a name="line-474"></a>
<a name="line-475"></a><span class='hs-comment'>-- For each temp in a register that is going to be clobbered:</span>
<a name="line-476"></a><span class='hs-comment'>-- - if the temp dies after this instruction, do nothing</span>
<a name="line-477"></a><span class='hs-comment'>-- - otherwise, put it somewhere safe (another reg if possible,</span>
<a name="line-478"></a><span class='hs-comment'>-- otherwise spill and record InBoth in the assignment).</span>
<a name="line-479"></a><span class='hs-comment'>-- - for allocateRegs on the temps *read*,</span>
<a name="line-480"></a><span class='hs-comment'>-- - clobbered regs are allocatable.</span>
<a name="line-481"></a><span class='hs-comment'>--</span>
<a name="line-482"></a><span class='hs-comment'>-- for allocateRegs on the temps *written*, </span>
<a name="line-483"></a><span class='hs-comment'>-- - clobbered regs are not allocatable.</span>
<a name="line-484"></a><span class='hs-comment'>--</span>
<a name="line-485"></a><span class='hs-comment'>-- TODO: instead of spilling, try to copy clobbered</span>
<a name="line-486"></a><span class='hs-comment'>-- temps to another register if possible.</span>
<a name="line-487"></a><span class='hs-comment'>--</span>
<a name="line-488"></a>
<a name="line-489"></a>
<a name="line-490"></a><a name="saveClobberedTemps"></a><span class='hs-definition'>saveClobberedTemps</span>
<a name="line-491"></a> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Instruction</span> <span class='hs-varid'>instr</span>
<a name="line-492"></a> <span class='hs-keyglyph'>=></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>RealReg</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- real registers clobbered by this instruction</span>
<a name="line-493"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Reg</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- registers which are no longer live after this insn</span>
<a name="line-494"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>RegM</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- return: instructions to spill any temps that will</span>
<a name="line-495"></a> <span class='hs-comment'>-- be clobbered.</span>
<a name="line-496"></a>
<a name="line-497"></a><span class='hs-definition'>saveClobberedTemps</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>_</span>
<a name="line-498"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-conid'>[]</span>
<a name="line-499"></a>
<a name="line-500"></a><span class='hs-definition'>saveClobberedTemps</span> <span class='hs-varid'>clobbered</span> <span class='hs-varid'>dying</span>
<a name="line-501"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-502"></a> <span class='hs-varid'>assig</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getAssigR</span>
<a name="line-503"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>to_spill</span>
<a name="line-504"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span> <span class='hs-layout'>(</span><span class='hs-varid'>temp</span><span class='hs-layout'>,</span><span class='hs-varid'>reg</span><span class='hs-layout'>)</span>
<a name="line-505"></a> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>temp</span><span class='hs-layout'>,</span> <span class='hs-conid'>InReg</span> <span class='hs-varid'>reg</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ufmToList</span> <span class='hs-varid'>assig</span>
<a name="line-506"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>any</span> <span class='hs-layout'>(</span><span class='hs-varid'>realRegsAlias</span> <span class='hs-varid'>reg</span><span class='hs-layout'>)</span> <span class='hs-varid'>clobbered</span>
<a name="line-507"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>temp</span> <span class='hs-varop'>`notElem`</span> <span class='hs-varid'>map</span> <span class='hs-varid'>getUnique</span> <span class='hs-varid'>dying</span> <span class='hs-keyglyph'>]</span>
<a name="line-508"></a>
<a name="line-509"></a> <span class='hs-layout'>(</span><span class='hs-varid'>instrs</span><span class='hs-layout'>,</span><span class='hs-varid'>assig'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>clobber</span> <span class='hs-varid'>assig</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>to_spill</span>
<a name="line-510"></a> <span class='hs-varid'>setAssigR</span> <span class='hs-varid'>assig'</span>
<a name="line-511"></a> <span class='hs-varid'>return</span> <span class='hs-varid'>instrs</span>
<a name="line-512"></a>
<a name="line-513"></a> <span class='hs-keyword'>where</span>
<a name="line-514"></a> <span class='hs-varid'>clobber</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>instrs</span> <span class='hs-conid'>[]</span>
<a name="line-515"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>instrs</span><span class='hs-layout'>,</span> <span class='hs-varid'>assig</span><span class='hs-layout'>)</span>
<a name="line-516"></a>
<a name="line-517"></a> <span class='hs-varid'>clobber</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>instrs</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>temp</span><span class='hs-layout'>,</span> <span class='hs-varid'>reg</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>rest</span><span class='hs-layout'>)</span>
<a name="line-518"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-519"></a> <span class='hs-layout'>(</span><span class='hs-varid'>spill</span><span class='hs-layout'>,</span> <span class='hs-varid'>slot</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>spillR</span> <span class='hs-layout'>(</span><span class='hs-conid'>RegReal</span> <span class='hs-varid'>reg</span><span class='hs-layout'>)</span> <span class='hs-varid'>temp</span>
<a name="line-520"></a>
<a name="line-521"></a> <span class='hs-comment'>-- record why this reg was spilled for profiling</span>
<a name="line-522"></a> <span class='hs-varid'>recordSpill</span> <span class='hs-layout'>(</span><span class='hs-conid'>SpillClobber</span> <span class='hs-varid'>temp</span><span class='hs-layout'>)</span>
<a name="line-523"></a>
<a name="line-524"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>new_assign</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>addToUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>temp</span> <span class='hs-layout'>(</span><span class='hs-conid'>InBoth</span> <span class='hs-varid'>reg</span> <span class='hs-varid'>slot</span><span class='hs-layout'>)</span>
<a name="line-525"></a>
<a name="line-526"></a> <span class='hs-varid'>clobber</span> <span class='hs-varid'>new_assign</span> <span class='hs-layout'>(</span><span class='hs-varid'>spill</span> <span class='hs-conop'>:</span> <span class='hs-varid'>instrs</span><span class='hs-layout'>)</span> <span class='hs-varid'>rest</span>
<a name="line-527"></a>
<a name="line-528"></a>
<a name="line-529"></a>
<a name="line-530"></a><a name="clobberRegs"></a><span class='hs-comment'>-- | Mark all these regal regs as allocated,</span>
<a name="line-531"></a><span class='hs-comment'>-- and kick out their vreg assignments.</span>
<a name="line-532"></a><span class='hs-comment'>--</span>
<a name="line-533"></a><span class='hs-definition'>clobberRegs</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>RealReg</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>RegM</span> <span class='hs-conid'>()</span>
<a name="line-534"></a><span class='hs-definition'>clobberRegs</span> <span class='hs-conid'>[]</span>
<a name="line-535"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-conid'>()</span>
<a name="line-536"></a>
<a name="line-537"></a><span class='hs-definition'>clobberRegs</span> <span class='hs-varid'>clobbered</span>
<a name="line-538"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-539"></a> <span class='hs-varid'>freeregs</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getFreeRegsR</span>
<a name="line-540"></a> <span class='hs-varid'>setFreeRegsR</span> <span class='hs-varop'>$!</span> <span class='hs-varid'>foldr</span> <span class='hs-varid'>allocateReg</span> <span class='hs-varid'>freeregs</span> <span class='hs-varid'>clobbered</span>
<a name="line-541"></a>
<a name="line-542"></a> <span class='hs-varid'>assig</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getAssigR</span>
<a name="line-543"></a> <span class='hs-varid'>setAssigR</span> <span class='hs-varop'>$!</span> <span class='hs-varid'>clobber</span> <span class='hs-varid'>assig</span> <span class='hs-layout'>(</span><span class='hs-varid'>ufmToList</span> <span class='hs-varid'>assig</span><span class='hs-layout'>)</span>
<a name="line-544"></a>
<a name="line-545"></a> <span class='hs-keyword'>where</span>
<a name="line-546"></a> <span class='hs-comment'>-- if the temp was InReg and clobbered, then we will have</span>
<a name="line-547"></a> <span class='hs-comment'>-- saved it in saveClobberedTemps above. So the only case</span>
<a name="line-548"></a> <span class='hs-comment'>-- we have to worry about here is InBoth. Note that this</span>
<a name="line-549"></a> <span class='hs-comment'>-- also catches temps which were loaded up during allocation</span>
<a name="line-550"></a> <span class='hs-comment'>-- of read registers, not just those saved in saveClobberedTemps.</span>
<a name="line-551"></a>
<a name="line-552"></a> <span class='hs-varid'>clobber</span> <span class='hs-varid'>assig</span> <span class='hs-conid'>[]</span>
<a name="line-553"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>assig</span>
<a name="line-554"></a>
<a name="line-555"></a> <span class='hs-varid'>clobber</span> <span class='hs-varid'>assig</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>temp</span><span class='hs-layout'>,</span> <span class='hs-conid'>InBoth</span> <span class='hs-varid'>reg</span> <span class='hs-varid'>slot</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>rest</span><span class='hs-layout'>)</span>
<a name="line-556"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>any</span> <span class='hs-layout'>(</span><span class='hs-varid'>realRegsAlias</span> <span class='hs-varid'>reg</span><span class='hs-layout'>)</span> <span class='hs-varid'>clobbered</span>
<a name="line-557"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>clobber</span> <span class='hs-layout'>(</span><span class='hs-varid'>addToUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>temp</span> <span class='hs-layout'>(</span><span class='hs-conid'>InMem</span> <span class='hs-varid'>slot</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>rest</span>
<a name="line-558"></a>
<a name="line-559"></a> <span class='hs-varid'>clobber</span> <span class='hs-varid'>assig</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>rest</span><span class='hs-layout'>)</span>
<a name="line-560"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>clobber</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>rest</span>
<a name="line-561"></a>
<a name="line-562"></a><span class='hs-comment'>-- -----------------------------------------------------------------------------</span>
<a name="line-563"></a><span class='hs-comment'>-- allocateRegsAndSpill</span>
<a name="line-564"></a>
<a name="line-565"></a><span class='hs-comment'>-- This function does several things:</span>
<a name="line-566"></a><span class='hs-comment'>-- For each temporary referred to by this instruction,</span>
<a name="line-567"></a><span class='hs-comment'>-- we allocate a real register (spilling another temporary if necessary).</span>
<a name="line-568"></a><span class='hs-comment'>-- We load the temporary up from memory if necessary.</span>
<a name="line-569"></a><span class='hs-comment'>-- We also update the register assignment in the process, and</span>
<a name="line-570"></a><span class='hs-comment'>-- the list of free registers and free stack slots.</span>
<a name="line-571"></a>
<a name="line-572"></a><a name="allocateRegsAndSpill"></a><span class='hs-definition'>allocateRegsAndSpill</span>
<a name="line-573"></a> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Instruction</span> <span class='hs-varid'>instr</span>
<a name="line-574"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Bool</span> <span class='hs-comment'>-- True <=> reading (load up spilled regs)</span>
<a name="line-575"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>VirtualReg</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- don't push these out</span>
<a name="line-576"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- spill insns</span>
<a name="line-577"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>RealReg</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- real registers allocated (accum.)</span>
<a name="line-578"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>VirtualReg</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- temps to allocate</span>
<a name="line-579"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>RegM</span> <span class='hs-layout'>(</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span>
<a name="line-580"></a> <span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>RealReg</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span>
<a name="line-581"></a>
<a name="line-582"></a><span class='hs-definition'>allocateRegsAndSpill</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>spills</span> <span class='hs-varid'>alloc</span> <span class='hs-conid'>[]</span>
<a name="line-583"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>spills</span><span class='hs-layout'>,</span> <span class='hs-varid'>reverse</span> <span class='hs-varid'>alloc</span><span class='hs-layout'>)</span>
<a name="line-584"></a>
<a name="line-585"></a><span class='hs-definition'>allocateRegsAndSpill</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>keep</span> <span class='hs-varid'>spills</span> <span class='hs-varid'>alloc</span> <span class='hs-layout'>(</span><span class='hs-varid'>r</span><span class='hs-conop'>:</span><span class='hs-varid'>rs</span><span class='hs-layout'>)</span>
<a name="line-586"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-varid'>assig</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getAssigR</span>
<a name="line-587"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>r</span> <span class='hs-keyword'>of</span>
<a name="line-588"></a> <span class='hs-comment'>-- case (1a): already in a register</span>
<a name="line-589"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-conid'>InReg</span> <span class='hs-varid'>my_reg</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span>
<a name="line-590"></a> <span class='hs-varid'>allocateRegsAndSpill</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>keep</span> <span class='hs-varid'>spills</span> <span class='hs-layout'>(</span><span class='hs-varid'>my_reg</span><span class='hs-conop'>:</span><span class='hs-varid'>alloc</span><span class='hs-layout'>)</span> <span class='hs-varid'>rs</span>
<a name="line-591"></a>
<a name="line-592"></a> <span class='hs-comment'>-- case (1b): already in a register (and memory)</span>
<a name="line-593"></a> <span class='hs-comment'>-- NB1. if we're writing this register, update its assignemnt to be</span>
<a name="line-594"></a> <span class='hs-comment'>-- InReg, because the memory value is no longer valid.</span>
<a name="line-595"></a> <span class='hs-comment'>-- NB2. This is why we must process written registers here, even if they</span>
<a name="line-596"></a> <span class='hs-comment'>-- are also read by the same instruction.</span>
<a name="line-597"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-conid'>InBoth</span> <span class='hs-varid'>my_reg</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span>
<a name="line-598"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span> <span class='hs-varid'>when</span> <span class='hs-layout'>(</span><span class='hs-varid'>not</span> <span class='hs-varid'>reading</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>setAssigR</span> <span class='hs-layout'>(</span><span class='hs-varid'>addToUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>r</span> <span class='hs-layout'>(</span><span class='hs-conid'>InReg</span> <span class='hs-varid'>my_reg</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-599"></a> <span class='hs-varid'>allocateRegsAndSpill</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>keep</span> <span class='hs-varid'>spills</span> <span class='hs-layout'>(</span><span class='hs-varid'>my_reg</span><span class='hs-conop'>:</span><span class='hs-varid'>alloc</span><span class='hs-layout'>)</span> <span class='hs-varid'>rs</span>
<a name="line-600"></a>
<a name="line-601"></a> <span class='hs-comment'>-- Not already in a register, so we need to find a free one...</span>
<a name="line-602"></a> <span class='hs-varid'>loc</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>allocRegsAndSpill_spill</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>keep</span> <span class='hs-varid'>spills</span> <span class='hs-varid'>alloc</span> <span class='hs-varid'>r</span> <span class='hs-varid'>rs</span> <span class='hs-varid'>loc</span> <span class='hs-varid'>assig</span>
<a name="line-603"></a>
<a name="line-604"></a>
<a name="line-605"></a><a name="allocRegsAndSpill_spill"></a><span class='hs-definition'>allocRegsAndSpill_spill</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>keep</span> <span class='hs-varid'>spills</span> <span class='hs-varid'>alloc</span> <span class='hs-varid'>r</span> <span class='hs-varid'>rs</span> <span class='hs-varid'>loc</span> <span class='hs-varid'>assig</span>
<a name="line-606"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-607"></a> <span class='hs-varid'>freeRegs</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getFreeRegsR</span>
<a name="line-608"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>freeRegs_thisClass</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getFreeRegs</span> <span class='hs-layout'>(</span><span class='hs-varid'>classOfVirtualReg</span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span> <span class='hs-varid'>freeRegs</span>
<a name="line-609"></a>
<a name="line-610"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>freeRegs_thisClass</span> <span class='hs-keyword'>of</span>
<a name="line-611"></a>
<a name="line-612"></a> <span class='hs-comment'>-- case (2): we have a free register</span>
<a name="line-613"></a> <span class='hs-layout'>(</span><span class='hs-varid'>my_reg</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span>
<a name="line-614"></a> <span class='hs-keyword'>do</span> <span class='hs-varid'>spills'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>loadTemp</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>r</span> <span class='hs-varid'>loc</span> <span class='hs-varid'>my_reg</span> <span class='hs-varid'>spills</span>
<a name="line-615"></a>
<a name="line-616"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>new_loc</span>
<a name="line-617"></a> <span class='hs-comment'>-- if the tmp was in a slot, then now its in a reg as well</span>
<a name="line-618"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-conid'>InMem</span> <span class='hs-varid'>slot</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>loc</span>
<a name="line-619"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>reading</span>
<a name="line-620"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>InBoth</span> <span class='hs-varid'>my_reg</span> <span class='hs-varid'>slot</span>
<a name="line-621"></a>
<a name="line-622"></a> <span class='hs-comment'>-- tmp has been loaded into a reg</span>
<a name="line-623"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span>
<a name="line-624"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>InReg</span> <span class='hs-varid'>my_reg</span>
<a name="line-625"></a>
<a name="line-626"></a> <span class='hs-varid'>setAssigR</span> <span class='hs-layout'>(</span><span class='hs-varid'>addToUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>r</span> <span class='hs-varop'>$!</span> <span class='hs-varid'>new_loc</span><span class='hs-layout'>)</span>
<a name="line-627"></a> <span class='hs-varid'>setFreeRegsR</span> <span class='hs-varop'>$</span> <span class='hs-varid'>allocateReg</span> <span class='hs-varid'>my_reg</span> <span class='hs-varid'>freeRegs</span>
<a name="line-628"></a>
<a name="line-629"></a> <span class='hs-varid'>allocateRegsAndSpill</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>keep</span> <span class='hs-varid'>spills'</span> <span class='hs-layout'>(</span><span class='hs-varid'>my_reg</span> <span class='hs-conop'>:</span> <span class='hs-varid'>alloc</span><span class='hs-layout'>)</span> <span class='hs-varid'>rs</span>
<a name="line-630"></a>
<a name="line-631"></a>
<a name="line-632"></a> <span class='hs-comment'>-- case (3): we need to push something out to free up a register</span>
<a name="line-633"></a> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span>
<a name="line-634"></a> <span class='hs-keyword'>do</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>keep'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>map</span> <span class='hs-varid'>getUnique</span> <span class='hs-varid'>keep</span>
<a name="line-635"></a>
<a name="line-636"></a> <span class='hs-comment'>-- the vregs we could kick out that are already in a slot</span>
<a name="line-637"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>candidates_inBoth</span>
<a name="line-638"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span> <span class='hs-layout'>(</span><span class='hs-varid'>temp</span><span class='hs-layout'>,</span> <span class='hs-varid'>reg</span><span class='hs-layout'>,</span> <span class='hs-varid'>mem</span><span class='hs-layout'>)</span>
<a name="line-639"></a> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>temp</span><span class='hs-layout'>,</span> <span class='hs-conid'>InBoth</span> <span class='hs-varid'>reg</span> <span class='hs-varid'>mem</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ufmToList</span> <span class='hs-varid'>assig</span>
<a name="line-640"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>temp</span> <span class='hs-varop'>`notElem`</span> <span class='hs-varid'>keep'</span>
<a name="line-641"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>targetClassOfRealReg</span> <span class='hs-varid'>reg</span> <span class='hs-varop'>==</span> <span class='hs-varid'>classOfVirtualReg</span> <span class='hs-varid'>r</span> <span class='hs-keyglyph'>]</span>
<a name="line-642"></a>
<a name="line-643"></a> <span class='hs-comment'>-- the vregs we could kick out that are only in a reg</span>
<a name="line-644"></a> <span class='hs-comment'>-- this would require writing the reg to a new slot before using it.</span>
<a name="line-645"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>candidates_inReg</span>
<a name="line-646"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span> <span class='hs-layout'>(</span><span class='hs-varid'>temp</span><span class='hs-layout'>,</span> <span class='hs-varid'>reg</span><span class='hs-layout'>)</span>
<a name="line-647"></a> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>temp</span><span class='hs-layout'>,</span> <span class='hs-conid'>InReg</span> <span class='hs-varid'>reg</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ufmToList</span> <span class='hs-varid'>assig</span>
<a name="line-648"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>temp</span> <span class='hs-varop'>`notElem`</span> <span class='hs-varid'>keep'</span>
<a name="line-649"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>targetClassOfRealReg</span> <span class='hs-varid'>reg</span> <span class='hs-varop'>==</span> <span class='hs-varid'>classOfVirtualReg</span> <span class='hs-varid'>r</span> <span class='hs-keyglyph'>]</span>
<a name="line-650"></a>
<a name="line-651"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>result</span>
<a name="line-652"></a>
<a name="line-653"></a> <span class='hs-comment'>-- we have a temporary that is in both register and mem,</span>
<a name="line-654"></a> <span class='hs-comment'>-- just free up its register for use.</span>
<a name="line-655"></a> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>temp</span><span class='hs-layout'>,</span> <span class='hs-varid'>my_reg</span><span class='hs-layout'>,</span> <span class='hs-varid'>slot</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>candidates_inBoth</span>
<a name="line-656"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-varid'>spills'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>loadTemp</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>r</span> <span class='hs-varid'>loc</span> <span class='hs-varid'>my_reg</span> <span class='hs-varid'>spills</span>
<a name="line-657"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>assig1</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>addToUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>temp</span> <span class='hs-layout'>(</span><span class='hs-conid'>InMem</span> <span class='hs-varid'>slot</span><span class='hs-layout'>)</span>
<a name="line-658"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>assig2</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>addToUFM</span> <span class='hs-varid'>assig1</span> <span class='hs-varid'>r</span> <span class='hs-layout'>(</span><span class='hs-conid'>InReg</span> <span class='hs-varid'>my_reg</span><span class='hs-layout'>)</span>
<a name="line-659"></a>
<a name="line-660"></a> <span class='hs-varid'>setAssigR</span> <span class='hs-varid'>assig2</span>
<a name="line-661"></a> <span class='hs-varid'>allocateRegsAndSpill</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>keep</span> <span class='hs-varid'>spills'</span> <span class='hs-layout'>(</span><span class='hs-varid'>my_reg</span><span class='hs-conop'>:</span><span class='hs-varid'>alloc</span><span class='hs-layout'>)</span> <span class='hs-varid'>rs</span>
<a name="line-662"></a>
<a name="line-663"></a> <span class='hs-comment'>-- otherwise, we need to spill a temporary that currently</span>
<a name="line-664"></a> <span class='hs-comment'>-- resides in a register.</span>
<a name="line-665"></a> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>temp_to_push_out</span><span class='hs-layout'>,</span> <span class='hs-layout'>(</span><span class='hs-varid'>my_reg</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>RealReg</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span>
<a name="line-666"></a> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>candidates_inReg</span>
<a name="line-667"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-668"></a> <span class='hs-layout'>(</span><span class='hs-varid'>spill_insn</span><span class='hs-layout'>,</span> <span class='hs-varid'>slot</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>spillR</span> <span class='hs-layout'>(</span><span class='hs-conid'>RegReal</span> <span class='hs-varid'>my_reg</span><span class='hs-layout'>)</span> <span class='hs-varid'>temp_to_push_out</span>
<a name="line-669"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>spill_store</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-keyword'>if</span> <span class='hs-varid'>reading</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>id</span> <span class='hs-keyword'>else</span> <span class='hs-varid'>reverse</span><span class='hs-layout'>)</span>
<a name="line-670"></a> <span class='hs-keyglyph'>[</span> <span class='hs-comment'>-- COMMENT (fsLit "spill alloc") </span>
<a name="line-671"></a> <span class='hs-varid'>spill_insn</span> <span class='hs-keyglyph'>]</span>
<a name="line-672"></a>
<a name="line-673"></a> <span class='hs-comment'>-- record that this temp was spilled</span>
<a name="line-674"></a> <span class='hs-varid'>recordSpill</span> <span class='hs-layout'>(</span><span class='hs-conid'>SpillAlloc</span> <span class='hs-varid'>temp_to_push_out</span><span class='hs-layout'>)</span>
<a name="line-675"></a>
<a name="line-676"></a> <span class='hs-comment'>-- update the register assignment</span>
<a name="line-677"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>assig1</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>addToUFM</span> <span class='hs-varid'>assig</span> <span class='hs-varid'>temp_to_push_out</span> <span class='hs-layout'>(</span><span class='hs-conid'>InMem</span> <span class='hs-varid'>slot</span><span class='hs-layout'>)</span>
<a name="line-678"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>assig2</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>addToUFM</span> <span class='hs-varid'>assig1</span> <span class='hs-varid'>r</span> <span class='hs-layout'>(</span><span class='hs-conid'>InReg</span> <span class='hs-varid'>my_reg</span><span class='hs-layout'>)</span>
<a name="line-679"></a> <span class='hs-varid'>setAssigR</span> <span class='hs-varid'>assig2</span>
<a name="line-680"></a>
<a name="line-681"></a> <span class='hs-comment'>-- if need be, load up a spilled temp into the reg we've just freed up.</span>
<a name="line-682"></a> <span class='hs-varid'>spills'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>loadTemp</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>r</span> <span class='hs-varid'>loc</span> <span class='hs-varid'>my_reg</span> <span class='hs-varid'>spills</span>
<a name="line-683"></a>
<a name="line-684"></a> <span class='hs-varid'>allocateRegsAndSpill</span> <span class='hs-varid'>reading</span> <span class='hs-varid'>keep</span>
<a name="line-685"></a> <span class='hs-layout'>(</span><span class='hs-varid'>spill_store</span> <span class='hs-varop'>++</span> <span class='hs-varid'>spills'</span><span class='hs-layout'>)</span>
<a name="line-686"></a> <span class='hs-layout'>(</span><span class='hs-varid'>my_reg</span><span class='hs-conop'>:</span><span class='hs-varid'>alloc</span><span class='hs-layout'>)</span> <span class='hs-varid'>rs</span>
<a name="line-687"></a>
<a name="line-688"></a>
<a name="line-689"></a> <span class='hs-comment'>-- there wasn't anything to spill, so we're screwed.</span>
<a name="line-690"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span>
<a name="line-691"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pprPanic</span> <span class='hs-layout'>(</span><span class='hs-str'>"RegAllocLinear.allocRegsAndSpill: no spill candidates\n"</span><span class='hs-layout'>)</span>
<a name="line-692"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>vcat</span>
<a name="line-693"></a> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-str'>"allocating vreg: "</span> <span class='hs-varop'><></span> <span class='hs-varid'>text</span> <span class='hs-layout'>(</span><span class='hs-varid'>show</span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span>
<a name="line-694"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>text</span> <span class='hs-str'>"assignment: "</span> <span class='hs-varop'><></span> <span class='hs-varid'>text</span> <span class='hs-layout'>(</span><span class='hs-varid'>show</span> <span class='hs-varop'>$</span> <span class='hs-varid'>ufmToList</span> <span class='hs-varid'>assig</span><span class='hs-layout'>)</span>
<a name="line-695"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>text</span> <span class='hs-str'>"freeRegs: "</span> <span class='hs-varop'><></span> <span class='hs-varid'>text</span> <span class='hs-layout'>(</span><span class='hs-varid'>show</span> <span class='hs-varid'>freeRegs</span><span class='hs-layout'>)</span>
<a name="line-696"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>text</span> <span class='hs-str'>"initFreeRegs: "</span> <span class='hs-varop'><></span> <span class='hs-varid'>text</span> <span class='hs-layout'>(</span><span class='hs-varid'>show</span> <span class='hs-varid'>initFreeRegs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>]</span>
<a name="line-697"></a>
<a name="line-698"></a> <span class='hs-varid'>result</span>
<a name="line-699"></a>
<a name="line-700"></a>
<a name="line-701"></a><a name="loadTemp"></a><span class='hs-comment'>-- | Load up a spilled temporary if we need to.</span>
<a name="line-702"></a><span class='hs-definition'>loadTemp</span>
<a name="line-703"></a> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Instruction</span> <span class='hs-varid'>instr</span>
<a name="line-704"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Bool</span>
<a name="line-705"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>VirtualReg</span> <span class='hs-comment'>-- the temp being loaded</span>
<a name="line-706"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>Loc</span> <span class='hs-comment'>-- the current location of this temp</span>
<a name="line-707"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>RealReg</span> <span class='hs-comment'>-- the hreg to load the temp into</span>
<a name="line-708"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span>
<a name="line-709"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>RegM</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>instr</span><span class='hs-keyglyph'>]</span>
<a name="line-710"></a>
<a name="line-711"></a><span class='hs-definition'>loadTemp</span> <span class='hs-conid'>True</span> <span class='hs-varid'>vreg</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-conid'>InMem</span> <span class='hs-varid'>slot</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>hreg</span> <span class='hs-varid'>spills</span>
<a name="line-712"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-713"></a> <span class='hs-varid'>insn</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>loadR</span> <span class='hs-layout'>(</span><span class='hs-conid'>RegReal</span> <span class='hs-varid'>hreg</span><span class='hs-layout'>)</span> <span class='hs-varid'>slot</span>
<a name="line-714"></a> <span class='hs-varid'>recordSpill</span> <span class='hs-layout'>(</span><span class='hs-conid'>SpillLoad</span> <span class='hs-varop'>$</span> <span class='hs-varid'>getUnique</span> <span class='hs-varid'>vreg</span><span class='hs-layout'>)</span>
<a name="line-715"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-comment'>{- COMMENT (fsLit "spill load") : -}</span> <span class='hs-varid'>insn</span> <span class='hs-conop'>:</span> <span class='hs-varid'>spills</span>
<a name="line-716"></a>
<a name="line-717"></a><span class='hs-definition'>loadTemp</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>spills</span> <span class='hs-keyglyph'>=</span>
<a name="line-718"></a> <span class='hs-varid'>return</span> <span class='hs-varid'>spills</span>
<a name="line-719"></a>
</pre></body>
</html>
