pgo for unused function detection

6 files changed, 97 insertions, 14 deletions

diff --git a/src/compiler.js b/src/compiler.js
index 3047daf1..447d34b7 100644
--- a/src/compiler.js
+++ b/src/compiler.js
@@ -163,6 +163,7 @@ if (SAFE_HEAP >= 2) {
 EXPORTED_FUNCTIONS = set(EXPORTED_FUNCTIONS);
 EXPORTED_GLOBALS = set(EXPORTED_GLOBALS);
 EXCEPTION_CATCHING_WHITELIST = set(EXCEPTION_CATCHING_WHITELIST);
+DEAD_FUNCTIONS = set(DEAD_FUNCTIONS);
 
 RUNTIME_DEBUG = LIBRARY_DEBUG || GL_DEBUG;
 
diff --git a/src/intertyper.js b/src/intertyper.js
index 2103ecfa..57e3011d 100644
--- a/src/intertyper.js
+++ b/src/intertyper.js
@@ -122,16 +122,19 @@ function intertyper(data, sidePass, baseLineNums) {
               SKIP_STACK_IN_SMALL = 0;
             }
 
-            unparsedBundles.push({
-              intertype: 'unparsedFunction',
-              // We need this early, to know basic function info - ident, params, varargs
-              ident: toNiceIdent(func.ident),
-              params: func.params,
-              returnType: func.returnType,
-              hasVarArgs: func.hasVarArgs,
-              lineNum: currFunctionLineNum,
-              lines: currFunctionLines
-            });
+            var ident = toNiceIdent(func.ident);
+            if (!(ident in DEAD_FUNCTIONS)) {
+              unparsedBundles.push({
+                intertype: 'unparsedFunction',
+                // We need this early, to know basic function info - ident, params, varargs
+                ident: ident,
+                params: func.params,
+                returnType: func.returnType,
+                hasVarArgs: func.hasVarArgs,
+                lineNum: currFunctionLineNum,
+                lines: currFunctionLines
+              });
+            }
             currFunctionLines = [];
           }
         }
