Skip to content

Instantly share code, notes, and snippets.

@indutny indutny/example.js
Created Oct 11, 2015

Embed
What would you like to do?
json-pipeline usage example
// Just for viewing graphviz output
var fs = require('fs');
var Pipeline = require('json-pipeline');
var Reducer = require('json-pipeline-reducer');
var Scheduler = require('json-pipeline-scheduler');
//
// Create empty graph with CFG convenience
// methods.
//
var p = Pipeline.create('cfg');
//
// Parse the printable data and generate
// the graph.
//
p.parse(`pipeline {
b0 {
i0 = literal 0
i1 = literal 0
i3 = array
i4 = jump ^b0
}
b0 -> b1
b1 {
i5 = ssa:phi ^b1 i0, i12
i6 = ssa:phi ^i5, i1, i14
i7 = loadArrayLength i3
i8 = cmp "<", i6, i7
i9 = if ^i6, i8
}
b1 -> b2, b3
b2 {
i10 = checkIndex ^b2, i3, i6
i11 = load ^i10, i3, i6
i12 = add i5, i11
i13 = literal 1
i14 = add i6, i13
i15 = jump ^b2
}
b2 -> b1
b3 {
i16 = exit ^b3
}
}`, { cfg: true }, 'printable');
if (process.env.DEBUG)
fs.writeFileSync('before.gv', p.render('graphviz'));
//
// Just a helper to run reductions
//
function reduce(graph, reduction) {
var reducer = new Reducer();
reducer.addReduction(reduction);
reducer.reduce(graph);
}
//
// Create reduction
//
var ranges = new Map();
function getRange(node) {
if (ranges.has(node))
return ranges.get(node);
var range = { from: -Infinity, to: +Infinity, type: 'any' };
ranges.set(node, range);
return range;
}
function updateRange(node, reducer, from, to) {
var range = getRange(node);
// Lowest type, can't get upwards
if (range.type === 'none')
return;
if (range.from === from && range.to === to && range.type === 'int')
return;
range.from = from;
range.to = to;
range.type = 'int';
reducer.change(node);
}
function updateType(node, reducer, type) {
var range = getRange(node);
if (range.type === type)
return;
range.type = type;
reducer.change(node);
}
//
// Set type of literal
//
function reduceLiteral(node, reducer) {
var value = node.literals[0];
updateRange(node, reducer, value, value);
}
function reduceBinary(node, left, right, reducer) {
if (left.type === 'none' || right.type === 'none') {
updateType(node, reducer, 'none');
return false;
}
if (left.type === 'int' || right.type === 'int')
updateType(node, reducer, 'int');
if (left.type !== 'int' || right.type !== 'int')
return false;
return true;
}
//
// Just join the ranges of inputs
//
function reducePhi(node, reducer) {
var left = getRange(node.inputs[0]);
var right = getRange(node.inputs[1]);
if (!reduceBinary(node, left, right, reducer))
return;
if (node.inputs[1].opcode !== 'add' || left.from !== left.to)
return;
var from = Math.min(left.from, right.from);
var to = Math.max(left.to, right.to);
updateRange(node, reducer, from, to);
}
//
// Detect: phi = phi + <positive number>, where initial phi is number,
// report proper range.
//
function reduceAdd(node, reducer) {
var left = getRange(node.inputs[0]);
var right = getRange(node.inputs[1]);
if (!reduceBinary(node, left, right, reducer))
return;
var phi = node.inputs[0];
if (phi.opcode !== 'ssa:phi' || right.from !== right.to)
return;
var number = right.from;
if (number <= 0 || phi.inputs[1] !== node)
return;
var initial = getRange(phi.inputs[0]);
if (initial.type !== 'int')
return;
updateRange(node, reducer, initial.from, +Infinity);
}
var limits = new Map();
function getLimit(node) {
if (limits.has(node))
return limits.get(node);
var map = new Map();
limits.set(node, map);
return map;
}
function updateLimit(holder, node, reducer, type, value) {
var map = getLimit(holder);
if (!map.has(node))
map.set(node, { type: 'any', value: null });
var limit = map.get(node);
if (limit.type === type && limit.value === value)
return;
limit.type = type;
limit.value = value;
reducer.change(holder);
}
function mergeLimit(node, reducer, other) {
var map = getLimit(node);
var otherMap = getLimit(other);
otherMap.forEach(function(limit, key) {
updateLimit(node, key, reducer, limit.type, limit.value);
});
}
//
// Propagate limit from: X < Y to `if`'s true branch
//
function reduceIf(node, reducer) {
var test = node.inputs[0];
if (test.opcode !== 'cmp' || test.literals[0] !== '<')
return;
var left = test.inputs[0];
var right = test.inputs[1];
updateLimit(node.controlUses[0], left, reducer, '<', right);
updateLimit(node.controlUses[2], left, reducer, '>=', right);
}
//
// Determine ranges and limits of
// the values.
//
var rangeAndLimit = new Reducer.Reduction({
reduce: function(node, reducer) {
if (node.opcode === 'literal')
reduceLiteral(node, reducer);
else if (node.opcode === 'ssa:phi')
reducePhi(node, reducer);
else if (node.opcode === 'add')
reduceAdd(node, reducer);
else if (node.opcode === 'if')
reduceIf(node, reducer);
}
});
reduce(p, rangeAndLimit);
//
// Now that we have ranges and limits,
// time to remove the useless array
// length checks.
//
function reduceCheckIndex(node, reducer) {
// Walk up the control chain
var region = node.control[0];
while (region.opcode !== 'region' && region.opcode !== 'start')
region = region.control[0];
var array = node.inputs[0];
var index = node.inputs[1];
var limit = getLimit(region).get(index);
if (!limit)
return;
var range = getRange(index);
// Negative array index is not valid
if (range.from < 0)
return;
// Index should be limited by array length
if (limit.type !== '<' ||
limit.value.opcode !== 'loadArrayLength' ||
limit.value.inputs[0] !== array) {
return;
}
// Check is safe to remove!
reducer.remove(node);
}
var eliminateChecks = new Reducer.Reduction({
reduce: function(node, reducer) {
if (node.opcode === 'checkIndex')
reduceCheckIndex(node, reducer);
}
});
reduce(p, eliminateChecks);
//
// Run scheduler to put everything
// back to the CFG
//
var out = Scheduler.create(p).run();
out.reindex();
if (process.env.DEBUG)
fs.writeFileSync('after.gv', out.render('graphviz'));
console.log(out.render({ cfg: true }, 'printable'));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.