| //"use strict"; |
| |
| // Analyze intertype data. Calculates things that are necessary in order |
| // to do the final conversion into JavaScript later, for example, |
| // properties of variables, loop structures of functions, etc. |
| |
| var VAR_NATIVE = 'native'; |
| var VAR_NATIVIZED = 'nativized'; |
| var VAR_EMULATED = 'emulated'; |
| |
| var ENTRY_IDENT = toNiceIdent('%0'); |
| |
| function recomputeLines(func) { |
| func.lines = func.labels.map(function(label) { return label.lines }).reduce(concatenator, []); |
| } |
| |
| // Handy sets |
| |
| var BRANCH_INVOKE = set('branch', 'invoke'); |
| var LABEL_ENDERS = set('branch', 'return', 'switch'); |
| var SIDE_EFFECT_CAUSERS = set('call', 'invoke', 'atomic'); |
| var UNUNFOLDABLE = set('value', 'structvalue', 'type', 'phiparam'); |
| var SHADOW_FLIP = { i64: 'double', double: 'i64' }; //, i32: 'float', float: 'i32' }; |
| |
| // Analyzer |
| |
| function analyzer(data, sidePass) { |
| var mainPass = !sidePass; |
| |
| // Substrate |
| var substrate = new Substrate('Analyzer'); |
| |
| // Sorter |
| substrate.addActor('Sorter', { |
| processItem: function(item) { |
| item.items.sort(function (a, b) { return a.lineNum - b.lineNum }); |
| this.forwardItem(item, 'Gatherer'); |
| } |
| }); |
| |
| // Gatherer |
| substrate.addActor('Gatherer', { |
| processItem: function(item) { |
| // Single-liners |
| ['globalVariable', 'functionStub', 'unparsedFunction', 'unparsedGlobals', 'unparsedTypes', 'alias'].forEach(function(intertype) { |
| var temp = splitter(item.items, function(item) { return item.intertype == intertype }); |
| item.items = temp.leftIn; |
| item[intertype + 's'] = temp.splitOut; |
| }); |
| var temp = splitter(item.items, function(item) { return item.intertype == 'type' }); |
| item.items = temp.leftIn; |
| temp.splitOut.forEach(function(type) { |
| //dprint('types', 'adding defined type: ' + type.name_); |
| Types.types[type.name_] = type; |
| if (QUANTUM_SIZE === 1) { |
| Types.fatTypes[type.name_] = copy(type); |
| } |
| }); |
| |
| // Functions & labels |
| item.functions = []; |
| var currLabelFinished; // Sometimes LLVM puts a branch in the middle of a label. We need to ignore all lines after that. |
| item.items.sort(function(a, b) { return a.lineNum - b.lineNum }); |
| for (var i = 0; i < item.items.length; i++) { |
| var subItem = item.items[i]; |
| assert(subItem.lineNum); |
| if (subItem.intertype == 'function') { |
| item.functions.push(subItem); |
| subItem.endLineNum = null; |
| subItem.lines = []; // We will fill in the function lines after the legalizer, since it can modify them |
| subItem.labels = []; |
| subItem.forceEmulated = false; |
| |
| // no explicit 'entry' label in clang on LLVM 2.8 - most of the time, but not all the time! - so we add one if necessary |
| if (item.items[i+1].intertype !== 'label') { |
| item.items.splice(i+1, 0, { |
| intertype: 'label', |
| ident: ENTRY_IDENT, |
| lineNum: subItem.lineNum + '.5' |
| }); |
| } |
| } else if (subItem.intertype == 'functionEnd') { |
| item.functions.slice(-1)[0].endLineNum = subItem.lineNum; |
| } else if (subItem.intertype == 'label') { |
| item.functions.slice(-1)[0].labels.push(subItem); |
| subItem.lines = []; |
| currLabelFinished = false; |
| } else if (item.functions.length > 0 && item.functions.slice(-1)[0].endLineNum === null) { |
| // Internal line |
| if (!currLabelFinished) { |
| item.functions.slice(-1)[0].labels.slice(-1)[0].lines.push(subItem); // If this line fails, perhaps missing a label? |
| if (subItem.intertype 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); |
| } |
| } |
| delete item.items; |
| this.forwardItem(item, 'CastAway'); |
| } |
| }); |
| |
| // CastAway - try to remove bitcasts of double<-->i64, which LLVM sometimes generates unnecessarily |
| // (load a double, convert to i64, use as i64). |
| // We optimize this by checking if there are such bitcasts. If so we create a shadow |
| // variable that is of the other type, and use that in the relevant places. (As SSA, this is valid, and |
| // variable elimination later will remove the double load if it is no longer needed.) |
| // |
| // 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; |
| |
| 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++; |
| } |
| 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. |
| // |
| // With full LLVM optimizations, it can generate types like i888 which do not exist in |
| // any actual hardware implementation, but are useful during optimization. LLVM then |
| // legalizes these types into real ones during code generation. Sadly, there is no LLVM |
| // IR pass to legalize them, which would have been useful and nice from a design perspective. |
| // The LLVM community is also not interested in receiving patches to implement that |
| // functionality, since it would duplicate existing code from the code generation |
| // component. Therefore, we implement legalization here in Emscripten. |
| // |
| // Currently we just legalize completely unrealistic types into bundles of i32s, and just |
| // the most common instructions that can be involved with such types: load, store, shifts, |
| // trunc and zext. |
| substrate.addActor('Legalizer', { |
| processItem: function(data) { |
| // Legalization |
| if (USE_TYPED_ARRAYS == 2) { |
| function getLegalVars(base, bits, 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 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; |
| } |
| i++; |
| } |
| } |
| function fixUnfolded(item) { |
| // Unfolded items may need some correction to work properly in the global scope |
| if (item.intertype in MATHOPS) { |
| item.op = item.intertype; |
| item.intertype = 'mathop'; |
| } |
| } |
| data.functions.forEach(function(func) { |
| // Legalize function params |
| legalizeFunctionParameters(func.params); |
| // Legalize lines in labels |
| var tempId = 0; |
| func.labels.forEach(function(label) { |
| 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; |
| } |
| }); |
| 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', 'We can only unfold illegal constants in phis'); |
| // we must handle this in the phi itself, if we unfold normally it will not be pushed back with the phi |
| } else { |
| var tempIdent = '$$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++); |
| 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' } |
| ], |
| }); |
| var actualSizeType = 'i' + element.bits; // The last one may be smaller than 32 bits |
| toAdd.push({ |
| intertype: 'store', |
| valueType: actualSizeType, |
| value: { intertype: 'value', ident: element.ident, type: actualSizeType }, |
| pointer: { intertype: 'value', ident: tempVar, type: actualSizeType + '*' }, |
| ident: tempVar, |
| pointerType: actualSizeType + '*', |
| align: item.align, |
| }); |
| j++; |
| }); |
| Types.needAnalysis['[0 x i32]'] = 0; |
| i += removeAndAdd(label.lines, i, toAdd); |
| continue; |
| } |
| // call, return: Return 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 |
| } |
| } |
| 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; |
| } |
| 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 |
| }; |
| } |
| 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 actualSizeType = 'i' + element.bits; // The last one may be smaller than 32 bits |
| toAdd.push({ |
| intertype: 'load', |
| assignTo: element.ident, |
| pointerType: actualSizeType + '*', |
| valueType: actualSizeType, |
| type: actualSizeType, // XXX why is this missing from intertyper? |
| pointer: { intertype: 'value', ident: tempVar, type: actualSizeType + '*' }, |
| ident: tempVar, |
| pointerType: actualSizeType + '*', |
| align: value.align |
| }); |
| j++; |
| }); |
| Types.needAnalysis['[0 x i32]'] = 0; |
| i += removeAndAdd(label.lines, i, toAdd); |
| continue; |
| } |
| case 'phi': { |
| bits = getBits(value.type); |
| var toAdd = []; |
| var elements = getLegalVars(item.assignTo, bits); |
| var j = 0; |
| var 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[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({ |
| intertype: 'value', |
| assignTo: elements[sourceIndex+j].ident, |
| type: 'i' + elements[sourceIndex+j].bits, |
| ident: partIndex == index ? indexElements[j].ident : sourceElements[sourceIndex+j].ident |
| }); |
| } |
| sourceIndex += currNum; |
| } |
| 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 |
| } |
| // fall through |
| } |
| case 'inttoptr': case 'ptrtoint': case 'zext': case 'sext': case 'trunc': case 'ashr': case 'lshr': case 'shl': case 'or': case 'and': case 'xor': { |
| value = { |
| op: item.intertype, |
| variant: item.variant, |
| type: item.type, |
| params: item.params |
| }; |
| // fall through |
| } |
| case 'mathop': { |
| var toAdd = []; |
| var sourceBits = getBits(value.params[0].type); |
| // All mathops can be parametrized by how many shifts we do, and how big the source is |
| var shifts = 0; |
| var targetBits = sourceBits; |
| var processor = null; |
| var signed = false; |
| switch (value.op) { |
| case 'ashr': { |
| signed = true; |
| // fall through |
| } |
| case 'lshr': { |
| shifts = parseInt(value.params[1].ident); |
| break; |
| } |
| case 'shl': { |
| shifts = -parseInt(value.params[1].ident); |
| break; |
| } |
| case 'sext': { |
| signed = true; |
| // fall through |
| } |
| case 'trunc': case 'zext': case 'ptrtoint': { |
| targetBits = getBits(value.params[1] ? value.params[1].ident : value.type); |
| break; |
| } |
| case 'inttoptr': { |
| targetBits = 32; |
| break; |
| } |
| case 'bitcast': { |
| 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': |
| 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: (j + sign + whole >= 0 && j + sign + whole < sourceElements.length) ? sourceElements[j + sign + whole].ident : (signed ? signedFill : '0'), |
| params: [(signed && j + sign + whole > sourceElements.length) ? signedKeepAlive : null], |
| type: 'i32', |
| }; |
| other = { |
| intertype: 'mathop', |
| op: shiftOp, |
| type: 'i32', |
| params: [ |
| other, |
| { intertype: 'value', ident: (32 - fraction).toString(), type: 'i32' } |
| ] |
| }; |
| result = { |
| intertype: 'mathop', |
| // shifting in 1s from the top is a special case |
| op: (signed && shifts >= 0 && j + sign + whole >= sourceElements.length) ? 'ashr' : shiftOpReverse, |
| type: 'i32', |
| params: [ |
| result, |
| { intertype: 'value', ident: fraction.toString(), type: 'i32' } |
| ] |
| }; |
| result = { |
| intertype: 'mathop', |
| op: 'or', |
| type: 'i32', |
| params: [ |
| result, |
| other |
| ] |
| } |
| } |
| if (targetElements[j].bits < 32 && shifts < 0) { |
| // truncate bits that fall off the end. This is not needed in most cases, can probably be optimized out |
| result = { |
| intertype: 'mathop', |
| op: 'and', |
| type: 'i32', |
| params: [ |
| result, |
| { intertype: 'value', ident: (Math.pow(2, targetElements[j].bits)-1).toString(), type: 'i32' } |
| ] |
| } |
| } |
| if (processor) { |
| result = processor(result, j); |
| } |
| result.assignTo = targetElements[j].ident; |
| toAdd.push(result); |
| } |
| if (targetBits <= 32) { |
| // We are generating a normal legal type here |
| legalValue = { |
| intertype: 'value', |
| ident: targetElements[0].ident + (targetBits < 32 ? '&' + (Math.pow(2, targetBits)-1) : ''), |
| type: 'rawJS' |
| }; |
| legalValue.assignTo = item.assignTo; |
| toAdd.push(legalValue); |
| } 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); |
| }); |
| }); |
| this.forwardItem(data, 'Typevestigator'); |
| } |
| }); |
| |
| function addTypeInternal(type, data) { |
| if (type.length == 1) return; |
| if (Types.types[type]) return; |
| if (['internal', 'hidden', 'inbounds', 'void'].indexOf(type) != -1) return; |
| if (Runtime.isNumberType(type)) return; |
| dprint('types', 'Adding type: ' + type); |
| |
| // 'blocks': [14 x %struct.X] etc. If this is a pointer, we need |
| // to look at the underlying type - it was not defined explicitly |
| // anywhere else. |
| var nonPointing = removeAllPointing(type); |
| var check = /^\[(\d+)\ x\ (.*)\]$/.exec(nonPointing); |
| if (check && !Types.types[nonPointing]) { |
| var num = parseInt(check[1]); |
| num = Math.max(num, 1); // [0 x something] is used not for allocations and such of course, but |
| // for indexing - for an |array of unknown length|, basically. So we |
| // define the 'type' as having a single field. TODO: Ensure as a sanity |
| // check that we never allocate with this (either as a child structure |
| // in the analyzer, or in calcSize in alloca). |
| var subType = check[2]; |
| addTypeInternal(subType, data); // needed for anonymous structure definitions (see below) |
| |
| // 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)'); |
| Types.types[nonPointing] = { |
| name_: nonPointing, |
| fields: range(num).map(function() { return subType }), |
| lineNum: '?' |
| }; |
| // Also add a |[0 x type]| type |
| var zerod = '[0 x ' + subType + ']'; |
| if (!Types.types[zerod]) { |
| Types.types[zerod] = { |
| name_: zerod, |
| fields: [subType, subType], // Two, so we get the flatFactor right. We care about the flatFactor, not the size here |
| lineNum: '?' |
| }; |
| } |
| return; |
| } |
| |
| // anonymous structure definition, for example |{ i32, i8*, void ()*, i32 }| |
| if (type[0] == '{' || type[0] == '<') { |
| type = nonPointing; |
| var packed = type[0] == '<'; |
| Types.types[type] = { |
| name_: type, |
| fields: splitTokenList(tokenize(type.substr(2 + packed, type.length - 4 - 2*packed)).tokens).map(function(segment) { |
| return segment[0].text; |
| }), |
| packed: packed, |
| lineNum: '?' |
| }; |
| return; |
| } |
| |
| if (isPointerType(type)) return; |
| if (['['].indexOf(type) != -1) return; |
| Types.types[type] = { |
| name_: type, |
| fields: [ 'i' + (QUANTUM_SIZE*8) ], // a single quantum size |
| flatSize: 1, |
| lineNum: '?' |
| }; |
| } |
| |
| function addType(type, data) { |
| addTypeInternal(type, data); |
| if (QUANTUM_SIZE === 1) { |
| Types.flipTypes(); |
| addTypeInternal(type, data); |
| Types.flipTypes(); |
| } |
| } |
| |
| // Typevestigator |
| substrate.addActor('Typevestigator', { |
| processItem: function(data) { |
| if (sidePass) { // Do not investigate in the main pass - it is only valid to start to do so in the first side pass, |
| // which handles type definitions, and later. Doing so before the first side pass will result in |
| // making bad guesses about types which are actually defined |
| for (var type in Types.needAnalysis) { |
| if (type) addType(type, data); |
| } |
| Types.needAnalysis = {}; |
| } |
| this.forwardItem(data, 'Typeanalyzer'); |
| } |
| }); |
| |
| // Type analyzer |
| substrate.addActor('Typeanalyzer', { |
| processItem: function analyzeTypes(item, fatTypes) { |
| var types = Types.types; |
| |
| // 'fields' is the raw list of LLVM fields. However, we embed |
| // child structures into parent structures, basically like C. |
| // So { int, { int, int }, int } would be represented as |
| // an Array of 4 ints. getelementptr on the parent would take |
| // values 0, 1, 2, where 2 is the entire middle structure. |
| // We also need to be careful with getelementptr to child |
| // structures - we return a pointer to the same slab, just |
| // a different offset. Likewise, need to be careful for |
| // getelementptr of 2 (the last int) - it's real index is 4. |
| // The benefit of this approach is inheritance - |
| // { { ancestor } , etc. } = descendant |
| // In this case it is easy to bitcast ancestor to descendant |
| // pointers - nothing needs to be done. If the ancestor were |
| // a new slab, it would need some pointer to the outer one |
| // for casting in that direction. |
| // TODO: bitcasts of non-inheritance cases of embedding (not at start) |
| var more = true; |
| while (more) { |
| more = false; |
| for (var typeName in types) { |
| var type = types[typeName]; |
| if (type.flatIndexes) continue; |
| var ready = true; |
| type.fields.forEach(function(field) { |
| if (isStructType(field)) { |
| if (!types[field]) { |
| addType(field, item); |
| ready = false; |
| } else { |
| if (!types[field].flatIndexes) { |
| ready = false; |
| } |
| } |
| } |
| }); |
| if (!ready) { |
| more = true; |
| continue; |
| } |
| |
| Runtime.calculateStructAlignment(type); |
| |
| if (dcheck('types')) dprint('type (fat=' + !!fatTypes + '): ' + type.name_ + ' : ' + JSON.stringify(type.fields)); |
| if (dcheck('types')) dprint(' has final size of ' + type.flatSize + ', flatting: ' + type.needsFlattening + ' ? ' + (type.flatFactor ? type.flatFactor : JSON.stringify(type.flatIndexes))); |
| } |
| } |
| |
| if (QUANTUM_SIZE === 1 && !fatTypes) { |
| Types.flipTypes(); |
| // Fake a quantum size of 4 for fat types. TODO: Might want non-4 for some reason? |
| var trueQuantumSize = QUANTUM_SIZE; |
| Runtime.QUANTUM_SIZE = 4; |
| analyzeTypes(item, true); |
| Runtime.QUANTUM_SIZE = trueQuantumSize; |
| Types.flipTypes(); |
| } |
| |
| if (!fatTypes) { |
| this.forwardItem(item, 'VariableAnalyzer'); |
| } |
| } |
| }); |
| |
| // Variable analyzer |
| substrate.addActor('VariableAnalyzer', { |
| processItem: function(item) { |
| // Globals |
| |
| var old = item.globalVariables; |
| item.globalVariables = {}; |
| old.forEach(function(variable) { |
| variable.impl = 'emulated'; // All global variables are emulated, for now. Consider optimizing later if useful |
| item.globalVariables[variable.ident] = variable; |
| }); |
| |
| // Function locals |
| |
| item.functions.forEach(function(func) { |
| func.variables = {}; |
| |
| // LLVM is SSA, so we always have a single assignment/write. We care about |
| // the reads/other uses. |
| |
| // Function parameters |
| func.params.forEach(function(param) { |
| if (param.intertype !== 'varargs') { |
| 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; |
| } |
| 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); |
| } |
| } |
| }); |
| } |
| |
| // Analyze variable uses |
| |
| function analyzeVariableUses() { |
| dprint('vars', 'Analyzing variables for ' + func.ident + '\n'); |
| |
| for (vname in func.variables) { |
| var variable = func.variables[vname]; |
| |
| // Whether the value itself is used. For an int, always yes. For a pointer, |
| // we might never use the pointer's value - we might always just store to it / |
| // read from it. If so, then we can optimize away the pointer. |
| variable.hasValueTaken = false; |
| |
| variable.pointingLevels = pointingLevels(variable.type); |
| |
| variable.uses = 0; |
| } |
| |
| // TODO: improve the analysis precision. bitcast, for example, means we take the value, but perhaps we only use it to load/store |
| var inNoop = 0; |
| func.lines.forEach(function(line) { |
| walkInterdata(line, function(item) { |
| if (item.intertype == 'noop') inNoop++; |
| if (!inNoop) { |
| if (item.ident in func.variables) { |
| func.variables[item.ident].uses++; |
| |
| if (item.intertype != 'load' && item.intertype != 'store') { |
| func.variables[item.ident].hasValueTaken = true; |
| } |
| } |
| } |
| }, function(item) { |
| if (item.intertype == 'noop') inNoop--; |
| }); |
| }); |
| |
| //if (dcheck('vars')) dprint('analyzed variables: ' + dump(func.variables)); |
| } |
| |
| analyzeVariableUses(); |
| |
| // Decision time |
| |
| for (vname in func.variables) { |
| var variable = func.variables[vname]; |
| var pointedType = pointingLevels(variable.type) > 0 ? removePointing(variable.type) : null; |
| if (variable.origin == 'getelementptr') { |
| // Use our implementation that emulates pointers etc. |
| // TODO Can we perhaps nativize some of these? However to do so, we need to discover their |
| // true types; we have '?' for them now, as they cannot be discovered in the intertyper. |
| variable.impl = VAR_EMULATED; |
| } else if (variable.origin == 'funcparam') { |
| variable.impl = VAR_EMULATED; |
| } else if (variable.type == 'i64*' && USE_TYPED_ARRAYS == 2) { |
| variable.impl = VAR_EMULATED; |
| } else if (MICRO_OPTS && variable.pointingLevels === 0) { |
| // A simple int value, can be implemented as a native variable |
| variable.impl = VAR_NATIVE; |
| } else if (MICRO_OPTS && variable.origin === 'alloca' && !variable.hasValueTaken && |
| variable.allocatedNum === 1 && |
| (Runtime.isNumberType(pointedType) || Runtime.isPointerType(pointedType))) { |
| // A pointer to a value which is only accessible through this pointer. Basically |
| // a local value on the stack, which nothing fancy is done on. So we can |
| // optimize away the pointing altogether, and just have a native variable |
| variable.impl = VAR_NATIVIZED; |
| } else { |
| variable.impl = VAR_EMULATED; |
| } |
| if (dcheck('vars')) dprint('// var ' + vname + ': ' + JSON.stringify(variable)); |
| } |
| }); |
| this.forwardItem(item, 'Signalyzer'); |
| } |
| }); |
| |
| // Sign analyzer |
| // |
| // Analyze our variables and detect their signs. In USE_TYPED_ARRAYS == 2, |
| // we can read signed or unsigned values and prevent the need for signing |
| // corrections. If on the other hand we are doing corrections anyhow, then |
| // we can skip this pass. |
| // |
| // For each variable that is the result of a Load, we look a little forward |
| // to see where it is used. We only care about mathops, since only they |
| // need signs. |
| // |
| substrate.addActor('Signalyzer', { |
| processItem: function(item) { |
| this.forwardItem(item, 'QuantumFixer'); |
| if (USE_TYPED_ARRAYS != 2 || 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++; |
| } |
| } |
| } |
| |
| item.functions.forEach(function(func) { |
| func.lines.forEach(function(line, i) { |
| if (line.intertype === 'load') { |
| // Floats have no concept of signedness. Mark them as 'signed', which is the default, for which we do nothing |
| if (line.type in Runtime.FLOAT_TYPES) { |
| line.unsigned = false; |
| return; |
| } |
| // Booleans are always unsigned |
| var data = func.variables[line.assignTo]; |
| if (data.type === 'i1') { |
| line.unsigned = true; |
| return; |
| } |
| |
| var total = data.uses; |
| if (total === 0) return; |
| var obj = { ident: line.assignTo, found: 0, unsigned: 0, signed: 0, total: total }; |
| // in loops with phis, we can also be used *before* we are defined |
| var j = i-1, k = i+1; |
| while(1) { |
| assert(j >= 0 || k < func.lines.length, 'Signalyzer ran out of space to look for sign indications for line ' + line.lineNum); |
| if (j >= 0 && walkInterdata(func.lines[j], seekIdent, seekMathop, obj)) break; |
| if (k < func.lines.length && walkInterdata(func.lines[k], seekIdent, seekMathop, obj)) break; |
| if (obj.total && obj.found >= obj.total) break; // see comment below |
| j -= 1; |
| k += 1; |
| } |
| |
| // unsigned+signed might be < total, since the same ident can appear multiple times in the same mathop. |
| // found can actually be > total, since we currently have the same ident in a GEP (see cubescript test) |
| // 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 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 getFlatIndexes(types, type) { |
| if (types[type]) return types[type].flatIndexes; |
| return [0]; |
| } |
| |
| 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; |
| } |
| |
| 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; |
| } 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 + ')'; |
| } |
| } |
| }); |
| }); |
| |
| // 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) { |
| ['label', 'labelTrue', 'labelFalse', 'toLabel', 'unwindLabel', 'defaultLabel'].forEach(function(id) { |
| if (item[id]) { |
| func(item, id); |
| } |
| }); |
| } |
| if (line.intertype in BRANCH_INVOKE) { |
| process(line); |
| } else if (line.intertype == 'switch') { |
| process(line); |
| line.switchLabels.forEach(process); |
| } |
| } |
| |
| // Label analyzer |
| substrate.addActor('LabelAnalyzer', { |
| processItem: function(item) { |
| item.functions.forEach(function(func) { |
| func.labelsDict = {}; |
| func.labelIds = {}; |
| func.labelIdsInverse = {}; |
| func.labelIds[toNiceIdent('%0')] = 1; |
| func.labelIdsInverse[0] = toNiceIdent('%0'); |
| func.labelIdCounter = 2; |
| func.labels.forEach(function(label) { |
| if (!(label.ident in func.labelIds)) { |
| func.labelIds[label.ident] = func.labelIdCounter++; |
| func.labelIdsInverse[func.labelIdCounter-1] = label.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; |
| }); |
| |
| // 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[ENTRY_IDENT]; |
| 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. |
| |
| // 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 |
| }); |
| } |
| } |
| // 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]; |
| } |
| } |
| }); |
| 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); |
| } |
| } |
| 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; |
| |
| 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; |
| } |
| } |
| 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 (func.otherStackAllocations) break; |
| |
| break; |
| } |
| }); |
| this.forwardItem(data, 'Relooper'); |
| } |
| }); |
| |
| // 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; |
| } |
| 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(); |
| } |
| }); |
| |
| // Data |
| substrate.addItem({ |
| items: data |
| }, 'Sorter'); |
| |
| // Solve it |
| return substrate.solve(); |
| } |
| |
