support for blockaddress/indirectbr. fixes issue 34

5 files changed, 82 insertions, 17 deletions

diff --git a/src/analyzer.js b/src/analyzer.js
index 9b8af51b..4f069695 100644
--- a/src/analyzer.js
+++ b/src/analyzer.js
@@ -553,10 +553,16 @@ function analyzer(data) {
     processItem: function(item) {
       item.functions.forEach(function(func) {
         func.labelsDict = {};
+        func.labelIds = {};
+        func.labelIdCounter = 0;
         func.labels.forEach(function(label) {
           func.labelsDict[label.ident] = label;
+          func.labelIds[label.ident] = func.labelIdCounter++;
         });
+        func.labelIds[toNiceIdent('%entry')] = -1; // entry is always -1
+
         func.hasPhi = false;
+        func.hasIndirectBr = false;
         func.remarkableLabels = [];
         func.labels.forEach(function(label) {
           label.lines.forEach(function(line) {
@@ -574,6 +580,9 @@ function analyzer(data) {
               }
               func.hasPhi = true;
             }
+            if (line.intertype == 'indirectbr') {
+              func.hasIndirectBr = true;
+            }
           });
         });
       });
@@ -791,7 +800,7 @@ function analyzer(data) {
       //              For now, we do this in a loop, so we can break out of it easily to get
       //              to the labels afterwards. TODO: Optimize that out
       //
-      function makeBlock(labels, entries, labelsDict) {
+      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
@@ -804,7 +813,7 @@ function analyzer(data) {
           labels: labels,
           entries: entries.slice(0)
         };
-        if (!RELOOP) return emulated;
+        if (!RELOOP || forceEmulated) return emulated;
 
         calcLabelBranchingData(labels, labelsDict);
 
@@ -986,7 +995,7 @@ function analyzer(data) {
       // TODO: each of these can be run in parallel
       item.functions.forEach(function(func) {
         dprint('relooping', "// relooping function: " + func.ident);
-        func.block = makeBlock(func.labels, [toNiceIdent(func.labels[0].ident)], func.labelsDict);
+        func.block = makeBlock(func.labels, [toNiceIdent(func.labels[0].ident)], func.labelsDict, func.hasIndirectBr);
       });
 
       return finish();
diff --git a/src/intertyper.js b/src/intertyper.js
index 226c3703..9e3f7f1e 100644
--- a/src/intertyper.js
+++ b/src/intertyper.js
@@ -258,6 +258,8 @@ function intertyper(data, parseFunctions, baseLineNum) {
               return 'Switch';
             if (token0Text == 'unreachable')
               return 'Unreachable';
+            if (tokensLength >= 3 && token0Text == 'indirectbr')
+              return 'IndirectBr';
           } else if (item.indent === -1) {
             if (tokensLength >= 3 &&
                 (token0Text == 'load' || token1Text == 'load'))
@@ -343,6 +345,8 @@ function intertyper(data, parseFunctions, baseLineNum) {
                 var text = segment[2].text;
                 text = text.substr(1, text.length-2);
                 return { intertype: 'string', text: text };
+              } else if (segment[1].text === 'blockaddress') {
+                return parseBlockAddress(segment);
               } else {
                 throw 'Invalid segment: ' + dump(segment);
               }
@@ -787,6 +791,19 @@ function intertyper(data, parseFunctions, baseLineNum) {
       }];
     }
   });
+  // 'indirectbr'
+  substrate.addActor('IndirectBr', {
+    processItem: function(item) {
+      var ret = {
+        intertype: 'indirectbr',
+        pointer: parseLLVMSegment(splitTokenList(item.tokens.slice(1))[0]),
+        type: item.tokens[1].text,
+        lineNum: item.lineNum
+      };
+      Types.needAnalysis[ret.type] = 0;
+      return [ret];
+    }
+  });
 
   // Input
 
diff --git a/src/jsifier.js b/src/jsifier.js
index 3f7698ef..62acf8d7 100644
--- a/src/jsifier.js
+++ b/src/jsifier.js
@@ -36,10 +36,11 @@ function JSify(data, functionsOnly, givenFunctions, givenGlobalVariables) {
   Functions.currFunctions = functionsOnly ? givenFunctions : {};
   // Now that analysis has completed, we can get around to handling unparsedFunctions
   (functionsOnly ? data.functions : data.unparsedFunctions.concat(data.functions)).forEach(function(func) {
-    // Save just what we need, to save memory - whether there are varargs, and the # of parameters
+    // Save just what we need, to save memory
     Functions.currFunctions[func.ident] = {
       hasVarArgs: func.hasVarArgs,
-      numParams: func.params.length
+      numParams: func.params.length,
+      labelIds: func.labelIds // TODO: We need this for globals, but perhaps we can calculate them early and free this
    };
   });
 
@@ -137,6 +138,8 @@ function JSify(data, functionsOnly, givenFunctions, givenGlobalVariables) {
             return alignStruct(handleSegments(segment.contents), segment.type);
           } else if (segment.intertype === 'string') {
             return parseLLVMString(segment.text); // + ' /* ' + text + '*/';
+          } else if (segment.intertype === 'blockaddress') {
+            return finalizeBlockAddress(segment);
           } else {
             throw 'Invalid segment: ' + dump(segment);
           }
@@ -303,7 +306,7 @@ function JSify(data, functionsOnly, givenFunctions, givenGlobalVariables) {
       item.labels.forEach(function(label) {
         label.lines.forEach(function(line) {
           line.func = item.ident;
-          line.funcData = item;
+          line.funcData = item; // TODO: remove all these, access it globally
           line.parentLabel = label.ident;
           ret.push(line);
           item.splitItems ++;
@@ -555,24 +558,20 @@ function JSify(data, functionsOnly, givenFunctions, givenGlobalVariables) {
 
   makeFuncLineActor('deleted', function(item) { return ';' });
 
-  var LABEL_IDs = {};
-  var LABEL_ID_COUNTER = 0;
   function getLabelId(label) {
-    label = label.substr(1);
-    if (label === 'entry') return '-1';
-    if (label === parseInt(label)) return label; // clang
-    //return '"' + label + '"'; // debugging
-    label = toNiceIdent(label);
-    if (label in LABEL_IDs) return LABEL_IDs[label];
-    return LABEL_IDs[label] = LABEL_ID_COUNTER ++;
+    var funcData = Framework.currItem.funcData;
+    var labelIds = funcData.labelIds;
+    if (labelIds[label] !== undefined) return labelIds[label];
+    return labelIds[label] = funcData.labelIdCounter++;
   }
 
-  function makeBranch(label, lastLabel) {
+  function makeBranch(label, lastLabel, labelIsVariable) {
     var pre = '';
     if (lastLabel) {
       pre = '__lastLabel__ = ' + getLabelId(lastLabel) + '; ';
     }
     if (label[0] == 'B') {
+      assert(!labelIsVariable, 'Cannot handle branches to variables with special branching options');
       var parts = label.split('|');
       var trueLabel = parts[1] || '';
       var oldLabel = parts[2] || '';
@@ -590,7 +589,8 @@ function JSify(data, functionsOnly, givenFunctions, givenGlobalVariables) {
         throw 'Invalid B-op in branch: ' + trueLabel + ',' + oldLabel;
       }
     } else {
-      return pre + '__label__ = ' + getLabelId(label) + ';' + (SHOW_LABELS ? ' /* to: ' + cleanLabel(label) + ' */' : '') + ' break;';
+      if (!labelIsVariable) label = getLabelId(label);
+      return pre + '__label__ = ' + label + ';' + (SHOW_LABELS ? ' /* to: ' + cleanLabel(label) + ' */' : '') + ' break;';
     }
   }
 
@@ -676,6 +676,9 @@ function JSify(data, functionsOnly, givenFunctions, givenGlobalVariables) {
                                       //       and we emulate them using simple JS objects { f1: , f2: , } etc., for speed
     return item.ident + '.f' + item.indexes[0][0].text;
   });
+  makeFuncLineActor('indirectbr', function(item) {
+    return makeBranch(finalizeLLVMParameter(item.pointer), item.currLabelId, true);
+  });
   makeFuncLineActor('alloca', function(item) {
     if (typeof item.allocatedIndex === 'number') {
       if (item.allocatedSize === 0) return ''; // This will not actually be shown - it's nativized
diff --git a/src/parseTools.js b/src/parseTools.js
index 3855c633..4f0cda35 100644
--- a/src/parseTools.js
+++ b/src/parseTools.js
@@ -365,6 +365,8 @@ function parseLLVMSegment(segment) {
     return parseLLVMFunctionCall([{text: '?'}].concat(segment));
   } else if (segment[1].text in PARSABLE_LLVM_FUNCTIONS) {
     return parseLLVMFunctionCall(segment);
+  } else if (segment[1].text === 'blockaddress') {
+    return parseBlockAddress(segment);
   } else {
     type = segment[0].text;
     Types.needAnalysis[type] = 0;
@@ -1051,6 +1053,8 @@ function finalizeLLVMParameter(param) {
     ret = parseNumerical(param.ident);
   } else if (param.intertype == 'structvalue') {
     ret = param.values.map(finalizeLLVMParameter);
+  } else if (param.intertype === 'blockaddress') {
+    return finalizeBlockAddress(param);
   } else {
     throw 'invalid llvm parameter: ' + param.intertype;
   }
@@ -1278,3 +1282,11 @@ function walkInterdata(item, pre, post, obj) {
   return post(item, originalObj, obj);
 }
 
+function parseBlockAddress(segment) {
+  return { intertype: 'blockaddress', func: toNiceIdent(segment[2].item.tokens[0].text), label: toNiceIdent(segment[2].item.tokens[2].text) };
+}
+
+function finalizeBlockAddress(param) {
+  return Functions.currFunctions[param.func].labelIds[param.label]; // XXX We rely on currFunctions here...?
+}
+
diff --git a/tests/runner.py b/tests/runner.py
index 1ba5a983..d7848769 100644
--- a/tests/runner.py
+++ b/tests/runner.py
@@ -1469,6 +1469,30 @@ if 'benchmark' not in sys.argv:
           '''
         self.do_test(src, '*96,97,98,101,101*')
 
+    def test_indirectbr(self):
+        src = '''
+          #include <stdio.h>
+          int main(void) {
+            const void *addrs[2] = { &&FOO, &&BAR };
+
+            // confuse the optimizer so it doesn't hardcode the jump and avoid generating an |indirectbr| instruction
+            int which = 0;
+            for (int x = 0; x < 1000; x++) which = (which + x*x) % 7;
+            which = (which % 2) + 1;
+
+            goto *addrs[which];
+
+          FOO:
+            printf("bad\\n");
+            return 1;
+          BAR:
+            printf("good\\n");
+            const void *addr = &&FOO;
+            goto *addr;
+          }
+          '''
+        self.do_test(src, 'good\nbad')
+
     def test_pack(self):
         src = '''
           #include <stdio.h>