Use VM tag in profile and add stack trace trie

runtime/vm/profiler.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "platform/utils.h"
 
 #include "vm/allocation.h"
 #include "vm/atomic.h"
 #include "vm/code_patcher.h"
 #include "vm/isolate.h"
@@ skipping 183 matching lines @@
 
   void tick(bool exclusive) {
     if (exclusive) {
       exclusive_ticks++;
     } else {
       inclusive_ticks++;
     }
   }
 };
 
+
 struct CallEntry {
   intptr_t code_table_index;
   intptr_t count;
 };
 
+
 typedef bool (*RegionCompare)(uword pc, uword region_start, uword region_end);
 

[siva, 2014/03/18 00:05:20]

blank line needed to maintain 2 blank lines.

[Cutch, 2014/03/18 14:39:19]

Done.

+class CodeRegionTrieNode : public ZoneAllocated {
+ public:
+  explicit CodeRegionTrieNode(intptr_t code_region_index)
+      : code_region_index_(code_region_index),
+        count_(0),
+        children_(new ZoneGrowableArray<CodeRegionTrieNode*>()) {
+  }
+
+  void Tick() {
+    ASSERT(code_region_index_ >= 0);
+    count_++;
+  }
+
+  intptr_t count() const {
+    ASSERT(code_region_index_ >= 0);
+    return count_;
+  }
+
+  intptr_t code_region_index() const {
+    return code_region_index_;
+  }
+
+  CodeRegionTrieNode* GetChild(intptr_t child_code_region_index) {
+    const intptr_t length = children_->length();
+    intptr_t i = 0;
+    for (; i < length; i++) {

[siva, 2014/03/18 00:05:20]

might be more readable as:
while (i < length) {
 ...
 ...
 ++i;
}

[Cutch, 2014/03/18 14:39:19]

Done.

+      CodeRegionTrieNode* child = (*children_)[i];
+      if (child->code_region_index() == child_code_region_index) {
+        return child;
+      }
+      if (child->code_region_index() > child_code_region_index) {
+        break;
+      }
+    }
+    // New code region.
+    CodeRegionTrieNode* child = new CodeRegionTrieNode(child_code_region_index);
+    if (i < length) {
+      // Insert at i.
+      children_->InsertAt(i, child);
+    } else {
+      // Add to end.
+      children_->Add(child);
+    }
+    return child;
+  }
+
+  void RecursiveSort() {
+    children_->Sort(CodeRegionTrieNodeCompare);
+    ZoneGrowableArray<CodeRegionTrieNode*>& kids = children();
+    intptr_t child_count = kids.length();
+    // Recurse.
+    for (intptr_t i = 0; i < child_count; i++) {
+      kids[i]->RecursiveSort();
+    }
+  }
+
+  void PrintToJSONArray(JSONArray* array) {

[siva, 2014/03/18 00:05:20]

void PrintToJSONArray(....) const {

[Cutch, 2014/03/18 14:39:19]

Done.

+    ASSERT(array != NULL);
+    // Write CodeRegion index.
+    array->AddValue(code_region_index_);
+    // Write count.
+    array->AddValue(count_);
+    // Write number of children.
+    ZoneGrowableArray<CodeRegionTrieNode*>& kids = children();
+    intptr_t child_count = kids.length();
+    array->AddValue(child_count);
+    // Recurse.
+    for (intptr_t i = 0; i < child_count; i++) {
+      kids[i]->PrintToJSONArray(array);
+    }
+  }
+
+  ZoneGrowableArray<CodeRegionTrieNode*>& children() const {
+    return *children_;
+  }

[siva, 2014/03/18 00:05:20]

Why not club this accessor with the other accessors above (count,
code_region_index)

[Cutch, 2014/03/18 14:39:19]

Done.

+
+ private:
+  static int CodeRegionTrieNodeCompare(CodeRegionTrieNode* const* a,
+                                       CodeRegionTrieNode* const* b) {
+    ASSERT(a != NULL);
+    ASSERT(b != NULL);
+    return (*b)->count() - (*a)->count();
+  }
+
+  const intptr_t code_region_index_;
+  intptr_t count_;
+  ZoneGrowableArray<CodeRegionTrieNode*>* children_;
+};
+
+
 // A contiguous address region that holds code. Each CodeRegion has a "kind"
 // which describes the type of code contained inside the region. Each
 // region covers the following interval: [start, end).
 class CodeRegion : public ZoneAllocated {
  public:
   enum Kind {
     kDartCode,       // Live Dart code.
     kCollectedCode,  // Dead Dart code.
     kNativeCode,     // Native code.
     kReusedCode,     // Dead Dart code that has been reused by new kDartCode.
     kTagCode,        // A special kind of code representing a tag.
   };
 
-  CodeRegion(Kind kind, uword start, uword end, int64_t timestamp) :
-      kind_(kind),
-      start_(start),
-      end_(end),
-      inclusive_ticks_(0),
-      exclusive_ticks_(0),
-      inclusive_tick_serial_(0),
-      name_(NULL),
-      compile_timestamp_(timestamp),
-      creation_serial_(0),
-      address_table_(new ZoneGrowableArray<AddressEntry>()),
-      callers_table_(new ZoneGrowableArray<CallEntry>()),
-      callees_table_(new ZoneGrowableArray<CallEntry>()) {
+  CodeRegion(Kind kind, uword start, uword end, int64_t timestamp)
+      : kind_(kind),
+        start_(start),
+        end_(end),
+        inclusive_ticks_(0),
+        exclusive_ticks_(0),
+        inclusive_tick_serial_(0),
+        name_(NULL),
+        compile_timestamp_(timestamp),
+        creation_serial_(0),
+        address_table_(new ZoneGrowableArray<AddressEntry>()),
+        callers_table_(new ZoneGrowableArray<CallEntry>()),
+        callees_table_(new ZoneGrowableArray<CallEntry>()) {
     ASSERT(start_ < end_);
   }
 
 
   uword start() const { return start_; }
   void set_start(uword start) {
     start_ = start;
   }
 
   uword end() const { return end_; }
@@ skipping 92 matching lines @@
     if (exclusive) {
       exclusive_ticks_++;
     } else {
       inclusive_ticks_++;
       // Mark the last serial we ticked the inclusive count.
       inclusive_tick_serial_ = serial;
     }
     TickAddress(pc, exclusive);
   }
 
-  void AddCaller(intptr_t index) {
-    AddCallEntry(callers_table_, index);
+  void AddCaller(intptr_t index, intptr_t count) {
+    AddCallEntry(callers_table_, index, count);
   }
 
-  void AddCallee(intptr_t index) {
-    AddCallEntry(callees_table_, index);
+  void AddCallee(intptr_t index, intptr_t count) {
+    AddCallEntry(callees_table_, index, count);
   }
 
   void PrintNativeCode(JSONObject* profile_code_obj) {
     ASSERT(kind() == kNativeCode);
     JSONObject obj(profile_code_obj, "code");
     obj.AddProperty("type", "@Code");
     obj.AddProperty("kind", "Native");
     obj.AddProperty("name", name());
     obj.AddProperty("user_name", name());
     obj.AddPropertyF("start", "%" Px "", start());
@@ skipping 45 matching lines @@
       // Generate a fake function entry.
       JSONObject func(&obj, "function");
       func.AddProperty("type", "@Function");
       obj.AddPropertyF("id", "functions/reused-%" Px "", start());
       func.AddProperty("name", name());
       func.AddProperty("user_name", name());
       func.AddProperty("kind", "Reused");
     }
   }
 
+  void  PrintTagCode(JSONObject* profile_code_obj) {
+    ASSERT(kind() == kTagCode);
+    JSONObject obj(profile_code_obj, "code");
+    obj.AddProperty("type", "@Code");
+    obj.AddProperty("kind", "Tag");
+    obj.AddPropertyF("id", "code/tag-%" Px "", start());
+    obj.AddProperty("name", name());
+    obj.AddProperty("user_name", name());
+    obj.AddPropertyF("start", "%" Px "", start());
+    obj.AddPropertyF("end", "%" Px "", end());
+    {
+      // Generate a fake function entry.
+      JSONObject func(&obj, "function");
+      func.AddProperty("type", "@Function");
+      func.AddProperty("kind", "Tag");
+      obj.AddPropertyF("id", "functions/tag-%" Px "", start());
+      func.AddProperty("name", name());
+      func.AddProperty("user_name", name());
+    }
+  }
+
   void PrintToJSONArray(Isolate* isolate, JSONArray* events, bool full) {
     JSONObject obj(events);
     obj.AddProperty("type", "CodeRegion");
     obj.AddProperty("kind", KindToCString(kind()));
     obj.AddPropertyF("inclusive_ticks", "%" Pd "", inclusive_ticks());
     obj.AddPropertyF("exclusive_ticks", "%" Pd "", exclusive_ticks());
     if (kind() == kDartCode) {
       // Look up code in Dart heap.
       Code& code = Code::Handle(isolate);
       code ^= Code::LookupCode(start());
       if (code.IsNull()) {
         // Code is a stub in the Vm isolate.
         code ^= Code::LookupCodeInVmIsolate(start());
       }
       ASSERT(!code.IsNull());
       obj.AddProperty("code", code, !full);
     } else if (kind() == kCollectedCode) {
       if (name() == NULL) {
         // Lazily set generated name.
         GenerateAndSetSymbolName("[Collected]");
       }
       PrintCollectedCode(&obj);
     } else if (kind() == kReusedCode) {
       if (name() == NULL) {
         // Lazily set generated name.
         GenerateAndSetSymbolName("[Reused]");
       }
       PrintOverwrittenCode(&obj);
+    } else if (kind() == kTagCode) {
+      if (name() == NULL) {
+        const char* tag_name = start() == 0 ? "root" : VMTag::TagName(start());
+        ASSERT(tag_name != NULL);
+        SetName(tag_name);
+      }
+      PrintTagCode(&obj);
     } else {
       ASSERT(kind() == kNativeCode);
       if (name() == NULL) {
         // Lazily set generated name.
         GenerateAndSetSymbolName("[Native]");
       }
       PrintNativeCode(&obj);
     }
     {
       JSONArray ticks(&obj, "ticks");
@@ skipping 46 matching lines @@
     if (i < length) {
       // Insert at i.
       address_table_->InsertAt(i, entry);
     } else {
       // Add to end.
       address_table_->Add(entry);
     }
   }
 
 
-  void AddCallEntry(ZoneGrowableArray<CallEntry>* table, intptr_t index) {
+  void AddCallEntry(ZoneGrowableArray<CallEntry>* table, intptr_t index,
+                    intptr_t count) {
     const intptr_t length = table->length();
     intptr_t i = 0;
     for (; i < length; i++) {
       CallEntry& entry = (*table)[i];
       if (entry.code_table_index == index) {
-        entry.count++;
+        entry.count += count;
         return;
       }
       if (entry.code_table_index > index) {
         break;
       }
     }
     CallEntry entry;
     entry.code_table_index = index;
-    entry.count = 1;
+    entry.count = count;
     if (i < length) {
       table->InsertAt(i, entry);
     } else {
       table->Add(entry);
     }
   }
 
   void GenerateAndSetSymbolName(const char* prefix) {
     const intptr_t kBuffSize = 512;
     char buff[kBuffSize];
@@ skipping 20 matching lines @@
   // The compilation timestamp associated with this code region.
   int64_t compile_timestamp_;
   // Serial number at which this CodeRegion was created.
   intptr_t creation_serial_;
   ZoneGrowableArray<AddressEntry>* address_table_;
   ZoneGrowableArray<CallEntry>* callers_table_;
   ZoneGrowableArray<CallEntry>* callees_table_;
   DISALLOW_COPY_AND_ASSIGN(CodeRegion);
 };
 
+
 // A sorted table of CodeRegions. Does not allow for overlap.
 class CodeRegionTable : public ValueObject {
  public:
   enum TickResult {
     kTicked = 0,     // CodeRegion found and ticked.
     kNotFound = -1,   // No CodeRegion found.
     kNewerCode = -2,  // CodeRegion found but it was compiled after sample.
   };
 
   CodeRegionTable() :
@@ skipping 142 matching lines @@
   }
 
   static bool CompareLowerBound(uword pc, uword start, uword end) {
     return end <= pc;
   }
 
   void HandleOverlap(CodeRegion* region, CodeRegion* code_region,
                      uword start, uword end) {
     // We should never see overlapping Dart code regions.
     ASSERT(region->kind() != CodeRegion::kDartCode);
+    // We should never see overlapping Tag code regions.
+    ASSERT(region->kind() != CodeRegion::kTagCode);
     // When code regions overlap, they should be of the same kind.
     ASSERT(region->kind() == code_region->kind());
     region->AdjustExtent(start, end);
   }
 
 #if defined(DEBUG)
   void VerifyOrder() {
     const intptr_t length = code_region_table_->length();
     if (length == 0) {
       return;
@@ skipping 22 matching lines @@
 #endif
 
   ZoneGrowableArray<CodeRegion*>* code_region_table_;
 };
 
 
 class CodeRegionTableBuilder : public SampleVisitor {
  public:
   CodeRegionTableBuilder(Isolate* isolate,
                          CodeRegionTable* live_code_table,
-                         CodeRegionTable* dead_code_table)
+                         CodeRegionTable* dead_code_table,
+                         CodeRegionTable* tag_code_table)
       : SampleVisitor(isolate),
         live_code_table_(live_code_table),
         dead_code_table_(dead_code_table),
+        tag_code_table_(tag_code_table),
         isolate_(isolate),
         vm_isolate_(Dart::vm_isolate()) {
     ASSERT(live_code_table_ != NULL);
     ASSERT(dead_code_table_ != NULL);
+    ASSERT(tag_code_table_ != NULL);
     frames_ = 0;
     min_time_ = kMaxInt64;
     max_time_ = 0;
     ASSERT(isolate_ != NULL);
     ASSERT(vm_isolate_ != NULL);
   }
 
   void VisitSample(Sample* sample) {
     int64_t timestamp = sample->timestamp();
     if (timestamp > max_time_) {
       max_time_ = timestamp;
     }
     if (timestamp < min_time_) {
       min_time_ = timestamp;
     }
+    // Make sure VM tag is created.
+    CreateTag(sample->vm_tag());
     // Exclusive tick for bottom frame.
     Tick(sample->At(0), true, timestamp);
     // Inclusive tick for all frames.
     for (intptr_t i = 0; i < FLAG_profile_depth; i++) {
       if (sample->At(i) == 0) {
         break;
       }
       frames_++;
       Tick(sample->At(i), false, timestamp);
     }
   }
 
   intptr_t frames() const { return frames_; }
 
   intptr_t  TimeDeltaMicros() const {
     return static_cast<intptr_t>(max_time_ - min_time_);
   }
   int64_t  max_time() const { return max_time_; }
 
  private:
+  void CreateTag(uword tag) {
+    intptr_t index = tag_code_table_->FindIndex(tag);
+    if (index >= 0) {
+      // Already created.
+      return;
+    }
+    CodeRegion* region = new CodeRegion(CodeRegion::kTagCode,
+                                        tag,
+                                        tag + 1,
+                                        0);
+    index = tag_code_table_->InsertCodeRegion(region);
+    ASSERT(index >= 0);
+    region->set_creation_serial(visited());
+  }
+
+  void TickTag(uword tag, bool exclusive) {
+    CodeRegionTable::TickResult r;
+    intptr_t serial = exclusive ? -1 : visited();
+    r = tag_code_table_->Tick(tag, exclusive, serial, 0);
+    if (r == CodeRegionTable::kTicked) {
+      // Live code found and ticked.
+      return;
+    }
+    ASSERT(r == CodeRegionTable::kNotFound);
+    CreateAndTickTagCodeRegion(tag, exclusive, serial);
+  }
+
+  void CreateAndTickTagCodeRegion(uword tag, bool exclusive, intptr_t serial) {
+    // Need to create tag code.
+    CodeRegion* region = new CodeRegion(CodeRegion::kTagCode,
+                                        tag,
+                                        tag + 1,
+                                        0);
+    intptr_t index = tag_code_table_->InsertCodeRegion(region);
+    region->set_creation_serial(visited());
+    ASSERT(index >= 0);
+    tag_code_table_->At(index)->Tick(tag, exclusive, serial);
+  }
+
   void Tick(uword pc, bool exclusive, int64_t timestamp) {
     CodeRegionTable::TickResult r;
     intptr_t serial = exclusive ? -1 : visited();
     r = live_code_table_->Tick(pc, exclusive, serial, timestamp);
     if (r == CodeRegionTable::kTicked) {
       // Live code found and ticked.
       return;
     }
     if (r == CodeRegionTable::kNewerCode) {
       // Code has been overwritten by newer code.
@@ skipping 79 matching lines @@
     code_region->SetName(native_name);
     free(native_name);
     return code_region;
   }
 
   intptr_t frames_;
   int64_t min_time_;
   int64_t max_time_;
   CodeRegionTable* live_code_table_;
   CodeRegionTable* dead_code_table_;
+  CodeRegionTable* tag_code_table_;
   Isolate* isolate_;
   Isolate* vm_isolate_;
 };
 
 
-class CodeRegionTableCallersBuilder : public SampleVisitor {
+class CodeRegionExclusiveTrieBuilder : public SampleVisitor {
  public:
-  CodeRegionTableCallersBuilder(Isolate* isolate,
-                                CodeRegionTable* live_code_table,
-                                CodeRegionTable* dead_code_table)
+  CodeRegionExclusiveTrieBuilder(Isolate* isolate,
+                                 CodeRegionTable* live_code_table,
+                                 CodeRegionTable* dead_code_table,
+                                 CodeRegionTable* tag_code_table)
       : SampleVisitor(isolate),
         live_code_table_(live_code_table),
-        dead_code_table_(dead_code_table) {
+        dead_code_table_(dead_code_table),
+        tag_code_table_(tag_code_table) {
     ASSERT(live_code_table_ != NULL);
     ASSERT(dead_code_table_ != NULL);
+    ASSERT(tag_code_table_ != NULL);
     dead_code_table_offset_ = live_code_table_->Length();
+    tag_code_table_offset_ = dead_code_table_offset_ +
+                             dead_code_table_->Length();
+    intptr_t root_index = tag_code_table_->FindIndex(0);
+    // Verify that the "0" tag does not exist.
+    ASSERT(root_index < 0);
+    // Insert the dummy tag CodeRegion that is used for the Trie root.
+    CodeRegion* region = new CodeRegion(CodeRegion::kTagCode, 0, 1, 0);
+    root_index = tag_code_table_->InsertCodeRegion(region);
+    ASSERT(root_index >= 0);
+    region->set_creation_serial(0);
+    root_ = new CodeRegionTrieNode(tag_code_table_offset_ + root_index);
+    // Use tags by default.
+    set_use_tags(true);
   }
 
   void VisitSample(Sample* sample) {
-    int64_t timestamp = sample->timestamp();
-    intptr_t current_index = FindFinalIndex(sample->At(0), timestamp);
-    ASSERT(current_index >= 0);
-    CodeRegion* current = At(current_index);
-    intptr_t caller_index = -1;
-    CodeRegion* caller = NULL;
-    intptr_t callee_index = -1;
-    CodeRegion* callee = NULL;
-    for (intptr_t i = 1; i < FLAG_profile_depth; i++) {
+    // Give the root a tick.
+    root_->Tick();
+    CodeRegionTrieNode* current = root_;
+    if (use_tags()) {
+      intptr_t tag_index = FindTagIndex(sample->vm_tag());
+      current = current->GetChild(tag_index);
+      // Give the tag a tick.
+      current->Tick();
+    }
+    // Walk the sampled PCs.
+    for (intptr_t i = 0; i < FLAG_profile_depth; i++) {
       if (sample->At(i) == 0) {
         break;
       }
-      caller_index = FindFinalIndex(sample->At(i), timestamp);
-      ASSERT(caller_index >= 0);
-      caller = At(caller_index);
-      current->AddCaller(caller_index);
-      if (callee != NULL) {
-        current->AddCallee(callee_index);
-      }
-      // Move cursors.
-      callee_index = current_index;
-      callee = current;
-      current_index = caller_index;
-      current = caller;
+      intptr_t index = FindFinalIndex(sample->At(i), sample->timestamp());
+      current = current->GetChild(index);
+      current->Tick();
     }
   }
 
+  CodeRegionTrieNode* root() const {
+    return root_;
+  }
+
+  bool use_tags() const {
+    return use_tags_;
+  }
+
+  void set_use_tags(bool use_tags) {
+    use_tags_ = use_tags;
+  }
+
  private:
+  intptr_t FindTagIndex(uword tag) const {
+    intptr_t index = tag_code_table_->FindIndex(tag);
+    ASSERT(index >= 0);
+    CodeRegion* region = tag_code_table_->At(index);
+    ASSERT(region->contains(tag));

[siva, 2014/03/18 00:05:20]

Can this be:
ASSERT((tag_code_table_->At(index))->contains(tag));

[Cutch, 2014/03/18 14:39:19]

Done.

+    return tag_code_table_offset_ + index;
+  }
+
   intptr_t FindFinalIndex(uword pc, int64_t timestamp) const {
     intptr_t index = live_code_table_->FindIndex(pc);
     ASSERT(index >= 0);
     CodeRegion* region = live_code_table_->At(index);
     ASSERT(region->contains(pc));
     if (region->compile_timestamp() > timestamp) {
       // Overwritten code, find in dead code table.
       index = dead_code_table_->FindIndex(pc);
       ASSERT(index >= 0);
       region = dead_code_table_->At(index);
       ASSERT(region->contains(pc));
       ASSERT(region->compile_timestamp() <= timestamp);
       return index + dead_code_table_offset_;
     }
     ASSERT(region->compile_timestamp() <= timestamp);
     return index;
   }
 
+  bool use_tags_;
+  CodeRegionTrieNode* root_;
+  CodeRegionTable* live_code_table_;
+  CodeRegionTable* dead_code_table_;
+  CodeRegionTable* tag_code_table_;
+  intptr_t dead_code_table_offset_;
+  intptr_t tag_code_table_offset_;
+};
+
+
+class CodeRegionTableCallersBuilder {
+ public:
+  CodeRegionTableCallersBuilder(CodeRegionTrieNode* exclusive_root,
+                                CodeRegionTable* live_code_table,
+                                CodeRegionTable* dead_code_table,
+                                CodeRegionTable* tag_code_table)
+      : exclusive_root_(exclusive_root),
+        live_code_table_(live_code_table),
+        dead_code_table_(dead_code_table),
+        tag_code_table_(tag_code_table) {
+    ASSERT(exclusive_root_ != NULL);
+    ASSERT(live_code_table_ != NULL);
+    ASSERT(dead_code_table_ != NULL);
+    ASSERT(tag_code_table_ != NULL);
+    dead_code_table_offset_ = live_code_table_->Length();
+    tag_code_table_offset_ = dead_code_table_offset_ +
+                             dead_code_table_->Length();
+  }
+
+  void Build() {
+    ProcessNode(exclusive_root_);
+  }
+
+ private:
+  void ProcessNode(CodeRegionTrieNode* parent) {
+    const ZoneGrowableArray<CodeRegionTrieNode*>& children = parent->children();
+    intptr_t parent_index = parent->code_region_index();
+    ASSERT(parent_index >= 0);
+    CodeRegion* parent_region = At(parent_index);
+    ASSERT(parent_region != NULL);
+    for (intptr_t i = 0; i < children.length(); i++) {
+      CodeRegionTrieNode* node = children[i];
+      ProcessNode(node);
+      intptr_t index = node->code_region_index();
+      ASSERT(index >= 0);
+      CodeRegion* region = At(index);
+      ASSERT(region != NULL);
+      region->AddCallee(parent_index, node->count());
+      parent_region->AddCaller(index, node->count());
+    }
+  }
+
   CodeRegion* At(intptr_t final_index) {
     ASSERT(final_index >= 0);
     if (final_index < dead_code_table_offset_) {
       return live_code_table_->At(final_index);
+    } else if (final_index < tag_code_table_offset_) {
+      return dead_code_table_->At(final_index - dead_code_table_offset_);
     } else {
-      return dead_code_table_->At(final_index - dead_code_table_offset_);
+      return tag_code_table_->At(final_index - tag_code_table_offset_);
     }
   }
 
+  CodeRegionTrieNode* exclusive_root_;
   CodeRegionTable* live_code_table_;
   CodeRegionTable* dead_code_table_;
+  CodeRegionTable* tag_code_table_;
   intptr_t dead_code_table_offset_;
+  intptr_t tag_code_table_offset_;
 };
 
+
 void Profiler::PrintToJSONStream(Isolate* isolate, JSONStream* stream,
-                                 bool full) {
+                                 bool full, bool use_tags) {
   ASSERT(isolate == Isolate::Current());
   // Disable profile interrupts while processing the buffer.
   EndExecution(isolate);
   MutexLocker profiler_data_lock(isolate->profiler_data_mutex());
   IsolateProfilerData* profiler_data = isolate->profiler_data();
   if (profiler_data == NULL) {
     JSONObject error(stream);
     error.AddProperty("type", "Error");
     error.AddProperty("text", "Isolate does not have profiling enabled.");
     return;
   }
   SampleBuffer* sample_buffer = profiler_data->sample_buffer();
   ASSERT(sample_buffer != NULL);
   {
     StackZone zone(isolate);
     {
       // Live code holds Dart, Native, and Collected CodeRegions.
       CodeRegionTable live_code_table;
       // Dead code holds Overwritten CodeRegions.
       CodeRegionTable dead_code_table;
+      // Tag code holds Tag CodeRegions.
+      CodeRegionTable tag_code_table;
       CodeRegionTableBuilder builder(isolate,
                                      &live_code_table,
-                                     &dead_code_table);
+                                     &dead_code_table,
+                                     &tag_code_table);
       {
         // Build CodeRegion tables.
-        ScopeStopwatch sw("CodeTableBuild");
+        ScopeStopwatch sw("CodeRegionTableBuilder");
         sample_buffer->VisitSamples(&builder);
       }
       intptr_t samples = builder.visited();
       intptr_t frames = builder.frames();
       if (FLAG_trace_profiled_isolates) {
         intptr_t total_live_code_objects = live_code_table.Length();
         intptr_t total_dead_code_objects = dead_code_table.Length();
+        intptr_t total_tag_code_objects = tag_code_table.Length();
         OS::Print("Processed %" Pd " frames\n", frames);
-        OS::Print("CodeTables: live=%" Pd " dead=%" Pd "\n",
+        OS::Print("CodeTables: live=%" Pd " dead=%" Pd " tag=%" Pd "\n",
                   total_live_code_objects,
-                  total_dead_code_objects);
+                  total_dead_code_objects,
+                  total_tag_code_objects);
       }
 #if defined(DEBUG)
       live_code_table.Verify();
       dead_code_table.Verify();
+      tag_code_table.Verify();
       if (FLAG_trace_profiled_isolates) {
         OS::Print("CodeRegionTables verified to be ordered and not overlap.\n");
       }
 #endif
-      CodeRegionTableCallersBuilder build_callers(isolate,
+      CodeRegionExclusiveTrieBuilder build_trie(isolate,
+                                                &live_code_table,
+                                                &dead_code_table,
+                                                &tag_code_table);
+      build_trie.set_use_tags(use_tags);
+      {
+        // Build CodeRegion trie.
+        ScopeStopwatch sw("CodeRegionExclusiveTrieBuilder");
+        sample_buffer->VisitSamples(&build_trie);
+        build_trie.root()->RecursiveSort();
+      }
+      CodeRegionTableCallersBuilder build_callers(build_trie.root(),
                                                   &live_code_table,
-                                                  &dead_code_table);
+                                                  &dead_code_table,
+                                                  &tag_code_table);
       {
         // Build CodeRegion callers.
-        ScopeStopwatch sw("CodeTableCallersBuild");
-        sample_buffer->VisitSamples(&build_callers);
+        ScopeStopwatch sw("CodeRegionTableCallersBuilder");
+        build_callers.Build();
       }
       {
         ScopeStopwatch sw("CodeTableStream");
         // Serialize to JSON.
         JSONObject obj(stream);
         obj.AddProperty("type", "Profile");
         obj.AddProperty("id", "profile");
         obj.AddProperty("samples", samples);
+        obj.AddProperty("depth", static_cast<intptr_t>(FLAG_profile_depth));
+        obj.AddProperty("period", static_cast<intptr_t>(FLAG_profile_period));
         obj.AddProperty("time_delta_micros", builder.TimeDeltaMicros());
+        {
+          JSONArray exclusive_trie(&obj, "exclusive_trie");
+          CodeRegionTrieNode* root = build_trie.root();
+          ASSERT(root != NULL);
+          root->PrintToJSONArray(&exclusive_trie);
+        }
         JSONArray codes(&obj, "codes");
         for (intptr_t i = 0; i < live_code_table.Length(); i++) {
           CodeRegion* region = live_code_table.At(i);
           ASSERT(region != NULL);
           region->PrintToJSONArray(isolate, &codes, full);
         }
         for (intptr_t i = 0; i < dead_code_table.Length(); i++) {
           CodeRegion* region = dead_code_table.At(i);
           ASSERT(region != NULL);
           region->PrintToJSONArray(isolate, &codes, full);
         }
+        for (intptr_t i = 0; i < tag_code_table.Length(); i++) {
+          CodeRegion* region = tag_code_table.At(i);
+          ASSERT(region != NULL);
+          region->PrintToJSONArray(isolate, &codes, full);
+        }
       }
     }
   }
   // Enable profile interrupts.
   BeginExecution(isolate);
 }
 
 
 void Profiler::WriteProfile(Isolate* isolate) {
   if (isolate == NULL) {
@@ skipping 10 matching lines @@
   Dart_FileCloseCallback file_close = Isolate::file_close_callback();
   Dart_FileWriteCallback file_write = Isolate::file_write_callback();
   if ((file_open == NULL) || (file_close == NULL) || (file_write == NULL)) {
     // Embedder has not provided necessary callbacks.
     return;
   }
   // We will be looking up code objects within the isolate.
   ASSERT(Isolate::Current() == isolate);
   JSONStream stream(10 * MB);
   intptr_t pid = OS::ProcessId();
-  PrintToJSONStream(isolate, &stream, true);
+  PrintToJSONStream(isolate, &stream, true, false);
   const char* format = "%s/dart-profile-%" Pd "-%" Pd ".json";
   intptr_t len = OS::SNPrint(NULL, 0, format,
                              FLAG_profile_dir, pid, isolate->main_port());
   char* filename = Isolate::Current()->current_zone()->Alloc<char>(len + 1);
   OS::SNPrint(filename, len + 1, format,
               FLAG_profile_dir, pid, isolate->main_port());
   void* f = file_open(filename, true);
   if (f == NULL) {
     // Cannot write.
     return;
@@ skipping 48 matching lines @@
                             uword sp)
       : sample_(sample),
         stack_upper_(stack_upper),
         original_pc_(pc),
         original_fp_(fp),
         original_sp_(sp),
         lower_bound_(stack_lower) {
     ASSERT(sample_ != NULL);
   }
 
-  int walk(Heap* heap) {
+  int walk(Heap* heap, uword vm_tag) {
     const intptr_t kMaxStep = 0x1000;  // 4K.
     const bool kWalkStack = true;  // Walk the stack.
     // Always store the exclusive PC.
     sample_->SetAt(0, original_pc_);
+    // Always store the vm tag.
+    sample_->set_vm_tag(vm_tag);
     if (!kWalkStack) {
       // Not walking the stack, only took exclusive sample.
       return 1;
     }
     uword* pc = reinterpret_cast<uword*>(original_pc_);
     uword* fp = reinterpret_cast<uword*>(original_fp_);
     uword* previous_fp = fp;
     if (original_sp_ > original_fp_) {
       // Stack pointer should not be above frame pointer.
       return 1;
@@ skipping 97 matching lines @@
   sample->Init(isolate, OS::GetCurrentTimeMicros(), state.tid);
   uword stack_lower = 0;
   uword stack_upper = 0;
   isolate->GetStackBounds(&stack_lower, &stack_upper);
   if ((stack_lower == 0) || (stack_upper == 0)) {
     stack_lower = 0;
     stack_upper = 0;
   }
   ProfilerSampleStackWalker stackWalker(sample, stack_lower, stack_upper,
                                         state.pc, state.fp, state.sp);
-  stackWalker.walk(isolate->heap());
+  stackWalker.walk(isolate->heap(), isolate->vm_tag());
 }
 
 
 }  // namespace dart