Lazily save initialState of registers during unwind.

[saugustine]

Summary

Copying all of the saved register state on every entry to
parseInstruction is a severe performance contraint, especially
because most of this saved state is never used. On x86 linux
this is about 560 bytes, and will be more on other platforms.

When performance testing libunwind, this memcpy appears at the
top of nearly all our tests.

By only saving this state as needed, we see increases in performance
of around 2.5% for the ctak test here.

https://github.com/clasp-developers/ctak

Certain internal extremely exception-heavy tasks run in about 2/3
the time.

Note that by stashing the new boolean inside what had been padding in
the original structure, this uses no additional memory.

[saugustine]

Minor formatting fixes.

[saugustine]

Formating fixes

[saugustine]

Fixing last linter complaint (the indent of the switch case), would include either re-indenting other cases involved in this switch, or having the cases not aligned. I think the current situation is better.

[saugustine]

Move initialization to in class.

[jgorbe]

libunwind/src/DwarfParser.hpp

427

What do you think about making this boolean argument an enum? This call site would be clearer if it was something like

// this enumerator is just an example, feel free to use anything better that comes to mind.
PrologInfo initialState(DONT_INITIALIZE);

[saugustine]

Switch boolean to a more clear enum to make call site clearer.

[jgorbe]

Looks good to me.

libunwind/src/DwarfParser.hpp

