Bug 757188 - Refactor FlowGraphSummary; r=jorendorff
authorEddy Bruel <ejpbruel@mozilla.com>
Tue, 19 Feb 2013 16:05:15 +0100
changeset 128759 a02cad4f32380702fe7412405906002429787437
parent 128758 451dd3f18ba5e94f0b5f68b59a507c34dbe8de71
child 128760 878874218b31ff8b776103ad5cd20250d592febe
push id3582
push userbbajaj@mozilla.com
push dateMon, 01 Apr 2013 20:50:56 +0000
treeherdermozilla-aurora@400370bbc9fa [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjorendorff
bugs757188
milestone21.0a1
Bug 757188 - Refactor FlowGraphSummary; r=jorendorff
js/src/vm/Debugger.cpp
--- a/js/src/vm/Debugger.cpp
+++ b/js/src/vm/Debugger.cpp
@@ -2883,150 +2883,242 @@ DebuggerScript_getOffsetLine(JSContext *
     size_t offset;
     if (!ScriptOffset(cx, script, args[0], &offset))
         return false;
     unsigned lineno = JS_PCToLineNumber(cx, script, script->code + offset);
     args.rval().setNumber(lineno);
     return true;
 }
 
-class BytecodeRangeWithLineNumbers : private BytecodeRange
+class BytecodeRangeWithPosition : private BytecodeRange
 {
   public:
     using BytecodeRange::empty;
     using BytecodeRange::frontPC;
     using BytecodeRange::frontOpcode;
     using BytecodeRange::frontOffset;
 
-    BytecodeRangeWithLineNumbers(JSContext *cx, JSScript *script)
-      : BytecodeRange(cx, script), lineno(script->lineno), sn(script->notes()), snpc(script->code)
+    BytecodeRangeWithPosition(JSContext *cx, JSScript *script)
+      : BytecodeRange(cx, script), lineno(script->lineno), column(0),
+        sn(script->notes()), snpc(script->code)
     {
         if (!SN_IS_TERMINATOR(sn))
             snpc += SN_DELTA(sn);
-        updateLine();
+        updatePosition();
         while (frontPC() != script->main())
             popFront();
     }
 
     void popFront() {
         BytecodeRange::popFront();
         if (!empty())
-            updateLine();
+            updatePosition();
     }
 
     size_t frontLineNumber() const { return lineno; }
+    size_t frontColumnNumber() const { return column; }
 
   private:
-    void updateLine() {
+    void updatePosition() {
         /*
          * Determine the current line number by reading all source notes up to
          * and including the current offset.
          */
         while (!SN_IS_TERMINATOR(sn) && snpc <= frontPC()) {
             SrcNoteType type = (SrcNoteType) SN_TYPE(sn);
-            if (type == SRC_SETLINE)
+            if (type == SRC_COLSPAN) {
+                ptrdiff_t colspan = js_GetSrcNoteOffset(sn, 0);
+
+                if (colspan >= SN_COLSPAN_DOMAIN / 2)
+                    colspan -= SN_COLSPAN_DOMAIN;
+                JS_ASSERT(ptrdiff_t(column) + colspan >= 0);
+                column += colspan;
+            } if (type == SRC_SETLINE) {
                 lineno = size_t(js_GetSrcNoteOffset(sn, 0));
-            else if (type == SRC_NEWLINE)
+                column = 0;
+            } else if (type == SRC_NEWLINE) {
                 lineno++;
+                column = 0;
+            }
 
             sn = SN_NEXT(sn);
             snpc += SN_DELTA(sn);
         }
     }
 
     size_t lineno;
+    size_t column;
     jssrcnote *sn;
     jsbytecode *snpc;
 };
 
-static const size_t NoEdges = -1;
-static const size_t MultipleEdges = -2;
-
 /*
  * FlowGraphSummary::populate(cx, script) computes a summary of script's
  * control flow graph used by DebuggerScript_{getAllOffsets,getLineOffsets}.
  *
- * jumpData[offset] is:
- *   - NoEdges if offset isn't the offset of an instruction, or if the
- *     instruction is apparently unreachable;
- *   - MultipleEdges if you can arrive at that instruction from
- *     instructions on multiple different lines OR it's the first
- *     instruction of the script;
- *   - otherwise, the (unique) line number of all instructions that can
- *     precede the instruction at offset.
+ * An instruction on a given line is an entry point for that line if it can be
+ * reached from (an instruction on) a different line. We distinguish between the
+ * following cases:
+ *   - hasNoEdges:
+ *       The instruction cannot be reached, so the instruction is not an entry
+ *       point for the line it is on.
+ *   - hasSingleEdge:
+ *   - hasMultipleEdgesFromSingleLine:
+ *       The instruction can be reached from a single line. If this line is
+ *       different from the line the instruction is on, the instruction is an
+ *       entry point for that line.
+ *   - hasMultipleEdgesFromMultipleLines:
+ *       The instruction can be reached from multiple lines. At least one of
+ *       these lines is guaranteed to be different from the line the instruction
+ *       is on, so the instruction is an entry point for that line.
  *
- * The generated graph does not contain edges for JSOP_RETSUB, which appears at
- * the end of finally blocks. The algorithm that uses this information works
- * anyway, because in non-exception cases, JSOP_RETSUB always returns to a
- * !FlowsIntoNext instruction (JSOP_GOTO/GOTOX or JSOP_RETRVAL) which generates
- * an edge if needed.
+ * Similarly, an instruction on a given position (line/column pair) is an
+ * entry point for that position if it can be reached from (an instruction on) a
+ * different position. Again, we distinguish between the following cases:
+ *   - hasNoEdges:
+ *       The instruction cannot be reached, so the instruction is not an entry
+ *       point for the position it is on.
+ *   - hasSingleEdge:
+ *       The instruction can be reached from a single position. If this line is
+ *       different from the position the instruction is on, the instruction is
+ *       an entry point for that position.
+ *   - hasMultipleEdgesFromSingleLine:
+ *   - hasMultipleEdgesFromMultipleLines:
+ *       The instruction can be reached from multiple positions. At least one
+ *       of these positions is guaranteed to be different from the position the
+ *       instruction is on, so the instruction is an entry point for that
+ *       position.
  */
-class FlowGraphSummary : public Vector<size_t> {
+class FlowGraphSummary {
   public:
-    typedef Vector<size_t> Base;
-    FlowGraphSummary(JSContext *cx) : Base(cx) {}
-
-    void addEdge(size_t sourceLine, size_t targetOffset) {
-        FlowGraphSummary &self = *this;
-        if (self[targetOffset] == NoEdges)
-            self[targetOffset] = sourceLine;
-        else if (self[targetOffset] != sourceLine)
-            self[targetOffset] = MultipleEdges;
-    }
-
-    void addEdgeFromAnywhere(size_t targetOffset) {
-        (*this)[targetOffset] = MultipleEdges;
+    class Entry {
+      public:
+        static Entry createWithNoEdges() {
+            return Entry(-1, 0);
+        }
+
+        static Entry createWithSingleEdge(size_t lineno, size_t column) {
+            return Entry(lineno, column);
+        }
+
+        static Entry createWithMultipleEdgesFromSingleLine(size_t lineno) {
+            return Entry(lineno, -1);
+        }
+
+        static Entry createWithMultipleEdgesFromMultipleLines() {
+            return Entry(-1, -1);
+        }
+
+        Entry() {}
+
+        bool hasNoEdges() const {
+            return lineno_ == -1 && column_ != -1;
+        }
+
+        bool hasSingleEdge() const {
+            return lineno_ != -1 && column_ != -1;
+        }
+
+        bool hasMultipleEdgesFromSingleLine() const {
+            return lineno_ != -1 && column_ == -1;
+        }
+
+        bool hasMultipleEdgesFromMultipleLines() const {
+            return lineno_ == -1 && column_ == -1;
+        }
+
+        bool operator==(const Entry &other) const {
+            return lineno_ == other.lineno_ && column_ == other.column_;
+        }
+
+        bool operator!=(const Entry &other) const {
+            return lineno_ != other.lineno_ || column_ != other.column_;
+        }
+
+        size_t lineno() const {
+            return lineno_;
+        }
+
+        size_t column() const {
+            return column_;
+        }
+
+      private:
+        Entry(size_t lineno, size_t column) : lineno_(lineno), column_(column) {}
+
+        size_t lineno_;
+        size_t column_;
+    };
+
+    FlowGraphSummary(JSContext *cx) : entries_(cx) {}
+
+    Entry &operator[](size_t index) {
+        return entries_[index];
     }
 
     bool populate(JSContext *cx, JSScript *script) {
-        if (!growBy(script->length))
+        if (!entries_.growBy(script->length))
             return false;
-        FlowGraphSummary &self = *this;
         unsigned mainOffset = script->main() - script->code;
-        self[mainOffset] = MultipleEdges;
+        entries_[mainOffset] = Entry::createWithMultipleEdgesFromMultipleLines();
         for (size_t i = mainOffset + 1; i < script->length; i++)
-            self[i] = NoEdges;
-
-        size_t prevLine = script->lineno;
+            entries_[i] = Entry::createWithNoEdges();
+
+        size_t prevLineno = script->lineno;
+        size_t prevColumn = 0;
         JSOp prevOp = JSOP_NOP;
-        for (BytecodeRangeWithLineNumbers r(cx, script); !r.empty(); r.popFront()) {
+        for (BytecodeRangeWithPosition r(cx, script); !r.empty(); r.popFront()) {
             size_t lineno = r.frontLineNumber();
+            size_t column = r.frontColumnNumber();
             JSOp op = r.frontOpcode();
 
             if (FlowsIntoNext(prevOp))
-                addEdge(prevLine, r.frontOffset());
+                addEdge(prevLineno, prevColumn, r.frontOffset());
 
             if (js_CodeSpec[op].type() == JOF_JUMP) {
-                addEdge(lineno, r.frontOffset() + GET_JUMP_OFFSET(r.frontPC()));
+                addEdge(lineno, column, r.frontOffset() + GET_JUMP_OFFSET(r.frontPC()));
             } else if (op == JSOP_TABLESWITCH) {
                 jsbytecode *pc = r.frontPC();
                 size_t offset = r.frontOffset();
                 ptrdiff_t step = JUMP_OFFSET_LEN;
                 size_t defaultOffset = offset + GET_JUMP_OFFSET(pc);
                 pc += step;
-                addEdge(lineno, defaultOffset);
+                addEdge(lineno, column, defaultOffset);
 
                 int32_t low = GET_JUMP_OFFSET(pc);
                 pc += JUMP_OFFSET_LEN;
                 int ncases = GET_JUMP_OFFSET(pc) - low + 1;
                 pc += JUMP_OFFSET_LEN;
 
                 for (int i = 0; i < ncases; i++) {
                     size_t target = offset + GET_JUMP_OFFSET(pc);
-                    addEdge(lineno, target);
+                    addEdge(lineno, column, target);
                     pc += step;
                 }
             }
 
+            prevLineno = lineno;
+            prevColumn = column;
             prevOp = op;
-            prevLine = lineno;
         }
 
         return true;
     }
+
+  private:
+    void addEdge(size_t sourceLineno, size_t sourceColumn, size_t targetOffset) {
+        if (entries_[targetOffset].hasNoEdges())
+            entries_[targetOffset] = Entry::createWithSingleEdge(sourceLineno, sourceColumn);
+        else if (entries_[targetOffset].lineno() != sourceLineno)
+            entries_[targetOffset] = Entry::createWithMultipleEdgesFromMultipleLines();
+        else if (entries_[targetOffset].column() != sourceColumn)
+            entries_[targetOffset] = Entry::createWithMultipleEdgesFromSingleLine(sourceLineno);
+    }
+
+    Vector<Entry> entries_;
 };
 
 static JSBool
 DebuggerScript_getAllOffsets(JSContext *cx, unsigned argc, Value *vp)
 {
     THIS_DEBUGSCRIPT_SCRIPT(cx, argc, vp, "getAllOffsets", args, obj, script);
 
     /*
@@ -3036,22 +3128,22 @@ DebuggerScript_getAllOffsets(JSContext *
     FlowGraphSummary flowData(cx);
     if (!flowData.populate(cx, script))
         return false;
 
     /* Second pass: build the result array. */
     RootedObject result(cx, NewDenseEmptyArray(cx));
     if (!result)
         return false;
-    for (BytecodeRangeWithLineNumbers r(cx, script); !r.empty(); r.popFront()) {
+    for (BytecodeRangeWithPosition r(cx, script); !r.empty(); r.popFront()) {
         size_t offset = r.frontOffset();
         size_t lineno = r.frontLineNumber();
 
         /* Make a note, if the current instruction is an entry point for the current line. */
-        if (flowData[offset] != NoEdges && flowData[offset] != lineno) {
+        if (!flowData[offset].hasNoEdges() && flowData[offset].lineno() != lineno) {
             /* Get the offsets array for this line. */
             RootedObject offsets(cx);
             RootedValue offsetsv(cx);
 
             RootedId id(cx, INT_TO_JSID(lineno));
 
             bool found;
             if (!JSObject::hasProperty(cx, result, id, &found))
@@ -3117,23 +3209,23 @@ DebuggerScript_getLineOffsets(JSContext 
     FlowGraphSummary flowData(cx);
     if (!flowData.populate(cx, script))
         return false;
 
     /* Second pass: build the result array. */
     RootedObject result(cx, NewDenseEmptyArray(cx));
     if (!result)
         return false;
-    for (BytecodeRangeWithLineNumbers r(cx, script); !r.empty(); r.popFront()) {
+    for (BytecodeRangeWithPosition r(cx, script); !r.empty(); r.popFront()) {
         size_t offset = r.frontOffset();
 
         /* If the op at offset is an entry point, append offset to result. */
         if (r.frontLineNumber() == lineno &&
-            flowData[offset] != NoEdges &&
-            flowData[offset] != lineno)
+            !flowData[offset].hasNoEdges() &&
+            flowData[offset].lineno() != lineno)
         {
             if (!js_NewbornArrayPush(cx, result, NumberValue(offset)))
                 return false;
         }
     }
 
     args.rval().setObject(*result);
     return true;