[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

2020-02-28 Thread Pavel Labath via Phabricator via lldb-commits 
labath added a comment.

In D74759#1896100 , @unnar wrote:

> In D74759#1895748 , @labath wrote:
>
> > That is a fair point. I suppose the reason why I see this as different is 
> > because this field is an implementation detail of the RangeDataVector 
> > class, and so the user should not even see it -- whereas the user has a 
> > legitimate reason to at least access the other fields (and most of the 
> > methods only provide read-only access to these fields).
> >
> > I'm sorry, I haven't gotten around to looking at this patch today, but I 
> > thought I'd at least say that...
>
>
> That is true. I am fine with changing it if that's the only thing that you 
> see as blocking this change from passing.


I finally took a good look at the patch, and I think that is the only remaining 
question on my mind. Could you try implementing that to see how it looks like?

@teemperor, do you have any more thoughts on this?




Comment at: lldb/include/lldb/Utility/RangeMap.h:814
+size_t mid = (lo + hi) / 2;
+auto &entry = m_entries[mid];
+

[[ 
http://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable
 | Llvm style guide ]] does not recommend using `auto` in this situation. 
`Entry &entry` is one character longer, but it makes it clear what is going on.



Comment at: lldb/include/lldb/Utility/RangeMap.h:834
+size_t mid = (lo + hi) / 2;
+auto entry = m_entries[mid];
+

`const Entry &` -- 
http://llvm.org/docs/CodingStandards.html#beware-unnecessary-copies-with-auto


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74759/new/

https://reviews.llvm.org/D74759



___
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

[Lldb-commits] [lldb] 7369ad3 - [lldb] Use llvm MC as the source of dwarf/eh register numbers for X86 ABIs

2020-02-28 Thread Pavel Labath via lldb-commits 

Author: Pavel Labath
Date: 2020-02-28T10:49:08+01:00
New Revision: 7369ad38f8decb4a85b168bbf9a9869fa4e648ee

URL: 
https://github.com/llvm/llvm-project/commit/7369ad38f8decb4a85b168bbf9a9869fa4e648ee
DIFF: 
https://github.com/llvm/llvm-project/commit/7369ad38f8decb4a85b168bbf9a9869fa4e648ee.diff

LOG: [lldb] Use llvm MC as the source of dwarf/eh register numbers for X86 ABIs

x86_64 ABIs were converted with 07355c1c0. This does the same with i386.

Added: 


Modified: 
lldb/source/Plugins/ABI/X86/ABIMacOSX_i386.cpp
lldb/source/Plugins/ABI/X86/ABIMacOSX_i386.h
lldb/source/Plugins/ABI/X86/ABISysV_i386.cpp
lldb/source/Plugins/ABI/X86/ABISysV_i386.h
lldb/source/Plugins/ABI/X86/ABIX86.cpp
lldb/source/Plugins/ABI/X86/ABIX86.h

Removed: 




diff  --git a/lldb/source/Plugins/ABI/X86/ABIMacOSX_i386.cpp 
b/lldb/source/Plugins/ABI/X86/ABIMacOSX_i386.cpp
index d11c1af1d259..89112deb2c4a 100644
--- a/lldb/source/Plugins/ABI/X86/ABIMacOSX_i386.cpp
+++ b/lldb/source/Plugins/ABI/X86/ABIMacOSX_i386.cpp
@@ -31,21 +31,6 @@ using namespace lldb_private;
 
 LLDB_PLUGIN_DEFINE(ABIMacOSX_i386)
 
-enum {
-  ehframe_eax = 0,
-  ehframe_ecx,
-  ehframe_edx,
-  ehframe_ebx,
-  ehframe_ebp, // Different from DWARF the regnums - eh_frame esp/ebp had their
-   // regnums switched on i386 darwin
-  ehframe_esp, // Different from DWARF the regnums - eh_frame esp/ebp had their
-   // regnums switched on i386 darwin
-  ehframe_esi,
-  ehframe_edi,
-  ehframe_eip,
-  ehframe_eflags
-};
-
 enum {
   dwarf_eax = 0,
   dwarf_ecx,
@@ -56,653 +41,8 @@ enum {
   dwarf_esi,
   dwarf_edi,
   dwarf_eip,
-  dwarf_eflags,
-  dwarf_stmm0 = 11,
-  dwarf_stmm1,
-  dwarf_stmm2,
-  dwarf_stmm3,
-  dwarf_stmm4,
-  dwarf_stmm5,
-  dwarf_stmm6,
-  dwarf_stmm7,
-  dwarf_xmm0 = 21,
-  dwarf_xmm1,
-  dwarf_xmm2,
-  dwarf_xmm3,
-  dwarf_xmm4,
-  dwarf_xmm5,
-  dwarf_xmm6,
-  dwarf_xmm7,
-  dwarf_ymm0 = dwarf_xmm0,
-  dwarf_ymm1 = dwarf_xmm1,
-  dwarf_ymm2 = dwarf_xmm2,
-  dwarf_ymm3 = dwarf_xmm3,
-  dwarf_ymm4 = dwarf_xmm4,
-  dwarf_ymm5 = dwarf_xmm5,
-  dwarf_ymm6 = dwarf_xmm6,
-  dwarf_ymm7 = dwarf_xmm7
 };
 
-static RegisterInfo g_register_infos[] = {
-//  NAME  ALT  SZ OFF ENCODING FORMAT
-//  EH_FRAME  DWARF GENERIC
-//  PROCESS PLUGINLLDB NATIVE
-//  =====  == === =
-//  = = 

-//    ==
-{"eax",
- nullptr,
- 4,
- 0,
- eEncodingUint,
- eFormatHex,
- {ehframe_eax, dwarf_eax, LLDB_INVALID_REGNUM, LLDB_INVALID_REGNUM,
-  LLDB_INVALID_REGNUM},
- nullptr,
- nullptr,
- nullptr,
- 0},
-{"ebx",
- nullptr,
- 4,
- 0,
- eEncodingUint,
- eFormatHex,
- {ehframe_ebx, dwarf_ebx, LLDB_INVALID_REGNUM, LLDB_INVALID_REGNUM,
-  LLDB_INVALID_REGNUM},
- nullptr,
- nullptr,
- nullptr,
- 0},
-{"ecx",
- nullptr,
- 4,
- 0,
- eEncodingUint,
- eFormatHex,
- {ehframe_ecx, dwarf_ecx, LLDB_REGNUM_GENERIC_ARG4, LLDB_INVALID_REGNUM,
-  LLDB_INVALID_REGNUM},
- nullptr,
- nullptr,
- nullptr,
- 0},
-{"edx",
- nullptr,
- 4,
- 0,
- eEncodingUint,
- eFormatHex,
- {ehframe_edx, dwarf_edx, LLDB_REGNUM_GENERIC_ARG3, LLDB_INVALID_REGNUM,
-  LLDB_INVALID_REGNUM},
- nullptr,
- nullptr,
- nullptr,
- 0},
-{"esi",
- nullptr,
- 4,
- 0,
- eEncodingUint,
- eFormatHex,
- {ehframe_esi, dwarf_esi, LLDB_REGNUM_GENERIC_ARG2, LLDB_INVALID_REGNUM,
-  LLDB_INVALID_REGNUM},
- nullptr,
- nullptr,
- nullptr,
- 0},
-{"edi",
- nullptr,
- 4,
- 0,
- eEncodingUint,
- eFormatHex,
- {ehframe_edi, dwarf_edi, LLDB_REGNUM_GENERIC_ARG1, LLDB_INVALID_REGNUM,
-  LLDB_INVALID_REGNUM},
- nullptr,
- nullptr,
- nullptr,
- 0},
-{"ebp",
- "fp",
- 4,
- 0,
- eEncodingUint,
- eFormatHex,
- {ehframe_ebp, dwarf_ebp, LLDB_REGNUM_GENERIC_FP, LLDB_INVALID_REGNUM,
-  LLDB_INVALID_REGNUM},
- nullptr,
- nullptr,
- nullptr,
- 0},
-{"esp",
- "sp",
- 4,
- 0,
- eEncodingUint,
- eFormatHex,
- {ehframe_esp, dwarf_esp, LLDB_REGNUM_GENERIC_SP, LLDB_INVALID_REGNUM,
-  LLDB_INVALID_REGNUM},
- nullptr,
- nullptr,
- nullptr,
- 0},
-{"eip",
- "pc",
- 4,
- 0,
- eEncodingUint,
- eFormatHex,
- {ehframe_eip, dwarf_eip, LLDB_REGNUM_GENERIC_PC, LLDB_INVALID_REGNUM,
-  LLDB_INVALID_REGNUM},
- nullptr,
- nullptr,
- nullptr,
- 0},
-{"eflags",
- nullptr,
- 4,
- 0,
- eEncodingUint,
- eFormatHex,
- {LLDB_INVALID_REGNUM, LLDB_INVALID_REGNUM, LLDB_REGNUM_GENERIC_FLAGS,

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

2020-02-28 Thread Unnar Freyr Erlendsson via Phabricator via lldb-commits 
unnar updated this revision to Diff 247211.
unnar marked 2 inline comments as done.
unnar added a comment.

As discussed with labath@ I made a separate struct called AugmentedEntry that 
is used internally but we only ever expose the Entry part to the user.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74759/new/

https://reviews.llvm.org/D74759

Files:
  lldb/include/lldb/Utility/RangeMap.h

Index: lldb/include/lldb/Utility/RangeMap.h
===
--- lldb/include/lldb/Utility/RangeMap.h
+++ lldb/include/lldb/Utility/RangeMap.h
@@ -601,19 +601,31 @@
   RangeData(B base, S size, DataType d) : Range(base, size), data(d) {}
 };
 
+template 
+struct AugmentedRangeData : public RangeData {
+  B upper_bound;
+
+  AugmentedRangeData(B base, S size, T data)
+  : RangeData(base, size, data), upper_bound() {}
+};
+
 template >
 class RangeDataVector {
 public:
   typedef lldb_private::Range Range;
   typedef RangeData Entry;
-  typedef llvm::SmallVector Collection;
+  typedef AugmentedRangeData AugmentedEntry;
+  typedef llvm::SmallVector Collection;
 
   RangeDataVector(Compare compare = Compare()) : m_compare(compare) {}
 
   ~RangeDataVector() = default;
 
-  void Append(const Entry &entry) { m_entries.push_back(entry); }
+  void Append(const Entry &entry) {
+AugmentedEntry augmented_entry(entry.base, entry.size, entry.data);
+m_entries.push_back(augmented_entry);
+  }
 
   void Sort() {
 if (m_entries.size() > 1)
@@ -625,13 +637,13 @@
return a.size < b.size;
  return compare(a.data, b.data);
});
+if (!m_entries.empty())
+  ComputeUpperBounds(0, m_entries.size());
   }
 
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
   bool IsSorted() const {
 typename Collection::const_iterator pos, end, prev;
-// First we determine if we can combine any of the Entry objects so we
-// don't end up allocating and making a new collection for no reason
 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
  prev = pos++) {
   if (prev != end && *pos < *prev)
@@ -701,26 +713,20 @@
   }
 
   uint32_t FindEntryIndexThatContains(B addr) const {
-const Entry *entry = FindEntryThatContains(addr);
+const AugmentedEntry *entry =
+static_cast(FindEntryThatContains(addr));
 if (entry)
   return std::distance(m_entries.begin(), entry);
 return UINT32_MAX;
   }
 
-  uint32_t FindEntryIndexesThatContain(B addr,
-   std::vector &indexes) const {
+  uint32_t FindEntryIndexesThatContain(B addr, std::vector &indexes) {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 assert(IsSorted());
 #endif
-// Search the entries until the first entry that has a larger base address
-// than `addr`. As m_entries is sorted by their base address, all following
-// entries can't contain `addr` as their base address is already larger.
-for (const auto &entry : m_entries) {
-  if (entry.Contains(addr))
-indexes.push_back(entry.data);
-  else if (entry.GetRangeBase() > addr)
-break;
-}
+if (!m_entries.empty())
+  FindEntryIndexesThatContain(addr, 0, m_entries.size(), indexes);
+
 return indexes.size();
   }
 
@@ -806,6 +812,56 @@
 protected:
   Collection m_entries;
   Compare m_compare;
+
+private:
+  // We can treat the vector as a flattened Binary Search Tree, augmenting it
+  // with upper bounds (max of range endpoints) for every index allows us to
+  // query for range containment quicker.
+  B ComputeUpperBounds(size_t lo, size_t hi) {
+size_t mid = (lo + hi) / 2;
+AugmentedEntry &entry = m_entries[mid];
+
+entry.upper_bound = entry.base + entry.size;
+
+if (lo < mid)
+  entry.upper_bound =
+  std::max(entry.upper_bound, ComputeUpperBounds(lo, mid));
+
+if (mid + 1 < hi)
+  entry.upper_bound =
+  std::max(entry.upper_bound, ComputeUpperBounds(mid + 1, hi));
+
+return entry.upper_bound;
+  }
+
+  // This is based on the augmented tree implementation found at
+  // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
+  void FindEntryIndexesThatContain(B addr, size_t lo, size_t hi,
+   std::vector &indexes) {
+size_t mid = (lo + hi) / 2;
+const AugmentedEntry &entry = m_entries[mid];
+
+// addr is greater than the rightmost point of any interval below mid
+// so there are cannot be any matches.
+if (addr > entry.upper_bound)
+  return;
+
+// Recursively search left subtree
+if (lo < mid)
+  FindEntryIndexesThatContain(addr, lo, mid, indexes);
+
+// If addr is smaller than the start of the current interval it
+// cannot contain it nor can any of its right subtree.
+if (addr < entry.base)
+  return;
+
+if (entry.Contains(addr))
+  indexes.push_back(entry.data);
+
+// Recursively search right subtree
+i

[Lldb-commits] [PATCH] D75330: [lldb] Remove checks behind LLDB_CONFIGURATION_DEBUG from TypeSystemClang

2020-02-28 Thread Adrian Prantl via Phabricator via lldb-commits 
aprantl accepted this revision.
aprantl added a comment.
This revision is now accepted and ready to land.

Great! You might want to do a git grep for LLDB_CONFIGURATION_DEBUG to find 
other instances, too.


Repository:
  rLLDB LLDB

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D75330/new/

https://reviews.llvm.org/D75330



___
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

[Lldb-commits] [PATCH] D75330: [lldb] Remove checks behind LLDB_CONFIGURATION_DEBUG from TypeSystemClang

2020-02-28 Thread Shafik Yaghmour via Phabricator via lldb-commits 
shafik added a comment.

Nice fix!


Repository:
  rLLDB LLDB

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D75330/new/

https://reviews.llvm.org/D75330



___
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits