Fix the representation of debug line table in DebugInfo LLVM library,

and "instruction address -> file/line" lookup.

Instead of plain collection of rows, debug line table for compilation unit is now
treated as the number of row ranges, describing sequences (series of contiguous machine
instructions). The sequences are not always listed in the order of increasing
address, so previously used std::lower_bound() sometimes produced wrong results.
Now the instruction address lookup consists of two stages: finding the correct
sequence, and searching for address in range of rows for this sequence.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161414 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 55 insertions, 6 deletions

diff --git a/lib/DebugInfo/DWARFDebugLine.h b/lib/DebugInfo/DWARFDebugLine.h
index a8c0669b73..6382b45a93 100644
--- a/lib/DebugInfo/DWARFDebugLine.h
+++ b/lib/DebugInfo/DWARFDebugLine.h
@@ -88,6 +88,10 @@ public:
     void reset(bool default_is_stmt);
     void dump(raw_ostream &OS) const;
 
+    static bool orderByAddress(const Row& LHS, const Row& RHS) {
+      return LHS.Address < RHS.Address;
+    }
+
     // The program-counter value corresponding to a machine instruction
     // generated by the compiler.
     uint64_t Address;
@@ -125,21 +129,63 @@ public:
             EpilogueBegin:1;
   };
 
+  // Represents a series of contiguous machine instructions. Line table for each
+  // compilation unit may consist of multiple sequences, which are not
+  // guaranteed to be in the order of ascending instruction address.
+  struct Sequence {
+    // Sequence describes instructions at address range [LowPC, HighPC)
+    // and is described by line table rows [FirstRowIndex, LastRowIndex).
+    uint64_t LowPC;
+    uint64_t HighPC;
+    unsigned FirstRowIndex;
+    unsigned LastRowIndex;
+    bool Empty;
+
+    Sequence() { reset(); }
+    void reset() {
+      LowPC = 0;
+      HighPC = 0;
+      FirstRowIndex = 0;
+      LastRowIndex = 0;
+      Empty = true;
+    }
+    static bool orderByLowPC(const Sequence& LHS, const Sequence& RHS) {
+      return LHS.LowPC < RHS.LowPC;
+    }
+    bool isValid() const {
+      return !Empty && (LowPC < HighPC) && (FirstRowIndex < LastRowIndex);
+    }
+    bool containsPC(uint64_t pc) const {
+      return (LowPC <= pc && pc < HighPC);
+    }
+  };
+
   struct LineTable {
     void appendRow(const DWARFDebugLine::Row &state) { Rows.push_back(state); }
+    void appendSequence(const DWARFDebugLine::Sequence &sequence) {
+      Sequences.push_back(sequence);
+    }
     void clear() {
       Prologue.clear();
       Rows.clear();
+      Sequences.clear();
     }
 
-    uint32_t lookupAddress(uint64_t address, uint64_t cu_high_pc) const;
+    // Returns the index of the row with file/line info for a given address,
+    // or -1 if there is no such row.
+    uint32_t lookupAddress(uint64_t address) const;
     void dump(raw_ostream &OS) const;
 
     struct Prologue Prologue;
-    std::vector<Row> Rows;
+    typedef std::vector<Row> RowVector;
+    typedef RowVector::const_iterator RowIter;
+    typedef std::vector<Sequence> SequenceVector;
+    typedef SequenceVector::const_iterator SequenceIter;
+    RowVector Rows;
+    SequenceVector Sequences;
   };
 
-  struct State : public Row, public LineTable {
+  struct State : public Row, public Sequence, public LineTable {
     // Special row codes.
     enum {
       StartParsingLineTable = 0,
@@ -150,8 +196,11 @@ public:
     virtual ~State();
 
     virtual void appendRowToMatrix(uint32_t offset);
-    virtual void finalize(uint32_t offset) { row = DoneParsingLineTable; }
-    virtual void reset() { Row::reset(Prologue.DefaultIsStmt); }
+    virtual void finalize();
+    virtual void reset() {
+      Row::reset(Prologue.DefaultIsStmt);
+      Sequence::reset();
+    }
 
     // The row number that starts at zero for the prologue, and increases for
     // each row added to the matrix.
@@ -161,7 +210,7 @@ public:
   struct DumpingState : public State {
     DumpingState(raw_ostream &OS) : OS(OS) {}
     virtual ~DumpingState();
-    virtual void finalize(uint32_t offset);
+    virtual void finalize();
   private:
     raw_ostream &OS;
   };