diff options
Diffstat (limited to 'src/analyzer.js')
| -rw-r--r-- | src/analyzer.js | 2766 |
1 files changed, 1366 insertions, 1400 deletions
diff --git a/src/analyzer.js b/src/analyzer.js index b20dedff..3fb20253 100644 --- a/src/analyzer.js +++ b/src/analyzer.js @@ -27,82 +27,72 @@ var SHADOW_FLIP = { i64: 'double', double: 'i64' }; //, i32: 'float', float: 'i3 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'); + var item = { items: data }; + var data = item; + + var newTypes = {}; + + // Gather + // 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; + newTypes[type.name_] = 1; + if (QUANTUM_SIZE === 1) { + Types.fatTypes[type.name_] = copy(type); } }); - // 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 in LABEL_ENDERS) { - currLabelFinished = true; - } - } else { - print('// WARNING: content after a branch in a label, line: ' + subItem.lineNum); - } - } else { - throw 'ERROR: what is this? ' + dump(subItem); + // Functions & labels + item.functions = []; + var currLabelFinished = false; // 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 in LABEL_ENDERS) { + currLabelFinished = true; } + } else { + print('// WARNING: content after a branch in a label, line: ' + subItem.lineNum); } - delete item.items; - this.forwardItem(item, 'CastAway'); + } else { + throw 'ERROR: what is this? ' + dump(subItem); } - }); + } + delete item.items; // CastAway - try to remove bitcasts of double<-->i64, which LLVM sometimes generates unnecessarily // (load a double, convert to i64, use as i64). @@ -113,75 +103,72 @@ function analyzer(data, sidePass) { // Note that aside from being an optimization, this is needed for correctness in some cases: If code // assumes it can bitcast a double to an i64 and back and forth without loss, that may be violated // due to NaN canonicalization. - substrate.addActor('CastAway', { - processItem: function(item) { - this.forwardItem(item, 'Legalizer'); - if (USE_TYPED_ARRAYS != 2) return; + function castAway() { + if (USE_TYPED_ARRAYS != 2) return; - item.functions.forEach(function(func) { - var has = false; - func.labels.forEach(function(label) { - var lines = label.lines; - for (var i = 0; i < lines.length; i++) { - var line = lines[i]; - if (line.intertype == 'bitcast' && line.type in SHADOW_FLIP) { - has = true; - } + item.functions.forEach(function(func) { + var has = false; + func.labels.forEach(function(label) { + var lines = label.lines; + for (var i = 0; i < lines.length; i++) { + var line = lines[i]; + if (line.intertype == 'bitcast' && line.type in SHADOW_FLIP) { + has = true; } - }); - if (!has) return; - // there are integer<->floating-point bitcasts, create shadows for everything - var shadowed = {}; - func.labels.forEach(function(label) { - var lines = label.lines; - var i = 0; - while (i < lines.length) { - var lines = label.lines; - var line = lines[i]; - if (line.intertype == 'load' && line.type in SHADOW_FLIP) { - if (line.pointer.intertype != 'value') { i++; continue } // TODO - shadowed[line.assignTo] = 1; - var shadow = line.assignTo + '$$SHADOW'; - var flip = SHADOW_FLIP[line.type]; - lines.splice(i + 1, 0, { // if necessary this element will be legalized in the next phase - tokens: null, - indent: 2, - lineNum: line.lineNum + 0.5, - assignTo: shadow, - intertype: 'load', - pointerType: flip + '*', - type: flip, - valueType: flip, - pointer: { - intertype: 'value', - ident: line.pointer.ident, - type: flip + '*' - }, - align: line.align, - ident: line.ident - }); - // note: no need to update func.lines, it is generated in a later pass - i++; - } + } + }); + if (!has) return; + // there are integer<->floating-point bitcasts, create shadows for everything + var shadowed = {}; + func.labels.forEach(function(label) { + var lines = label.lines; + var i = 0; + while (i < lines.length) { + var lines = label.lines; + var line = lines[i]; + if (line.intertype == 'load' && line.type in SHADOW_FLIP) { + if (line.pointer.intertype != 'value') { i++; continue } // TODO + shadowed[line.assignTo] = 1; + var shadow = line.assignTo + '$$SHADOW'; + var flip = SHADOW_FLIP[line.type]; + lines.splice(i + 1, 0, { // if necessary this element will be legalized in the next phase + tokens: null, + indent: 2, + lineNum: line.lineNum + 0.5, + assignTo: shadow, + intertype: 'load', + pointerType: flip + '*', + type: flip, + valueType: flip, + pointer: { + intertype: 'value', + ident: line.pointer.ident, + type: flip + '*' + }, + align: line.align, + ident: line.ident + }); + // note: no need to update func.lines, it is generated in a later pass i++; } - }); - // use shadows where possible - func.labels.forEach(function(label) { - var lines = label.lines; - for (var i = 0; i < lines.length; i++) { - var line = lines[i]; - if (line.intertype == 'bitcast' && line.type in SHADOW_FLIP && line.ident in shadowed) { - var shadow = line.ident + '$$SHADOW'; - line.params[0].ident = shadow; - line.params[0].type = line.type; - line.type2 = line.type; - } + i++; + } + }); + // use shadows where possible + func.labels.forEach(function(label) { + var lines = label.lines; + for (var i = 0; i < lines.length; i++) { + var line = lines[i]; + if (line.intertype == 'bitcast' && line.type in SHADOW_FLIP && line.ident in shadowed) { + var shadow = line.ident + '$$SHADOW'; + line.params[0].ident = shadow; + line.params[0].type = line.type; + line.type2 = line.type; } - }); + } }); - } - }); + }); + } // Legalize LLVM unrealistic types into realistic types. // @@ -196,727 +183,724 @@ function analyzer(data, sidePass) { // 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, allowLegal) { - bits = bits || 32; // things like pointers are all i32, but show up as 0 bits from getBits - if (allowLegal && bits <= 32) return [{ ident: base + ('i' + bits in Runtime.INT_TYPES ? '' : '$0'), bits: bits }]; - if (isNumber(base)) return getLegalLiterals(base, bits); - if (base[0] == '{') { - warnOnce('seeing source of illegal data ' + base + ', likely an inline struct - assuming zeroinit'); - return getLegalLiterals('0', bits); - } - var ret = new Array(Math.ceil(bits/32)); - var i = 0; - if (base == 'zeroinitializer' || base == 'undef') base = 0; - while (bits > 0) { - ret[i] = { ident: base ? base + '$' + i : '0', 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; + function legalizer() { + // Legalization + if (USE_TYPED_ARRAYS == 2) { + function getLegalVars(base, bits, allowLegal) { + bits = bits || 32; // things like pointers are all i32, but show up as 0 bits from getBits + if (allowLegal && bits <= 32) return [{ ident: base + ('i' + bits in Runtime.INT_TYPES ? '' : '$0'), bits: bits }]; + if (isNumber(base)) return getLegalLiterals(base, bits); + if (base[0] == '{') { + warnOnce('seeing source of illegal data ' + base + ', likely an inline struct - assuming zeroinit'); + return getLegalLiterals('0', bits); } - function getLegalStructuralParts(value) { - return value.params.slice(0); + var ret = new Array(Math.ceil(bits/32)); + var i = 0; + if (base == 'zeroinitializer' || base == 'undef') base = 0; + while (bits > 0) { + ret[i] = { ident: base ? base + '$' + i : '0', bits: Math.min(32, bits) }; + bits -= 32; + i++; } - function getLegalParams(params, bits) { - return params.map(function(param) { - var value = param.value || param; - if (isNumber(value.ident)) { - return getLegalLiterals(value.ident, bits); - } else if (value.intertype == 'structvalue') { - return getLegalStructuralParts(value).map(function(part) { - return { ident: part.ident, bits: part.type.substr(1) }; - }); - } else { - return getLegalVars(value.ident, bits); - } - }); + 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++; } - // 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); - assert(k == 0 || toAdd[k].lineNum > toAdd[k-1].lineNum); + return ret; + } + function getLegalStructuralParts(value) { + return value.params.slice(0); + } + function getLegalParams(params, bits) { + return params.map(function(param) { + var value = param.value || param; + if (isNumber(value.ident)) { + return getLegalLiterals(value.ident, bits); + } else if (value.intertype == 'structvalue') { + return getLegalStructuralParts(value).map(function(part) { + return { ident: part.ident, bits: part.type.substr(1) }; + }); + } else { + return getLegalVars(value.ident, bits); } + }); + } + // 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); + assert(k == 0 || toAdd[k].lineNum > toAdd[k-1].lineNum); } - function removeAndAdd(lines, i, toAdd) { - var item = lines[i]; - interpLines(lines, i, toAdd); - Array.prototype.splice.apply(lines, [i, 1].concat(toAdd)); - if (i > 0) assert(lines[i].lineNum > lines[i-1].lineNum); - if (i + toAdd.length < lines.length) assert(lines[i + toAdd.length - 1].lineNum < lines[i + toAdd.length].lineNum); - 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; - } else if (param.intertype == 'structvalue') { - // 'flatten' out the struct into scalars - var toAdd = param.params; - toAdd.forEach(function(param) { - param.byval = 0; - }); - Array.prototype.splice.apply(params, [i, 1].concat(toAdd)); - continue; // do not increment i; proceed to process the new params - } - i++; + } + function removeAndAdd(lines, i, toAdd) { + var item = lines[i]; + interpLines(lines, i, toAdd); + Array.prototype.splice.apply(lines, [i, 1].concat(toAdd)); + if (i > 0) assert(lines[i].lineNum > lines[i-1].lineNum); + if (i + toAdd.length < lines.length) assert(lines[i + toAdd.length - 1].lineNum < lines[i + toAdd.length].lineNum); + 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; + } else if (param.intertype == 'structvalue') { + // 'flatten' out the struct into scalars + var toAdd = param.params; + toAdd.forEach(function(param) { + param.byval = 0; + }); + Array.prototype.splice.apply(params, [i, 1].concat(toAdd)); + continue; // do not increment i; proceed to process the new params } + 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'; - } + } + 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) { - if (dcheck('legalizer')) dprint('zz legalizing: \n' + dump(label.lines)); - 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'; - } - } else if (item.intertype == 'inttoptr') { - var input = item.params[0]; - if (input.type == 'i64') input.type = 'i32'; // inttoptr can only care about 32 bits anyhow since pointers are 32-bit - } - if (isIllegalType(item.valueType) || isIllegalType(item.type)) { - isIllegal = true; - } else if ((item.intertype == 'load' || item.intertype == 'store') && isStructType(item.valueType)) { - isIllegal = true; // storing an entire structure is illegal - } else if (item.intertype == 'mathop' && item.op == 'trunc' && isIllegalType(item.params[1].ident)) { // trunc stores target value in second ident - isIllegal = true; + } + data.functions.forEach(function(func) { + // Legalize function params + legalizeFunctionParameters(func.params); + // Legalize lines in labels + var tempId = 0; + func.labels.forEach(function(label) { + if (dcheck('legalizer')) dprint('zz legalizing: \n' + dump(label.lines)); + 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 (!isIllegal) { - //if (dcheck('legalizer')) dprint('no need to legalize \n' + dump(item)); - i++; - continue; + } else if (item.intertype == 'inttoptr') { + var input = item.params[0]; + if (input.type == 'i64') input.type = 'i32'; // inttoptr can only care about 32 bits anyhow since pointers are 32-bit } - // 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' || subItem.intertype == 'structvalue' || subItem.intertype in PARSABLE_LLVM_FUNCTIONS, 'We can only unfold some expressions in phis'); - // we must handle this in the phi itself, if we unfold normally it will not be pushed back with the phi - } else { + if (isIllegalType(item.valueType) || isIllegalType(item.type)) { + isIllegal = true; + } else if ((item.intertype == 'load' || item.intertype == 'store') && isStructType(item.valueType)) { + isIllegal = true; // storing an entire structure is illegal + } else if (item.intertype == 'mathop' && item.op == 'trunc' && isIllegalType(item.params[1].ident)) { // trunc stores target value in second ident + isIllegal = true; + } + }); + if (!isIllegal) { + //if (dcheck('legalizer')) dprint('no need to legalize \n' + dump(item)); + 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' || subItem.intertype == 'structvalue' || subItem.intertype in PARSABLE_LLVM_FUNCTIONS, 'We can only unfold some expressions 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 = '$$etemp$' + (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 = '$$etemp$' + (tempId++); - subItem.assignTo = tempIdent; - unfolded.unshift(subItem); - fixUnfolded(subItem); - return { intertype: 'value', ident: tempIdent, type: subItem.type }; + unfolded.unshift({ + assignTo: tempIdent, + intertype: 'value', + ident: switchLabel.value, + type: subItem.type + }); + switchLabel.value = tempIdent; } - } else if (subItem.intertype == 'switch' && isIllegalType(subItem.type)) { - subItem.switchLabels.forEach(function(switchLabel) { - if (switchLabel.value[0] != '$') { - var tempIdent = '$$etemp$' + (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); + var finalizer = null; + switch (item.intertype) { + case 'store': { + var toAdd = []; + bits = getBits(item.valueType); + var elements = getLegalParams([item.value], bits)[0]; + var j = 0; + elements.forEach(function(element) { + var tempVar = '$st$' + (tempId++) + '$' + 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' } + ], }); - } - }); - 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 + 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; } - // This is an illegal-containing line, and it is unfolded. Legalize it now - dprint('legalizer', 'Legalizing ' + item.intertype + ' at line ' + item.lineNum); - var finalizer = null; - switch (item.intertype) { - case 'store': { - var toAdd = []; - bits = getBits(item.valueType); - var elements = getLegalParams([item.value], bits)[0]; - var j = 0; - elements.forEach(function(element) { - var tempVar = '$st$' + (tempId++) + '$' + 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 + // call, return: Return the first 32 bits, the rest are in temp + case 'call': { + var toAdd = [value]; + // legalize parameters + legalizeFunctionParameters(value.params); + // legalize return value, if any + var returnType = getReturnType(item.type); + if (value.assignTo && isIllegalType(returnType)) { + bits = getBits(returnType); + var elements = getLegalVars(item.assignTo, bits); + // legalize return value + value.assignTo = elements[0].ident; + for (var j = 1; j < elements.length; j++) { + var element = elements[j]; 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, + intertype: 'value', + assignTo: element.ident, + type: element.bits, + ident: 'tempRet' + (j - 1) }); - j++; - }); - Types.needAnalysis['[0 x i32]'] = 0; - i += removeAndAdd(label.lines, i, toAdd); - continue; - } - // call, return: Return the first 32 bits, the rest are in temp - case 'call': { - var toAdd = [value]; - // legalize parameters - legalizeFunctionParameters(value.params); - // legalize return value, if any - var returnType = getReturnType(item.type); - if (value.assignTo && isIllegalType(returnType)) { - bits = getBits(returnType); - var elements = getLegalVars(item.assignTo, bits); - // legalize return value - value.assignTo = elements[0].ident; - for (var j = 1; j < elements.length; j++) { - var element = elements[j]; - toAdd.push({ - intertype: 'value', - assignTo: element.ident, - type: element.bits, - ident: 'tempRet' + (j - 1) - }); - assert(j<10); // TODO: dynamically create more than 10 tempRet-s - } + assert(j<10); // TODO: dynamically create more than 10 tempRet-s } - i += removeAndAdd(label.lines, i, toAdd); - continue; } - case 'landingpad': { - // not much to legalize - i++; - continue; - } - case 'return': { - bits = getBits(item.type); - var elements = getLegalVars(item.value.ident, bits); - item.value.ident = '('; - for (var j = 1; j < elements.length; j++) { - item.value.ident += 'tempRet' + (j-1) + '=' + elements[j].ident + ','; - } - item.value.ident += elements[0].ident + ')'; - i++; - continue; + i += removeAndAdd(label.lines, i, toAdd); + continue; + } + case 'landingpad': { + // not much to legalize + i++; + continue; + } + case 'return': { + bits = getBits(item.type); + var elements = getLegalVars(item.value.ident, bits); + item.value.ident = '('; + for (var j = 1; j < elements.length; j++) { + item.value.ident += 'tempRet' + (j-1) + '=' + elements[j].ident + ','; } - 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; + item.value.ident += elements[0].ident + ')'; + 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 'structvalue': { + bits = getBits(value.type); + var elements = getLegalVars(item.assignTo, bits); + var toAdd = []; + for (var j = 0; j < item.params.length; j++) { + toAdd[j] = { + intertype: 'value', + assignTo: elements[j].ident, + type: 'i32', + ident: item.params[j].ident + }; } - 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 = '$ld$' + (tempId++) + '$' + 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' } + ] }); - i += removeAndAdd(label.lines, i, toAdd); - continue; - } - case 'structvalue': { - bits = getBits(value.type); - var elements = getLegalVars(item.assignTo, bits); - var toAdd = []; - for (var j = 0; j < item.params.length; j++) { - toAdd[j] = { - intertype: 'value', - assignTo: elements[j].ident, - type: 'i32', - ident: item.params[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 = '$ld$' + (tempId++) + '$' + 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 newItem = { - intertype: 'load', + var newItem = { + intertype: 'load', + assignTo: element.ident, + pointerType: 'i32*', + valueType: 'i32', + type: 'i32', + pointer: { intertype: 'value', ident: tempVar, type: 'i32*' }, + ident: tempVar, + align: value.align + }; + var newItem2 = null; + // The last one may be smaller than 32 bits + if (element.bits < 32) { + newItem.assignTo += '$preadd$'; + newItem2 = { + intertype: 'mathop', + op: 'and', assignTo: element.ident, - pointerType: 'i32*', - valueType: 'i32', type: 'i32', - pointer: { intertype: 'value', ident: tempVar, type: 'i32*' }, - ident: tempVar, - align: value.align - }; - var newItem2 = null; - // The last one may be smaller than 32 bits - if (element.bits < 32) { - newItem.assignTo += '$preadd$'; - newItem2 = { - intertype: 'mathop', - op: 'and', - assignTo: element.ident, + params: [{ + intertype: 'value', type: 'i32', - params: [{ - intertype: 'value', - type: 'i32', - ident: newItem.assignTo - }, { - intertype: 'value', - type: 'i32', - ident: (0xffffffff >>> (32 - element.bits)).toString() - }], - }; - } - toAdd.push(newItem); - if (newItem2) toAdd.push(newItem2); - 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 values = getLegalParams(value.params, bits); - elements.forEach(function(element) { - var k = 0; - 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: values[k++][j].ident, - type: 'i' + element.bits, - } - }; - }) - }); - j++; - }); - i += removeAndAdd(label.lines, i, toAdd); - continue; - } - case 'switch': { - i++; - continue; // special case, handled in makeComparison - } - case 'va_arg': { - assert(value.type == 'i64'); - assert(value.value.type == 'i32*', value.value.type); - i += removeAndAdd(label.lines, i, range(2).map(function(x) { - return { - intertype: 'va_arg', - assignTo: value.assignTo + '$' + x, - type: 'i32', - value: { + ident: newItem.assignTo + }, { intertype: 'value', - ident: value.value.ident, // We read twice from the same i32* var, incrementing // + '$' + x, - type: 'i32*' - } + type: 'i32', + ident: (0xffffffff >>> (32 - element.bits)).toString() + }], }; - })); - continue; - } - case 'extractvalue': { // XXX we assume 32-bit alignment in extractvalue/insertvalue, - // but in theory they can run on packed structs too (see use getStructuralTypePartBits) - // potentially legalize the actual extracted value too if it is >32 bits, not just the extraction in general - var index = item.indexes[0][0].text; - var parts = getStructureTypeParts(item.type); - var indexedType = parts[index]; - var targetBits = getBits(indexedType); - var sourceBits = getBits(item.type); - var elements = getLegalVars(item.assignTo, targetBits, true); // possibly illegal - var sourceElements = getLegalVars(item.ident, sourceBits); // definitely illegal - var toAdd = []; - var sourceIndex = 0; - for (var partIndex = 0; partIndex < parts.length; partIndex++) { - if (partIndex == index) { - for (var j = 0; j < elements.length; j++) { - toAdd.push({ - intertype: 'value', - assignTo: elements[j].ident, - type: 'i' + elements[j].bits, - ident: sourceElements[sourceIndex+j].ident - }); - } - break; - } - sourceIndex += getStructuralTypePartBits(parts[partIndex])/32; } - i += removeAndAdd(label.lines, i, toAdd); - continue; - } - case 'insertvalue': { - var index = item.indexes[0][0].text; // the modified index - var parts = getStructureTypeParts(item.type); - var indexedType = parts[index]; - var indexBits = getBits(indexedType); - var bits = getBits(item.type); // source and target - bits = getBits(value.type); - var toAdd = []; - var elements = getLegalVars(item.assignTo, bits); - var sourceElements = getLegalVars(item.ident, bits); - var indexElements = getLegalVars(item.value.ident, indexBits, true); // possibly legal - var sourceIndex = 0; - for (var partIndex = 0; partIndex < parts.length; partIndex++) { - var currNum = getStructuralTypePartBits(parts[partIndex])/32; - for (var j = 0; j < currNum; j++) { + toAdd.push(newItem); + if (newItem2) toAdd.push(newItem2); + 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 values = getLegalParams(value.params, bits); + elements.forEach(function(element) { + var k = 0; + 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: values[k++][j].ident, + type: 'i' + element.bits, + } + }; + }) + }); + j++; + }); + i += removeAndAdd(label.lines, i, toAdd); + continue; + } + case 'switch': { + i++; + continue; // special case, handled in makeComparison + } + case 'va_arg': { + assert(value.type == 'i64'); + assert(value.value.type == 'i32*', value.value.type); + i += removeAndAdd(label.lines, i, range(2).map(function(x) { + return { + intertype: 'va_arg', + assignTo: value.assignTo + '$' + x, + type: 'i32', + value: { + intertype: 'value', + ident: value.value.ident, // We read twice from the same i32* var, incrementing // + '$' + x, + type: 'i32*' + } + }; + })); + continue; + } + case 'extractvalue': { // XXX we assume 32-bit alignment in extractvalue/insertvalue, + // but in theory they can run on packed structs too (see use getStructuralTypePartBits) + // potentially legalize the actual extracted value too if it is >32 bits, not just the extraction in general + var index = item.indexes[0][0].text; + var parts = getStructureTypeParts(item.type); + var indexedType = parts[index]; + var targetBits = getBits(indexedType); + var sourceBits = getBits(item.type); + var elements = getLegalVars(item.assignTo, targetBits, true); // possibly illegal + var sourceElements = getLegalVars(item.ident, sourceBits); // definitely illegal + var toAdd = []; + var sourceIndex = 0; + for (var partIndex = 0; partIndex < parts.length; partIndex++) { + if (partIndex == index) { + for (var j = 0; j < elements.length; j++) { toAdd.push({ intertype: 'value', - assignTo: elements[sourceIndex+j].ident, - type: 'i' + elements[sourceIndex+j].bits, - ident: partIndex == index ? indexElements[j].ident : sourceElements[sourceIndex+j].ident + assignTo: elements[j].ident, + type: 'i' + elements[j].bits, + ident: sourceElements[sourceIndex+j].ident }); } - sourceIndex += currNum; + break; } - i += removeAndAdd(label.lines, i, toAdd); - continue; + sourceIndex += getStructuralTypePartBits(parts[partIndex])/32; } - 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 + i += removeAndAdd(label.lines, i, toAdd); + continue; + } + case 'insertvalue': { + var index = item.indexes[0][0].text; // the modified index + var parts = getStructureTypeParts(item.type); + var indexedType = parts[index]; + var indexBits = getBits(indexedType); + var bits = getBits(item.type); // source and target + bits = getBits(value.type); + var toAdd = []; + var elements = getLegalVars(item.assignTo, bits); + var sourceElements = getLegalVars(item.ident, bits); + var indexElements = getLegalVars(item.value.ident, indexBits, true); // possibly legal + var sourceIndex = 0; + for (var partIndex = 0; partIndex < parts.length; partIndex++) { + var currNum = getStructuralTypePartBits(parts[partIndex])/32; + for (var j = 0; j < currNum; j++) { + toAdd.push({ + intertype: 'value', + assignTo: elements[sourceIndex+j].ident, + type: 'i' + elements[sourceIndex+j].bits, + ident: partIndex == index ? indexElements[j].ident : sourceElements[sourceIndex+j].ident + }); } - // fall through + sourceIndex += currNum; } - 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 + i += removeAndAdd(label.lines, i, toAdd); + continue; + } + 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 } - 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': { - if (!sourceBits) { - // we can be asked to bitcast doubles or such to integers, handle that as best we can (if it's a double that - // was an x86_fp80, this code will likely break when called) - sourceBits = targetBits = Runtime.getNativeTypeSize(value.params[0].type); - warn('legalizing non-integer bitcast on ll #' + item.lineNum); - } - break; - } - case 'select': { - sourceBits = targetBits = getBits(value.params[1].type); - var params = getLegalParams(value.params.slice(1), sourceBits); - processor = function(result, j) { - return { - intertype: 'mathop', - op: 'select', - type: 'i' + params[0][j].bits, - params: [ - value.params[0], - { intertype: 'value', ident: params[0][j].ident, type: 'i' + params[0][j].bits }, - { intertype: 'value', ident: params[1][j].ident, type: 'i' + params[1][j].bits } - ] - }; - }; - break; - } - case 'or': case 'and': case 'xor': case 'icmp': { - var otherElements = getLegalVars(value.params[1].ident, sourceBits); - processor = function(result, j) { - return { - intertype: 'mathop', - op: value.op, - variant: value.variant, - type: 'i' + otherElements[j].bits, - params: [ - result, - { intertype: 'value', ident: otherElements[j].ident, type: 'i' + otherElements[j].bits } - ] - }; - }; - if (value.op == 'icmp') { - if (sourceBits == 64) { // handle the i64 case in processMathOp, where we handle full i64 math - i++; - continue; - } - finalizer = function() { - var ident = ''; - for (var i = 0; i < targetElements.length; i++) { - if (i > 0) { - switch(value.variant) { - case 'eq': ident += '&'; break; - case 'ne': ident += '|'; break; - default: throw 'unhandleable illegal icmp: ' + value.variant; - } - } - ident += targetElements[i].ident; - } - return { - intertype: 'value', - ident: ident, - type: 'rawJS', - assignTo: item.assignTo - }; - } - } - break; - } - case 'add': case 'sub': case 'sdiv': case 'udiv': case 'mul': case 'urem': case 'srem': { - if (sourceBits < 32) { - // when we add illegal types like i24, we must work on the singleton chunks - item.assignTo += '$0'; - item.params[0].ident += '$0'; - item.params[1].ident += '$0'; - } - // fall through - } - case 'uitofp': case 'sitofp': case 'fptosi': case 'fptoui': { - // 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)]; + // 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 } - // Do the legalization - var sourceElements = getLegalVars(value.params[0].ident, sourceBits, true); - 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'); - assert(PRECISE_I64_MATH, 'Must have precise i64 math for non-constant 64-bit shifts'); - Types.preciseI64MathUsed = 1; - value.intertype = 'value'; - value.ident = 'var ' + value.assignTo + '$0 = ' + - asmCoercion('_bitshift64' + value.op[0].toUpperCase() + value.op.substr(1) + '(' + - asmCoercion(sourceElements[0].ident, 'i32') + ',' + - asmCoercion(sourceElements[1].ident, 'i32') + ',' + - asmCoercion(value.params[1].ident + '$0', 'i32') + ')', 'i32' - ) + ';' + - 'var ' + value.assignTo + '$1 = tempRet0;'; - value.assignTo = null; - i++; - continue; + case 'lshr': { + shifts = parseInt(value.params[1].ident); + break; } - 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 = '(' + makeSignOp(sourceElements[sourceElements.length-1].ident, 'i' + sourceElements[sourceElements.length-1].bits, 're', 1, 1) + ' < 0 ? -1 : 0)'; - var signedKeepAlive = { intertype: 'value', ident: sourceElements[sourceElements.length-1].ident, type: 'i32' }; + case 'shl': { + shifts = -parseInt(value.params[1].ident); + break; } - 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 && sourceBits < 32) { - // zext sign correction - result.ident = makeSignOp(result.ident, 'i' + sourceBits, isUnsignedOp(value.op) ? 'un' : 're', 1, 1); + 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': { + if (!sourceBits) { + // we can be asked to bitcast doubles or such to integers, handle that as best we can (if it's a double that + // was an x86_fp80, this code will likely break when called) + sourceBits = targetBits = Runtime.getNativeTypeSize(value.params[0].type); + warn('legalizing non-integer bitcast on ll #' + item.lineNum); } - 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 = { + break; + } + case 'select': { + sourceBits = targetBits = getBits(value.params[1].type); + var params = getLegalParams(value.params.slice(1), sourceBits); + processor = function(result, j) { + return { intertype: 'mathop', - op: shiftOp, - type: 'i32', + op: 'select', + type: 'i' + params[0][j].bits, params: [ - other, - { intertype: 'value', ident: (32 - fraction).toString(), type: 'i32' } + value.params[0], + { intertype: 'value', ident: params[0][j].ident, type: 'i' + params[0][j].bits }, + { intertype: 'value', ident: params[1][j].ident, type: 'i' + params[1][j].bits } ] }; - result = { + }; + break; + } + case 'or': case 'and': case 'xor': case 'icmp': { + var otherElements = getLegalVars(value.params[1].ident, sourceBits); + processor = function(result, j) { + return { 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', + op: value.op, + variant: value.variant, + type: 'i' + otherElements[j].bits, params: [ result, - { intertype: 'value', ident: fraction.toString(), type: 'i32' } + { intertype: 'value', ident: otherElements[j].ident, type: 'i' + otherElements[j].bits } ] }; - result = { - intertype: 'mathop', - op: 'or', - type: 'i32', - params: [ - result, - other - ] + }; + if (value.op == 'icmp') { + if (sourceBits == 64) { // handle the i64 case in processMathOp, where we handle full i64 math + i++; + continue; } - } - 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' } - ] + finalizer = function() { + var ident = ''; + for (var i = 0; i < targetElements.length; i++) { + if (i > 0) { + switch(value.variant) { + case 'eq': ident += '&'; break; + case 'ne': ident += '|'; break; + default: throw 'unhandleable illegal icmp: ' + value.variant; + } + } + ident += targetElements[i].ident; + } + return { + intertype: 'value', + ident: ident, + type: 'rawJS', + assignTo: item.assignTo + }; } } - if (processor) { - result = processor(result, j); + break; + } + case 'add': case 'sub': case 'sdiv': case 'udiv': case 'mul': case 'urem': case 'srem': { + if (sourceBits < 32) { + // when we add illegal types like i24, we must work on the singleton chunks + item.assignTo += '$0'; + item.params[0].ident += '$0'; + item.params[1].ident += '$0'; } - result.assignTo = targetElements[j].ident; - toAdd.push(result); + // fall through } - if (targetBits <= 32) { - // We are generating a normal legal type here - legalValue = { + case 'uitofp': case 'sitofp': case 'fptosi': case 'fptoui': { + // 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 = getLegalVars(value.params[0].ident, sourceBits, true); + 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'); + assert(PRECISE_I64_MATH, 'Must have precise i64 math for non-constant 64-bit shifts'); + Types.preciseI64MathUsed = 1; + value.intertype = 'value'; + value.ident = 'var ' + value.assignTo + '$0 = ' + + asmCoercion('_bitshift64' + value.op[0].toUpperCase() + value.op.substr(1) + '(' + + asmCoercion(sourceElements[0].ident, 'i32') + ',' + + asmCoercion(sourceElements[1].ident, 'i32') + ',' + + asmCoercion(value.params[1].ident + '$0', 'i32') + ')', 'i32' + ) + ';' + + 'var ' + value.assignTo + '$1 = tempRet0;'; + value.assignTo = null; + 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 = '(' + makeSignOp(sourceElements[sourceElements.length-1].ident, 'i' + sourceElements[sourceElements.length-1].bits, 're', 1, 1) + ' < 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 && sourceBits < 32) { + // zext sign correction + result.ident = makeSignOp(result.ident, 'i' + sourceBits, isUnsignedOp(value.op) ? 'un' : 're', 1, 1); + } + if (fraction != 0) { + var other = { intertype: 'value', - ident: targetElements[0].ident + (targetBits < 32 ? '&' + (Math.pow(2, targetBits)-1) : ''), - type: 'rawJS' + 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' } + ] }; - legalValue.assignTo = item.assignTo; - toAdd.push(legalValue); - } else if (finalizer) { - toAdd.push(finalizer()); + 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 + ] + } } - i += removeAndAdd(label.lines, i, toAdd); - continue; + 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); + } else if (finalizer) { + toAdd.push(finalizer()); + } + 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); + assert(0, 'Could not legalize illegal line: ' + [item.lineNum, dump(item)]); + } + if (dcheck('legalizer')) dprint('zz legalized: \n' + dump(label.lines)); }); }); - this.forwardItem(data, 'Typevestigator'); } - }); - function addTypeInternal(type, data) { + // 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); + }); + }); + } + + function addTypeInternal(type) { if (type.length == 1) return; if (Types.types[type]) return; if (['internal', 'hidden', 'inbounds', 'void'].indexOf(type) != -1) return; @@ -927,8 +911,9 @@ function analyzer(data, sidePass) { // to look at the underlying type - it was not defined explicitly // anywhere else. var nonPointing = removeAllPointing(type); + if (Types.types[nonPointing]) return; var check = /^\[(\d+)\ x\ (.*)\]$/.exec(nonPointing); - if (check && !Types.types[nonPointing]) { + if (check) { 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 @@ -936,7 +921,7 @@ function analyzer(data, sidePass) { // 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) + addTypeInternal(subType); // needed for anonymous structure definitions (see below) // Huge structural types are represented very inefficiently, both here and in generated JS. Best to avoid them - for example static char x[10*1024*1024]; is bad, while static char *x = malloc(10*1024*1024) is fine. if (num >= 10*1024*1024) warnOnce('warning: very large fixed-size structural type: ' + type + ' - can you reduce it? (compilation may be slow)'); @@ -945,6 +930,7 @@ function analyzer(data, sidePass) { fields: range(num).map(function() { return subType }), lineNum: '?' }; + newTypes[nonPointing] = 1; // Also add a |[0 x type]| type var zerod = '[0 x ' + subType + ']'; if (!Types.types[zerod]) { @@ -953,6 +939,7 @@ function analyzer(data, sidePass) { fields: [subType, subType], // Two, so we get the flatFactor right. We care about the flatFactor, not the size here lineNum: '?' }; + newTypes[zerod] = 1; } return; } @@ -983,6 +970,7 @@ function analyzer(data, sidePass) { packed: packed, lineNum: '?' }; + newTypes[type] = 1; return; } @@ -994,251 +982,243 @@ function analyzer(data, sidePass) { flatSize: 1, lineNum: '?' }; + newTypes[type] = 1; } - function addType(type, data) { - addTypeInternal(type, data); + function addType(type) { + addTypeInternal(type); if (QUANTUM_SIZE === 1) { Types.flipTypes(); - addTypeInternal(type, data); + addTypeInternal(type); 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 = {}; + function typevestigator() { + 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); } - this.forwardItem(data, 'Typeanalyzer'); + Types.needAnalysis = {}; } - }); + } // 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); + function analyzeTypes(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 newTypes) { + var type = types[typeName]; + if (type.flatIndexes) continue; + var ready = true; + type.fields.forEach(function(field) { + if (isStructType(field)) { + if (!types[field]) { + addType(field); + ready = false; + } else { + if (!types[field].flatIndexes) { + newTypes[field] = 1; 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 (!ready) { + more = true; + continue; } - } - 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(); - } + Runtime.calculateStructAlignment(type); - if (!fatTypes) { - this.forwardItem(item, 'VariableAnalyzer'); + 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(true); + Runtime.QUANTUM_SIZE = trueQuantumSize; + Types.flipTypes(); + } + + newTypes = null; + } // 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 variableAnalyzer() { + // 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') { + if (func.variables[param.ident]) warn('cannot have duplicate variable names: ' + param.ident); // toNiceIdent collisions? + func.variables[param.ident] = { + ident: param.ident, + type: param.type, + origin: 'funcparam', + lineNum: func.lineNum, + rawLinesIndex: -1 + }; + } }); - // 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') { - if (func.variables[param.ident]) warn('cannot have duplicate variable names: ' + param.ident); // toNiceIdent collisions? - 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) { + if (func.variables[item.assignTo]) warn('cannot have duplicate variable names: ' + item.assignTo); // toNiceIdent collisions? + 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; } - }); - - // Normal variables - func.lines.forEach(function(item, i) { - if (item.assignTo) { - if (func.variables[item.assignTo]) warn('cannot have duplicate variable names: ' + item.assignTo); // toNiceIdent collisions? - 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 (variable.origin === 'call') { - variable.type = getReturnType(variable.type); - } + if (variable.origin === 'call') { + variable.type = getReturnType(variable.type); } - }); + } + }); - 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); + 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 + // Analyze variable uses - function analyzeVariableUses() { - dprint('vars', 'Analyzing variables for ' + func.ident + '\n'); + function analyzeVariableUses() { + dprint('vars', 'Analyzing variables for ' + func.ident + '\n'); - for (vname in func.variables) { - var variable = func.variables[vname]; + 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; + // 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.pointingLevels = pointingLevels(variable.type); - variable.uses = 0; - } + 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; - } + // 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--; - }); + } + }, function(item) { + if (item.intertype == 'noop') inNoop--; }); + }); - //if (dcheck('vars')) dprint('analyzed variables: ' + dump(func.variables)); - } - - analyzeVariableUses(); - - // Decision time + //if (dcheck('vars')) dprint('analyzed variables: ' + dump(func.variables)); + } - 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)); + 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; } - }); - this.forwardItem(item, 'Signalyzer'); - } - }); + if (dcheck('vars')) dprint('// var ' + vname + ': ' + JSON.stringify(variable)); + } + }); + } // Sign analyzer // @@ -1251,214 +1231,208 @@ function analyzer(data, sidePass) { // 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 || CORRECT_SIGNS == 1) return; - - function seekIdent(item, obj) { - if (item.ident === obj.ident) { - obj.found++; - } + function signalyzer() { + if (USE_TYPED_ARRAYS != 2 || CORRECT_SIGNS == 1) 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++; - } + 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; - } + 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; + } - // 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) - // in the GEP item, and a child item (we have the ident copied onto the GEP item as a convenience). - // probably not a bug-causer, but FIXME. see also a reference to this above - // we also leave the loop above potentially early due to this. otherwise, though, we end up scanning the - // entire function in some cases which is very slow - assert(obj.found >= obj.total, 'Could not Signalyze line ' + line.lineNum); - line.unsigned = obj.unsigned > 0; - dprint('vars', 'Signalyzer: ' + line.assignTo + ' has unsigned == ' + line.unsigned + ' (line ' + line.lineNum + ')'); + 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) + // in the GEP item, and a child item (we have the ident copied onto the GEP item as a convenience). + // probably not a bug-causer, but FIXME. see also a reference to this above + // we also leave the loop above potentially early due to this. otherwise, though, we end up scanning the + // entire function in some cases which is very slow + assert(obj.found >= obj.total, 'Could not Signalyze line ' + line.lineNum); + line.unsigned = obj.unsigned > 0; + dprint('vars', 'Signalyzer: ' + line.assignTo + ' has unsigned == ' + line.unsigned + ' (line ' + line.lineNum + ')'); + } }); - } - }); + }); + } // Quantum fixer // // See settings.js for the meaning of QUANTUM_SIZE. The issue we fix here is, // to correct the .ll assembly code so that things work with QUANTUM_SIZE=1. // - substrate.addActor('QuantumFixer', { - processItem: function(item) { - this.forwardItem(item, 'LabelAnalyzer'); - if (QUANTUM_SIZE !== 1) return; - - // ptrs: the indexes of parameters that are pointers, whose originalType is what we want - // bytes: the index of the 'bytes' parameter - // TODO: malloc, realloc? - var FIXABLE_CALLS = { - 'memcpy': { ptrs: [0,1], bytes: 2 }, - 'memmove': { ptrs: [0,1], bytes: 2 }, - 'memset': { ptrs: [0], bytes: 2 }, - 'qsort': { ptrs: [0], bytes: 2 } - }; + function quantumFixer() { + if (QUANTUM_SIZE !== 1) return; + + // ptrs: the indexes of parameters that are pointers, whose originalType is what we want + // bytes: the index of the 'bytes' parameter + // TODO: malloc, realloc? + var FIXABLE_CALLS = { + 'memcpy': { ptrs: [0,1], bytes: 2 }, + 'memmove': { ptrs: [0,1], bytes: 2 }, + 'memset': { ptrs: [0], bytes: 2 }, + 'qsort': { ptrs: [0], bytes: 2 } + }; - function getSize(types, type, fat) { - if (types[type]) return types[type].flatSize; - if (fat) { - Runtime.QUANTUM_SIZE = 4; - } - var ret = Runtime.getNativeTypeSize(type); - if (fat) { - Runtime.QUANTUM_SIZE = 1; - } - return ret; + function getSize(types, type, fat) { + if (types[type]) return types[type].flatSize; + if (fat) { + Runtime.QUANTUM_SIZE = 4; } - - function getFlatIndexes(types, type) { - if (types[type]) return types[type].flatIndexes; - return [0]; + var ret = Runtime.getNativeTypeSize(type); + if (fat) { + Runtime.QUANTUM_SIZE = 1; } + return ret; + } - item.functions.forEach(function(func) { - function getOriginalType(param) { - function get() { - if (param.intertype === 'value' && !isNumber(param.ident)) { - if (func.variables[param.ident]) { - return func.variables[param.ident].originalType || null; - } else { - return item.globalVariables[param.ident].originalType; - } - } else if (param.intertype === 'bitcast') { - return param.params[0].type; - } else if (param.intertype === 'getelementptr') { - if (param.params[0].type[0] === '[') return param.params[0].type; - } - return null; - } - var ret = get(); - if (ret && ret[0] === '[') { - var check = /^\[(\d+)\ x\ (.*)\]\*$/.exec(ret); - assert(check); - ret = check[2] + '*'; - } - return ret; - } + function getFlatIndexes(types, type) { + if (types[type]) return types[type].flatIndexes; + return [0]; + } - func.lines.forEach(function(line) { - // Call - if (line.intertype === 'call') { - var funcIdent = LibraryManager.getRootIdent(line.ident.substr(1)); - var fixData = FIXABLE_CALLS[funcIdent]; - if (!fixData) return; - var ptrs = fixData.ptrs.map(function(ptr) { return line.params[ptr] }); - var bytes = line.params[fixData.bytes].ident; - - // Only consider original types. This assumes memcpy always has pointers bitcast to i8* - var originalTypes = ptrs.map(getOriginalType); - for (var i = 0; i < originalTypes.length; i++) { - if (!originalTypes[i]) return; - } - originalTypes = originalTypes.map(function(type) { return removePointing(type) }); - var sizes = originalTypes.map(function(type) { return getSize(Types.types, type) }); - var fatSizes = originalTypes.map(function(type) { return getSize(Types.fatTypes, type, true) }); - // The sizes may not be identical, if we copy a descendant class into a parent class. We use - // the smaller size in that case. However, this may also be a bug, it is hard to tell, hence a warning - warn(dedup(sizes).length === 1, 'All sizes should probably be identical here: ' + dump(originalTypes) + ':' + dump(sizes) + ':' + - line.lineNum); - warn(dedup(fatSizes).length === 1, 'All fat sizes should probably be identical here: ' + dump(originalTypes) + ':' + dump(sizes) + ':' + - line.lineNum); - var size = Math.min.apply(null, sizes); - var fatSize = Math.min.apply(null, fatSizes); - if (isNumber(bytes)) { - // Figure out how much to copy. - var fixedBytes; - if (bytes % fatSize === 0) { - fixedBytes = size*(bytes/fatSize); - } else if (fatSize % bytes === 0 && size % (fatSize/bytes) === 0) { - // Assume this is a simple array. XXX We can be wrong though! See next TODO - fixedBytes = size/(fatSize/bytes); - } else { - // Just part of a structure. Align them to see how many fields. Err on copying more. - // TODO: properly generate a complete structure, including nesteds, and calculate on that - var flatIndexes = getFlatIndexes(Types.types, originalTypes[0]).concat(size); - var fatFlatIndexes = getFlatIndexes(Types.fatTypes, originalTypes[0]).concat(fatSize); - var index = 0; - var left = bytes; - fixedBytes = 0; - while (left > 0) { - left -= fatFlatIndexes[index+1] - fatFlatIndexes[index]; // note: we copy the alignment bytes too, which is unneeded - fixedBytes += flatIndexes[index+1] - flatIndexes[index]; - } - } - line.params[fixData.bytes].ident = fixedBytes; + item.functions.forEach(function(func) { + function getOriginalType(param) { + function get() { + if (param.intertype === 'value' && !isNumber(param.ident)) { + if (func.variables[param.ident]) { + return func.variables[param.ident].originalType || null; } else { - line.params[fixData.bytes].intertype = 'jsvalue'; - // We have an assertion in library::memcpy() that this is round - line.params[fixData.bytes].ident = size + '*(' + bytes + '/' + fatSize + ')'; + return item.globalVariables[param.ident].originalType; } + } else if (param.intertype === 'bitcast') { + return param.params[0].type; + } else if (param.intertype === 'getelementptr') { + if (param.params[0].type[0] === '[') return param.params[0].type; } - }); - }); + return null; + } + var ret = get(); + if (ret && ret[0] === '[') { + var check = /^\[(\d+)\ x\ (.*)\]\*$/.exec(ret); + assert(check); + ret = check[2] + '*'; + } + return ret; + } - // 2nd part - fix hardcoded constant offsets in global constants - values(item.globalVariables).forEach(function(variable) { - function recurse(item) { - if (item.contents) { - item.contents.forEach(recurse); - } else if (item.intertype === 'getelementptr' && item.params[0].intertype === 'bitcast' && item.params[0].type === 'i8*') { - var originalType = removePointing(item.params[0].params[0].type); - var fatSize = getSize(Types.fatTypes, originalType, true); - var slimSize = getSize(Types.types, originalType, false); - assert(fatSize % slimSize === 0); - item.params.slice(1).forEach(function(param) { - if (param.intertype === 'value' && isNumber(param.ident)) { - var corrected = parseInt(param.ident)/(fatSize/slimSize); - assert(corrected % 1 === 0); - param.ident = corrected.toString(); + func.lines.forEach(function(line) { + // Call + if (line.intertype === 'call') { + var funcIdent = LibraryManager.getRootIdent(line.ident.substr(1)); + var fixData = FIXABLE_CALLS[funcIdent]; + if (!fixData) return; + var ptrs = fixData.ptrs.map(function(ptr) { return line.params[ptr] }); + var bytes = line.params[fixData.bytes].ident; + + // Only consider original types. This assumes memcpy always has pointers bitcast to i8* + var originalTypes = ptrs.map(getOriginalType); + for (var i = 0; i < originalTypes.length; i++) { + if (!originalTypes[i]) return; + } + originalTypes = originalTypes.map(function(type) { return removePointing(type) }); + var sizes = originalTypes.map(function(type) { return getSize(Types.types, type) }); + var fatSizes = originalTypes.map(function(type) { return getSize(Types.fatTypes, type, true) }); + // The sizes may not be identical, if we copy a descendant class into a parent class. We use + // the smaller size in that case. However, this may also be a bug, it is hard to tell, hence a warning + warn(dedup(sizes).length === 1, 'All sizes should probably be identical here: ' + dump(originalTypes) + ':' + dump(sizes) + ':' + + line.lineNum); + warn(dedup(fatSizes).length === 1, 'All fat sizes should probably be identical here: ' + dump(originalTypes) + ':' + dump(sizes) + ':' + + line.lineNum); + var size = Math.min.apply(null, sizes); + var fatSize = Math.min.apply(null, fatSizes); + if (isNumber(bytes)) { + // Figure out how much to copy. + var fixedBytes; + if (bytes % fatSize === 0) { + fixedBytes = size*(bytes/fatSize); + } else if (fatSize % bytes === 0 && size % (fatSize/bytes) === 0) { + // Assume this is a simple array. XXX We can be wrong though! See next TODO + fixedBytes = size/(fatSize/bytes); + } else { + // Just part of a structure. Align them to see how many fields. Err on copying more. + // TODO: properly generate a complete structure, including nesteds, and calculate on that + var flatIndexes = getFlatIndexes(Types.types, originalTypes[0]).concat(size); + var fatFlatIndexes = getFlatIndexes(Types.fatTypes, originalTypes[0]).concat(fatSize); + var index = 0; + var left = bytes; + fixedBytes = 0; + while (left > 0) { + left -= fatFlatIndexes[index+1] - fatFlatIndexes[index]; // note: we copy the alignment bytes too, which is unneeded + fixedBytes += flatIndexes[index+1] - flatIndexes[index]; } - }); - } else if (item.params) { - item.params.forEach(recurse); + } + line.params[fixData.bytes].ident = fixedBytes; + } else { + line.params[fixData.bytes].intertype = 'jsvalue'; + // We have an assertion in library::memcpy() that this is round + line.params[fixData.bytes].ident = size + '*(' + bytes + '/' + fatSize + ')'; } } - if (!variable.external && variable.value) recurse(variable.value); }); - } - }); + }); + + // 2nd part - fix hardcoded constant offsets in global constants + values(item.globalVariables).forEach(function(variable) { + function recurse(item) { + if (item.contents) { + item.contents.forEach(recurse); + } else if (item.intertype === 'getelementptr' && item.params[0].intertype === 'bitcast' && item.params[0].type === 'i8*') { + var originalType = removePointing(item.params[0].params[0].type); + var fatSize = getSize(Types.fatTypes, originalType, true); + var slimSize = getSize(Types.types, originalType, false); + assert(fatSize % slimSize === 0); + item.params.slice(1).forEach(function(param) { + if (param.intertype === 'value' && isNumber(param.ident)) { + var corrected = parseInt(param.ident)/(fatSize/slimSize); + assert(corrected % 1 === 0); + param.ident = corrected.toString(); + } + }); + } else if (item.params) { + item.params.forEach(recurse); + } + } + if (!variable.external && variable.value) recurse(variable.value); + }); + } function operateOnLabels(line, func) { function process(item, id) { @@ -1477,268 +1451,260 @@ function analyzer(data, sidePass) { } // Label analyzer - substrate.addActor('LabelAnalyzer', { - processItem: function(item) { - item.functions.forEach(function(func) { - func.labelsDict = {}; - func.labelIds = {}; - func.labelIdsInverse = {}; - func.labelIdCounter = 1; - func.labels.forEach(function(label) { - if (!(label.ident in func.labelIds)) { - func.labelIds[label.ident] = func.labelIdCounter++; - func.labelIdsInverse[func.labelIdCounter-1] = label.ident; - } - }); - var entryIdent = func.labels[0].ident; - - // Minify label ids to numeric ids. - func.labels.forEach(function(label) { - label.ident = func.labelIds[label.ident]; - label.lines.forEach(function(line) { - operateOnLabels(line, function(item, id) { - item[id] = func.labelIds[item[id]].toString(); // strings, because we will append as we process - }); + function labelAnalyzer() { + item.functions.forEach(function(func) { + func.labelsDict = {}; + func.labelIds = {}; + func.labelIdsInverse = {}; + func.labelIdCounter = 1; + func.labels.forEach(function(label) { + if (!(label.ident in func.labelIds)) { + func.labelIds[label.ident] = func.labelIdCounter++; + func.labelIdsInverse[func.labelIdCounter-1] = label.ident; + } + }); + var entryIdent = func.labels[0].ident; + + // Minify label ids to numeric ids. + func.labels.forEach(function(label) { + label.ident = func.labelIds[label.ident]; + label.lines.forEach(function(line) { + operateOnLabels(line, function(item, id) { + item[id] = func.labelIds[item[id]].toString(); // strings, because we will append as we process }); }); + }); - func.labels.forEach(function(label) { - func.labelsDict[label.ident] = label; - }); + func.labels.forEach(function(label) { + func.labelsDict[label.ident] = label; + }); - // Correct phis - func.labels.forEach(function(label) { - label.lines.forEach(function(phi) { - if (phi.intertype == 'phi') { - for (var i = 0; i < phi.params.length; i++) { - phi.params[i].label = func.labelIds[phi.params[i].label]; - if (VERBOSE && !phi.params[i].label) warn('phi refers to nonexistent label on line ' + phi.lineNum); - } + // Correct phis + func.labels.forEach(function(label) { + label.lines.forEach(function(phi) { + if (phi.intertype == 'phi') { + for (var i = 0; i < phi.params.length; i++) { + phi.params[i].label = func.labelIds[phi.params[i].label]; + if (VERBOSE && !phi.params[i].label) warn('phi refers to nonexistent label on line ' + phi.lineNum); } - }); - }); - - func.lines.forEach(function(line) { - if (line.intertype == 'indirectbr') { - func.forceEmulated = true; } }); + }); - function getActualLabelId(labelId) { - if (func.labelsDict[labelId]) return labelId; - // If not present, it must be a surprisingly-named entry (or undefined behavior, in which case, still ok to use the entry) - labelId = func.labelIds[entryIdent]; - assert(func.labelsDict[labelId]); - return labelId; + func.lines.forEach(function(line) { + if (line.intertype == 'indirectbr') { + func.forceEmulated = true; } + }); - // Basic longjmp support, see library.js setjmp/longjmp - var setjmp = toNiceIdent('@setjmp'); - func.setjmpTable = null; - for (var i = 0; i < func.labels.length; i++) { - var label = func.labels[i]; - for (var j = 0; j < label.lines.length; j++) { - var line = label.lines[j]; - if ((line.intertype == 'call' || line.intertype == 'invoke') && line.ident == setjmp) { - // Add a new label - var oldLabel = label.ident; - var newLabel = func.labelIdCounter++; - if (!func.setjmpTable) func.setjmpTable = []; - func.setjmpTable.push({ oldLabel: oldLabel, newLabel: newLabel, assignTo: line.assignTo }); - func.labels.splice(i+1, 0, { - intertype: 'label', - ident: newLabel, - lineNum: label.lineNum + 0.5, - lines: label.lines.slice(j+1) - }); - func.labelsDict[newLabel] = func.labels[i+1]; - label.lines = label.lines.slice(0, j+1); - label.lines.push({ - intertype: 'branch', - label: toNiceIdent(newLabel), - lineNum: line.lineNum + 0.01, // XXX legalizing might confuse this - }); - // Correct phis - func.labels.forEach(function(label) { - label.lines.forEach(function(phi) { - if (phi.intertype == 'phi') { - for (var i = 0; i < phi.params.length; i++) { - var sourceLabelId = getActualLabelId(phi.params[i].label); - if (sourceLabelId == oldLabel) { - phi.params[i].label = newLabel; - } + function getActualLabelId(labelId) { + if (func.labelsDict[labelId]) return labelId; + // If not present, it must be a surprisingly-named entry (or undefined behavior, in which case, still ok to use the entry) + labelId = func.labelIds[entryIdent]; + assert(func.labelsDict[labelId]); + return labelId; + } + + // Basic longjmp support, see library.js setjmp/longjmp + var setjmp = toNiceIdent('@setjmp'); + func.setjmpTable = null; + for (var i = 0; i < func.labels.length; i++) { + var label = func.labels[i]; + for (var j = 0; j < label.lines.length; j++) { + var line = label.lines[j]; + if ((line.intertype == 'call' || line.intertype == 'invoke') && line.ident == setjmp) { + // Add a new label + var oldLabel = label.ident; + var newLabel = func.labelIdCounter++; + if (!func.setjmpTable) func.setjmpTable = []; + func.setjmpTable.push({ oldLabel: oldLabel, newLabel: newLabel, assignTo: line.assignTo }); + func.labels.splice(i+1, 0, { + intertype: 'label', + ident: newLabel, + lineNum: label.lineNum + 0.5, + lines: label.lines.slice(j+1) + }); + func.labelsDict[newLabel] = func.labels[i+1]; + label.lines = label.lines.slice(0, j+1); + label.lines.push({ + intertype: 'branch', + label: toNiceIdent(newLabel), + lineNum: line.lineNum + 0.01, // XXX legalizing might confuse this + }); + // Correct phis + func.labels.forEach(function(label) { + label.lines.forEach(function(phi) { + if (phi.intertype == 'phi') { + for (var i = 0; i < phi.params.length; i++) { + var sourceLabelId = getActualLabelId(phi.params[i].label); + if (sourceLabelId == oldLabel) { + phi.params[i].label = newLabel; } } - }); + } }); - } + }); } } - if (func.setjmpTable) { - func.forceEmulated = true; - recomputeLines(func); - } - - // Properly implement phis, by pushing them back into the branch - // that leads to here. We will only have the |var| definition in this location. + } + if (func.setjmpTable) { + func.forceEmulated = true; + recomputeLines(func); + } - // First, push phis back - func.labels.forEach(function(label) { - label.lines.forEach(function(phi) { - if (phi.intertype == 'phi') { - for (var i = 0; i < phi.params.length; i++) { - var param = phi.params[i]; - if (VERBOSE && !param.label) warn('phi refers to nonexistent label on line ' + phi.lineNum); - var sourceLabelId = getActualLabelId(param.label); - if (sourceLabelId) { - var sourceLabel = func.labelsDict[sourceLabelId]; - var lastLine = sourceLabel.lines.slice(-1)[0]; - assert(lastLine.intertype in LLVM.PHI_REACHERS, 'Only some can lead to labels with phis:' + [func.ident, label.ident, lastLine.intertype]); - if (!lastLine.phi) { - lastLine.phi = true; - assert(!lastLine.dependent); - lastLine.dependent = { - intertype: 'phiassigns', - params: [] - }; + // Properly implement phis, by pushing them back into the branch + // that leads to here. We will only have the |var| definition in this location. + + // First, push phis back + func.labels.forEach(function(label) { + label.lines.forEach(function(phi) { + if (phi.intertype == 'phi') { + for (var i = 0; i < phi.params.length; i++) { + var param = phi.params[i]; + if (VERBOSE && !param.label) warn('phi refers to nonexistent label on line ' + phi.lineNum); + var sourceLabelId = getActualLabelId(param.label); + if (sourceLabelId) { + var sourceLabel = func.labelsDict[sourceLabelId]; + var lastLine = sourceLabel.lines.slice(-1)[0]; + assert(lastLine.intertype in LLVM.PHI_REACHERS, 'Only some can lead to labels with phis:' + [func.ident, label.ident, lastLine.intertype]); + if (!lastLine.phi) { + lastLine.phi = true; + assert(!lastLine.dependent); + lastLine.dependent = { + intertype: 'phiassigns', + params: [] }; - lastLine.dependent.params.push({ - intertype: 'phiassign', - ident: phi.assignTo, - value: param.value, - targetLabel: label.ident - }); - } + }; + lastLine.dependent.params.push({ + intertype: 'phiassign', + ident: phi.assignTo, + value: param.value, + targetLabel: label.ident + }); } - // The assign to phi is now just a var - phi.intertype = 'var'; - phi.ident = phi.assignTo; - phi.assignTo = null; } - }); + // The assign to phi is now just a var + phi.intertype = 'var'; + phi.ident = phi.assignTo; + phi.assignTo = null; + } }); + }); - if (func.ident in NECESSARY_BLOCKADDRS) { - Functions.blockAddresses[func.ident] = {}; - for (var needed in NECESSARY_BLOCKADDRS[func.ident]) { - assert(needed in func.labelIds); - Functions.blockAddresses[func.ident][needed] = func.labelIds[needed]; - } + if (func.ident in NECESSARY_BLOCKADDRS) { + Functions.blockAddresses[func.ident] = {}; + for (var needed in NECESSARY_BLOCKADDRS[func.ident]) { + assert(needed in func.labelIds); + Functions.blockAddresses[func.ident][needed] = func.labelIds[needed]; } - }); - this.forwardItem(item, 'StackAnalyzer'); - } - }); + } + }); + } // Stack analyzer - calculate the base stack usage - substrate.addActor('StackAnalyzer', { - processItem: function(data) { - data.functions.forEach(function(func) { - var lines = func.labels[0].lines; - for (var i = 0; i < lines.length; i++) { - var item = lines[i]; - if (!item.assignTo || item.intertype != 'alloca' || !isNumber(item.allocatedNum)) break; - item.allocatedSize = func.variables[item.assignTo].impl === VAR_EMULATED ? - calcAllocatedSize(item.allocatedType)*item.allocatedNum: 0; - if (USE_TYPED_ARRAYS === 2) { - // We need to keep the stack aligned - item.allocatedSize = Runtime.forceAlign(item.allocatedSize, Runtime.STACK_ALIGN); - } + function stackAnalyzer() { + data.functions.forEach(function(func) { + var lines = func.labels[0].lines; + for (var i = 0; i < lines.length; i++) { + var item = lines[i]; + if (!item.assignTo || item.intertype != 'alloca' || !isNumber(item.allocatedNum)) break; + item.allocatedSize = func.variables[item.assignTo].impl === VAR_EMULATED ? + calcAllocatedSize(item.allocatedType)*item.allocatedNum: 0; + if (USE_TYPED_ARRAYS === 2) { + // We need to keep the stack aligned + item.allocatedSize = Runtime.forceAlign(item.allocatedSize, Runtime.STACK_ALIGN); } - var index = 0; - for (var i = 0; i < lines.length; i++) { - var item = lines[i]; - if (!item.assignTo || item.intertype != 'alloca' || !isNumber(item.allocatedNum)) break; - item.allocatedIndex = index; - index += item.allocatedSize; - delete item.allocatedSize; - } - func.initialStack = index; - func.otherStackAllocations = false; - while (func.initialStack == 0) { // one-time loop with possible abort in the middle - // If there is no obvious need for stack management, perhaps we don't need it - // (we try to optimize that way with SKIP_STACK_IN_SMALL). However, - // we need to note if stack allocations other than initial allocs can happen here - // If so, we need to rewind the stack when we leave. - - // By-value params are causes of additional allocas (although we could in theory make them normal allocas too) - func.params.forEach(function(param) { - if (param.byVal) { - func.otherStackAllocations = true; - } - }); - if (func.otherStackAllocations) break; + } + var index = 0; + for (var i = 0; i < lines.length; i++) { + var item = lines[i]; + if (!item.assignTo || item.intertype != 'alloca' || !isNumber(item.allocatedNum)) break; + item.allocatedIndex = index; + index += item.allocatedSize; + delete item.allocatedSize; + } + func.initialStack = index; + func.otherStackAllocations = false; + while (func.initialStack == 0) { // one-time loop with possible abort in the middle + // If there is no obvious need for stack management, perhaps we don't need it + // (we try to optimize that way with SKIP_STACK_IN_SMALL). However, + // we need to note if stack allocations other than initial allocs can happen here + // If so, we need to rewind the stack when we leave. + + // By-value params are causes of additional allocas (although we could in theory make them normal allocas too) + func.params.forEach(function(param) { + if (param.byVal) { + func.otherStackAllocations = true; + } + }); + if (func.otherStackAllocations) break; - // Allocas - var finishedInitial = false; + // Allocas + var finishedInitial = false; - lines = func.lines; // We need to consider all the function lines now, not just the first label + lines = func.lines; // We need to consider all the function lines now, not just the first label - for (var i = 0; i < lines.length; i++) { - var item = lines[i]; - if (!finishedInitial && (!item.assignTo || item.intertype != 'alloca' || !isNumber(item.allocatedNum))) { - finishedInitial = true; - } - if (item.intertype == 'alloca' && finishedInitial) { - func.otherStackAllocations = true; - break; - } + for (var i = 0; i < lines.length; i++) { + var item = lines[i]; + if (!finishedInitial && (!item.assignTo || item.intertype != 'alloca' || !isNumber(item.allocatedNum))) { + finishedInitial = true; } - if (func.otherStackAllocations) break; - - // Varargs - for (var i = 0; i < lines.length; i++) { - var item = lines[i]; - if (item.intertype == 'call' && isVarArgsFunctionType(item.type)) { - func.otherStackAllocations = true; - break; - } + if (item.intertype == 'alloca' && finishedInitial) { + func.otherStackAllocations = true; + break; } - if (func.otherStackAllocations) break; + } + if (func.otherStackAllocations) break; - break; + // Varargs + for (var i = 0; i < lines.length; i++) { + var item = lines[i]; + if (item.intertype == 'call' && isVarArgsFunctionType(item.type)) { + func.otherStackAllocations = true; + break; + } } - }); - this.forwardItem(data, 'Relooper'); - } - }); + if (func.otherStackAllocations) break; - // ReLooper - reconstruct nice loops, as much as possible - // This is now done in the jsify stage, using compiled relooper2 - substrate.addActor('Relooper', { - processItem: function(item) { - function finish() { - item.__finalResult__ = true; - return [item]; - } - function makeBlock(labels, entries, labelsDict, forceEmulated) { - if (labels.length == 0) return null; - dprint('relooping', 'prelooping: ' + entries + ',' + labels.length + ' labels'); - assert(entries && entries[0]); // need at least 1 entry - - var emulated = { - type: 'emulated', - id: 'B', - labels: labels, - entries: entries.slice(0) - }; - return emulated; + break; } - item.functions.forEach(function(func) { - dprint('relooping', "// relooping function: " + func.ident); - func.block = makeBlock(func.labels, [func.labels[0].ident], func.labelsDict, func.forceEmulated); - }); + }); + } - return finish(); + // ReLooper - reconstruct nice loops, as much as possible + // This is now done in the jsify stage, using compiled relooper2 + function relooper() { + function makeBlock(labels, entries, labelsDict, forceEmulated) { + if (labels.length == 0) return null; + dprint('relooping', 'prelooping: ' + entries + ',' + labels.length + ' labels'); + assert(entries && entries[0]); // need at least 1 entry + + var emulated = { + type: 'emulated', + id: 'B', + labels: labels, + entries: entries.slice(0) + }; + return emulated; } - }); - - // Data - substrate.addItem({ - items: data - }, 'Sorter'); + item.functions.forEach(function(func) { + dprint('relooping', "// relooping function: " + func.ident); + func.block = makeBlock(func.labels, [func.labels[0].ident], func.labelsDict, func.forceEmulated); + }); + } - // Solve it - return substrate.solve(); + // main + castAway(); + legalizer(); + typevestigator(); + analyzeTypes(); + variableAnalyzer(); + signalyzer(); + quantumFixer(); + labelAnalyzer(); + stackAnalyzer(); + relooper(); + + return item; } |