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);
 
+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++) {
+      CodeRegionTrieNode* child = (*children_)[i];
+      if (child->code_region_index() == child_code_region_index) {
+        return child;
+      }
+      if (child->code_region_index() > child_code_region_index) {

[turnidge, 2014/03/17 21:19:31]

Just to make sure I understand -- GetChild relies on the children being sorted
by region index but later after we call RecursiveSort they will be sorted by
count.  Do we want to check that children aren't added after RecursiveSort has
been called?

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

You understand correctly. I've added comments about the restrictions on calling
order.

+        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) {
+    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_;
+  }
+
+ 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));
+    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();

[turnidge, 2014/03/17 21:19:31]

Maybe rename RecursiveSort to SortByCount?

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

Done.

+      }
+      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