[intelpt] Refactor timestamps out of IntelPTInstruction

[zrthxn]

Summary

Storing timestamps (TSCs) in a more efficient map at the decoded thread level to speed up TSC lookup, as well as reduce the amount of memory taken up by each instruction. Also introduced TSC range which keeps the current timestamp valid for all subsequent instructions until the next timestamp is emitted.

[zrthxn]

Update cursor timestamp when we have a new one

[wallace]

let's better use the word TSC instead of timestamps, which is more accurate

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

164

receive const &pt_insn to avoid copies

166–167

Let's just use an overload

void AppendInstruction(const pt_insn &instruction, uint64_t tsc);

181–182

This has to be an optional because it might not be present

[wallace]

lldb/source/Plugins/Trace/intel-pt/DecodedThread.cpp

94–96

doing [] is O(logn), and we want to be faster than this.

You can do the following which is O(1)

auto it = m_instruction_timestamps.end()
if (it != m_instruction_timestamps.begin()) {
  it--;
  if (it->second != tsc) {
    // this tsc is not the same!
   m_instruction_timestamps.insert(insn_idx, tsc);
  } else {
    // this tsc is the same, do nothing
  }
}

you can further optimize this by storing the last tsc that has been appended, that way you don't even need to create iterators

115–118

this is wrong, you need to use upper_bound - 1, like this:

if (m_instruction_timestamps.empty())
  return None;

auto it = m_instruction_timestamps.upper_bound(insn_idx);
if (it == m_instruction_timestamps.begin())
  return None;

--it;
return it->second;

this will allow you to go to the largest index that is <= than insn_idx

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

181–182

better use insn_idx instead of index for all these variables

184–188

I actually like this, let's improve it

lldb/source/Plugins/Trace/intel-pt/IntelPTDecoder.cpp

153–154 ↗

