//"use strict";

// Analyze intertype data. Calculates things that are necessary in order

// to do the final conversion into JavaScript later, for example,

// properties of variables, loop structures of functions, etc.

var VAR_NATIVE = 'native';

var VAR_NATIVIZED = 'nativized';

var VAR_EMULATED = 'emulated';

var ENTRY_IDENT = toNiceIdent('%0');

var ENTRY_IDENTS = set(toNiceIdent('%0'), toNiceIdent('%1'));

function recomputeLines(func) {

func.lines = func.labels.map(function(label) { return label.lines }).reduce(concatenator, []);

}

// Handy sets

var BRANCH_INVOKE = set('branch', 'invoke');

var SIDE_EFFECT_CAUSERS = set('call', 'invoke', 'atomic');

var UNUNFOLDABLE = set('value', 'type', 'phiparam');

// Analyzer

function analyzer(data, sidePass) {

var mainPass = !sidePass;

// Substrate

var substrate = new Substrate('Analyzer');

// Sorter

substrate.addActor('Sorter', {

processItem: function(item) {

item.items.sort(function (a, b) { return a.lineNum - b.lineNum });

this.forwardItem(item, 'Gatherer');

}

});

// Gatherer

substrate.addActor('Gatherer', {

processItem: function(item) {

// Single-liners

['globalVariable', 'functionStub', 'unparsedFunction', 'unparsedGlobals', 'unparsedTypes', 'alias'].forEach(function(intertype) {

var temp = splitter(item.items, function(item) { return item.intertype == intertype });

item.items = temp.leftIn;

item[intertype + 's'] = temp.splitOut;

});

var temp = splitter(item.items, function(item) { return item.intertype == 'type' });

item.items = temp.leftIn;

temp.splitOut.forEach(function(type) {

//dprint('types', 'adding defined type: ' + type.name_);

Types.types[type.name_] = type;

if (QUANTUM_SIZE === 1) {

Types.fatTypes[type.name_] = copy(type);

}

});

// Functions & labels

item.functions = [];

var currLabelFinished; // Sometimes LLVM puts a branch in the middle of a label. We need to ignore all lines after that.

item.items.sort(function(a, b) { return a.lineNum - b.lineNum });

for (var i = 0; i < item.items.length; i++) {

var subItem = item.items[i];

assert(subItem.lineNum);

if (subItem.intertype == 'function') {

item.functions.push(subItem);

subItem.endLineNum = null;

subItem.lines = []; // We will fill in the function lines after the legalizer, since it can modify them

subItem.labels = [];

subItem.forceEmulated = false;

// no explicit 'entry' label in clang on LLVM 2.8 - most of the time, but not all the time! - so we add one if necessary

if (item.items[i+1].intertype !== 'label') {

item.items.splice(i+1, 0, {

intertype: 'label',

ident: ENTRY_IDENT,

lineNum: subItem.lineNum + '.5'

});

}

} else if (subItem.intertype == 'functionEnd') {

item.functions.slice(-1)[0].endLineNum = subItem.lineNum;

} else if (subItem.intertype == 'label') {

item.functions.slice(-1)[0].labels.push(subItem);

subItem.lines = [];

currLabelFinished = false;

} else if (item.functions.length > 0 && item.functions.slice(-1)[0].endLineNum === null) {

// Internal line

if (!currLabelFinished) {

item.functions.slice(-1)[0].labels.slice(-1)[0].lines.push(subItem); // If this line fails, perhaps missing a label?

if (subItem.intertype === 'branch') {

currLabelFinished = true;

}

} else {

print('// WARNING: content after a branch in a label, line: ' + subItem.lineNum);

}

} else {

throw 'ERROR: what is this? ' + dump(subItem);

}

}

delete item.items;

this.forwardItem(item, 'Legalizer');

}

});

// Legalize LLVM unrealistic types into realistic types.

//

// With full LLVM optimizations, it can generate types like i888 which do not exist in

// any actual hardware implementation, but are useful during optimization. LLVM then

// legalizes these types into real ones during code generation. Sadly, there is no LLVM

// IR pass to legalize them, which would have been useful and nice from a design perspective.

// The LLVM community is also not interested in receiving patches to implement that

// functionality, since it would duplicate existing code from the code generation

// component. Therefore, we implement legalization here in Emscripten.

//

// Currently we just legalize completely unrealistic types into bundles of i32s, and just

// the most common instructions that can be involved with such types: load, store, shifts,

// trunc and zext.

substrate.addActor('Legalizer', {

processItem: function(data) {

// Legalization

if (USE_TYPED_ARRAYS == 2) {

function getLegalVars(base, bits) {

assert(!isNumber(base));

var ret = new Array(Math.ceil(bits/32));

var i = 0;

while (bits > 0) {

ret[i] = { ident: base + '$' + i, bits: Math.min(32, bits) };

bits -= 32;

i++;

}

return ret;

}

function getLegalLiterals(text, bits) {

var parsed = parseArbitraryInt(text, bits);

var ret = new Array(Math.ceil(bits/32));

var i = 0;

while (bits > 0) {

ret[i] = { ident: (parsed[i]|0).toString(), bits: Math.min(32, bits) }; // resign all values

bits -= 32;

i++;

}

return ret;

}

// Uses the right factor to multiply line numbers by so that they fit in between

// the line[i] and the line after it

function interpLines(lines, i, toAdd) {

var prev = i >= 0 ? lines[i].lineNum : -1;

var next = (i < lines.length-1) ? lines[i+1].lineNum : (lines[i].lineNum + 0.5);

var factor = (next - prev)/(4*toAdd.length+3);

for (var k = 0; k < toAdd.length; k++) {

toAdd[k].lineNum = prev + ((k+1)*factor);

}

}

function removeAndAdd(lines, i, toAdd) {

var item = lines[i];

interpLines(lines, i, toAdd);

Array.prototype.splice.apply(lines, [i, 1].concat(toAdd));

return toAdd.length;

}

function legalizeFunctionParameters(params) {

var i = 0;

while (i < params.length) {

var param = params[i];

if (param.intertype == 'value' && isIllegalType(param.type)) {

var toAdd = getLegalVars(param.ident, getBits(param.type)).map(function(element) {

return {

intertype: 'value',

type: 'i' + element.bits,

ident: element.ident,

byval: 0

};

});

Array.prototype.splice.apply(params, [i, 1].concat(toAdd));

i += toAdd.length;

continue;

}

i++;

}

}

function fixUnfolded(item) {

// Unfolded items may need some correction to work properly in the global scope

if (item.intertype in MATHOPS) {

item.op = item.intertype;

item.intertype = 'mathop';

}

}

data.functions.forEach(function(func) {

// Legalize function params

legalizeFunctionParameters(func.params);

// Legalize lines in labels

var tempId = 0;

func.labels.forEach(function(label) {

var i = 0, bits;

while (i < label.lines.length) {

var item = label.lines[i];

var value = item;

// Check if we need to legalize here, and do some trivial legalization along the way

var isIllegal = false;

walkInterdata(item, function(item) {

if (item.intertype == 'getelementptr' || (item.intertype == 'call' && item.ident in LLVM.INTRINSICS_32)) {

// Turn i64 args into i32

for (var i = 0; i < item.params.length; i++) {

if (item.params[i].type == 'i64') item.params[i].type = 'i32';

}

}

if (isIllegalType(item.valueType) || isIllegalType(item.type)) {

isIllegal = true;

}

});

if (!isIllegal) {

i++;

continue;

}

// Unfold this line. If we unfolded, we need to return and process the lines we just

// generated - they may need legalization too

var unfolded = [];

walkAndModifyInterdata(item, function(subItem) {

// Unfold all non-value interitems that we can, and also unfold all numbers (doing the latter

// makes it easier later since we can then assume illegal expressions are always variables

// accessible through ident$x, and not constants we need to parse then and there)

if (subItem != item && (!(subItem.intertype in UNUNFOLDABLE) ||

(subItem.intertype == 'value' && isNumber(subItem.ident) && isIllegalType(subItem.type)))) {

if (item.intertype == 'phi') {

assert(subItem.intertype == 'value', 'We can only unfold illegal constants in phis');

// we must handle this in the phi itself, if we unfold normally it will not be pushed back with the phi

} else {

var tempIdent = '$$emscripten$temp$' + (tempId++);

subItem.assignTo = tempIdent;

unfolded.unshift(subItem);

fixUnfolded(subItem);

return { intertype: 'value', ident: tempIdent, type: subItem.type };

}

} else if (subItem.intertype == 'switch' && isIllegalType(subItem.type)) {

subItem.switchLabels.forEach(function(switchLabel) {

if (switchLabel.value[0] != '$') {

var tempIdent = '$$emscripten$temp$' + (tempId++);

unfolded.unshift({

assignTo: tempIdent,

intertype: 'value',

ident: switchLabel.value,

type: subItem.type

});

switchLabel.value = tempIdent;

}

});

}

});

if (unfolded.length > 0) {

interpLines(label.lines, i-1, unfolded);

Array.prototype.splice.apply(label.lines, [i, 0].concat(unfolded));

continue; // remain at this index, to unfold newly generated lines

}

// This is an illegal-containing line, and it is unfolded. Legalize it now

dprint('legalizer', 'Legalizing ' + item.intertype + ' at line ' + item.lineNum);

switch (item.intertype) {

case 'store': {

var toAdd = [];

bits = getBits(item.valueType);

var elements;

elements = getLegalVars(item.value.ident, bits);

var j = 0;

elements.forEach(function(element) {

var tempVar = '$st$' + i + '$' + j;

toAdd.push({

intertype: 'getelementptr',

assignTo: tempVar,

ident: item.pointer.ident,

type: '[0 x i32]*',

params: [

{ intertype: 'value', ident: item.pointer.ident, type: '[0 x i32]*' }, // technically a bitcase is needed in llvm, but not for us

{ intertype: 'value', ident: '0', type: 'i32' },

{ intertype: 'value', ident: j.toString(), type: 'i32' }

],

});

var actualSizeType = 'i' + element.bits; // The last one may be smaller than 32 bits

toAdd.push({

intertype: 'store',

valueType: actualSizeType,

value: { intertype: 'value', ident: element.ident, type: actualSizeType },

pointer: { intertype: 'value', ident: tempVar, type: actualSizeType + '*' },

ident: tempVar,

pointerType: actualSizeType + '*',

align: item.align,

});

j++;

});

Types.needAnalysis['[0 x i32]'] = 0;

i += removeAndAdd(label.lines, i, toAdd);

continue;

}

// call, return: Return value is in an unlegalized array literal. Not fully optimal.

case 'call': {

bits = getBits(value.type);

var elements = getLegalVars(item.assignTo, bits);

var toAdd = [value];

// legalize parameters

legalizeFunctionParameters(value.params);

if (value.assignTo) {

// legalize return value

var j = 0;

toAdd = toAdd.concat(elements.map(function(element) {

return {

intertype: 'value',

assignTo: element.ident,

type: 'i' + bits,

ident: value.assignTo + '[' + (j++) + ']'

};

}));

}

i += removeAndAdd(label.lines, i, toAdd);

continue;

}

case 'return': {

bits = getBits(item.type);

var elements = getLegalVars(item.value.ident, bits);

item.value.ident = '[' + elements.map(function(element) { return element.ident }).join(',') + ']';

i++;

continue;

}

case 'invoke': {

legalizeFunctionParameters(value.params);

// We can't add lines after this, since invoke already modifies control flow. So we handle the return in invoke

i++;

continue;

}

case 'value': {

bits = getBits(value.type);

var elements = getLegalVars(item.assignTo, bits);

var values = getLegalLiterals(item.ident, bits);

var j = 0;

var toAdd = elements.map(function(element) {

return {

intertype: 'value',

assignTo: element.ident,

type: 'i' + bits,

ident: values[j++].ident

};

});

i += removeAndAdd(label.lines, i, toAdd);

continue;

}

case 'load': {

bits = getBits(value.valueType);

var elements = getLegalVars(item.assignTo, bits);

var j = 0;

var toAdd = [];

elements.forEach(function(element) {

var tempVar = '$st$' + i + '$' + j;

toAdd.push({

intertype: 'getelementptr',

assignTo: tempVar,

ident: value.pointer.ident,

type: '[0 x i32]*',

params: [

{ intertype: 'value', ident: value.pointer.ident, type: '[0 x i32]*' }, // technically bitcast is needed in llvm, but not for us

{ intertype: 'value', ident: '0', type: 'i32' },

{ intertype: 'value', ident: j.toString(), type: 'i32' }

]

});

var actualSizeType = 'i' + element.bits; // The last one may be smaller than 32 bits

toAdd.push({

intertype: 'load',

assignTo: element.ident,

pointerType: actualSizeType + '*',

valueType: actualSizeType,

type: actualSizeType, // XXX why is this missing from intertyper?

pointer: { intertype: 'value', ident: tempVar, type: actualSizeType + '*' },

ident: tempVar,

pointerType: actualSizeType + '*',

align: value.align

});

j++;

});

Types.needAnalysis['[0 x i32]'] = 0;

i += removeAndAdd(label.lines, i, toAdd);

continue;

}

case 'phi': {

bits = getBits(value.type);

var toAdd = [];

var elements = getLegalVars(item.assignTo, bits);

var j = 0;

var literalValues = {}; // special handling of literals - we cannot unfold them normally

value.params.map(function(param) {

if (isNumber(param.value.ident)) {

literalValues[param.value.ident] = getLegalLiterals(param.value.ident, bits);

}

});

elements.forEach(function(element) {

toAdd.push({

intertype: 'phi',

assignTo: element.ident,

type: 'i' + element.bits,

params: value.params.map(function(param) {

return {

intertype: 'phiparam',

label: param.label,

value: {

intertype: 'value',

ident: (param.value.ident in literalValues) ? literalValues[param.value.ident][j].ident : (param.value.ident + '$' + j),

type: 'i' + element.bits,

}

};

})

});

j++;

});

i += removeAndAdd(label.lines, i, toAdd);

continue;

}

case 'switch': {

i++;

continue; // special case, handled in makeComparison

}

case 'bitcast': {

var inType = item.type2;

var outType = item.type;

if ((inType in Runtime.INT_TYPES && outType in Runtime.FLOAT_TYPES) ||

(inType in Runtime.FLOAT_TYPES && outType in Runtime.INT_TYPES)) {

i++;

continue; // special case, handled in processMathop

}

// fall through

}

case 'inttoptr': case 'ptrtoint': case 'zext': case 'sext': case 'trunc': case 'ashr': case 'lshr': case 'shl': case 'or': case 'and': case 'xor': {

value = {

op: item.intertype,

variant: item.variant,

type: item.type,

params: item.params

};

// fall through

}

case 'mathop': {

var toAdd = [];

var sourceBits = getBits(value.params[0].type);

// All mathops can be parametrized by how many shifts we do, and how big the source is

var shifts = 0;

var targetBits = sourceBits;

var processor = null;

var signed = false;

switch (value.op) {

case 'ashr': {

signed = true;

// fall through

}

case 'lshr': {

shifts = parseInt(value.params[1].ident);

break;

}

case 'shl': {

shifts = -parseInt(value.params[1].ident);

break;

}

case 'sext': {

signed = true;

// fall through

}

case 'trunc': case 'zext': case 'ptrtoint': {

targetBits = getBits(value.params[1] ? value.params[1].ident : value.type);

break;

}

case 'inttoptr': {

targetBits = 32;

break;

}

case 'bitcast': {

break;

}

case 'select': {

sourceBits = targetBits = getBits(value.params[1].type);

var otherElementsA = getLegalVars(value.params[1].ident, sourceBits);

var otherElementsB = getLegalVars(value.params[2].ident, sourceBits);

processor = function(result, j) {

return {

intertype: 'mathop',

op: 'select',

type: 'i' + otherElementsA[j].bits,

params: [

value.params[0],

{ intertype: 'value', ident: otherElementsA[j].ident, type: 'i' + otherElementsA[j].bits },

{ intertype: 'value', ident: otherElementsB[j].ident, type: 'i' + otherElementsB[j].bits }

]

};

};

break;

}

case 'or': case 'and': case 'xor': {

var otherElements = getLegalVars(value.params[1].ident, sourceBits);

processor = function(result, j) {

return {

intertype: 'mathop',

op: value.op,

type: 'i' + otherElements[j].bits,

params: [

result,

{ intertype: 'value', ident: otherElements[j].ident, type: 'i' + otherElements[j].bits }

]

};

};

break;

}

case 'add': case 'sub': case 'sdiv': case 'udiv': case 'mul': case 'urem': case 'srem':

case 'icmp':case 'uitofp': case 'sitofp': {

// We cannot do these in parallel chunks of 32-bit operations. We will handle these in processMathop

i++;

continue;

}

default: throw 'Invalid mathop for legalization: ' + [value.op, item.lineNum, dump(item)];

}

// Do the legalization

var sourceElements;

if (sourceBits <= 32) {

// The input is a legal type

sourceElements = [{ ident: value.params[0].ident, bits: sourceBits }];

} else {

sourceElements = getLegalVars(value.params[0].ident, sourceBits);

}

if (!isNumber(shifts)) {

// We can't statically legalize this, do the operation at runtime TODO: optimize

assert(sourceBits == 64, 'TODO: handle nonconstant shifts on != 64 bits');

value.intertype = 'value';

value.ident = 'Runtime.bitshift64(' + sourceElements[0].ident + ', ' +

sourceElements[1].ident + ',"' + value.op + '",' + value.params[1].ident + '$0);' +

'var ' + value.assignTo + '$0 = ' + value.assignTo + '[0], ' + value.assignTo + '$1 = ' + value.assignTo + '[1];';

i++;

continue;

}

var targetElements = getLegalVars(item.assignTo, targetBits);

var sign = shifts >= 0 ? 1 : -1;

var shiftOp = shifts >= 0 ? 'shl' : 'lshr';

var shiftOpReverse = shifts >= 0 ? 'lshr' : 'shl';

var whole = shifts >= 0 ? Math.floor(shifts/32) : Math.ceil(shifts/32);

var fraction = Math.abs(shifts % 32);

if (signed) {

var signedFill = '((' + sourceElements[sourceElements.length-1].ident + '|0) < 0 ? -1 : 0)';

var signedKeepAlive = { intertype: 'value', ident: sourceElements[sourceElements.length-1].ident, type: 'i32' };

}

for (var j = 0; j < targetElements.length; j++) {

var result = {

intertype: 'value',

ident: (j + whole >= 0 && j + whole < sourceElements.length) ? sourceElements[j + whole].ident : (signed ? signedFill : '0'),

params: [(signed && j + whole > sourceElements.length) ? signedKeepAlive : null],

type: 'i32',

};

if (j == 0 && isUnsignedOp(value.op) && sourceBits < 32) {

// zext sign correction

result.ident = makeSignOp(result.ident, 'i' + sourceBits, 'un', 1, 1);

}

if (fraction != 0) {

var other = {

intertype: 'value',

ident: (j + sign + whole >= 0 && j + sign + whole < sourceElements.length) ? sourceElements[j + sign + whole].ident : (signed ? signedFill : '0'),

params: [(signed && j + sign + whole > sourceElements.length) ? signedKeepAlive : null],

type: 'i32',

};

other = {

intertype: 'mathop',

op: shiftOp,

type: 'i32',

params: [

other,

{ intertype: 'value', ident: (32 - fraction).toString(), type: 'i32' }

]

};

result = {

intertype: 'mathop',

// shifting in 1s from the top is a special case

op: (signed && shifts >= 0 && j + sign + whole >= sourceElements.length) ? 'ashr' : shiftOpReverse,

type: 'i32',

params: [

result,

{ intertype: 'value', ident: fraction.toString(), type: 'i32' }

]

};

result = {

intertype: 'mathop',

op: 'or',

type: 'i32',

params: [

result,

other

]

}

}

if (targetElements[j].bits < 32 && shifts < 0) {

// truncate bits that fall off the end. This is not needed in most cases, can probably be optimized out

result = {

intertype: 'mathop',

op: 'and',

type: 'i32',

params: [

result,

{ intertype: 'value', ident: (Math.pow(2, targetElements[j].bits)-1).toString(), type: 'i32' }

]

}

}

if (processor) {

result = processor(result, j);

}

result.assignTo = targetElements[j].ident;

toAdd.push(result);

}

if (targetBits <= 32) {

// We are generating a normal legal type here

legalValue = {

intertype: 'value',

ident: targetElements[0].ident + (targetBits < 32 ? '&' + (Math.pow(2, targetBits)-1) : ''),

type: 'rawJS'

};

legalValue.assignTo = item.assignTo;

toAdd.push(legalValue);

}

i += removeAndAdd(label.lines, i, toAdd);

continue;

}

}

assert(0, 'Could not legalize illegal line: ' + [item.lineNum, dump(item)]);

}

if (dcheck('legalizer')) dprint('zz legalized: \n' + dump(label.lines));

});

});

}

// Add function lines to func.lines, after our modifications to the label lines

data.functions.forEach(function(func) {

func.labels.forEach(function(label) {

func.lines = func.lines.concat(label.lines);

});

});

this.forwardItem(data, 'Typevestigator');

}

});

function addTypeInternal(type, data) {

if (type.length == 1) return;

if (Types.types[type]) return;

if (['internal', 'hidden', 'inbounds', 'void'].indexOf(type) != -1) return;

if (Runtime.isNumberType(type)) return;

dprint('types', 'Adding type: ' + type);

// 'blocks': [14 x %struct.X] etc. If this is a pointer, we need

// to look at the underlying type - it was not defined explicitly

// anywhere else.

var nonPointing = removeAllPointing(type);

var check = /^\[(\d+)\ x\ (.*)\]$/.exec(nonPointing);

if (check && !Types.types[nonPointing]) {

var num = parseInt(check[1]);

num = Math.max(num, 1); // [0 x something] is used not for allocations and such of course, but

// for indexing - for an |array of unknown length|, basically. So we

// define the 'type' as having a single field. TODO: Ensure as a sanity

// check that we never allocate with this (either as a child structure

// in the analyzer, or in calcSize in alloca).

var subType = check[2];

addTypeInternal(subType, data); // needed for anonymous structure definitions (see below)

Types.types[nonPointing] = {

name_: nonPointing,

fields: range(num).map(function() { return subType }),

lineNum: '?'

};

// Also add a |[0 x type]| type

var zerod = '[0 x ' + subType + ']';

if (!Types.types[zerod]) {

Types.types[zerod] = {

name_: zerod,

fields: [subType, subType], // Two, so we get the flatFactor right. We care about the flatFactor, not the size here

lineNum: '?'

};

}

return;

}

// anonymous structure definition, for example |{ i32, i8*, void ()*, i32 }|

if (type[0] == '{' || type[0] == '<') {

type = nonPointing;

var packed = type[0] == '<';

Types.types[type] = {

name_: type,

fields: splitTokenList(tokenize(type.substr(2 + packed, type.length - 4 - 2*packed)).tokens).map(function(segment) {

return segment[0].text;

}),

packed: packed,

lineNum: '?'

};

return;

}

if (isPointerType(type)) return;

if (['['].indexOf(type) != -1) return;

Types.types[type] = {

name_: type,

fields: [ 'i' + (QUANTUM_SIZE*8) ], // a single quantum size

flatSize: 1,

lineNum: '?'

};

}

function addType(type, data) {

addTypeInternal(type, data);

if (QUANTUM_SIZE === 1) {

Types.flipTypes();

addTypeInternal(type, data);

Types.flipTypes();

}

}

// Typevestigator

substrate.addActor('Typevestigator', {

processItem: function(data) {

if (sidePass) { // Do not investigate in the main pass - it is only valid to start to do so in the first side pass,

// which handles type definitions, and later. Doing so before the first side pass will result in

// making bad guesses about types which are actually defined

for (var type in Types.needAnalysis) {

if (type) addType(type, data);

}

Types.needAnalysis = {};

}

this.forwardItem(data, 'Typeanalyzer');

}

});

// Type analyzer

substrate.addActor('Typeanalyzer', {

processItem: function analyzeTypes(item, fatTypes) {

var types = Types.types;

// 'fields' is the raw list of LLVM fields. However, we embed

// child structures into parent structures, basically like C.

// So { int, { int, int }, int } would be represented as

// an Array of 4 ints. getelementptr on the parent would take

// values 0, 1, 2, where 2 is the entire middle structure.

// We also need to be careful with getelementptr to child

// structures - we return a pointer to the same slab, just

// a different offset. Likewise, need to be careful for

// getelementptr of 2 (the last int) - it's real index is 4.

// The benefit of this approach is inheritance -

// { { ancestor } , etc. } = descendant

// In this case it is easy to bitcast ancestor to descendant

// pointers - nothing needs to be done. If the ancestor were

// a new slab, it would need some pointer to the outer one

// for casting in that direction.

// TODO: bitcasts of non-inheritance cases of embedding (not at start)

var more = true;

while (more) {

more = false;

for (var typeName in types) {

var type = types[typeName];

if (type.flatIndexes) continue;

var ready = true;

type.fields.forEach(function(field) {

if (isStructType(field)) {

if (!types[field]) {

addType(field, item);

ready = false;

} else {

if (!types[field].flatIndexes) {

ready = false;

}

}

}

});

if (!ready) {

more = true;

continue;

}

Runtime.calculateStructAlignment(type);

if (dcheck('types')) dprint('type (fat=' + !!fatTypes + '): ' + type.name_ + ' : ' + JSON.stringify(type.fields));

if (dcheck('types')) dprint(' has final size of ' + type.flatSize + ', flatting: ' + type.needsFlattening + ' ? ' + (type.flatFactor ? type.flatFactor : JSON.stringify(type.flatIndexes)));

}

}

if (QUANTUM_SIZE === 1 && !fatTypes) {

Types.flipTypes();

// Fake a quantum size of 4 for fat types. TODO: Might want non-4 for some reason?

var trueQuantumSize = QUANTUM_SIZE;

Runtime.QUANTUM_SIZE = 4;

analyzeTypes(item, true);

Runtime.QUANTUM_SIZE = trueQuantumSize;

Types.flipTypes();

}

if (!fatTypes) {

this.forwardItem(item, 'VariableAnalyzer');

}

}

});

// Variable analyzer

substrate.addActor('VariableAnalyzer', {

processItem: function(item) {

// Globals

var old = item.globalVariables;

item.globalVariables = {};

old.forEach(function(variable) {

variable.impl = 'emulated'; // All global variables are emulated, for now. Consider optimizing later if useful

item.globalVariables[variable.ident] = variable;

});

// Function locals

item.functions.forEach(function(func) {

func.variables = {};

// LLVM is SSA, so we always have a single assignment/write. We care about

// the reads/other uses.

// Function parameters

func.params.forEach(function(param) {

if (param.intertype !== 'varargs') {

func.variables[param.ident] = {

ident: param.ident,

type: param.type,

origin: 'funcparam',

lineNum: func.lineNum,

rawLinesIndex: -1

};

}

});

// Normal variables

func.lines.forEach(function(item, i) {

if (item.assignTo) {

var variable = func.variables[item.assignTo] = {

ident: item.assignTo,

type: item.type,

origin: item.intertype,

lineNum: item.lineNum,

rawLinesIndex: i

};

if (variable.origin === 'alloca') {

variable.allocatedNum = item.allocatedNum;

}

}

});

if (QUANTUM_SIZE === 1) {

// Second pass over variables - notice when types are crossed by bitcast

func.lines.forEach(function(item) {

if (item.assignTo && item.intertype === 'bitcast') {

// bitcasts are unique in that they convert one pointer to another. We

// sometimes need to know the original type of a pointer, so we save that.

//

// originalType is the type this variable is created from

// derivedTypes are the types that this variable is cast into

func.variables[item.assignTo].originalType = item.type2;

if (!isNumber(item.assignTo)) {

if (!func.variables[item.assignTo].derivedTypes) {

func.variables[item.assignTo].derivedTypes = [];

}

func.variables[item.assignTo].derivedTypes.push(item.type);

}

}

});

}

// Analyze variable uses

function analyzeVariableUses() {

dprint('vars', 'Analyzing variables for ' + func.ident + '\n');

for (vname in func.variables) {

var variable = func.variables[vname];

// Whether the value itself is used. For an int, always yes. For a pointer,

// we might never use the pointer's value - we might always just store to it /

// read from it. If so, then we can optimize away the pointer.

variable.hasValueTaken = false;

variable.pointingLevels = pointingLevels(variable.type);

variable.uses = 0;

}

// TODO: improve the analysis precision. bitcast, for example, means we take the value, but perhaps we only use it to load/store

var inNoop = 0;

func.lines.forEach(function(line) {

walkInterdata(line, function(item) {

if (item.intertype == 'noop') inNoop++;

if (!inNoop) {

if (item.ident in func.variables) {

func.variables[item.ident].uses++;

if (item.intertype != 'load' && item.intertype != 'store') {

func.variables[item.ident].hasValueTaken = true;

}

}

}

}, function(item) {

if (item.intertype == 'noop') inNoop--;

});

});

//if (dcheck('vars')) dprint('analyzed variables: ' + dump(func.variables));

}

analyzeVariableUses();

// Decision time

for (vname in func.variables) {

var variable = func.variables[vname];

var pointedType = pointingLevels(variable.type) > 0 ? removePointing(variable.type) : null;

if (variable.origin == 'getelementptr') {

// Use our implementation that emulates pointers etc.

// TODO Can we perhaps nativize some of these? However to do so, we need to discover their

// true types; we have '?' for them now, as they cannot be discovered in the intertyper.

variable.impl = VAR_EMULATED;

} else if (variable.origin == 'funcparam') {

variable.impl = VAR_EMULATED;

} else if (variable.type == 'i64*' && USE_TYPED_ARRAYS == 2) {

variable.impl = VAR_EMULATED;

} else if (MICRO_OPTS && variable.pointingLevels === 0) {

// A simple int value, can be implemented as a native variable

variable.impl = VAR_NATIVE;

} else if (MICRO_OPTS && variable.origin === 'alloca' && !variable.hasValueTaken &&

variable.allocatedNum === 1 &&

(Runtime.isNumberType(pointedType) || Runtime.isPointerType(pointedType))) {

// A pointer to a value which is only accessible through this pointer. Basically

// a local value on the stack, which nothing fancy is done on. So we can

// optimize away the pointing altogether, and just have a native variable

variable.impl = VAR_NATIVIZED;

} else {

variable.impl = VAR_EMULATED;

}

if (dcheck('vars')) dprint('// var ' + vname + ': ' + JSON.stringify(variable));

}

});

this.forwardItem(item, 'Signalyzer');

}

});

// Sign analyzer

//

// Analyze our variables and detect their signs. In USE_TYPED_ARRAYS == 2,

// we can read signed or unsigned values and prevent the need for signing

// corrections.

//

// For each variable that is the result of a Load, we look a little forward

// to see where it is used. We only care about mathops, since only they

// need signs.

//

substrate.addActor('Signalyzer', {

processItem: function(item) {

this.forwardItem(item, 'QuantumFixer');

if (USE_TYPED_ARRAYS !== 2) return;

function seekIdent(item, obj) {

if (item.ident === obj.ident) {

obj.found++;

}

}

function seekMathop(item, obj) {

if (item.intertype === 'mathop' && obj.found && !obj.decided) {

if (isUnsignedOp(item.op, item.variant)) {

obj.unsigned++;

} else {

obj.signed++;

}

}

}

item.functions.forEach(function(func) {

func.lines.forEach(function(line, i) {

if (line.intertype === 'load') {

// Floats have no concept of signedness. Mark them as 'signed', which is the default, for which we do nothing

if (line.type in Runtime.FLOAT_TYPES) {

line.unsigned = false;

return;

}

// Booleans are always unsigned

var data = func.variables[line.assignTo];

if (data.type === 'i1') {

line.unsigned = true;

return;

}

var total = data.uses;

if (total === 0) return;

var obj = { ident: line.assignTo, found: 0, unsigned: 0, signed: 0, total: total };

// in loops with phis, we can also be used *before* we are defined

var j = i-1, k = i+1;

while(1) {

assert(j >= 0 || k < func.lines.length, 'Signalyzer ran out of space to look for sign indications for line ' + line.lineNum);

if (j >= 0 && walkInterdata(func.lines[j], seekIdent, seekMathop, obj)) break;

if (k < func.lines.length && walkInterdata(func.lines[k], seekIdent, seekMathop, obj)) break;

if (obj.total && obj.found >= obj.total) break; // see comment below

j -= 1;

k += 1;

}

// unsigned+signed might be < total, since the same ident can appear multiple times in the same mathop.

// found can actually be > total, since we currently have the same ident in a GEP (see cubescript test)