DWARF: Update debug_ranges (#2612)

Pretty straightforward given all we have so far.

Note that fannkuch3_manyopts has an example of
a sequence of ranges of which some must be skipped
while others must not, showing we handle that by
skipping the bad ones and updating the remaining. That
is, if that we have a sequence of two (begin, end) spans

[(10, 20),
 (30, 40)]

It's possible (10, 20) maps in the new binary to (110, 120)
while (30, 40) was eliminated by the optimizer and we have
nothing valid to map it to. In that case we emit

[(110, 120)]

6 files changed, 94 insertions, 46 deletions

diff --git a/src/wasm/wasm-debug.cpp b/src/wasm/wasm-debug.cpp
index 7ca9c9df5..ac1314ad6 100644
--- a/src/wasm/wasm-debug.cpp
+++ b/src/wasm/wasm-debug.cpp
@@ -368,7 +368,6 @@ struct AddrExprMap {
     }
   }
 
-
   Expression* getStart(BinaryLocation addr) const {
     auto iter = startMap.find(addr);
     if (iter != startMap.end()) {
@@ -498,6 +497,10 @@ struct LocationUpdater {
     return 0;
   }
 
+  bool hasOldExprEndAddr(BinaryLocation oldAddr) const {
+    return oldExprAddrMap.getEnd(oldAddr);
+  }
+
   BinaryLocation getNewFuncStartAddr(BinaryLocation oldAddr) const {
     if (auto* func = oldFuncAddrMap.getStart(oldAddr)) {
       // The function might have been optimized away, check.
@@ -612,7 +615,6 @@ static void updateDebugLines(llvm::DWARFYAML::Data& data,
         } else if (locationUpdater.hasOldExtraAddr(oldAddr)) {
           newAddr = locationUpdater.getNewExtraAddr(oldAddr);
         }
-        // TODO: last 'end' of a function
         if (newAddr) {
           // LLVM sometimes emits the same address more than once. We should
           // probably investigate that.
@@ -764,6 +766,55 @@ static void updateCompileUnits(const BinaryenDWARFInfo& info,
     });
 }
 
+static void updateRanges(llvm::DWARFYAML::Data& yaml,
+                         const LocationUpdater& locationUpdater) {
+  // In each range section, try to update the start and end. If we no longer
+  // have something to map them to, we must skip that part.
+  size_t skip = 0;
+  for (size_t i = 0; i < yaml.Ranges.size(); i++) {
+    auto& range = yaml.Ranges[i];
+    BinaryLocation oldStart = range.Start, oldEnd = range.End, newStart = 0,
+                   newEnd = 0;
+    // If this was not an end marker, try to find what it should be updated to.
+    if (oldStart != 0 && oldEnd != 0) {
+      if (locationUpdater.hasOldExprAddr(oldStart)) {
+        newStart = locationUpdater.getNewExprAddr(oldStart);
+      } else if (locationUpdater.hasOldFuncStartAddr(oldStart)) {
+        newStart = locationUpdater.getNewFuncStartAddr(oldStart);
+      }
+      if (locationUpdater.hasOldExprEndAddr(oldEnd)) {
+        newEnd = locationUpdater.getNewExprEndAddr(oldEnd);
+      } else if (locationUpdater.hasOldFuncEndAddr(oldEnd)) {
+        newEnd = locationUpdater.getNewFuncEndAddr(oldEnd);
+      }
+      if (newStart == 0 || newEnd == 0) {
+        // This part of the range no longer has a mapping, so we must skip it.
+        skip++;
+        continue;
+      }
+      // The range start and end markers have been preserved. However, TODO
+      // instructions in the middle may have moved around, making the range no
+      // longer contiguous, we should check that, and possibly split/merge
+      // the range. Or, we may need to have tracking in the IR for this.
+    } else {
+      // This was not a valid range in the old binary. It was either two 0's
+      // (an end marker) or an invalid value that should be ignored. Either way,
+      // write an end marker and finish the current section of ranges, filling
+      // it out to the original size (we must fill it out as indexes into
+      // the ranges section are not updated - we could update them and then
+      // pack the section, as an optimization TODO).
+      while (skip) {
+        auto& writtenRange = yaml.Ranges[i - skip];
+        writtenRange.Start = writtenRange.End = 0;
+        skip--;
+      }
+    }
+    auto& writtenRange = yaml.Ranges[i - skip];
+    writtenRange.Start = newStart;
+    writtenRange.End = newEnd;
+  }
+}
+
 void writeDWARFSections(Module& wasm, const BinaryLocations& newLocations) {
   BinaryenDWARFInfo info(wasm);
 
@@ -779,6 +830,8 @@ void writeDWARFSections(Module& wasm, const BinaryLocations& newLocations) {
 
   updateCompileUnits(info, data, locationUpdater);
 
+  updateRanges(data, locationUpdater);
+
   // Convert to binary sections.
   auto newSections =
     EmitDebugSections(data, false /* EmitFixups for debug_info */);
diff --git a/test/passes/fannkuch0.bin.txt b/test/passes/fannkuch0.bin.txt
index 1f8bd371d..5bced45b4 100644
--- a/test/passes/fannkuch0.bin.txt
+++ b/test/passes/fannkuch0.bin.txt
@@ -2420,9 +2420,9 @@ Abbrev table for offset: 0x00000000
               DW_AT_comp_dir [DW_FORM_strp]	( .debug_str[0x000000a8] = "/home/alon/Dev/emscripten")
               DW_AT_low_pc [DW_FORM_addr]	(0x0000000000000000)
               DW_AT_ranges [DW_FORM_sec_offset]	(0x00000000
-                 [0x00000006, 0x0000088c)
-                 [0x0000088e, 0x000009dc)
-                 [0x000009de, 0x00001042))
+                 [0x00000006, 0x00000872)
+                 [0x00000874, 0x000009a0)
+                 [0x000009a2, 0x00000fde))
 
 0x00000026:   DW_TAG_pointer_type [2]  
                 DW_AT_type [DW_FORM_ref4]	(cu + 0x002b => {0x0000002b} "worker_args")
@@ -5188,9 +5188,9 @@ file_names[  3]:
 0x00000191: "cleanup"
 
 .debug_ranges contents:
-00000000 00000006 0000088c
-00000000 0000088e 000009dc
-00000000 000009de 00001042
+00000000 00000006 00000872
+00000000 00000874 000009a0
+00000000 000009a2 00000fde
 00000000 <End of list>
 (module
  (type $i32_=>_i32 (func (param i32) (result i32)))
diff --git a/test/passes/fannkuch3.bin.txt b/test/passes/fannkuch3.bin.txt
index e2f3e3675..0d5d8a859 100644
--- a/test/passes/fannkuch3.bin.txt
+++ b/test/passes/fannkuch3.bin.txt
@@ -2469,8 +2469,8 @@ Abbrev table for offset: 0x00000000
               DW_AT_comp_dir [DW_FORM_strp]	( .debug_str[0x000000a9] = "/usr/local/google/home/azakai/Dev/2-binaryen")
               DW_AT_low_pc [DW_FORM_addr]	(0x0000000000000000)
               DW_AT_ranges [DW_FORM_sec_offset]	(0x00000040
-                 [0x00000006, 0x0000039d)
-                 [0x0000039f, 0x000006e1))
+                 [0x00000006, 0x00000389)
+                 [0x0000038b, 0x00000686))
 
 0x00000026:   DW_TAG_pointer_type [2]  
                 DW_AT_type [DW_FORM_ref4]	(cu + 0x002b => {0x0000002b} "worker_args")
@@ -2678,10 +2678,10 @@ Abbrev table for offset: 0x00000000
 
 0x00000159:     DW_TAG_lexical_block [14] *
                   DW_AT_ranges [DW_FORM_sec_offset]	(0x00000000
-                     [0x00000185, 0x000001c3)
-                     [0x000001ed, 0x000001f6)
-                     [0x0000030e, 0x0000034c)
-                     [0x00000376, 0x0000037f))
+                     [0x00000175, 0x000001b3)
+                     [0x000001dd, 0x000001e6)
+                     [0x00000302, 0x00000340)
+                     [0x0000036a, 0x00000373))
 
 0x0000015e:       DW_TAG_variable [12]  
                     DW_AT_name [DW_FORM_strp]	( .debug_str[0x00000163] = "p0")
@@ -2927,8 +2927,8 @@ Abbrev table for offset: 0x00000000
 
 0x000002e3:       DW_TAG_lexical_block [14] *
                     DW_AT_ranges [DW_FORM_sec_offset]	(0x00000028
-                       [0x00000517, 0x0000055e)
-                       [0x000005de, 0x0000062b))
+                       [0x000004d9, 0x00000520)
+                       [0x0000059e, 0x000005eb))
 
 0x000002e8:         DW_TAG_variable [26]  
                       DW_AT_location [DW_FORM_sec_offset]	(0x000003bc: 
@@ -4778,16 +4778,16 @@ file_names[  4]:
 0x000001ad: "char"
 
 .debug_ranges contents:
-00000000 00000185 000001c3
-00000000 000001ed 000001f6
-00000000 0000030e 0000034c
-00000000 00000376 0000037f
+00000000 00000175 000001b3
+00000000 000001dd 000001e6
+00000000 00000302 00000340
+00000000 0000036a 00000373
 00000000 <End of list>
-00000028 00000517 0000055e
-00000028 000005de 0000062b
+00000028 000004d9 00000520
+00000028 0000059e 000005eb
 00000028 <End of list>
-00000040 00000006 0000039d
-00000040 0000039f 000006e1
+00000040 00000006 00000389
+00000040 0000038b 00000686
 00000040 <End of list>
 (module
  (type $i32_=>_i32 (func (param i32) (result i32)))
diff --git a/test/passes/fannkuch3_manyopts.bin.txt b/test/passes/fannkuch3_manyopts.bin.txt
index 0ffb00d72..e8055b7e3 100644
--- a/test/passes/fannkuch3_manyopts.bin.txt
+++ b/test/passes/fannkuch3_manyopts.bin.txt
@@ -2469,8 +2469,8 @@ Abbrev table for offset: 0x00000000
               DW_AT_comp_dir [DW_FORM_strp]	( .debug_str[0x000000a9] = "/usr/local/google/home/azakai/Dev/2-binaryen")
               DW_AT_low_pc [DW_FORM_addr]	(0x0000000000000000)
               DW_AT_ranges [DW_FORM_sec_offset]	(0x00000040
-                 [0x00000006, 0x0000039d)
-                 [0x0000039f, 0x000006e1))
+                 [0x00000007, 0x0000035a)
+                 [0x0000035c, 0x0000062b))
 
 0x00000026:   DW_TAG_pointer_type [2]  
                 DW_AT_type [DW_FORM_ref4]	(cu + 0x002b => {0x0000002b} "worker_args")
@@ -2677,11 +2677,7 @@ Abbrev table for offset: 0x00000000
                   DW_AT_type [DW_FORM_ref4]	(cu + 0x0059 => {0x00000059} "int")
 
 0x00000159:     DW_TAG_lexical_block [14] *
-                  DW_AT_ranges [DW_FORM_sec_offset]	(0x00000000
-                     [0x00000185, 0x000001c3)
-                     [0x000001ed, 0x000001f6)
-                     [0x0000030e, 0x0000034c)
-                     [0x00000376, 0x0000037f))
+                  DW_AT_ranges [DW_FORM_sec_offset]	(0x00000000)
 
 0x0000015e:       DW_TAG_variable [12]  
                     DW_AT_name [DW_FORM_strp]	( .debug_str[0x00000163] = "p0")
@@ -2927,8 +2923,7 @@ Abbrev table for offset: 0x00000000
 
 0x000002e3:       DW_TAG_lexical_block [14] *
                     DW_AT_ranges [DW_FORM_sec_offset]	(0x00000028
-                       [0x00000517, 0x0000055e)
-                       [0x000005de, 0x0000062b))
+                       [0x00000553, 0x0000059d))
 
 0x000002e8:         DW_TAG_variable [26]  
                       DW_AT_location [DW_FORM_sec_offset]	(0x000003bc: 
@@ -3712,16 +3707,16 @@ file_names[  4]:
 0x000001ad: "char"
 
 .debug_ranges contents:
-00000000 00000185 000001c3
-00000000 000001ed 000001f6
-00000000 0000030e 0000034c
-00000000 00000376 0000037f
 00000000 <End of list>
-00000028 00000517 0000055e
-00000028 000005de 0000062b
+00000008 <End of list>
+00000010 <End of list>
+00000018 <End of list>
+00000020 <End of list>
+00000028 00000553 0000059d
 00000028 <End of list>
-00000040 00000006 0000039d
-00000040 0000039f 000006e1
+00000038 <End of list>
+00000040 00000007 0000035a
+00000040 0000035c 0000062b
 00000040 <End of list>
 (module
  (type $i32_=>_i32 (func (param i32) (result i32)))
diff --git a/test/passes/fib2.bin.txt b/test/passes/fib2.bin.txt
index 4341eee8c..8b7eb7104 100644
--- a/test/passes/fib2.bin.txt
+++ b/test/passes/fib2.bin.txt
@@ -382,7 +382,7 @@ Abbrev table for offset: 0x00000000
               DW_AT_low_pc [DW_FORM_addr]	(0x0000000000000000)
               DW_AT_ranges [DW_FORM_sec_offset]	(0x00000000
                  [0x00000005, 0x0000003d)
-                 [0x0000003e, 0x00000048))
+                 [0x0000003e, 0x00000044))
 
 0x00000026:   DW_TAG_subprogram [2] *
                 DW_AT_low_pc [DW_FORM_addr]	(0x0000000000000005)
@@ -610,7 +610,7 @@ file_names[  1]:
 
 .debug_ranges contents:
 00000000 00000005 0000003d
-00000000 0000003e 00000048
+00000000 0000003e 00000044
 00000000 <End of list>
 (module
  (type $none_=>_none (func))
diff --git a/test/passes/ignore_missing_func.bin.txt b/test/passes/ignore_missing_func.bin.txt
index 4f06c2418..6fff7c970 100644
--- a/test/passes/ignore_missing_func.bin.txt
+++ b/test/passes/ignore_missing_func.bin.txt
@@ -622,7 +622,7 @@ Abbrev table for offset: 0x00000000
               DW_AT_comp_dir [DW_FORM_strp]	( .debug_str[0x0000009b] = "/home/alon/Dev/emscripten")
               DW_AT_low_pc [DW_FORM_addr]	(0x0000000000000000)
               DW_AT_ranges [DW_FORM_sec_offset]	(0x00000000
-                 [0x00000005, 0x0000005f))
+                 [0x00000005, 0x0000005b))
 
 0x00000026:   DW_TAG_variable [2]  
                 DW_AT_name [DW_FORM_strp]	( .debug_str[0x000000b5] = "quine")
@@ -817,9 +817,9 @@ file_names[  1]:
 0x000000e9: "x"
 
 .debug_ranges contents:
-00000000 00000005 0000005f
+00000000 00000005 0000005b
 00000000 <End of list>
-00000010 00000060 000000c4
+00000010 0000005c 000000ad
 00000010 <End of list>
 (module
  (type $none_=>_none (func))