(On Diff #418660)

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.cpp

25–26

here you need to set the correct value of m_current_tsc

44–45

this will be O(logn). We can do better if m_current_tsc is the following little structure

class DecodedThread {

struct TscRange {
  size_t start_index;
  size_t end_index;
  size_t tsc;
  std::map<size_t, uint64_t>::iterator prev;
  std::map<size_t, uint64_t>::iterator next;
};

}

Optional<TscRange> m_current_tsc;

Then you can ask the new method Optional<TscRange> DecodedThread::GetTSCRange(size_t insn_index) which will give you the entire range of the tsc that covers insn_index. With these numbers, you can do a comparison in this line to very quickly move from TSC to TSC only when needed.

You can also have the method DecodedThread::GetNextTscRange(const TscRange& range) that computes in O(1) the next range, and you can similarly have GetPrevTscRange()`. The iterators will help you do that withing using lower_bound, which is O(1)

66–84

you need to calculate the new tsc_range after moving m_pos

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.h

45–46

Optional<uint64_t> m_current_tsc;

[zrthxn]

Introduced TscRange for quicker operation

[wallace]

I'm proposing a new interface for the TscRange. Let me know if you have questions

lldb/source/Plugins/Trace/intel-pt/DecodedThread.cpp

95

we need to update it because of the optional

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

166–167

Let's improve the documentation and let's use the word TSC more ubiquitously

184

185–193

Let's add more logic to this object so that it handles as much as it can and we reduce the logic that was added to DecodedThread. We also don't need two iterators, just one is enough. Don't forget to add documentation to these new methods.

Given this new definition for TscRange. The only method we need to add in DecodedThread is CalculateTscRange(size_t insn_index), and mention the documentation that this operation is O(logn) and should be used sparingly.

186–188

196–203

Let's improve the documentation and also get rid of the struct keyword in return types. That's old style C

219–238

don't start variable names with __, as may people think that those variables should be discarded. Let's just give it a proper name. Let's also use an Optional and let's add documentation to all the variables.

[zrthxn]

Change TscRange to class

[zrthxn]

Update memory calc function

[zrthxn]

Prevent crash on printing info when we have 0 instructions

[wallace]

Some calculations are wrong, but overall this is good. We are very close!

lldb/source/Plugins/Trace/intel-pt/DecodedThread.cpp

117–118

now that I think of this, you can delete this, because if the map is empty, this function will return in line 117

137–140

undo these two lines

159

decoded_thread instead of ref

161–162

delete

164–168

seeing ++ and -- is very hard to read. I also prefer not to modify the it variable for cleanness. Also doing end->first might crash the program. I'm writing here a correct version

173

178

The comparison is not right. let's use <= in a specific order to make it easier to read

186

As m_it is valid, doing the comparison m_it == m_decoded_thread.m_instruction_timestamps.end() will always return false. Remember that .end() will return a fake iterator that points to no value.

Besides that, don't modify m_it. Let's better create a new iterator

190–192

Similarly, this has to be improved. I also like to put --it statements in their own line to make it easier to read.

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

182

187–188

189

Move this class to the beginning of the public section of DecodedThread for easier discoverability

191

207–213

let's better delete this. It adds some maintenance cost with little benefits

218

This comment is hard to follow. Let's just delete it because it's a private constructor

223–227

let's add another piece of information

225–228

Let's just delete this, as we can get them directly from m_it without doing any operations

227

230

Setting to llvm::None here is equivalent to doing it from all the constructors

233

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.cpp

45–52

No need to do m_current_tsc = m_decoded_thread_sp->CalculateTscRange(m_pos); because its value has already been calculated in the constructor. We can simplify this as well

99–101

are you using git clang-format? I'm curious why this line changed

101–107

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.h

45

/// Tsc range covering the current instruction.

lldb/source/Plugins/Trace/intel-pt/TraceIntelPT.cpp

124

Instead of doing *raw_size, better remove this number from CalculateApproximateMemoryUsage()

[zrthxn]

Included requested changes, removed extra members

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.cpp

45–52

It is possible that when TraceCursorIntelPT is created the m_current_tsc is None, for example when just started the trace and tried to dump instructions... But then if a tsc is emitted later, this would cause it to remain None since we don't re-calculate it if it was initially None

99–101

Yes I am. I think its because its longer than 80 chars.

101–107

m_current_tsc is already checked at the beginning of this function

[zrthxn]

Change tsc check anyway

[zrthxn]

Fixed issue with TSC becoming invalid midway through trace

[zrthxn]

Updated tests according to new memory usage calculation

[wallace]

almost there! Mostly cosmetic changes needed

lldb/source/Plugins/Trace/intel-pt/DecodedThread.cpp

94–98

We need to handle a special case. It might happen that the first instruction is an error, which won't have a TSC, and the second instruction is an actual instruction, and from that point on you'll always have TSCs. For this case, we can assume that the TSC of the error instruction at the beginning of the trace is the same as the first valid TSC.

117–118

delete these two lines. The rest of the code will work well without it

158–160

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

104

+1

140

Let's be more verbose with the names to improve readability

142

148

let's receive a reference here and then convert it to pointer, so that we minimize the number of places with pointers. Also, if later we decide to use a shared_ptr instead of a pointer, we can do it inside of the constructor without changing this line

150

181–182

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.cpp

65–84

we can simplify this so that we only invoke CalculateTscRange once

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.h

46

rename it to m_tsc_range. The word current is very redundant in this case

lldb/source/Plugins/Trace/intel-pt/TraceIntelPT.cpp

123–124

Use doubles, as the average might not be a whole number

[zrthxn]

Incorporate feedback and update tests

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.cpp

65–84

This is incorrect The converted code always returns 0. I've refactored it to have CalculateTscRange once but its a side-effect-y function and will need some future attention.

[wallace]

one last nit and good to go

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.cpp

82

don't use auto for simple types

[jj10306]

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

145

nit: No need to friend the enclosing class since C++11 - https://en.cppreference.com/w/cpp/language/nested_types

[wallace]

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

145

TIL!

[zrthxn]

Dont use auto for simple types

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

145

We need the friend because we are using a private constructor from outside, in DecodedThread::CalculateTscRange and a couple other places. The idea is to let only DecodedThread create TscRange.

[wallace]

lgtm

[wallace]

Don't forget to update the description of this diff and of the commit before pushing (you need to do both). Include the avg instruction size for a trace of at least 10k instructions as well :)

[zrthxn]

The difference in memory usage is appreciable with large number of instructions, as shown below

# Before (with current metrics, total memory does not include raw trace size)
  Raw trace size: 2048 KiB
  Total number of instructions: 900004
  Total approximate memory usage: 56143.10 KiB
  Average memory usage per instruction: 63.87 bytes

# After
  Raw trace size: 2048 KiB
  Total number of instructions: 900004
  Total approximate memory usage: 42187.69 KiB
  Average memory usage per instruction: 48.00 bytes

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

 ///
 /// Gaps in the trace can come in a few flavors:
 ///   - tracing gaps (e.g. tracing was paused and then resumed)
 ///   - tracing errors (e.g. buffer overflow)
 ///   - decoding errors (e.g. some memory region couldn't be decoded)
 /// As mentioned, any gap is represented as an error in this class.
 class IntelPTInstruction {
 public:
-  IntelPTInstruction(const pt_insn &pt_insn, uint64_t timestamp)
-      : m_pt_insn(pt_insn), m_timestamp(timestamp), m_is_error(false) {}
-
   IntelPTInstruction(const pt_insn &pt_insn)
       : m_pt_insn(pt_insn), m_is_error(false) {}
 
   /// Error constructor
   IntelPTInstruction();
 
   /// Check if this object represents an error (i.e. a gap).
   ///
   /// \return
   ///     Whether this object represents an error.
   bool IsError() const;
 
   /// \return
   ///     The instruction pointer address, or \a LLDB_INVALID_ADDRESS if it is
   ///     an error.
   lldb::addr_t GetLoadAddress() const;
 
   /// Get the size in bytes of an instance of this class
   static size_t GetMemoryUsage();
 
-  /// Get the timestamp associated with the current instruction. The timestamp
-  /// is similar to what a rdtsc instruction would return.
-  ///
-  /// \return
-  ///     The timestamp or \b llvm::None if not available.
-  llvm::Optional<uint64_t> GetTimestampCounter() const;
-
   /// Get the \a lldb::TraceInstructionControlFlowType categories of the
   /// instruction.
   ///
   /// \param[in] next_load_address
   ///     The address of the next instruction in the trace or \b
   ///     LLDB_INVALID_ADDRESS if not available.
   ///
   /// \return
   ///     The control flow categories, or \b 0 if the instruction is an error.
   lldb::TraceInstructionControlFlowType
   GetControlFlowType(lldb::addr_t next_load_address) const;
 
   IntelPTInstruction(IntelPTInstruction &&other) = default;
 
 private:
   IntelPTInstruction(const IntelPTInstruction &other) = delete;
   const IntelPTInstruction &operator=(const IntelPTInstruction &other) = delete;
 
   // When adding new members to this class, make sure to update
-  // IntelPTInstruction::GetNonErrorMemoryUsage() if needed.
+  // IntelPTInstruction::GetMemoryUsage() if needed.
   pt_insn m_pt_insn;
-  llvm::Optional<uint64_t> m_timestamp;
   bool m_is_error;
 };
 
 /// \class DecodedThread
 /// Class holding the instructions and function call hierarchy obtained from
 /// decoding a trace, as well as a position cursor used when reverse debugging
 /// the trace.
 ///
 /// Each decoded thread contains a cursor to the current position the user is
 /// stopped at. See \a Trace::GetCursorPosition for more information.
 class DecodedThread : public std::enable_shared_from_this<DecodedThread> {
 public:
+  /// \class TscRange
+  /// Class that represents the trace range associated with a given TSC.
+  /// It provides efficient iteration to the previous or next TSC range in the
+  /// decoded trace.
+  ///
+  /// TSC timestamps are emitted by the decoder infrequently, which means
+  /// that each TSC covers a range of instruction indices, which can be used to
+  /// speed up TSC lookups.
+  class TscRange {
+  public:
+    /// Check if this TSC range includes the given instruction index.
+    bool InRange(size_t insn_index);
+
+    /// Get the next range chronologically.
+    llvm::Optional<TscRange> Next();
+
+    /// Get the previous range chronologically.
+    llvm::Optional<TscRange> Prev();
+
+    /// Get the TSC value.
+    size_t GetTsc() const;
+    /// Get the smallest instruction index that has this TSC.
+    size_t GetStartInstructionIndex() const;
+    /// Get the largest instruction index that has this TSC.
+    size_t GetEndInstructionIndex() const;
+
+  private:
+    friend class DecodedThread;
+
+    TscRange(std::map<size_t, uint64_t>::const_iterator it,
+             const DecodedThread &decoded_thread);
+
+    /// The iterator pointing to the beginning of the range.
+    std::map<size_t, uint64_t>::const_iterator m_it;
+    /// The largest instruction index that has this TSC.
+    size_t m_end_index;
+
+    const DecodedThread *m_decoded_thread;
+  };
+
   DecodedThread(lldb::ThreadSP thread_sp);
 
   /// Utility constructor that initializes the trace with a provided error.
   DecodedThread(lldb::ThreadSP thread_sp, llvm::Error &&err);
 
+  /// Append a successfully decoded instruction.
+  void AppendInstruction(const pt_insn &instruction);
+
+  /// Append a sucessfully decoded instruction with an associated TSC timestamp.
+  void AppendInstruction(const pt_insn &instruction, uint64_t tsc);
+
+  /// Append a decoding error (i.e. an instruction that failed to be decoded).
+  void AppendError(llvm::Error &&error);
+
   /// Get the instructions from the decoded trace. Some of them might indicate
   /// errors (i.e. gaps) in the trace. For an instruction error, you can access
   /// its underlying error message with the \a GetErrorByInstructionIndex()
   /// method.
   ///
   /// \return
   ///   The instructions of the trace.
   llvm::ArrayRef<IntelPTInstruction> GetInstructions() const;
 
+  /// Construct the TSC range that covers the given instruction index.
+  /// This operation is O(logn) and should be used sparingly.
+  /// If the trace was collected with TSC support, all the instructions of
+  /// the trace will have associated TSCs. This means that this method will
+  /// only return \b llvm::None if there are no TSCs whatsoever in the trace.
+  llvm::Optional<TscRange> CalculateTscRange(size_t insn_index) const;
+
+  /// Check if an instruction given by its index is an error.
+  bool IsInstructionAnError(size_t insn_idx) const;
+
   /// Get the error associated with a given instruction index.
   ///
   /// \return
   ///   The error message of \b nullptr if the given index
   ///   points to a valid instruction.
-  const char *GetErrorByInstructionIndex(uint64_t ins_idx);
-
-  /// Append a successfully decoded instruction.
-  template <typename... Ts> void AppendInstruction(Ts... instruction_args) {
-    m_instructions.emplace_back(instruction_args...);
-  }
-
-  /// Append a decoding error (i.e. an instruction that failed to be decoded).
-  void AppendError(llvm::Error &&error);
+  const char *GetErrorByInstructionIndex(size_t ins_idx);
 
   /// Get a new cursor for the decoded thread.
   lldb::TraceCursorUP GetCursor();
 
   /// Set the size in bytes of the corresponding Intel PT raw trace.
   void SetRawTraceSize(size_t size);
 
   /// Get the size in bytes of the corresponding Intel PT raw trace.
   ///
   /// \return
   ///   The size of the trace, or \b llvm::None if not available.
   llvm::Optional<size_t> GetRawTraceSize() const;
 
   /// The approximate size in bytes used by this instance,
   /// including all the already decoded instructions.
   size_t CalculateApproximateMemoryUsage() const;
 
   lldb::ThreadSP GetThread();
 
 private:
   /// When adding new members to this class, make sure
   /// to update \a CalculateApproximateMemoryUsage() accordingly.
   lldb::ThreadSP m_thread_sp;
+  /// The low level storage of all instruction addresses. Each instruction has
+  /// an index in this vector and it will be used in other parts of the code.
   std::vector<IntelPTInstruction> m_instructions;
+  /// This map contains the TSCs of the decoded instructions. It maps
+  /// `instruction index -> TSC`, where `instruction index` is the first index
+  /// at which the mapped TSC appears. We use this representation because TSCs
+  /// are sporadic and we can think of them as ranges. If TSCs are present in
+  /// the trace, all instructions will have an associated TSC, including the
+  /// first one. Otherwise, this map will be empty.
+  std::map<size_t, uint64_t> m_instruction_timestamps;
+  /// This is the chronologically last TSC that has been added.
+  llvm::Optional<uint64_t> m_last_tsc = llvm::None;
+  // This variables stores the messages of all the error instructions in the
+  // trace. It maps `instruction index -> error message`.
   llvm::DenseMap<uint64_t, std::string> m_errors;
+  /// The size in bytes of the raw buffer before decoding. It might be None if
+  /// the decoding failed.
   llvm::Optional<size_t> m_raw_trace_size;
 };
 
 using DecodedThreadSP = std::shared_ptr<DecodedThread>;
 
 } // namespace trace_intel_pt
 } // namespace lldb_private
 
 #endif // LLDB_SOURCE_PLUGINS_TRACE_INTEL_PT_DECODEDTHREAD_H

lldb/source/Plugins/Trace/intel-pt/DecodedThread.cpp

 bool IntelPTInstruction::IsError() const { return m_is_error; }
 
 lldb::addr_t IntelPTInstruction::GetLoadAddress() const { return m_pt_insn.ip; }
 
 size_t IntelPTInstruction::GetMemoryUsage() {
   return sizeof(IntelPTInstruction);
 }
 
-Optional<uint64_t> IntelPTInstruction::GetTimestampCounter() const {
-  return m_timestamp;
-}
-
 Optional<size_t> DecodedThread::GetRawTraceSize() const {
   return m_raw_trace_size;
 }
 
 TraceInstructionControlFlowType
 IntelPTInstruction::GetControlFlowType(lldb::addr_t next_load_address) const {
   if (IsError())
     return (TraceInstructionControlFlowType)0;
default:
     break;
   }
 
   return mask;
 }
 
 ThreadSP DecodedThread::GetThread() { return m_thread_sp; }
 
+void DecodedThread::AppendInstruction(const pt_insn &insn) {
+  m_instructions.emplace_back(insn);
+}
+
+void DecodedThread::AppendInstruction(const pt_insn &insn, uint64_t tsc) {
+  m_instructions.emplace_back(insn);
+  if (!m_last_tsc || *m_last_tsc != tsc) {
+    // In case the first instructions are errors or did not have a TSC, we'll
+    // get a first valid TSC not in position 0. We can safely force these error
+    // instructions to use the first valid TSC, so that all the trace has TSCs.
+    size_t start_index =
+        m_instruction_timestamps.empty() ? 0 : m_instructions.size() - 1;
+    m_instruction_timestamps.emplace(start_index, tsc);
+    m_last_tsc = tsc;
+  }
+}
+
 void DecodedThread::AppendError(llvm::Error &&error) {
   m_errors.try_emplace(m_instructions.size(), toString(std::move(error)));
   m_instructions.emplace_back();
 }
 
 ArrayRef<IntelPTInstruction> DecodedThread::GetInstructions() const {
   return makeArrayRef(m_instructions);
 }
 
-const char *DecodedThread::GetErrorByInstructionIndex(uint64_t idx) {
-  auto it = m_errors.find(idx);
+Optional<DecodedThread::TscRange>
+DecodedThread::CalculateTscRange(size_t insn_index) const {
+  auto it = m_instruction_timestamps.upper_bound(insn_index);
+  if (it == m_instruction_timestamps.begin())
+    return None;
+
+  return TscRange(--it, *this);
+}
+
+bool DecodedThread::IsInstructionAnError(size_t insn_idx) const {
+  return m_instructions[insn_idx].IsError();
+}
+
+const char *DecodedThread::GetErrorByInstructionIndex(size_t insn_idx) {
+  auto it = m_errors.find(insn_idx);
   if (it == m_errors.end())
     return nullptr;
 
   return it->second.c_str();
 }
 
 DecodedThread::DecodedThread(ThreadSP thread_sp) : m_thread_sp(thread_sp) {}
 
 DecodedThread::DecodedThread(ThreadSP thread_sp, Error &&error)
     : m_thread_sp(thread_sp) {
   AppendError(std::move(error));
 }
 
 void DecodedThread::SetRawTraceSize(size_t size) { m_raw_trace_size = size; }
 
 lldb::TraceCursorUP DecodedThread::GetCursor() {
   // We insert a fake error signaling an empty trace if needed becasue the
   // TraceCursor requires non-empty traces.
   if (m_instructions.empty())
     AppendError(createStringError(inconvertibleErrorCode(), "empty trace"));
   return std::make_unique<TraceCursorIntelPT>(m_thread_sp, shared_from_this());
 }
 
 size_t DecodedThread::CalculateApproximateMemoryUsage() const {
-  return m_raw_trace_size.getValueOr(0) +
-         IntelPTInstruction::GetMemoryUsage() * m_instructions.size() +
+  return IntelPTInstruction::GetMemoryUsage() * m_instructions.size() +
          m_errors.getMemorySize();
 }
+
+DecodedThread::TscRange::TscRange(std::map<size_t, uint64_t>::const_iterator it,
+                                  const DecodedThread &decoded_thread)
+    : m_it(it), m_decoded_thread(&decoded_thread) {
+  auto next_it = m_it;
+  ++next_it;
+  m_end_index = (next_it == m_decoded_thread->m_instruction_timestamps.end())
+                    ? m_decoded_thread->GetInstructions().size() - 1
+                    : next_it->first - 1;
+}
+
+size_t DecodedThread::TscRange::GetTsc() const { return m_it->second; }
+
+size_t DecodedThread::TscRange::GetStartInstructionIndex() const {
+  return m_it->first;
+}
+
+size_t DecodedThread::TscRange::GetEndInstructionIndex() const {
+  return m_end_index;
+}
+
+bool DecodedThread::TscRange::InRange(size_t insn_index) {
+  return GetStartInstructionIndex() <= insn_index &&
+         insn_index <= GetEndInstructionIndex();
+}
+
+Optional<DecodedThread::TscRange> DecodedThread::TscRange::Next() {
+  auto next_it = m_it;
+  ++next_it;
+  if (next_it == m_decoded_thread->m_instruction_timestamps.end())
+    return None;
+  return TscRange(next_it, *m_decoded_thread);
+}
+
+Optional<DecodedThread::TscRange> DecodedThread::TscRange::Prev() {
+  if (m_it == m_decoded_thread->m_instruction_timestamps.begin())
+    return None;
+  auto prev_it = m_it;
+  --prev_it;
+  return TscRange(prev_it, *m_decoded_thread);
+}
 No newline at end of file

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.h

 
 private:
   size_t GetInternalInstructionSize();
 
   /// Storage of the actual instructions
   DecodedThreadSP m_decoded_thread_sp;
   /// Internal instruction index currently pointing at.
   size_t m_pos;
+  /// Tsc range covering the current instruction.
+  llvm::Optional<DecodedThread::TscRange> m_tsc_range;
 };
 
 } // namespace trace_intel_pt
 } // namespace lldb_private
 
 #endif // LLDB_SOURCE_PLUGINS_TRACE_INTEL_PT_TRACECURSORINTELPT_H

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.cpp

 using namespace lldb_private::trace_intel_pt;
 using namespace llvm;
 
 TraceCursorIntelPT::TraceCursorIntelPT(ThreadSP thread_sp,
                                        DecodedThreadSP decoded_thread_sp)
     : TraceCursor(thread_sp), m_decoded_thread_sp(decoded_thread_sp) {
   assert(!m_decoded_thread_sp->GetInstructions().empty() &&
          "a trace should have at least one instruction or error");
   m_pos = m_decoded_thread_sp->GetInstructions().size() - 1;
+  m_tsc_range = m_decoded_thread_sp->CalculateTscRange(m_pos);
 }
 
 size_t TraceCursorIntelPT::GetInternalInstructionSize() {
   return m_decoded_thread_sp->GetInstructions().size();
 }
 
 bool TraceCursorIntelPT::Next() {
   auto canMoveOne = [&]() {
     if (IsForwards())
       return m_pos + 1 < GetInternalInstructionSize();
     return m_pos > 0;
   };
 
   size_t initial_pos = m_pos;
 
   while (canMoveOne()) {
     m_pos += IsForwards() ? 1 : -1;
+
+    if (m_tsc_range && !m_tsc_range->InRange(m_pos))
+      m_tsc_range = IsForwards() ? m_tsc_range->Next() : m_tsc_range->Prev();
+
     if (!m_ignore_errors && IsError())
       return true;
     if (GetInstructionControlFlowType() & m_granularity)
       return true;
   }
 
   // Didn't find any matching instructions
   m_pos = initial_pos;
   return false;
 }
 
 size_t TraceCursorIntelPT::Seek(int64_t offset, SeekType origin) {
   int64_t last_index = GetInternalInstructionSize() - 1;
 
   auto fitPosToBounds = [&](int64_t raw_pos) -> int64_t {
     return std::min(std::max((int64_t)0, raw_pos), last_index);
   };
 
+  auto FindDistanceAndSetPos = [&]() -> int64_t {
     switch (origin) {
     case TraceCursor::SeekType::Set:
       m_pos = fitPosToBounds(offset);
       return m_pos;
     case TraceCursor::SeekType::End:
       m_pos = fitPosToBounds(offset + last_index);
       return last_index - m_pos;
     case TraceCursor::SeekType::Current:
       int64_t new_pos = fitPosToBounds(offset + m_pos);
       int64_t dist = m_pos - new_pos;
       m_pos = new_pos;
       return std::abs(dist);
     }
+  };
+  
+  int64_t dist = FindDistanceAndSetPos();
+  m_tsc_range = m_decoded_thread_sp->CalculateTscRange(m_pos);
+  return dist;
 }
 
 bool TraceCursorIntelPT::IsError() {
-  return m_decoded_thread_sp->GetInstructions()[m_pos].IsError();
+  return m_decoded_thread_sp->IsInstructionAnError(m_pos);
 }
 
 const char *TraceCursorIntelPT::GetError() {
   return m_decoded_thread_sp->GetErrorByInstructionIndex(m_pos);
 }
 
 lldb::addr_t TraceCursorIntelPT::GetLoadAddress() {
   return m_decoded_thread_sp->GetInstructions()[m_pos].GetLoadAddress();
 }
 
-Optional<uint64_t> TraceCursorIntelPT::GetCounter(lldb::TraceCounter counter_type) {
+Optional<uint64_t>
+TraceCursorIntelPT::GetCounter(lldb::TraceCounter counter_type) {
   switch (counter_type) {
-    case lldb::eTraceCounterTSC:
-      return m_decoded_thread_sp->GetInstructions()[m_pos].GetTimestampCounter();
+    if (m_tsc_range)
+      return m_tsc_range->GetTsc();
+    else
+      return llvm::None;
   }
 }
 
 TraceInstructionControlFlowType
 TraceCursorIntelPT::GetInstructionControlFlowType() {
   lldb::addr_t next_load_address =
       m_pos + 1 < GetInternalInstructionSize()
           ? m_decoded_thread_sp->GetInstructions()[m_pos + 1].GetLoadAddress()
           : LLDB_INVALID_ADDRESS;
   return m_decoded_thread_sp->GetInstructions()[m_pos].GetControlFlowType(
       next_load_address);
 }

lldb/source/Plugins/Trace/intel-pt/TraceIntelPT.cpp

void TraceIntelPT::DumpTraceInfo(Thread &thread, Stream &s, bool verbose) {
 
   size_t insn_len = Decode(thread)->GetInstructions().size();
   size_t mem_used = Decode(thread)->CalculateApproximateMemoryUsage();
 
   s.Printf("  Raw trace size: %zu KiB\n", *raw_size / 1024);
   s.Printf("  Total number of instructions: %zu\n", insn_len);
   s.Printf("  Total approximate memory usage: %0.2lf KiB\n",
            (double)mem_used / 1024);
-  s.Printf("  Average memory usage per instruction: %zu bytes\n",
-           mem_used / insn_len);
+  if (insn_len != 0)
+    s.Printf("  Average memory usage per instruction: %0.2lf bytes\n",
+             (double)mem_used / insn_len);
   return;
 }
 
 Optional<size_t> TraceIntelPT::GetRawTraceSize(Thread &thread) {
   if (IsTraced(thread.GetID()))
     return Decode(thread)->GetRawTraceSize();
   else
     return None;

lldb/test/API/commands/trace/TestTraceDumpInfo.py

def testDumpRawTraceSize(self):
         substrs=["intel-pt"])
 
         self.expect("thread trace dump info",
             substrs=['''Trace technology: intel-pt
 
 thread #1: tid = 3842849
   Raw trace size: 4 KiB
   Total number of instructions: 21
-  Total approximate memory usage: 5.31 KiB
-  Average memory usage per instruction: 259 bytes'''])
+  Total approximate memory usage: 0.98 KiB
+  Average memory usage per instruction: 48.00 bytes'''])

lldb/test/API/commands/trace/TestTraceLoad.py

def testLoadTrace(self):
         # check that the Process and Thread objects were created correctly
         self.expect("thread info", substrs=["tid = 3842849"])
         self.expect("thread list", substrs=["Process 1234 stopped", "tid = 3842849"])
         self.expect("thread trace dump info", substrs=['''Trace technology: intel-pt
 
 thread #1: tid = 3842849
   Raw trace size: 4 KiB
   Total number of instructions: 21
-  Total approximate memory usage: 5.31 KiB
-  Average memory usage per instruction: 259 bytes'''])
+  Total approximate memory usage: 0.98 KiB
+  Average memory usage per instruction: 48.00 bytes'''])
 
     def testLoadInvalidTraces(self):
         src_dir = self.getSourceDir()
         # We test first an invalid type
         self.expect("trace load -v " + os.path.join(src_dir, "intelpt-trace", "trace_bad.json"), error=True,
           substrs=['''error: expected object at traceSession.processes[0]
 
 Context: