31:Tb8a,md`[Register allocation](https://en.wikipedia.org/wiki/Register_allocation) is the process of assigning variables in a computer program to a small number of physical memory locations on the CPU, called *registers*. The limited number of registers means that the potentially large number of variables may contend for them. The basic principle is that any time an instruction uses two or more variables at the same time—for example, \`a = b + c\` requires three registers, two from which to read inputs and one in which to write the result—we require a separate register for each variable. (Actually there's a bit more to it and what we care about is not so much the inputs and outputs of single instructions but instead the sets of variables which must coexist in memory at each point during execution of the program. The [notes below](#references) walk through the process carefully.) If we denote the register to which we assign a variable by color, then we require that any two variables used at the same time have a different color. Thus we can illustrate the problem as a graph in which each vertex represents a variable. Every time two (or more) variables coexist in memory, we draw all undirected edges between them. This is called a *register interference graph*. Once we've drawn the register interference graph, successful allocation of ${tex`k`} registers corresponds to a a coloring of the graph with k or fewer colors such that no two adjacent vertices share the same coloring. This is just the [k-coloring](https://en.wikipedia.org/wiki/Graph_coloring) problem! The k-coloring problem is [NP-hard](https://en.wikipedia.org/wiki/NP-hardness) so that an exact solution may be very expensive. This notebook steps through a useful approximate algorithm called Chaitin's algorithm. The algorithm works as follows. We start by selecting a vertex with fewer than ${tex`k`} neighbors since we know we'll *always* be able to select a color for it. We don't select a color yet but instead remove the vertex and its edges and push the vertex onto a stack for later. We then repeat, always selecting a vertex we know we'll be able to color and removing it from the remaining graph until no vertices remain. Once we're done, we pop vertices off of the stack and select available colors for them, one by one. This process doesn't always work—though that doesn't necessarily mean a k-coloring doesn't *exist*. If no nodes have degree less than ${tex`k`}, then we have no choice but to *spill* a node, writing it to non-register memory and reading it later. This notebook illustrates the basic k-coloring problem with spillage. It doesn't make good heuristic choices about the order in which vertices are selected and/or spilled, and the code is written to facilitate explanation, so please don't expect too much from it! A practical solution to register allocation requires going a bit further than this toy example, but this was a fun start!`32:T132b,function* chaitinAlgorithm(graph, k) { const numVertices = graph.vertices.length; const edgeList = graph.edgeList(); let hasSpillage = false; let state = { graph: graph.clone(), stack: new Stack() }; const g = state.graph; const stack = state.stack; function step(label, mut) { mut && mut(state); return { label, graph: g.clone(), stack: stack.clone() }; } yield step( `The Chaitin-Briggs algorithm begins by iteratively removing vertices with degree less than k (= ${k}) since they have less than k neighbors and thus, by virtue of definition, can always be be k-colored. For each found vertex, we push it onto a stack and temporarily remove all edges emanating from it.` ); var vertList = range(numVertices); let iter = 0; var i; // Iterate until we've pushed all vertices onto the stack while (vertList.length && ++iter < 1000) { // Look for a remaining vertex with degree < k for (i = 0; i < vertList.length; i++) { const v = vertList[i]; // Compute the degree excluding inactive edges const degree = g.degree(v, e => !g.getEdgeProp(e, 'inactive')); if (degree < k) { { if (stack.length) stack.setProp(stack.length - 1, 'focused', false); g.setVertexProp(v, 'focused', true); yield step( `Vertex ${v} has degree ${degree}, which is less than k = ${k}.` ); } state.stack.push(v); vertList.splice(i, 1); { stack.setProp(stack.length - 1, 'focused', true); g.setVertexProp(v, 'focused', false); g.setVertexProp(v, 'inactive', true); g.star(v).forEach(e => g.setEdgeProp(e, 'inactive', true)); yield step( `Push vertex ${v} onto the stack and remove its edges from the graph.` ); } break; } } // If we arrived here, then we didn't find anything so we must spill if (i && i === vertList.length) { hasSpillage = true; // Simply choose the next vertex. There are better choices! var v = vertList.pop(); { if (stack.length) stack.setProp(stack.length - 1, 'focused', false); g.setVertexProp(v, 'spilled', true); yield step( `There aren't any vertices with degree < ${k}, so we'll have to choose one anyway, remove its connections, and spill it.` ); } state.stack.push(v); { stack.setProp(stack.length - 1, 'focused', true); stack.setProp(stack.length - 1, 'spilled', true); g.setVertexProp(v, 'focused', false); g.setVertexProp(v, 'inactive', true); g.star(v).forEach(e => g.setEdgeProp(e, 'inactive', true)); yield step( `Push vertex ${v} onto the stack and remove its edges from the graph.` ); } } } // Set up the next view once we start to pop { if (stack.length) stack.setProp(stack.length - 1, 'focused', false); yield step( `Now we reverse the process, popping each vertex off the stack and applying a color different than its neighbors.` ); } // Pop vertices until done let ii = 0; while (state.stack.length) { let wasSpilled = stack.getProp(stack.length - 1, 'spilled'); // Configure the view { g.setVertexProp(stack.get(stack.length - 1), 'inactive', false); g.setVertexProp(stack.get(stack.length - 1), 'focused', true); stack.setProp(stack.length - 1, 'focused', true); yield step( `Pop vertex ${stack.get(stack.length - 1)} off the end of the stack.` ); } // Pop the next vertex let v = state.stack.pop(); const adjacentColors = g .vertexStar(v, vp => g.getVertexProp(vp, 'colornum') !== undefined) .map(v => g.getVertexProp(v, 'colornum')); // Determine an available color var i; for (i = 0; i < k; i++) { if (adjacentColors.indexOf(i) === -1) { g.setVertexProp(v, 'colornum', i); break; } } // If none, just set any color if (i === k) { g.setVertexProp(v, 'colornum', 0); } // Configure the view { g.setVertexProp(v, 'focused', false); g.star(v).forEach(e => { if ( g.getVertexProp(e[0], 'spilled') || g.getVertexProp(e[1], 'spilled') ) { return; } g.setEdgeProp(e, 'inactive', false); }); yield step( [ `Apply a color #${g.getVertexProp(v, 'colornum') + 1} to vertex ${v}.`, wasSpilled ? `We had to spill this vertex, so we'll try our best to color it, but it may or may not work out.` : '' ].join(' ') ); } } // Complete! { yield step( `We've successfully ${k}-colored the graph${ hasSpillage ? ' (with a bit of spillage)' : '' }!` ); } }33:T508,function drawGraph(state) { const INACTIVE_COLOR = '#bbbbbb'; function vertexFillcolor(v) { const colornum = state.graph.getVertexProp(v, 'colornum'); const isSpilled = state.graph.getVertexProp(v, 'spilled'); if (colornum === undefined && isSpilled) return COLOR.SPILLED; const isFocused = state.graph.getVertexProp(v, 'focused'); if (isFocused) return COLOR.FOCUSED; if (colornum !== undefined) return kColors[colornum % kColors.length]; return 'transparent'; } function vertexColor(v) { const isInactive = state.graph.getVertexProp(v, 'inactive'); if (isInactive) return COLOR.INACTIVE; return 'black'; } function edgeColor(e) { const isInactive = state.graph.getEdgeProp(e, 'inactive'); if (isInactive) return COLOR.INACTIVE; return 'black'; } return dot`graph registerInterferenceGraph { rankdir="LR" size=6 ${state.graph.vertices .map( (v, i) => `${i} [ style=filled color="${vertexColor(i)}" fontcolor="${vertexColor(i)}" fillcolor="${vertexFillcolor(i)}" ]` ) .join('\n')} ${state.graph .edgeList() .map(e => `${e[0]} -- ${e[1]} [color="${edgeColor(e)}"];`) .join('\n')} }`; }34:Tb4e,UndirectedGraph = { // A very bad graph implementation which facilitates attaching properties. // A lot of the storage and iteration fits nicely into a line or two, but // as a result it's pretty inefficient and I can't recommend using it! function UndirectedGraph(n) { this.edges = []; this.vertices = new Array(n).fill(0).map(() => {}); } UndirectedGraph.prototype.addEdge = function(e) { let vmin = Math.min(e[0], e[1]); let vmax = Math.max(e[0], e[1]); if (!this.edges[vmin]) this.edges[vmin] = []; var data = {}; this.edges[vmin][vmax] = data; return data; }; UndirectedGraph.prototype.hasEdge = function(e) { let vmin = Math.min(e[0], e[1]); let vmax = Math.max(e[0], e[1]); return ( this.edges[vmin] !== undefined && this.edges[vmin][vmax] !== undefined ); }; UndirectedGraph.prototype.setEdgeProp = function(e, prop, value) { if (!this.hasEdge(e)) throw new Error('Edge not present: ' + e); this.edges[Math.min(e[0], e[1])][Math.max(e[0], e[1])][prop] = value; }; UndirectedGraph.prototype.getEdgeProp = function(e, prop) { if (!this.hasEdge(e)) throw new Error('Edge not present: ' + e); return this.edges[Math.min(e[0], e[1])][Math.max(e[0], e[1])][prop]; }; UndirectedGraph.prototype.setVertexProp = function(v, prop, value) { if (!this.vertices[v]) this.vertices[v] = {}; this.vertices[v][prop] = value; }; UndirectedGraph.prototype.getVertexProp = function(v, prop) { if (!this.vertices[v]) return undefined; return this.vertices[v][prop]; }; UndirectedGraph.prototype.clone = function() { var g = new UndirectedGraph(); g.edges = JSON.parse(JSON.stringify(this.edges)); g.vertices = JSON.parse(JSON.stringify(this.vertices)); return g; }; UndirectedGraph.prototype.edgeList = function() { var edges = []; for (var v1 = 0; v1 < this.edges.length; v1++) { if (!this.edges[v1]) continue; for (var v2 = 0; v2 < this.edges[v1].length; v2++) { if (!this.edges[v1][v2]) continue; edges.push([v1, v2]); } } return edges; }; UndirectedGraph.prototype.degree = function(v, condition) { let degree = 0; this.edgeList().forEach(e => { if (e[0] === v || e[1] === v) { if (condition && !condition(e)) return; degree++; } }); return degree; }; UndirectedGraph.prototype.star = function(v, condition) { const star = []; this.edgeList().forEach(e => { if (e[0] === v || e[1] === v) { if (condition && !condition(e)) return; star.push(e); } }); return star; }; UndirectedGraph.prototype.vertexStar = function(v, condition) { let verts = this.star(v).map(e => (e[0] === v ? e[1] : e[0])); if (condition) verts = verts.filter(condition); return verts; }; return UndirectedGraph; }35:T47f,Stack = { // A very bad stack implementation which facilitates attaching properties function Stack() { this.stack = []; this.props = []; Object.defineProperty(this, 'length', { enumerable: false, get: function() { return this.stack.length; } }); } Stack.prototype.clone = function() { const newStack = new Stack(); newStack.props = JSON.parse(JSON.stringify(this.props)); newStack.stack = JSON.parse(JSON.stringify(this.stack)); return newStack; }; Stack.prototype.push = function(value, props) { this.stack.push(value); this.props.push(Object.assign({}, props)); }; Stack.prototype.pop = function() { this.props.pop(); return this.stack.pop(); }; Stack.prototype.getProp = function(i, prop) { return this.props[i][prop]; }; Stack.prototype.setProp = function(i, prop, value) { return (this.props[i][prop] = value); }; Stack.prototype.map = function(clbk) { return this.stack.map((item, i) => { return clbk(item, i, this.props[i]); }); }; Stack.prototype.get = function(i) { return this.stack[i]; }; return Stack; }36:T723,/* Source: https://github.com/mattdesl/float-hsl2rgb The MIT License (MIT) Copyright (c) 2015 Matt DesLauriers Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ function hsl2rgb(hsl) { var h = hsl[0], s = hsl[1], l = hsl[2], t1, t2, t3, rgb, val; if (s === 0) { val = l; return [val, val, val]; } if (l < 0.5) { t2 = l * (1 + s); } else { t2 = l + s - l * s; } t1 = 2 * l - t2; rgb = [0, 0, 0]; for (var i = 0; i < 3; i++) { t3 = h + (1 / 3) * -(i - 1); if (t3 < 0) { t3++; } if (t3 > 1) { t3--; } if (6 * t3 < 1) { val = t1 + (t2 - t1) * 6 * t3; } else if (2 * t3 < 1) { val = t2; } else if (3 * t3 < 2) { val = t1 + (t2 - t1) * (2 / 3 - t3) * 6; } else { val = t1; } rgb[i] = val; } return rgb; }37:[] 2f:{"title":"Register Allocation and the k-Coloring Problem","cells":[{"id":0,"value":"md`# Register Allocation and the k-Coloring Problem`","pinned":false,"hidden":false,"mode":"ojs"},{"id":826,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1038,"value":"references = md`## References\n\n- [Standard CS143: Register Allocation](https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/17/Slides17.pdf)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":782,"value":"viewof vertexCount = slider({\n min: 5,\n max: 20,\n value: 8,\n step: 1,\n description: 'Number of vertices, n'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":789,"value":"viewof edgeCount = slider({\n min: 5,\n max: 40,\n value: 15,\n step: 1,\n description: 'Number of edges, e'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":345,"value":"viewof randomize = button({ value: 'Randomize graph' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":150,"value":"viewof k = slider({\n min: 1,\n max: 10,\n value: 4,\n step: 1,\n description: 'Number of colors, k'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":923,"value":"html`Colors: ${kColors.map(\n (c, i) =>\n html`

#${i +\n 1}

`\n)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":91,"value":"viewof step = (await visibility) &&\n Scrubber(steps, {\n delay: 800,\n autoplay: !showFinished,\n loop: false,\n initial: showFinished ? steps.length - 1 : 0,\n format: (step, i) => ''\n })","pinned":false,"hidden":false,"mode":"ojs"},{"id":60,"value":"drawGraph(step)","pinned":false,"hidden":false,"mode":"ojs"},{"id":975,"value":"drawStack(step.stack)","pinned":false,"hidden":false,"mode":"ojs"},{"id":388,"value":"md`${step.label}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":914,"value":"viewof showFinished = checkbox({\n options: ['Show completed coloring']\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":633,"value":"md`## Implementation`","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"registerInterferenceGraph = (randomize,\ngenerateRandomUndirectedGraph(vertexCount, edgeCount))","pinned":false,"hidden":false,"mode":"ojs"},{"id":290,"value":"steps = [...chaitinAlgorithm(registerInterferenceGraph, k)]","pinned":true,"hidden":false,"mode":"ojs"},{"id":245,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":49,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":594,"value":"function drawStack(stack) {\n function fillcolor(i) {\n if (stack.getProp(i, 'spilled')) return COLOR.SPILLED;\n if (stack.getProp(i, 'focused')) return COLOR.FOCUSED;\n return 'transparent';\n }\n return dot`graph stack {\n rankdir=\"LR\"\n ${stack\n .map(\n (v, i) => `${v} [\n style=\"filled\"\n fillcolor=\"${fillcolor(i)}\"\n ];`\n )\n .join('\\n')}\n ${range(stack.length - 1)\n .map(i => `${stack.get(i)} -- ${stack.get(i + 1)}`)\n .join('\\n')}\n}`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":176,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":638,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"function generateRandomUndirectedGraph(vertexCount, edgeCount) {\n var graph = new UndirectedGraph(vertexCount);\n\n var maxTries = 1000;\n var currentEdges = {};\n for (var i = 0; i < edgeCount; i++) {\n var currentTry = 0;\n // Not fancy or efficient, but just retry random edges until\n while (++currentTry < maxTries) {\n // Sample two integers without replacement\n var v1 = Math.floor(Math.random() * vertexCount);\n var v2 = Math.floor(Math.random() * (vertexCount - 1));\n if (v2 >= v1) v2++;\n\n if (!graph.hasEdge([v1, v2])) break;\n }\n\n if (currentTry === maxTries) {\n throw new Error('Graph is too dense to find any available edges.');\n }\n\n graph.addEdge([v1, v2]);\n }\n return graph;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":695,"value":"COLOR = ({\n FOCUSED: '#55ff66',\n SPILLED: '#ff5566',\n INACTIVE: '#dddddd'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":710,"value":"kColors = range(k)\n .map(i => hsl2rgb([(i + 0.75) / k, 0.8, 0.75]))\n .map(floatRgbToHex)","pinned":false,"hidden":false,"mode":"ojs"},{"id":707,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":402,"value":"function range(n) {\n return [...Array(Math.max(0, n)).keys()];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":718,"value":"import { floatRgbToHex } from '@rreusser/utils'","pinned":false,"hidden":false,"mode":"ojs"},{"id":46,"value":"import { dot } from '@observablehq/graphviz'","pinned":false,"hidden":false,"mode":"ojs"},{"id":88,"value":"import { Scrubber } from '@mbostock/scrubber'","pinned":false,"hidden":false,"mode":"ojs"},{"id":146,"value":"import { slider, button, checkbox } from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W37","stdlib":"1","titling":"auto"}