5794

Rather surprisingly, all the treeshake tooling is done in just about 2
hours of work. From now on it'll be easier to update stats.txt. Observations:

a) Binaries are tiny compared to conventional stacks. Tens of KB.
b) ~80% of binaries are tests and unused libraries in all my apps.
c) ~75% of LoC in SubX sources are tests or comments.

6 files changed, 198 insertions, 103 deletions

diff --git a/apps/survey.subx b/apps/survey.subx
index 701e4abe..8563116f 100644
--- a/apps/survey.subx
+++ b/apps/survey.subx
@@ -3313,8 +3313,8 @@ $emit-headers:end:
 
 emit-elf-header:  # out : (address buffered-file), segments : (address stream {string, segment-info}), labels : (address stream {string, label-info})
     # pseudocode
-    #   *Elf_e_entry = get(labels, "Entry")->address
-    #   *Elf_e_phnum = segments->write / 16         # size of a row
+    #   *$Elf_e_entry = get(labels, "Entry")->address
+    #   *$Elf_e_phnum = segments->write / 16         # size of a row
     #   emit-hex-array(out, Elf_header)
     #   write-buffered(out, "\n")
     #
@@ -3325,7 +3325,7 @@ emit-elf-header:  # out : (address buffered-file), segments : (address stream {s
     50/push-eax
     51/push-ecx
     52/push-edx  # just because we need to call idiv
-    # *Elf_e_entry = get(labels, "Entry")->address
+    # *$Elf_e_entry = get(labels, "Entry")->address
     # . eax = labels
     8b/copy                         1/mod/*+disp8   5/rm32/ebp    .           .             .           0/r32/eax   0x10/disp8      .                 # copy *(ebp+16) to eax
     # . label-info/eax = get(labels, "Entry", row-size=16, "label table")
@@ -3340,9 +3340,9 @@ emit-elf-header:  # out : (address buffered-file), segments : (address stream {s
     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               0x10/imm32        # add to esp
     # . eax = label-info->address
     8b/copy                         1/mod/*+disp8   0/rm32/eax    .           .             .           0/r32/eax   8/disp8         .                 # copy *(eax+8) to eax
-    # . *Elf_e_entry = eax
-    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   Elf_e_entry/disp32                # copy eax to *Elf_e_entry
-    # *Elf_e_phnum = segments->write / 0x10
+    # . *$Elf_e_entry = eax
+    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   $Elf_e_entry/disp32               # copy eax to *$Elf_e_entry
+    # *$Elf_e_phnum = segments->write / 0x10
     # . eax = segments
     8b/copy                         1/mod/*+disp8   5/rm32/ebp    .           .             .           0/r32/eax   0xc/disp8       .                 # copy *(ebp+12) to eax
     # . len/eax = segments->write
@@ -3351,8 +3351,8 @@ emit-elf-header:  # out : (address buffered-file), segments : (address stream {s
     b9/copy-to-ecx  0x10/imm32
     31/xor                          3/mod/direct    2/rm32/edx    .           .             .           2/r32/edx   .               .                 # clear edx
     f7          7/subop/idiv        3/mod/direct    1/rm32/ecx    .           .             .           .           .               .                 # divide edx:eax by ecx, storing quotient in eax and remainder in edx
-    # . *Elf_e_phnum = eax
-    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   Elf_e_phnum/disp32                # copy eax to *Elf_e_phnum
+    # . *$Elf_e_phnum = eax
+    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   $Elf_e_phnum/disp32               # copy eax to *$Elf_e_phnum
     # emit-hex-array(out, Elf_header)
     # . . push args
     68/push  Elf_header/imm32
@@ -3381,15 +3381,15 @@ $emit-elf-header:end:
 
 emit-elf-program-header-entry:  # out : (address buffered-file), curr-segment : (address {string, segment-info})
     # pseudocode:
-    #   *Elf_p_offset = curr-segment->file-offset
-    #   *Elf_p_vaddr = curr-segment->address
-    #   *Elf_p_paddr = curr-segment->address
-    #   *Elf_p_filesz = curr-segment->size
-    #   *Elf_p_memsz = curr-segment->size
+    #   *$Elf_p_offset = curr-segment->file-offset
+    #   *$Elf_p_vaddr = curr-segment->address
+    #   *$Elf_p_paddr = curr-segment->address
+    #   *$Elf_p_filesz = curr-segment->size
+    #   *$Elf_p_memsz = curr-segment->size
     #   if curr-segment->name == "code"
-    #     *Elf_p_flags = 5  # r-x
+    #     *$Elf_p_flags = 5  # r-x
     #   else
-    #     *Elf_p_flags = 6  # rw-
+    #     *$Elf_p_flags = 6  # rw-
     #   emit-hex-array(out, Elf_program_header_entry)
     #   write-buffered(out, "\n")
     #
@@ -3401,25 +3401,25 @@ emit-elf-program-header-entry:  # out : (address buffered-file), curr-segment :
     56/push-esi
     # esi = curr-segment
     8b/copy                         1/mod/*+disp8   5/rm32/ebp    .           .             .           6/r32/esi   0xc/disp8       .                 # copy *(ebp+12) to esi
-    # *Elf_p_offset = curr-segment->file-offset
+    # *$Elf_p_offset = curr-segment->file-offset
     # . eax = curr-segment->file-offset
     8b/copy                         1/mod/*+disp8   6/rm32/esi    .           .             .           0/r32/eax   8/disp8         .                 # copy *(esi+8) to eax
-    # . *Elf_p_offset = eax
-    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   Elf_p_offset/disp32               # copy eax to *Elf_p_offset
-    # *Elf_p_vaddr = curr-segment->address
+    # . *$Elf_p_offset = eax
+    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   $Elf_p_offset/disp32              # copy eax to *$Elf_p_offset
+    # *$Elf_p_vaddr = curr-segment->address
     # . eax = curr-segment->address
     8b/copy                         1/mod/*+disp8   6/rm32/esi    .           .             .           0/r32/eax   4/disp8         .                 # copy *(esi+4) to eax
-    # . *Elf_p_vaddr = eax
-    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   Elf_p_vaddr/disp32                # copy eax to *Elf_p_vaddr
-    # *Elf_p_paddr = curr-segment->address
-    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   Elf_p_paddr/disp32                # copy eax to *Elf_p_paddr
-    # *Elf_p_filesz = curr-segment->size
+    # . *$Elf_p_vaddr = eax
+    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   $Elf_p_vaddr/disp32               # copy eax to *$Elf_p_vaddr
+    # *$Elf_p_paddr = curr-segment->address
+    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   $Elf_p_paddr/disp32               # copy eax to *$Elf_p_paddr
+    # *$Elf_p_filesz = curr-segment->size
     # . eax = curr-segment->size
     8b/copy                         1/mod/*+disp8   6/rm32/esi    .           .             .           0/r32/eax   0xc/disp8       .                 # copy *(esi+12) to eax
-    # . *Elf_p_filesz = eax
-    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   Elf_p_filesz/disp32               # copy eax to *Elf_p_filesz
-    # *Elf_p_memsz = curr-segment->size
-    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   Elf_p_memsz/disp32                # copy eax to *Elf_p_memsz
+    # . *$Elf_p_filesz = eax
+    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   $Elf_p_filesz/disp32              # copy eax to *$Elf_p_filesz
+    # *$Elf_p_memsz = curr-segment->size
+    89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           0/r32/eax   $Elf_p_memsz/disp32               # copy eax to *$Elf_p_memsz
     # if (!string-equal?(curr-segment->name, "code") goto next check
     # . eax = curr-segment->name
     8b/copy                         0/mod/indirect  6/rm32/esi    .           .             .           0/r32/eax   .               .                 # copy *esi to eax
@@ -3434,12 +3434,12 @@ emit-elf-program-header-entry:  # out : (address buffered-file), curr-segment :
     # . if (eax == 0) goto next check
     3d/compare-eax-and  0/imm32
     74/jump-if-equal  $emit-elf-program-header-entry:data/disp8
-    # *Elf_p_flags = r-x
-    c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .           Elf_p_flags/disp32  5/imm32       # copy to *Elf_p_flags
+    # *$Elf_p_flags = r-x
+    c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .           $Elf_p_flags/disp32  5/imm32      # copy to *$Elf_p_flags
     eb/jump  $emit-elf-program-header-entry:really-emit/disp8
 $emit-elf-program-header-entry:data:
-    # otherwise *Elf_p_flags = rw-
-    c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .           Elf_p_flags/disp32  6/imm32       # copy to *Elf_p_flags
+    # otherwise *$Elf_p_flags = rw-
+    c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .           $Elf_p_flags/disp32  6/imm32      # copy to *$Elf_p_flags
 $emit-elf-program-header-entry:really-emit:
     # emit-hex-array(out, Elf_program_header_entry)
     # . . push args
@@ -4667,7 +4667,7 @@ test-num-bytes-handles-imm32:
 == data
 
 # This block of bytes gets copied to the start of the output ELF file, with
-# some fields filled in.
+# some fields (the ones with labels capitalized) filled in.
 # http://www.sco.com/developers/gabi/latest/ch4.eheader.html
 Elf_header:
   # - length
@@ -4683,7 +4683,7 @@ $e_machine:
   03 00
 $e_version:
   1/imm32
-Elf_e_entry:
+$Elf_e_entry:
   0x09000000/imm32  # approximate default; must be updated
 $e_phoff:
   0x34/imm32  # offset for the 'program header table' containing segment headers
@@ -4695,7 +4695,7 @@ $e_ehsize:
   0x34 00
 $e_phentsize:
   0x20 00
-Elf_e_phnum:
+$Elf_e_phnum:
   00 00  # number of segments; must be updated
 $e_shentsize:
   00 00  # no sections
@@ -4713,17 +4713,17 @@ Elf_program_header_entry:
   # - data
 $p_type:
   1/imm32/PT_LOAD
-Elf_p_offset:
+$Elf_p_offset:
   0/imm32  # byte offset in the file at which a segment begins; must be updated
-Elf_p_vaddr:
+$Elf_p_vaddr:
   0/imm32  # starting address to store the segment at before running the program
-Elf_p_paddr:
-  0/imm32  # should have same value as Elf_p_vaddr
-Elf_p_filesz:
+$Elf_p_paddr:
+  0/imm32  # should have same value as $Elf_p_vaddr
+$Elf_p_filesz:
   0/imm32
-Elf_p_memsz:
-  0/imm32  # should have same value as Elf_p_filesz
-Elf_p_flags:
+$Elf_p_memsz:
+  0/imm32  # should have same value as $Elf_p_filesz
+$Elf_p_flags:
   6/imm32/rw-  # read/write/execute permissions for the segment; must be updated for the code segment
 $p_align:
   # we hold this constant; changing it will require adjusting the way we
diff --git a/stats.txt b/stats.txt
index fcf0191f..393f82fc 100644
--- a/stats.txt
+++ b/stats.txt
@@ -1,36 +1,50 @@
-                          Initial   -tests/whitespace/comments
-## Lines in source
-standard library           9597     2316
-apps/crenshaw2-1b.subx      798      176
-apps/crenshaw2-1.subx       601      180
-apps/factorial.subx         107       28
-apps/handle.subx            361       58
-apps/hex.subx              1511      144
-apps/pack.subx             7348     1054
-apps/assort.subx           1318      284
-apps/dquotes.subx          2694      497
-apps/survey.subx           4573      998
+## Lines in source files
+                          Initial   -whitespace/comments/tests
+apps/factorial.subx         120       44
+apps/crenshaw2-1.subx       561      180
+apps/crenshaw2-1b.subx      757      186
+apps/handle.subx            428       44
+apps/hex.subx              1442      149
+apps/survey.subx           4733      905
+apps/pack.subx             5881      840
+apps/dquotes.subx          1925      383
+apps/assort.subx            905      183
+apps/tests.subx             284      137
+apps/sigils.subx           4641      896
+apps/calls.subx             360      448
+apps/braces.subx           1785      121
+apps/mu.subx (incomplete)  4038     1330
 
-## Bytes in executable
-apps/crenshaw2-1          17612     4112
-apps/crenshaw2-1b         18171     4140
-apps/factorial            16530     3488
-apps/handle               17323     3582
-apps/hex                  22684     4909
-apps/pack                 37316     7825
-apps/assort               22506     5342
-apps/dquotes              27186     5849
-apps/survey               42791    11258
+## Total source lines needed including libraries
+                          Initial   -whitespace/comments/tests/dead code
+apps/factorial.subx        8436     1700
+apps/crenshaw2-1.subx      8644     1925
+apps/crenshaw2-1b.subx     8736     1931
+apps/handle.subx           8601     1638
+apps/hex.subx              9065     1908
+apps/survey.subx          10217     3248
+apps/pack.subx            10589     2727
+apps/dquotes.subx          9262     2468
+apps/assort.subx           8686     2425
+apps/tests.subx            8519     2214
+apps/sigils.subx          10578     3043
+apps/calls.subx            9242     2388
+apps/braces.subx           8545     2111
+apps/mu.subx (incomplete) 10804     3421
 
-# lines per test (including whitespace/comments)
-                          num tests     num lines     lines/test
-apps/crenshaw2-1.subx        2            585          292.5
-apps/crenshaw2-1b.subx       4            785          196.25
-apps/factorial.subx          1            117          117
-apps/handle.subx             4            412          103
-apps/hex.subx               12           1515          126.25
-apps/pack.subx              42           5977          142.3
-apps/assort.subx             1            839          839
-apps/dquotes.subx           26           2680          103
-apps/survey.subx            18           4570          254
-apps/subx-common.subx       32           3098           96.8125
+## executable size in KB
+                          Initial   -tests/dead code
+apps/crenshaw2-1            41        4.3
+apps/crenshaw2-1b           42        5.2
+apps/factorial              42        5.2
+apps/handle                 42        4.2
+apps/hex                    45        5.0
+apps/survey                 51        9.6
+apps/pack                   54        7.6
+apps/dquotes                46        6.5
+apps/assort                 42        6.4
+apps/tests                  41        5.8
+apps/sigils                 54        9.1
+apps/calls                  47        7.1
+apps/braces                 42        5.9
+apps/mu (incomplete)        62       13.0
diff --git a/treeshake.cc b/treeshake.cc
index db8b5135..9bf5106e 100644
--- a/treeshake.cc
+++ b/treeshake.cc
@@ -27,6 +27,7 @@ using std::string;
 #include<iostream>
 using std::cin;
 using std::cout;
+using std::cerr;
 
 #include<sstream>
 using std::istringstream;
@@ -38,6 +39,8 @@ bool starts_with(const string& s, const string& pat) {
   return b == pat.end();
 }
 
+// input
+
 void read_body(string name, string definition_line, map<string, vector<string> >& segment) {
   // last definition wins; this only matters for the 'Entry' label in the code segment
   segment[name] = vector<string>();
@@ -78,9 +81,48 @@ void read_lines(map<string, vector<string> >& code, map<string, vector<string> >
   }
 }
 
-void treeshake(const map<string, vector<string> >& code, map<string, vector<string> >& data) {
+// treeshake
+
+bool any_line_matches(string pat, const vector<string>& lines) {
+  for (int i = 0;  i < SIZE(lines);  ++i)
+    if (lines.at(i).find(pat) != string::npos)  // conservative: confused by word boundaries, comments and string literals
+      return true;
+  return false;
+}
+
+bool is_dead(string key, const map<string, vector<string> >& code, const map<string, vector<string> >& data) {
+  if (key == "Entry") return false;
+  if (key == "==") return false;
+  for (map<string, vector<string> >::const_iterator p = code.begin();  p != code.end();  ++p) {
+    if (p->first == key) continue;
+    if (any_line_matches(key, p->second)) return false;
+  }
+  for (map<string, vector<string> >::const_iterator p = data.begin();  p != data.end();  ++p) {
+    if (p->first == key) continue;
+    if (any_line_matches(key, p->second)) return false;
+  }
+  return true;
 }
 
+void treeshake(map<string, vector<string> >& code, map<string, vector<string> >& data) {
+  for (map<string, vector<string> >::iterator p = code.begin();  p != code.end();  ++p) {
+    if (is_dead(p->first, code, data)) {
+//?       cerr << "  erasing " << p->first << '\n';
+      code.erase(p);
+      return;
+    }
+  }
+  for (map<string, vector<string> >::iterator p = data.begin();  p != data.end();  ++p) {
+    if (is_dead(p->first, code, data)) {
+//?       cerr << "  erasing " << p->first << '\n';
+      data.erase(p);
+      return;
+    }
+  }
+}
+
+// output
+
 void dump(const map<string, vector<string> > definitions) {
   // nothing special needed for segment headers, since '=' precedes all alphabet in ASCII
   for (map<string, vector<string> >::const_iterator p = definitions.begin();  p != definitions.end();  ++p) {
@@ -90,10 +132,11 @@ void dump(const map<string, vector<string> > definitions) {
   }
 }
 
-int main(int argc, const char* argv[]) {
+int main() {
   map<string, vector<string> > code, data;
   read_lines(code, data);
-  while (true) {
+  for (int iter = 0;  ;  ++iter) {
+//?     cerr << "iter: " << iter << '\n';
     int old_csize = SIZE(code), old_dsize = SIZE(data);
     treeshake(code, data);
     if (SIZE(code) == old_csize && SIZE(data) == old_dsize) break;
diff --git a/treeshake_all b/treeshake_all
index 2a13f50a..8ebf51d0 100755
--- a/treeshake_all
+++ b/treeshake_all
@@ -9,38 +9,34 @@ cd `dirname $0`
 
 export OS=${OS:-linux}
 
-for app in factorial crenshaw2-1 crenshaw2-1b
+echo "== deleting dead code"
+for app in factorial crenshaw2-1 crenshaw2-1b handle hex survey pack dquotes assort tests sigils calls braces
 do
   echo $app
-  ./treeshake_translate init.$OS 0*.subx apps/$app.subx
+  ./treeshake_translate init.$OS 0*.subx apps/subx-params.subx apps/$app.subx 2> apps/$app.stderr
+  mv a.in apps/$app.in
   mv a.treeshake apps/$app.treeshake
+  echo "LoC `cat apps/$app.subx |wc -l` => `grep -vh '^\s*$\|^\s*#' apps/$app.subx |./treeshake |wc -l`"
+  echo "LoC including common libraries: `cat apps/$app.in |wc -l` => `cat apps/$app.treeshake |wc -l`"
   mv a.elf apps/$app.treeshake.bin
-  apps/$app test
-  echo
-  apps/$app.treeshake.bin test
-  echo
+  echo "binary size: `ls -lh apps/$app |column 5` => `ls -lh apps/$app.treeshake.bin |column 5`"
 done
 
-# Phases of the self-hosted SubX translator.
+echo "== testing treeshaken binaries"
+for app in factorial crenshaw2-1 crenshaw2-1b
+do
+  echo $app
+  ./treeshake_ntranslate init.$OS 0*.subx apps/$app.subx
+  diff apps/$app a.elf
+done
 
 for app in hex survey pack assort dquotes tests sigils calls braces
 do
   echo $app
-  ./treeshake_translate init.$OS 0*.subx apps/subx-params.subx apps/$app.subx
-  mv a.treeshake apps/$app.treeshake
-  mv a.elf apps/$app.treeshake.bin
-  apps/$app test
-  echo
-  apps/$app.treeshake.bin test
-  echo
+  ./treeshake_ntranslate init.$OS 0*.subx apps/subx-params.subx apps/$app.subx
+  diff apps/$app a.elf
 done
 
-# Mu translator
 echo mu.subx
-./treeshake_translate init.$OS 0*.subx apps/mu.subx
-mv a.treeshake apps/mu.treeshake
-mv a.elf apps/mu.treeshake.bin
-apps/mu test
-echo
-apps/mu.treeshake.bin test
-echo
+./treeshake_ntranslate init.$OS 0*.subx apps/mu.subx
+diff apps/mu a.elf
diff --git a/treeshake_ntranslate b/treeshake_ntranslate
new file mode 100755
index 00000000..7a54e436
--- /dev/null
+++ b/treeshake_ntranslate
@@ -0,0 +1,40 @@
+#!/bin/sh
+# Translate SubX by running the minified self-hosted translator natively on Linux.
+# This script is a hack; see the other *translate scripts instead.
+
+set -e
+
+./build
+
+cat $*          |apps/braces.treeshake.bin   > a.braces
+
+cat a.braces    |apps/calls.treeshake.bin    > a.calls
+
+cat a.calls     |apps/sigils.treeshake.bin   > a.sigils
+
+cat a.sigils    |apps/tests.treeshake.bin    > a.tests
+
+cat a.tests     |apps/assort.treeshake.bin   > a.assort
+
+cat a.assort    |apps/dquotes.treeshake.bin  > a.dquotes
+
+# A little hack. We want ntranslate to always emit identical binaries to the
+# C++ translator. The C++ translator assorts segments before it processes
+# string literals, so we follow the same order above.
+#
+# However, dquotes currently emits a separate data segment for string literals.
+# So we need to run assort a second time to clean up after it.
+#
+# Potential solutions:
+#   a) modify C++ translator to process string literals before assorting.
+#   b) clean up dquotes to assume assorted segments, and append to the
+#   existing data segment.
+cat a.dquotes   |apps/assort.treeshake.bin   > a.assort2
+
+cat a.assort2   |apps/pack.treeshake.bin     > a.pack
+
+cat a.pack      |apps/survey.treeshake.bin   > a.survey
+
+cat a.survey    |apps/hex.treeshake.bin      > a.elf
+
+chmod +x a.elf
diff --git a/treeshake_translate b/treeshake_translate
index beb19aa5..6794b066 100755
--- a/treeshake_translate
+++ b/treeshake_translate
@@ -6,7 +6,9 @@ set -e
 
 ./build
 
-grep -vh '^\s*#\|^\s*$' $* |./treeshake > a.treeshake
+grep -vh '^\s*#\|^\s*$' $*     > a.in
+
+cat a.in        |./treeshake   > a.treeshake
 
 cat a.treeshake |apps/braces   > a.braces