enum RegisterSavedWhere {
     kRegisterInCFA,
     kRegisterOffsetFromCFA,
     kRegisterInRegister,
     kRegisterAtExpression,
     kRegisterIsExpression
   };
   struct RegisterLocation {
     RegisterSavedWhere location;
+    bool initialStateSaved;
     int64_t value;
   };
   /// Information about a frame layout and registers saved determined
   /// by "running" the DWARF FDE "instructions"
   struct PrologInfo {
     uint32_t          cfaRegister;
     int32_t           cfaRegisterOffset;  // CFA = (cfaRegister)+cfaRegisterOffset
     int64_t           cfaExpression;      // CFA = expression
     uint32_t          spExtraArgSize;
     uint32_t          codeOffsetAtStackDecrement;
     bool              registersInOtherRegisters;
     bool              sameValueUsed;
     RegisterLocation  savedRegisters[kMaxRegisterNumber + 1];
+    // When saving registers, this data structure is lazily initialized.
+    PrologInfo(bool Initialize = true) {
+      if (Initialize)
+        memset(this, 0, sizeof(*this));
+    }
+    void checkSaveRegister(uint64_t reg, PrologInfo &initialState) {
+      if (!savedRegisters[reg].initialStateSaved) {
+        initialState.savedRegisters[reg] = savedRegisters[reg];
+        savedRegisters[reg].initialStateSaved = true;
+      }
+    }
+    void setRegister(uint64_t reg, RegisterSavedWhere newLocation,
+                     int64_t newValue, PrologInfo &initialState) {
+      checkSaveRegister(reg, initialState);
+      savedRegisters[reg].location = newLocation;
+      savedRegisters[reg].value = newValue;
+    }
+    void setRegisterLocation(uint64_t reg, RegisterSavedWhere newLocation,
+                             PrologInfo &initialState) {
+      checkSaveRegister(reg, initialState);
+      savedRegisters[reg].location = newLocation;
+    }
+    void setRegisterValue(uint64_t reg, int64_t newValue,
+                          PrologInfo &initialState) {
+      checkSaveRegister(reg, initialState);
+      savedRegisters[reg].value = newValue;
+    }
+    void restoreRegisterToInitialState(uint64_t reg, PrologInfo &initialState) {
+      if (savedRegisters[reg].initialStateSaved)
+        savedRegisters[reg] = initialState.savedRegisters[reg];
+      // else the register still holds its initial state
+    }
   };
 
   struct PrologInfoStackEntry {
     PrologInfoStackEntry(PrologInfoStackEntry *n, const PrologInfo &i)
         : next(n), info(i) {}
     PrologInfoStackEntry *next;
     PrologInfo info;
   };

 
 
 /// "run" the DWARF instructions and create the abstact PrologInfo for an FDE
 template <typename A>
 bool CFI_Parser<A>::parseFDEInstructions(A &addressSpace,
                                          const FDE_Info &fdeInfo,
                                          const CIE_Info &cieInfo, pint_t upToPC,
                                          int arch, PrologInfo *results) {
-  // clear results
-  memset(results, '\0', sizeof(PrologInfo));
   PrologInfoStackEntry *rememberStack = NULL;
 
   // parse CIE then FDE instructions
   bool returnValue =
       parseInstructions(addressSpace, cieInfo.cieInstructions,
                         cieInfo.cieStart + cieInfo.cieLength, cieInfo,
                         (pint_t)(-1), rememberStack, arch, results) &&
       parseInstructions(addressSpace, fdeInfo.fdeInstructions,

 template <typename A>
 bool CFI_Parser<A>::parseInstructions(A &addressSpace, pint_t instructions,
                                       pint_t instructionsEnd,
                                       const CIE_Info &cieInfo, pint_t pcoffset,
                                       PrologInfoStackEntry *&rememberStack,
                                       int arch, PrologInfo *results) {
   pint_t p = instructions;
   pint_t codeOffset = 0;
-  PrologInfo initialState = *results;
+  // initialState is lazily initialized as registers in results are
+  // modified. Take care to use PrologInfo accessor functions to avoid reading
+  // uninitialized data.
+  PrologInfo initialState(false);
 
   _LIBUNWIND_TRACE_DWARF("parseInstructions(instructions=0x%0" PRIx64 ")\n",
                          static_cast<uint64_t>(instructionsEnd));
 
   // see DWARF Spec, section 6.4.2 for details on unwind opcodes
   while ((p < instructionsEnd) && (codeOffset < pcoffset)) {
     uint64_t reg;
     uint64_t reg2;
case DW_CFA_offset_extended:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       offset = (int64_t)addressSpace.getULEB128(p, instructionsEnd)
                                                   * cieInfo.dataAlignFactor;
       if (reg > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0(
                 "malformed DW_CFA_offset_extended DWARF unwind, reg too big");
         return false;
       }
-      results->savedRegisters[reg].location = kRegisterInCFA;
-      results->savedRegisters[reg].value = offset;
+      results->setRegister(reg, kRegisterInCFA, offset, initialState);
       _LIBUNWIND_TRACE_DWARF("DW_CFA_offset_extended(reg=%" PRIu64 ", "
                              "offset=%" PRId64 ")\n",
                              reg, offset);
       break;
     case DW_CFA_restore_extended:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       if (reg > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0(
             "malformed DW_CFA_restore_extended DWARF unwind, reg too big");
         return false;
       }
-      results->savedRegisters[reg] = initialState.savedRegisters[reg];
+      results->restoreRegisterToInitialState(reg, initialState);
       _LIBUNWIND_TRACE_DWARF("DW_CFA_restore_extended(reg=%" PRIu64 ")\n", reg);
       break;
     case DW_CFA_undefined:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       if (reg > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0(
                 "malformed DW_CFA_undefined DWARF unwind, reg too big");
         return false;
       }
-      results->savedRegisters[reg].location = kRegisterUnused;
+      results->setRegisterLocation(reg, kRegisterUnused, initialState);
       _LIBUNWIND_TRACE_DWARF("DW_CFA_undefined(reg=%" PRIu64 ")\n", reg);
       break;
     case DW_CFA_same_value:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       if (reg > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0(
                 "malformed DW_CFA_same_value DWARF unwind, reg too big");
         return false;
       }
       // <rdar://problem/8456377> DW_CFA_same_value unsupported
       // "same value" means register was stored in frame, but its current
       // value has not changed, so no need to restore from frame.
       // We model this as if the register was never saved.
-      results->savedRegisters[reg].location = kRegisterUnused;
+      results->setRegisterLocation(reg, kRegisterUnused, initialState);
       // set flag to disable conversion to compact unwind
       results->sameValueUsed = true;
       _LIBUNWIND_TRACE_DWARF("DW_CFA_same_value(reg=%" PRIu64 ")\n", reg);
       break;
     case DW_CFA_register:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       reg2 = addressSpace.getULEB128(p, instructionsEnd);
       if (reg > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0(
                 "malformed DW_CFA_register DWARF unwind, reg too big");
         return false;
       }
       if (reg2 > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0(
                 "malformed DW_CFA_register DWARF unwind, reg2 too big");
         return false;
       }
-      results->savedRegisters[reg].location = kRegisterInRegister;
-      results->savedRegisters[reg].value = (int64_t)reg2;
+      results->setRegister(reg, kRegisterInRegister, (int64_t)reg2,
+                           initialState);
       // set flag to disable conversion to compact unwind
       results->registersInOtherRegisters = true;
       _LIBUNWIND_TRACE_DWARF(
           "DW_CFA_register(reg=%" PRIu64 ", reg2=%" PRIu64 ")\n", reg, reg2);
       break;
 #if !defined(_LIBUNWIND_NO_HEAP)
     case DW_CFA_remember_state:
       // avoid operator new, because that would be an upward dependency
case DW_CFA_def_cfa_expression:
       break;
     case DW_CFA_expression:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       if (reg > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0(
                 "malformed DW_CFA_expression DWARF unwind, reg too big");
         return false;
       }
-      results->savedRegisters[reg].location = kRegisterAtExpression;
-      results->savedRegisters[reg].value = (int64_t)p;
+      results->setRegister(reg, kRegisterAtExpression, (int64_t)p,
+                           initialState);
       length = addressSpace.getULEB128(p, instructionsEnd);
       assert(length < static_cast<pint_t>(~0) && "pointer overflow");
       p += static_cast<pint_t>(length);
       _LIBUNWIND_TRACE_DWARF("DW_CFA_expression(reg=%" PRIu64 ", "
                              "expression=0x%" PRIx64 ", "
                              "length=%" PRIu64 ")\n",
                              reg, results->savedRegisters[reg].value, length);
       break;
     case DW_CFA_offset_extended_sf:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       if (reg > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0(
             "malformed DW_CFA_offset_extended_sf DWARF unwind, reg too big");
         return false;
       }
       offset =
           addressSpace.getSLEB128(p, instructionsEnd) * cieInfo.dataAlignFactor;
-      results->savedRegisters[reg].location = kRegisterInCFA;
-      results->savedRegisters[reg].value = offset;
+      results->setRegister(reg, kRegisterInCFA, offset, initialState);
       _LIBUNWIND_TRACE_DWARF("DW_CFA_offset_extended_sf(reg=%" PRIu64 ", "
                              "offset=%" PRId64 ")\n",
                              reg, offset);
       break;
     case DW_CFA_def_cfa_sf:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       offset =
           addressSpace.getSLEB128(p, instructionsEnd) * cieInfo.dataAlignFactor;
case DW_CFA_val_offset:
         _LIBUNWIND_LOG(
                 "malformed DW_CFA_val_offset DWARF unwind, reg (%" PRIu64
                 ") out of range\n",
                 reg);
         return false;
       }
       offset = (int64_t)addressSpace.getULEB128(p, instructionsEnd)
                                                     * cieInfo.dataAlignFactor;
-      results->savedRegisters[reg].location = kRegisterOffsetFromCFA;
-      results->savedRegisters[reg].value = offset;
+      results->setRegister(reg, kRegisterOffsetFromCFA, offset, initialState);
       _LIBUNWIND_TRACE_DWARF("DW_CFA_val_offset(reg=%" PRIu64 ", "
                              "offset=%" PRId64 "\n",
                              reg, offset);
       break;
     case DW_CFA_val_offset_sf:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       if (reg > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0(
                 "malformed DW_CFA_val_offset_sf DWARF unwind, reg too big");
         return false;
       }
       offset =
           addressSpace.getSLEB128(p, instructionsEnd) * cieInfo.dataAlignFactor;
-      results->savedRegisters[reg].location = kRegisterOffsetFromCFA;
-      results->savedRegisters[reg].value = offset;
+      results->setRegister(reg, kRegisterOffsetFromCFA, offset, initialState);
       _LIBUNWIND_TRACE_DWARF("DW_CFA_val_offset_sf(reg=%" PRIu64 ", "
                              "offset=%" PRId64 "\n",
                              reg, offset);
       break;
     case DW_CFA_val_expression:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       if (reg > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0(
                 "malformed DW_CFA_val_expression DWARF unwind, reg too big");
         return false;
       }
-      results->savedRegisters[reg].location = kRegisterIsExpression;
-      results->savedRegisters[reg].value = (int64_t)p;
+      results->setRegister(reg, kRegisterIsExpression, (int64_t)p,
+                           initialState);
       length = addressSpace.getULEB128(p, instructionsEnd);
       assert(length < static_cast<pint_t>(~0) && "pointer overflow");
       p += static_cast<pint_t>(length);
       _LIBUNWIND_TRACE_DWARF("DW_CFA_val_expression(reg=%" PRIu64 ", "
                              "expression=0x%" PRIx64 ", length=%" PRIu64 ")\n",
                              reg, results->savedRegisters[reg].value, length);
       break;
     case DW_CFA_GNU_args_size:
       length = addressSpace.getULEB128(p, instructionsEnd);
       results->spExtraArgSize = (uint32_t)length;
       _LIBUNWIND_TRACE_DWARF("DW_CFA_GNU_args_size(%" PRIu64 ")\n", length);
       break;
     case DW_CFA_GNU_negative_offset_extended:
       reg = addressSpace.getULEB128(p, instructionsEnd);
       if (reg > kMaxRegisterNumber) {
         _LIBUNWIND_LOG0("malformed DW_CFA_GNU_negative_offset_extended DWARF "
                         "unwind, reg too big");
         return false;
       }
       offset = (int64_t)addressSpace.getULEB128(p, instructionsEnd)
                                                     * cieInfo.dataAlignFactor;
-      results->savedRegisters[reg].location = kRegisterInCFA;
-      results->savedRegisters[reg].value = -offset;
+      results->setRegister(reg, kRegisterInCFA, -offset, initialState);
       _LIBUNWIND_TRACE_DWARF(
           "DW_CFA_GNU_negative_offset_extended(%" PRId64 ")\n", offset);
       break;
 
 #if defined(_LIBUNWIND_TARGET_AARCH64) || defined(_LIBUNWIND_TARGET_SPARC)
     // The same constant is used to represent different instructions on
     // AArch64 (negate_ra_state) and SPARC (window_save).
     static_assert(DW_CFA_AARCH64_negate_ra_state == DW_CFA_GNU_window_save,
                   "uses the same constant");
     case DW_CFA_AARCH64_negate_ra_state:
       switch (arch) {
 #if defined(_LIBUNWIND_TARGET_AARCH64)
-      case REGISTERS_ARM64:
-        results->savedRegisters[UNW_ARM64_RA_SIGN_STATE].value ^= 0x1;
+        case REGISTERS_ARM64: {
+          int64_t value =
+              results->savedRegisters[UNW_ARM64_RA_SIGN_STATE].value ^ 0x1;
+          results->setRegisterValue(UNW_ARM64_RA_SIGN_STATE, value, initialState);
           _LIBUNWIND_TRACE_DWARF("DW_CFA_AARCH64_negate_ra_state\n");
-        break;
+        } break;
 #endif
+
 #if defined(_LIBUNWIND_TARGET_SPARC)
       // case DW_CFA_GNU_window_save:
       case REGISTERS_SPARC:
         _LIBUNWIND_TRACE_DWARF("DW_CFA_GNU_window_save()\n");
         for (reg = UNW_SPARC_O0; reg <= UNW_SPARC_O7; reg++) {
-          results->savedRegisters[reg].location = kRegisterInRegister;
-          results->savedRegisters[reg].value =
-              ((int64_t)reg - UNW_SPARC_O0) + UNW_SPARC_I0;
+          results->setRegister(reg, kRegisterInRegister,
+                               ((int64_t)reg - UNW_SPARC_O0) + UNW_SPARC_I0,
+                               initialState);
         }
 
         for (reg = UNW_SPARC_L0; reg <= UNW_SPARC_I7; reg++) {
-          results->savedRegisters[reg].location = kRegisterInCFA;
-          results->savedRegisters[reg].value =
-              ((int64_t)reg - UNW_SPARC_L0) * 4;
+          results->setRegister(reg, kRegisterInCFA,
+                               ((int64_t)reg - UNW_SPARC_L0) * 4, initialState);
         }
         break;
 #endif
       }
       break;
 #else
       (void)arch;
 #endif
 
     default:
       operand = opcode & 0x3F;
       switch (opcode & 0xC0) {
       case DW_CFA_offset:
         reg = operand;
         if (reg > kMaxRegisterNumber) {
           _LIBUNWIND_LOG("malformed DW_CFA_offset DWARF unwind, reg (%" PRIu64
                          ") out of range",
                   reg);
           return false;
         }
         offset = (int64_t)addressSpace.getULEB128(p, instructionsEnd)
                                                     * cieInfo.dataAlignFactor;
-        results->savedRegisters[reg].location = kRegisterInCFA;
-        results->savedRegisters[reg].value = offset;
+        results->setRegister(reg, kRegisterInCFA, offset, initialState);
         _LIBUNWIND_TRACE_DWARF("DW_CFA_offset(reg=%d, offset=%" PRId64 ")\n",
                                operand, offset);
         break;
       case DW_CFA_advance_loc:
         codeOffset += operand * cieInfo.codeAlignFactor;
         _LIBUNWIND_TRACE_DWARF("DW_CFA_advance_loc: new offset=%" PRIu64 "\n",
                                static_cast<uint64_t>(codeOffset));
         break;
       case DW_CFA_restore:
         reg = operand;
         if (reg > kMaxRegisterNumber) {
           _LIBUNWIND_LOG("malformed DW_CFA_restore DWARF unwind, reg (%" PRIu64
                          ") out of range",
                   reg);
           return false;
         }
-        results->savedRegisters[reg] = initialState.savedRegisters[reg];
+        results->restoreRegisterToInitialState(reg, initialState);
         _LIBUNWIND_TRACE_DWARF("DW_CFA_restore(reg=%" PRIu64 ")\n",
                                static_cast<uint64_t>(operand));
         break;
       default:
         _LIBUNWIND_TRACE_DWARF("unknown CFA opcode 0x%02X\n", opcode);
         return false;
       }
     }
   }
 
   return true;
 }
 
 } // namespace libunwind
 
 #endif // __DWARF_PARSER_HPP__