[Courgette] Using LabelManager to reduce Courgette-apply peak RAM by 25%.

courgette/disassembler_elf_32.cc

Index: courgette/disassembler_elf_32.cc
diff --git a/courgette/disassembler_elf_32.cc b/courgette/disassembler_elf_32.cc
index 6285c3878170f4c2f7371b43282432b8fde688da..4809391fb3bfc59def1ef654d4f04a4169df6f72 100644
--- a/courgette/disassembler_elf_32.cc
+++ b/courgette/disassembler_elf_32.cc
@@ -32,6 +32,15 @@ std::vector<Elf32_Half> GetSectionHeaderFileOffsetOrder(
 
 }  // namespace
 
+DisassemblerElf32::Elf32RvaVisitor_Rel32::Elf32RvaVisitor_Rel32(
+    const std::vector<TypedRVA*>& rva_locations)
+    : VectorRvaVisitor<TypedRVA*>(rva_locations) {
+}
+
+RVA DisassemblerElf32::Elf32RvaVisitor_Rel32::Get() const {
+  return (*it_)->rva() + (*it_)->relative_target();
+}
+
 DisassemblerElf32::DisassemblerElf32(const void* start, size_t length)
     : Disassembler(start, length),
       header_(nullptr),
@@ -163,12 +172,16 @@ bool DisassemblerElf32::Disassemble(AssemblyProgram* target) {
   if (!ParseAbs32Relocs())
     return false;
 
-  if (!ParseRel32RelocsFromSections())
+  if (!ParseRel32RelocsFromSections())  // Does not sort rel32 locations.
     return false;
 
+  PrecomputeLabels(target);
+  RemoveUnusedRel32Locations(target);
+
   if (!ParseFile(target))
     return false;
 
+  // Finally sort rel32 locations.
   std::sort(rel32_locations_.begin(),
             rel32_locations_.end(),
             TypedRVA::IsLessThanByRVA);
@@ -179,6 +192,28 @@ bool DisassemblerElf32::Disassemble(AssemblyProgram* target) {
   return true;
 }
 
+CheckBool DisassemblerElf32::IsValidTargetRVA(RVA rva) const {
+  if (rva == kUnassignedRVA)
+    return false;
+
+  // |rva| is valid if it's contained in any program segment.
+  for (Elf32_Half segment_id = 0; segment_id < ProgramSegmentHeaderCount();
+       ++segment_id) {
+    const Elf32_Phdr* segment_header = ProgramSegmentHeader(segment_id);
+
+    if (segment_header->p_type != PT_LOAD)
+      continue;
+
+    Elf32_Addr begin = segment_header->p_vaddr;
+    Elf32_Addr end = segment_header->p_vaddr + segment_header->p_memsz;
+
+    if (rva >= begin && rva < end)
+      return true;
+  }
+
+  return false;
+}
+
 bool DisassemblerElf32::UpdateLength() {
   Elf32_Off result = 0;
 
@@ -237,32 +272,11 @@ CheckBool DisassemblerElf32::SectionName(const Elf32_Shdr& shdr,
   return true;
 }
 
-CheckBool DisassemblerElf32::IsValidTargetRVA(RVA rva) const {
-  if (rva == kUnassignedRVA)
-    return false;
-
-  // It's valid if it's contained in any program segment
-  for (Elf32_Half segment_id = 0; segment_id < ProgramSegmentHeaderCount();
-       ++segment_id) {
-    const Elf32_Phdr* segment_header = ProgramSegmentHeader(segment_id);
-
-    if (segment_header->p_type != PT_LOAD)
-      continue;
-
-    Elf32_Addr begin = segment_header->p_vaddr;
-    Elf32_Addr end = segment_header->p_vaddr + segment_header->p_memsz;
-
-    if (rva >= begin && rva < end)
-      return true;
-  }
-
-  return false;
-}
-
 CheckBool DisassemblerElf32::RVAsToFileOffsets(
     const std::vector<RVA>& rvas,
     std::vector<FileOffset>* file_offsets) {
   file_offsets->clear();
+  file_offsets->reserve(rvas.size());
   for (RVA rva : rvas) {
     FileOffset file_offset = RVAToFileOffset(rva);
     if (file_offset == kNoFileOffset)
@@ -283,6 +297,24 @@ CheckBool DisassemblerElf32::RVAsToFileOffsets(
   return true;
 }
 
+RvaVisitor* DisassemblerElf32::CreateAbs32TargetRvaVisitor() {
+  return new RvaVisitor_Abs32(abs32_locations_, *this);
+}
+
+RvaVisitor* DisassemblerElf32::CreateRel32TargetRvaVisitor() {
+  return new Elf32RvaVisitor_Rel32(rel32_locations_.get());
+}
+
+void DisassemblerElf32::RemoveUnusedRel32Locations(AssemblyProgram* program) {
+  auto cond = [program](const TypedRVA* typed_rva) -> bool {
+    RVA target_rva = typed_rva->rva() + typed_rva->relative_target();
+    return program->FindRel32Label(target_rva) == nullptr;
+  };
+  rel32_locations_.erase(
+      std::remove_if(rel32_locations_.begin(), rel32_locations_.end(), cond),
+      rel32_locations_.end());
+}
+
 CheckBool DisassemblerElf32::ParseFile(AssemblyProgram* program) {
   // Walk all the bytes in the file, whether or not in a section.
   FileOffset file_offset = 0;
@@ -422,7 +454,9 @@ CheckBool DisassemblerElf32::ParseProgbitsSection(
       RVA target_rva = PointerToTargetRVA(FileOffsetToPointer(file_offset));
       DCHECK_NE(kNoRVA, target_rva);
 
-      if (!program->EmitAbs32(program->FindOrMakeAbs32Label(target_rva)))
+      Label* label = program->FindAbs32Label(target_rva);
+      CHECK(label);
+      if (!program->EmitAbs32(label))
         return false;
       file_offset += sizeof(RVA);
       ++(*current_abs_offset);
@@ -432,12 +466,17 @@ CheckBool DisassemblerElf32::ParseProgbitsSection(
     if (*current_rel != end_rel &&
         file_offset == (**current_rel)->file_offset()) {
       uint32_t relative_target = (**current_rel)->relative_target();
+      CHECK_EQ(RVA(origin + (file_offset - origin_offset)),
+               (**current_rel)->rva());
       // This cast is for 64 bit systems, and is only safe because we
       // are working on 32 bit executables.
       RVA target_rva = (RVA)(origin + (file_offset - origin_offset) +
                              relative_target);
 
-      if (!(**current_rel)->EmitInstruction(program, target_rva))
+      Label* label = program->FindRel32Label(target_rva);
+      CHECK(label);
+
+      if (!(**current_rel)->EmitInstruction(program, label))
         return false;
       file_offset += (**current_rel)->op_size();
       ++(*current_rel);