diff --git a/src/jsifier.js b/src/jsifier.js
index ff58ece2..1662d249 100644
--- a/src/jsifier.js
+++ b/src/jsifier.js
@@ -600,6 +600,10 @@ function JSify(data, functionsOnly, givenFunctions) {
       
       func.JS += 'function ' + func.ident + '(' + paramIdents.join(', ') + ') {\n';
 
+      if (PGO) {
+        func.JS += '  PGOMonitor.called["' + func.ident + '"] = 1;\n';
+      }
+
       if (ASM_JS) {
         // spell out argument types
         func.params.forEach(function(param) {
@@ -1587,11 +1591,17 @@ function JSify(data, functionsOnly, givenFunctions) {
 
     var shellParts = read(shellFile).split('{{BODY}}');
     print(shellParts[1]);
-    // Print out some useful metadata (for additional optimizations later, like the eliminator)
-    if (EMIT_GENERATED_FUNCTIONS) {
-      print('// EMSCRIPTEN_GENERATED_FUNCTIONS: ' + JSON.stringify(keys(Functions.implementedFunctions).filter(function(func) {
+    // Print out some useful metadata
+    if (EMIT_GENERATED_FUNCTIONS || PGO) {
+      var generatedFunctions = JSON.stringify(keys(Functions.implementedFunctions).filter(function(func) {
         return IGNORED_FUNCTIONS.indexOf(func.ident) < 0;
-      })) + '\n');
+      }));
+      if (PGO) {
+        print('PGOMonitor.allGenerated = ' + generatedFunctions + ';\nremoveRunDependency("pgo");\n');
+      }
+      if (EMIT_GENERATED_FUNCTIONS) {
+        print('// EMSCRIPTEN_GENERATED_FUNCTIONS: ' + generatedFunctions + '\n');
+      }
     }
 
     PassManager.serialize();
diff --git a/src/preamble.js b/src/preamble.js
index 9bc68d8f..7538b19c 100644
--- a/src/preamble.js
+++ b/src/preamble.js
@@ -848,5 +848,22 @@ Module['removeRunDependency'] = removeRunDependency;
 Module["preloadedImages"] = {}; // maps url to image data
 Module["preloadedAudios"] = {}; // maps url to audio data
 
+#if PGO
+var PGOMonitor = {
+  called: {},
+  dump: function() {
+    var dead = [];
+    for (var i = 0; i < this.allGenerated.length; i++) {
+      var func = this.allGenerated[i];
+      if (!this.called[func]) dead.push(func);
+    }
+    Module.print('-s DEAD_FUNCTIONS=\'' + JSON.stringify(dead) + '\'\n');
+  }
+};
+__ATEXIT__.push({ func: function() { PGOMonitor.dump() } });
+if (!Module.preRun) Module.preRun = [];
+Module.preRun.push(function() { addRunDependency('pgo') });
+#endif
+
 // === Body ===
 
diff --git a/src/settings.js b/src/settings.js
index 440d5094..101c403c 100644
--- a/src/settings.js
+++ b/src/settings.js
@@ -332,6 +332,14 @@ var ASM_JS = 0; // If 1, generate code in asm.js format. XXX This is highly expe
                 // and will not work on most codebases yet. It is NOT recommended that you
                 // try this yet.
 
+var PGO = 0; // Enables profile-guided optimization in the form of runtime checks for
+             // which functions are actually called. Emits a list during shutdown that you
+             // can pass to DEAD_FUNCTIONS (you can also emit the list manually by
+             // calling PGOMonitor.dump());
+var DEAD_FUNCTIONS = []; // A list of functions that no code will be emitted for, and
+                         // a runtime abort will happen if they are called
+                         // TODO: options to lazily load such functions
+
 var EXPLICIT_ZEXT = 0; // If 1, generate an explicit conversion of zext i1 to i32, using ?:
 
 var NECESSARY_BLOCKADDRS = []; // List of (function, block) for all block addresses that are taken.
diff --git a/tests/runner.py b/tests/runner.py
index b8855c62..61fb582a 100755
--- a/tests/runner.py
+++ b/tests/runner.py
@@ -7672,6 +7672,50 @@ def process(filename):
 
       self.do_run(src, '*\nnumber,5\nnumber,3.14\nstring,hello world\n12\nundefined\n14.56\nundefined\ncheez\nundefined\narr-ay\nundefined\nmore\nnumber,10\n650\nnumber,21\n*\natr\n10\nbret\n53\n*\nstack is ok.\n', post_build=post)
 
+    def test_pgo(self):
+      if Settings.ASM_JS: return self.skip('PGO does not work in asm mode')
+
+      src = r'''
+        #include <stdio.h>
+        extern "C" {
+        int used(int x) {
+          if (x == 0) return -1;
+          return used(x/3) + used(x/17) + x%5;
+        }
+        int unused(int x) {
+          if (x == 0) return -1;
+          return unused(x/4) + unused(x/23) + x%7;
+        }
+        }
+        int main(int argc, char **argv) {
+          printf("*%d*\n", argc == 3 ? unused(argv[0][0] + 1024) : used(argc + 1555));
+          return 0;
+        }
+      '''
+
+      def test(expected, args=[], no_build=False):
+        self.do_run(src, expected, args=args, no_build=no_build)
+        return open(self.in_dir('src.cpp.o.js')).read()
+
+      # Sanity check that it works and the dead function is emitted
+      js = test('*9*')
+      assert 'function _unused(' in js
+
+      # Run with PGO, see that unused is true to its name
+      Settings.PGO = 1
+      test("*9*\n-s DEAD_FUNCTIONS='[\"_unused\"]'")
+      Settings.PGO = 0
+
+      # Kill off the dead function, still works and it is not emitted
+      Settings.DEAD_FUNCTIONS = ['_unused']
+      js = test('*9*')
+      assert 'function _unused(' not in js
+
+      # Run the same code with argc that uses the dead function, see abort
+      test('ReferenceError: _unused is not defined', args=['a', 'b'], no_build=True)
+
+      # TODO: function pointers
+
     def test_scriptaclass(self):
         if self.emcc_args is None: return self.skip('requires emcc')
         if Settings.ASM_JS: return self.skip('asm does not bindings generator yet')