gprofng/src/PathTree.cc

   1 /* Copyright (C) 2021 Free Software Foundation, Inc.
   2    Contributed by Oracle.
   3
   4    This file is part of GNU Binutils.
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software
  18    Foundation, 51 Franklin Street - Fifth Floor, Boston,
  19    MA 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24
  25 #include "util.h"
  26 #include "DefaultMap.h"
  27 #include "CacheMap.h"
  28
  29 #include "DbeSession.h"
  30 #include "Application.h"
  31 #include "CallStack.h"
  32 #include "Emsg.h"
  33 #include "Experiment.h"
  34 #include "Expression.h"
  35 #include "Function.h"
  36 #include "Histable.h"
  37 #include "IndexObject.h"
  38 #include "MetricList.h"
  39 #include "Module.h"
  40 #include "DbeView.h"
  41 #include "Metric.h"
  42 #include "PathTree.h"
  43 #include "LoadObject.h"
  44 #include "Sample.h"
  45 #include "StringBuilder.h"
  46 #include "Table.h"
  47
  48 // Define counts, rate for error warnings for statistical profiles
  49 #define MIN_PROF_CNT    100
  50 #define MAX_PROF_RATE   1000.
  51
  52 #define NUM_DESCENDANTS(nd) ((nd)->descendants ? (nd)->descendants->size() : 0)
  53 #define IS_LEAF(nd)         ((nd)->descendants == NULL)
  54
  55 #ifdef DEBUG
  56 #define DBG(__func) __func
  57 #else
  58 #define DBG(__func)
  59 #endif
  60
  61 void
  62 PathTree::construct (DbeView *_dbev, int _indxtype, PathTreeType _pathTreeType)
  63 {
  64   dbev = _dbev;
  65   indxtype = _indxtype;
  66   pathTreeType = _pathTreeType;
  67   status = 0;
  68   nchunks = 0;
  69   chunks = NULL;
  70   nodes = 1; // don't use node 0
  71   nslots = 0;
  72   slots = NULL;
  73   root_idx = 0;
  74   root = NULL;
  75   depth = 1;
  76   dnodes = 0;
  77   phaseIdx = -1;
  78   nexps = 0;
  79   total_obj = NULL;
  80   indx_expr = NULL;
  81   statsq = NULL;
  82   warningq = NULL;
  83   cancel_ok = 1;
  84   ptree_internal = NULL;
  85   ftree_internal = NULL;
  86   ftree_needs_update = false;
  87   depth_map = NULL;
  88   init ();
  89 }
  90
  91 PathTree::~PathTree ()
  92 {
  93   fini ();
  94   for (long i = 0; i < nchunks; i++)
  95     delete[] chunks[i];
  96   delete[] chunks;
  97 }
  98
  99 void
 100 PathTree::init ()
 101 {
 102   fn_map = new DefaultMap<Function*, NodeIdx>;
 103   stack_prop = PROP_NONE;
 104   desc_htable_size = 511;
 105   desc_htable_nelem = 0;
 106   descHT = new hash_node_t*[desc_htable_size];
 107   for (int i = 0; i < desc_htable_size; i++)
 108     descHT[i] = NULL;
 109   pathMap = new CacheMap<uint64_t, NodeIdx>;
 110   statsq = new Emsgqueue (NTXT ("statsq"));
 111   warningq = new Emsgqueue (NTXT ("warningq"));
 112   if (indxtype < 0)
 113     {
 114       Function *ftotal = dbeSession->get_Total_Function ();
 115       if (pathTreeType == PATHTREE_INTERNAL_FUNCTREE)
 116         total_obj = ftotal;
 117       else
 118         total_obj = ftotal->find_dbeinstr (0, 0);
 119       VMode view_mode = dbev->get_view_mode ();
 120       if (view_mode == VMODE_MACHINE)
 121         stack_prop = PROP_MSTACK;
 122       else if (view_mode == VMODE_EXPERT)
 123         stack_prop = PROP_XSTACK;
 124       else if (view_mode == VMODE_USER)
 125         {
 126           stack_prop = PROP_USTACK;
 127           if (dbeSession->is_omp_available ()
 128               && pathTreeType == PATHTREE_INTERNAL_OMP)
 129             stack_prop = PROP_XSTACK;
 130         }
 131     }
 132   else
 133     {
 134       total_obj = new IndexObject (indxtype, (uint64_t) - 2);
 135       total_obj->set_name (dbe_strdup (NTXT ("<Total>")));
 136       char *idxname = dbeSession->getIndexSpaceName (indxtype);
 137       if (streq (idxname, NTXT ("OMP_preg")))
 138         stack_prop = PROP_CPRID;
 139       else if (streq (idxname, NTXT ("OMP_task")))
 140         stack_prop = PROP_TSKID;
 141       else
 142         indx_expr = dbeSession->getIndexSpaceExpr (indxtype);
 143     }
 144   root_idx = new_Node (0, total_obj, false);
 145   root = NODE_IDX (root_idx);
 146 }
 147
 148 void
 149 PathTree::fini ()
 150 {
 151   // For each node free its descendants vector
 152   // and reset the node list of its function
 153   for (long i = 1; i < nodes; i++)
 154     {
 155       Node *node = NODE_IDX (i);
 156       if (node->descendants)
 157         delete node->descendants;
 158     }
 159   nodes = 1; // don't use node 0
 160
 161   for (int i = 0; i < nslots; i++)
 162     {
 163       int **tmp = slots[i].mvals;
 164       for (long j = 0; j < nchunks; j++)
 165         delete[] tmp[j];
 166       delete[] tmp;
 167     }
 168   delete[] slots;
 169   slots = NULL;
 170   nslots = 0;
 171   delete fn_map;
 172   fn_map = NULL;
 173   delete pathMap;
 174   pathMap = NULL;
 175   destroy (depth_map);
 176   depth_map = NULL;
 177   if (indxtype >= 0)
 178     delete total_obj;
 179
 180   for (int i = 0; i < desc_htable_size; i++)
 181     {
 182       hash_node_t *p = descHT[i];
 183       while (p)
 184         {
 185           hash_node_t *p1 = p;
 186           p = p->next;
 187           delete p1;
 188         }
 189     }
 190   delete[] descHT;
 191   delete statsq;
 192   delete warningq;
 193   depth = 1;
 194   dnodes = 0;
 195   phaseIdx = -1;
 196   nexps = 0;
 197   status = 0;
 198 }
 199
 200 PtreePhaseStatus
 201 PathTree::reset ()
 202 {
 203   if (pathTreeType == PATHTREE_INTERNAL_FUNCTREE)
 204     return NORMAL; // never process reset for ftree_internal.
 205
 206   if (dbeSession->is_omp_available () && dbev->get_view_mode () == VMODE_USER
 207       && pathTreeType == PATHTREE_MAIN && ptree_internal == NULL)
 208     ptree_internal = new PathTree (dbev, indxtype, PATHTREE_INTERNAL_OMP);
 209
 210   if (phaseIdx != dbev->getPhaseIdx ())
 211     {
 212       fini ();
 213       init ();
 214       phaseIdx = dbev->getPhaseIdx ();
 215       ftree_needs_update = true;
 216     }
 217   for (; nexps < dbeSession->nexps (); nexps++)
 218     {
 219       ftree_needs_update = true;
 220       if (add_experiment (nexps) == CANCELED)
 221         return CANCELED;
 222     }
 223
 224   // LIBRARY_VISIBILITY
 225   if (dbev->isNewViewMode ())
 226     dbev->resetNewViewMode ();
 227   if (dbev->isShowHideChanged ())
 228     dbev->resetShowHideChanged ();
 229   return NORMAL;
 230 }
 231
 232 int
 233 PathTree::allocate_slot (int id, ValueTag vtype)
 234 {
 235
 236   int i;
 237   int slot_idx = find_slot (id);
 238   if (slot_idx >= 0)
 239     {
 240       DBG (assert (slots[slot_idx].vtype == vtype));
 241       return slot_idx;
 242     }
 243   slot_idx = nslots++;
 244
 245   Slot *old_slots = slots;
 246   slots = new Slot[nslots];
 247   for (i = 0; i < slot_idx; i++)
 248     slots[i] = old_slots[i];
 249   delete[] old_slots;
 250
 251   slots[slot_idx].id = id;
 252   slots[slot_idx].vtype = vtype;
 253   int **ip = new int*[nchunks];
 254   for (i = 0; i < nchunks; i++)
 255     ip[i] = NULL;
 256   slots[slot_idx].mvals = ip;
 257
 258   return slot_idx;
 259 }
 260
 261 void
 262 PathTree::allocate_slots (Slot *new_slots, int new_nslots)
 263 {
 264   // duplicates new_slots
 265
 266   // if previously had more slots than currently requested, delete the data from those slots.
 267   for (int i = new_nslots; i < nslots; i++)
 268     {
 269       int **tmp = slots[i].mvals;
 270       for (long j = 0; j < nchunks; j++)
 271         delete tmp[j];
 272       delete tmp;
 273     }
 274   if (new_nslots == 0)
 275     {
 276       nslots = new_nslots;
 277       delete[] slots;
 278       slots = NULL;
 279       return;
 280     }
 281
 282   Slot *old_slots = slots;
 283   slots = new Slot[new_nslots];
 284   for (int i = 0; i < new_nslots; i++)
 285     {
 286       slots[i] = new_slots[i]; // pick up id and vtype
 287       if (i < nslots)
 288         slots[i].mvals = old_slots[i].mvals;
 289       else
 290         {
 291           if (nchunks == 0)
 292             slots[i].mvals = NULL;
 293           else
 294             {
 295               int **ip = new int*[nchunks];
 296               for (long j = 0; j < nchunks; j++)
 297                 ip[j] = NULL;
 298               slots[i].mvals = ip;
 299             }
 300         }
 301     }
 302   nslots = new_nslots;
 303   delete old_slots;
 304 }
 305
 306 int
 307 PathTree::find_slot (int id)
 308 {
 309   for (int i = 0; i < nslots; i++)
 310     if (slots[i].id == id)
 311       return i;
 312   return -1;
 313 }
 314
 315 PathTree::NodeIdx
 316 PathTree::new_Node (NodeIdx anc, Histable *instr, bool leaf)
 317 {
 318   if (nodes >= nchunks * CHUNKSZ)
 319     {
 320       long idx = nchunks++;
 321
 322       // Reallocate Node chunk array
 323       Node **old_chunks = chunks;
 324       chunks = new Node*[nchunks];
 325       for (long k = 0; k < idx; k++)
 326         chunks[k] = old_chunks[k];
 327       delete[] old_chunks;
 328
 329       // Reallocate metric value chunk arrays.
 330       for (int i = 0; i < nslots; i++)
 331         {
 332           int **mvals = new int*[nchunks];
 333           for (long k = 0; k < idx; k++)
 334             {
 335               mvals[k] = slots[i].mvals[k];
 336             }
 337           delete[] slots[i].mvals;
 338           slots[i].mvals = mvals;
 339           slots[i].mvals[idx] = NULL;
 340         }
 341
 342       // Allocate new chunk for nodes.
 343       // Note that we don't need to allocate new chunks
 344       // for metric values at this point as we rely on
 345       // lazy allocation.
 346       //
 347       allocate_chunk (chunks, idx);
 348     }
 349   NodeIdx node_idx = nodes++;
 350   Node *node = NODE_IDX (node_idx);
 351   node->ancestor = anc;
 352   node->descendants = leaf ? (Vector<NodeIdx>*)NULL : new Vector<NodeIdx>(2);
 353   node->instr = instr;
 354   Function *func = (Function*) (instr->convertto (Histable::FUNCTION));
 355   node->funclist = fn_map->get (func);
 356   fn_map->put (func, node_idx);
 357   return node_idx;
 358 }
 359
 360 PathTree::NodeIdx
 361 PathTree::find_path (Experiment *exp, DataView *dview, long recIdx)
 362 {
 363   if (indx_expr != NULL)
 364     {
 365       Expression::Context ctx (dbev, exp, dview, recIdx);
 366       uint64_t idx = indx_expr->eval (&ctx);
 367       Histable *cur_obj = dbeSession->createIndexObject (indxtype, idx);
 368       cur_obj->set_name_from_context (&ctx);
 369       NodeIdx dsc_idx = find_in_desc_htable (root_idx, cur_obj, true);
 370       depth = 2;
 371       return dsc_idx;
 372     }
 373
 374   bool showAll = dbev->isShowAll ();
 375   int t_stack_prop = stack_prop;
 376   void *stackId = dview->getObjValue (t_stack_prop, recIdx);
 377   NodeIdx node_idx;
 378   if (stackId != NULL)
 379     {
 380       // pathMap does not work with NULL key
 381       node_idx = pathMap->get ((uint64_t) stackId);
 382       if (node_idx != 0)
 383         return node_idx;
 384     }
 385   Vector<Histable*> *stack = (Vector<Histable*>*)CallStack::getStackPCs (stackId, !showAll);
 386   int stack_size = stack->size ();
 387   if (stack_size == 0)
 388     return root_idx;
 389
 390   node_idx = root_idx;
 391   int thisdepth = 1;
 392
 393   for (int i = stack_size - 1; i >= 0; i--)
 394     {
 395       bool leaf = (i == 0);
 396       Histable *cur_addr = stack->fetch (i);
 397
 398       // bail out of loop if load object API-only is set
 399       // and this is not the top frame
 400       // This is now done in HSTACK if hide is set
 401
 402       Function *func = (Function*) cur_addr->convertto (Histable::FUNCTION);
 403       if (func != NULL)
 404         {
 405           Module *mod = func->module;
 406           LoadObject *lo = mod->loadobject;
 407           int segx = lo->seg_idx;
 408           if (showAll && dbev->get_lo_expand (segx) == LIBEX_API
 409               && i != stack_size - 1)
 410             leaf = true;
 411         }
 412
 413       NodeIdx dsc_idx = find_desc_node (node_idx, cur_addr, leaf);
 414       thisdepth++;
 415       node_idx = dsc_idx;
 416
 417       // LIBEX_API processing might have set leaf to true
 418       if (leaf)
 419         break;
 420     }
 421   if (thisdepth > depth)
 422     depth = thisdepth;
 423   delete stack;
 424   pathMap->put ((uint64_t) stackId, node_idx);
 425   return node_idx;
 426 }
 427
 428 static int
 429 desc_node_comp (const void *s1, const void *s2, const void *ptree)
 430 {
 431   PathTree::NodeIdx t1, t2;
 432   t1 = *(PathTree::NodeIdx *)s1;
 433   t2 = *(PathTree::NodeIdx *)s2;
 434   PathTree* Ptree = (PathTree *) ptree;
 435   PathTree::Node *n1 = Ptree->NODE_IDX (t1);
 436   PathTree::Node *n2 = Ptree->NODE_IDX (t2);
 437   Histable *d1 = n1->instr;
 438   Histable *d2 = n2->instr;
 439   if (d1->id < d2->id)
 440     return -1;
 441   else if (d1->id > d2->id)
 442     return +1;
 443   else
 444     return 0;
 445 }
 446
 447 PathTree::NodeIdx
 448 PathTree::find_in_desc_htable (NodeIdx node_idx, Histable *instr, bool leaf)
 449 {
 450   unsigned int hash_code = (unsigned int) instr->id % desc_htable_size;
 451   Node *node = NODE_IDX (node_idx);
 452   hash_node_t *p = NULL;
 453   for (p = descHT[hash_code]; p; p = p->next)
 454     {
 455       Node *dsc = NODE_IDX (p->nd);
 456       Histable *dinstr = dsc->instr;
 457       if (dinstr->id == instr->id && leaf == IS_LEAF (dsc))
 458         return p->nd;
 459     }
 460   // Not found
 461   NodeIdx dsc_idx = new_Node (node_idx, instr, leaf);
 462   node->descendants->append (dsc_idx);
 463   p = new hash_node_t ();
 464   p->nd = dsc_idx;
 465   p->next = descHT[hash_code];
 466   descHT[hash_code] = p;
 467   desc_htable_nelem++;
 468
 469   // time to resize
 470   if (desc_htable_nelem == desc_htable_size)
 471     {
 472       int old_htable_size = desc_htable_size;
 473       desc_htable_size = old_htable_size * 2 + 1;
 474       hash_node_t **old_htable = descHT;
 475       descHT = new hash_node_t*[desc_htable_size];
 476       for (int i = 0; i < desc_htable_size; i++)
 477         descHT[i] = NULL;
 478
 479       for (int i = 0; i < old_htable_size; i++)
 480         if (old_htable[i] != NULL)
 481           {
 482             hash_node *old_p;
 483             hash_node_t *hash_p = old_htable[i];
 484             while (hash_p != NULL)
 485               {
 486                 hash_node_t *new_p = new hash_node_t ();
 487                 new_p->nd = hash_p->nd;
 488                 Node *dnode = NODE_IDX (hash_p->nd);
 489                 Histable *dnode_instr = dnode->instr;
 490                 hash_code = (unsigned int) dnode_instr->id % desc_htable_size;
 491                 new_p->next = descHT[hash_code];
 492                 descHT[hash_code] = new_p;
 493                 old_p = hash_p;
 494                 hash_p = hash_p->next;
 495                 delete old_p;
 496               }
 497           }
 498       delete[] old_htable;
 499     }
 500   return dsc_idx;
 501 }
 502
 503 PathTree::NodeIdx
 504 PathTree::find_desc_node (NodeIdx node_idx, Histable *instr, bool leaf)
 505 {
 506   // Binary search. All nodes are ordered by Histable::id.
 507
 508   // We have a special case when two nodes with the same
 509   //    id value may co-exist: one representing a leaf node and
 510   //    another one representing a call site.
 511   Node *node = NODE_IDX (node_idx);
 512   int left = 0;
 513   int right = NUM_DESCENDANTS (node) - 1;
 514   while (left <= right)
 515     {
 516       int index = (left + right) / 2;
 517       NodeIdx dsc_idx = node->descendants->fetch (index);
 518       Node *dsc = NODE_IDX (dsc_idx);
 519       Histable *dinstr = dsc->instr;
 520       if (instr->id < dinstr->id)
 521         right = index - 1;
 522       else if (instr->id > dinstr->id)
 523         left = index + 1;
 524       else if (leaf == IS_LEAF (dsc))
 525         return dsc_idx;
 526       else if (leaf)
 527         right = index - 1;
 528       else
 529         left = index + 1;
 530     }
 531
 532   // None was found. Create one.
 533   NodeIdx dsc_idx = new_Node (node_idx, instr, leaf);
 534   node->descendants->insert (left, dsc_idx);
 535   return dsc_idx;
 536 }
 537
 538 PtreePhaseStatus
 539 PathTree::process_packets (Experiment *exp, DataView *packets, int data_type)
 540 {
 541   Expression::Context ctx (dbev, exp);
 542   char *progress_bar_msg = NULL;
 543   int progress_bar_percent = -1;
 544
 545   Vector<BaseMetric*> *mlist = dbev->get_all_reg_metrics ();
 546   Vector<BaseMetric*> mlist2;
 547   StringBuilder stb;
 548   for (int midx = 0, mlist_sz = mlist->size (); midx < mlist_sz; ++midx)
 549     {
 550       BaseMetric *mtr = mlist->fetch (midx);
 551       if (mtr->get_packet_type () == data_type &&
 552           (mtr->get_expr () == NULL || mtr->get_expr ()->passes (&ctx)))
 553         {
 554           Hwcentry *hwc = mtr->get_hw_ctr ();
 555           if (hwc)
 556             {
 557               stb.setLength (0);
 558               // XXX this should be done at metric registration
 559               Collection_params *col_params = exp->get_params ();
 560               for (int i = 0; i < MAX_HWCOUNT; i++)
 561                 {
 562                   // We may have duplicate counters in col_params,
 563                   // check for all (see 5081284).
 564                   if (dbe_strcmp (hwc->name, col_params->hw_aux_name[i]) == 0)
 565                     {
 566                       if (stb.length () != 0)
 567                         stb.append (NTXT ("||"));
 568                       stb.append (NTXT ("HWCTAG=="));
 569                       stb.append (i);
 570                     }
 571                 }
 572               if (stb.length () == 0)
 573                 continue;
 574               stb.append (NTXT ("&& ((HWCINT & "));
 575               stb.append ((long long) HWCVAL_ERR_FLAG);
 576               stb.append (NTXT (")==0)"));
 577               char *s = stb.toString ();
 578               mtr->set_cond_spec (s);
 579               free (s);
 580             }
 581           ValueTag vtype = mtr->get_vtype ();
 582           switch (vtype)
 583             {
 584             case VT_INT:
 585             case VT_ULLONG:
 586             case VT_LLONG:
 587               break; // nothing to do
 588             default:
 589               vtype = VT_ULLONG; // ym: not sure when this would happen
 590               break;
 591             }
 592           allocate_slot (mtr->get_id (), vtype);
 593           mlist2.append (mtr);
 594         }
 595     }
 596
 597   Slot **mslots = new Slot*[mlist2.size ()];
 598   for (int midx = 0, mlist_sz = mlist2.size (); midx < mlist_sz; ++midx)
 599     {
 600       BaseMetric *mtr = mlist2.fetch (midx);
 601       int id = mtr->get_id ();
 602       int slot_ind = find_slot (id);
 603       mslots[midx] = SLOT_IDX (slot_ind);
 604     }
 605
 606   for (long i = 0, packets_sz = packets->getSize (); i < packets_sz; ++i)
 607     {
 608       if (dbeSession->is_interactive ())
 609         {
 610           if (NULL == progress_bar_msg)
 611             progress_bar_msg = dbe_sprintf (GTXT ("Processing Experiment: %s"),
 612                                           get_basename (exp->get_expt_name ()));
 613           int val = (int) (100 * i / packets_sz);
 614           if (val > progress_bar_percent)
 615             {
 616               progress_bar_percent += 10;
 617               if (theApplication->set_progress (val, progress_bar_msg)
 618                   && cancel_ok)
 619                 {
 620                   delete[] mslots;
 621                   return CANCELED;
 622                 }
 623             }
 624         }
 625
 626       NodeIdx path_idx = 0;
 627       ctx.put (packets, i);
 628
 629       for (int midx = 0, mlist_sz = mlist2.size (); midx < mlist_sz; ++midx)
 630         {
 631           BaseMetric *mtr = mlist2.fetch (midx);
 632           if (mtr->get_cond () != NULL && !mtr->get_cond ()->passes (&ctx))
 633             continue;
 634
 635           int64_t mval = mtr->get_val ()->eval (&ctx);
 636           if (mval == 0)
 637             continue;
 638           if (path_idx == 0)
 639             path_idx = find_path (exp, packets, i);
 640           NodeIdx node_idx = path_idx;
 641           Slot *mslot = mslots[midx];
 642           while (node_idx)
 643             {
 644               INCREMENT_METRIC (mslot, node_idx, mval);
 645               node_idx = NODE_IDX (node_idx)->ancestor;
 646             }
 647         }
 648     }
 649   if (dbeSession->is_interactive ())
 650     free (progress_bar_msg);
 651   delete[] mslots;
 652   if (indx_expr != NULL)
 653     root->descendants->sort ((CompareFunc) desc_node_comp, this);
 654   return NORMAL;
 655 }
 656
 657 DataView *
 658 PathTree::get_filtered_events (int exp_index, int data_type)
 659 {
 660   if (indx_expr != NULL)
 661     {
 662       IndexObjType_t *indexObj = dbeSession->getIndexSpace (indxtype);
 663       if (indexObj->memObj && data_type != DATA_HWC)
 664         return NULL;
 665     }
 666   return dbev->get_filtered_events (exp_index, data_type);
 667 }
 668
 669 PtreePhaseStatus
 670 PathTree::add_experiment (int exp_index)
 671 {
 672   StringBuilder sb;
 673   char *expt_name;
 674   char *base_name;
 675   Emsg *m;
 676   Experiment *experiment = dbeSession->get_exp (exp_index);
 677   if (experiment->broken != 0)
 678     return NORMAL;
 679   status = 0;
 680   expt_name = experiment->get_expt_name ();
 681   base_name = get_basename (expt_name);
 682
 683   hrtime_t starttime = gethrtime ();
 684   hrtime_t startvtime = gethrvtime ();
 685
 686   // Experiment::getEndTime was initially implemented as
 687   // returning exp->last_event. To preserve the semantics
 688   // new Experiment::getLastEvent() is used here.
 689   hrtime_t tot_time = experiment->getLastEvent () - experiment->getStartTime ();
 690
 691   if (!dbev->isShowAll () && (dbev->isShowHideChanged ()
 692                               || dbev->isNewViewMode ()))
 693     experiment->resetShowHideStack ();
 694
 695   // To report experiment index to the user,
 696   // start numeration from 1, not 0
 697   sb.sprintf (GTXT ("PathTree processing experiment %d (`%s'); duration %lld.%06lld"),
 698               exp_index + 1, base_name,
 699               tot_time / NANOSEC, (tot_time % NANOSEC / 1000));
 700   m = new Emsg (CMSG_COMMENT, sb);
 701   statsq->append (m);
 702
 703   DataView *prof_packet = get_filtered_events (exp_index, DATA_CLOCK);
 704   if (prof_packet && prof_packet->getSize () > 0)
 705     {
 706       if (process_packets (experiment, prof_packet, DATA_CLOCK) == CANCELED)
 707         return CANCELED;
 708       long clock_cnt = prof_packet->getSize ();
 709       double clock_rate;
 710       if (tot_time != 0)
 711         clock_rate = (double) clock_cnt / (double) tot_time * (double) NANOSEC;
 712       else
 713         clock_rate = (double) 0.;
 714       if (experiment->timelineavail)
 715         sb.sprintf (GTXT ("  Processed %ld clock-profile events (%3.2f/sec.)"),
 716                     clock_cnt, clock_rate);
 717       else
 718         sb.sprintf (GTXT ("  Processed %ld clock-profile events"), clock_cnt);
 719       m = new Emsg (CMSG_COMMENT, sb);
 720       statsq->append (m);
 721
 722       // check for statistical validity
 723       if ((experiment->timelineavail == true)
 724            && !dbev->get_filter_active () && (clock_cnt < MIN_PROF_CNT))
 725         {
 726           sb.sprintf (GTXT ("WARNING: too few clock-profile events (%ld) in experiment %d (`%s') for statistical validity"),
 727                       clock_cnt, exp_index + 1, base_name);
 728           m = new Emsg (CMSG_COMMENT, sb);
 729           statsq->append (m);
 730         }
 731     }
 732
 733   DataView *sync_packet = get_filtered_events (exp_index, DATA_SYNCH);
 734   if (sync_packet && sync_packet->getSize () > 0)
 735     {
 736       if (process_packets (experiment, sync_packet, DATA_SYNCH) == CANCELED)
 737         return CANCELED;
 738       long sync_cnt = sync_packet->getSize ();
 739       sb.sprintf (GTXT ("  Processed %ld synctrace events"), sync_cnt);
 740       m = new Emsg (CMSG_COMMENT, sb);
 741       statsq->append (m);
 742     }
 743
 744   DataView *iotrace_packet = get_filtered_events (exp_index, DATA_IOTRACE);
 745   if (iotrace_packet && iotrace_packet->getSize () > 0)
 746     {
 747       if (process_packets (experiment, iotrace_packet, DATA_IOTRACE) == CANCELED)
 748         return CANCELED;
 749       long iotrace_cnt = iotrace_packet->getSize ();
 750       sb.sprintf (GTXT ("  Processed %ld IO trace events"), iotrace_cnt);
 751       m = new Emsg (CMSG_COMMENT, sb);
 752       statsq->append (m);
 753     }
 754
 755   DataView *hwc_packet = get_filtered_events (exp_index, DATA_HWC);
 756   if (hwc_packet && hwc_packet->getSize () > 0)
 757     {
 758       if (process_packets (experiment, hwc_packet, DATA_HWC) == CANCELED)
 759         return CANCELED;
 760       long hwc_cnt = hwc_packet->getSize ();
 761       double hwc_rate = (double) hwc_cnt / (double) tot_time * (double) NANOSEC;
 762       if (experiment->timelineavail)
 763         sb.sprintf (GTXT ("  Processed %ld hwc-profile events (%3.2f/sec.)"),
 764                     hwc_cnt, hwc_rate);
 765       else
 766         sb.sprintf (GTXT ("  Processed %ld hwc-profile events"), hwc_cnt);
 767       m = new Emsg (CMSG_COMMENT, sb);
 768       statsq->append (m);
 769
 770       // check for statistical validity
 771       if (experiment->timelineavail && !dbev->get_filter_active () && (hwc_cnt < MIN_PROF_CNT))
 772         {
 773           sb.sprintf (GTXT ("WARNING: too few HW counter profile events (%ld) in experiment %d (`%s') for statistical validity"),
 774                       hwc_cnt, exp_index + 1, base_name);
 775           m = new Emsg (CMSG_COMMENT, sb);
 776           statsq->append (m);
 777         }
 778     }
 779
 780   DataView *heap_packet = get_filtered_events (exp_index, DATA_HEAP);
 781   if (heap_packet && heap_packet->getSize () > 0)
 782     {
 783       if (process_packets (experiment, heap_packet, DATA_HEAP) == CANCELED)
 784         return CANCELED;
 785       long heap_cnt = heap_packet->getSize ();
 786       sb.sprintf (GTXT ("  Processed %ld heaptrace events"), heap_cnt);
 787       m = new Emsg (CMSG_COMMENT, sb);
 788       statsq->append (m);
 789     }
 790
 791   DataView *race_packet = get_filtered_events (exp_index, DATA_RACE);
 792   if (race_packet && race_packet->getSize () > 0)
 793     {
 794       if (process_packets (experiment, race_packet, DATA_RACE) == CANCELED)
 795         return CANCELED;
 796       long race_cnt = race_packet->getSize ();
 797       sb.sprintf (GTXT ("  Processed %ld race access events"), race_cnt);
 798       m = new Emsg (CMSG_COMMENT, sb);
 799       statsq->append (m);
 800     }
 801
 802   DataView *deadlock_packet = get_filtered_events (exp_index, DATA_DLCK);
 803   if (deadlock_packet && deadlock_packet->getSize () > 0)
 804     {
 805       if (process_packets (experiment, deadlock_packet, DATA_DLCK) == CANCELED)
 806         return CANCELED;
 807       long race_cnt = deadlock_packet->getSize ();
 808       sb.sprintf (GTXT ("  Processed %ld race access events"), race_cnt);
 809       m = new Emsg (CMSG_COMMENT, sb);
 810       statsq->append (m);
 811     }
 812
 813   hrtime_t pathtime = gethrtime () - starttime;
 814   hrtime_t pathvtime = gethrvtime () - startvtime;
 815   sb.sprintf (GTXT ("PathTree time = %lld.%06lld CPU-time %lld.%06lld\n"),
 816               pathtime / NANOSEC, (pathtime % NANOSEC) / 1000,
 817               pathvtime / NANOSEC, (pathvtime % NANOSEC) / 1000);
 818   m = new Emsg (CMSG_COMMENT, sb);
 819   statsq->append (m);
 820   return NORMAL;
 821 }
 822
 823 Hist_data *
 824 PathTree::compute_metrics (MetricList *mlist, Histable::Type type,
 825                            Hist_data::Mode mode, Vector<Histable*> *objs,
 826                            Histable *context, Vector<Histable*> *sel_objs,
 827                            PtreeComputeOption computeOpt)
 828 {
 829   VMode view_mode = dbev->get_view_mode ();
 830
 831   // For displaying disassembly correctly in user mode with openmp
 832   if (ptree_internal != NULL &&
 833       (view_mode == VMODE_EXPERT ||
 834        (view_mode == VMODE_USER && (type == Histable::INSTR
 835                                     || (dbev->isOmpDisMode ()
 836                                         && type == Histable::FUNCTION
 837                                         && mode == Hist_data::CALLEES
 838                                         && computeOpt == COMPUTEOPT_OMP_CALLEE))
 839                                     )))
 840     return ptree_internal->compute_metrics (mlist, type, mode, objs, context,
 841                                             sel_objs);
 842
 843   PtreePhaseStatus resetStatus = reset ();
 844
 845   hist_data = new Hist_data (mlist, type, mode);
 846   int nmetrics = mlist->get_items ()->size ();
 847   int sort_ind = -1;
 848   Hist_data::HistItem *hi;
 849   int index;
 850
 851   if (status != 0 || resetStatus == CANCELED)
 852     return hist_data;
 853
 854   hist_data->set_status (Hist_data::SUCCESS);
 855   if (dbeSession->is_interactive () && mode != Hist_data::CALLEES)
 856     theApplication->set_progress (0, GTXT ("Constructing Metrics"));
 857
 858   xlate = new int[nmetrics];
 859   for (int mind = 0; mind < nmetrics; mind++)
 860     {
 861       Metric *mtr = mlist->get (mind);
 862       xlate[mind] = find_slot (mtr->get_id ());
 863     }
 864
 865   // Compute dynamic metrics
 866   obj_list = new Histable*[depth];
 867   if ((type == Histable::LINE || type == Histable::INSTR)
 868       && mode == Hist_data::CALLERS)
 869     node_list = new Node*[depth];
 870   percent = 0;
 871   ndone = 0;
 872   if (mode == Hist_data::MODL)
 873     {
 874       Histable *obj = objs && objs->size () > 0 ? objs->fetch (0) : NULL;
 875       if (obj != NULL)
 876         {
 877           switch (obj->get_type ())
 878             {
 879             case Histable::FUNCTION:
 880               {
 881                 Vector<Function*> *funclist = new Vector<Function*>;
 882                 funclist->append ((Function*) obj);
 883                 get_metrics (funclist, context);
 884                 delete funclist;
 885                 break;
 886               }
 887             case Histable::MODULE:
 888               {
 889                 Vector<Histable*> *comparableModules = obj->get_comparable_objs ();
 890                 if (comparableModules != NULL)
 891                   {
 892                     Vector<Function*> *functions = new Vector<Function*>;
 893                     for (int i = 0; i < comparableModules->size (); i++)
 894                       {
 895                         Module *mod = (Module*) comparableModules->fetch (i);
 896                         if (mod)
 897                           {
 898                             bool found = false;
 899                             for (int i1 = 0; i1 < i; i1++)
 900                               {
 901                                 if (mod == comparableModules->fetch (i1))
 902                                   {
 903                                     found = true;
 904                                     break;
 905                                   }
 906                               }
 907                             if (!found)
 908                               functions->addAll (mod->functions);
 909                           }
 910                       }
 911                     get_metrics (functions, context);
 912                     delete functions;
 913                   }
 914                 else
 915                   get_metrics (((Module*) obj)->functions, context);
 916                 break;
 917               }
 918             case Histable::SOURCEFILE:
 919               get_metrics (((SourceFile *) obj)->get_functions (), context);
 920               break;
 921             default:
 922               DBG (assert (0));
 923             }
 924         }
 925     }
 926   else if (mode == Hist_data::CALLERS)
 927     {
 928       if (objs && objs->size () > 0)
 929         get_clr_metrics (objs);
 930     }
 931   else if (mode == Hist_data::CALLEES)
 932     {
 933       if (objs && objs->size () > 0)
 934         get_cle_metrics (objs);
 935       else   // Special case: get root
 936         get_cle_metrics (NULL);
 937     }
 938   else if (mode == Hist_data::SELF)
 939     {
 940       if (objs->size () == 1)
 941         {
 942           Histable *obj = objs->fetch (0);
 943           if (obj != NULL)
 944             {
 945               if (obj->get_type () == Histable::LINE)
 946                 {
 947                   Vector<Function*> *funclist = new Vector<Function*>;
 948                   for (DbeLine *dl = (DbeLine*) obj->convertto (Histable::LINE);
 949                           dl; dl = dl->dbeline_func_next)
 950                     if (dl->func)
 951                       funclist->append (dl->func);
 952
 953                   get_self_metrics (obj, funclist, sel_objs);
 954                   delete funclist;
 955                 }
 956               else if (obj->get_type () == Histable::FUNCTION
 957                        || obj->get_type () == Histable::INSTR)
 958                 {
 959                   // Use shortcut for functions and oth.
 960                   if (context)
 961                     {
 962                       Vector<Function*> *funclist = NULL;
 963                       if (context->get_type () == Histable::MODULE)
 964                         funclist = ((Module*) context)->functions->copy ();
 965                       else
 966                         {
 967                           funclist = new Vector<Function*>;
 968                           funclist->append ((Function*) context);
 969                         }
 970                       get_self_metrics (obj, funclist, sel_objs);
 971                       delete funclist;
 972                     }
 973                   else
 974                     get_self_metrics (objs);
 975                 }
 976               else
 977                 get_self_metrics (objs);
 978             }
 979         }
 980       else
 981         get_self_metrics (objs);
 982     }
 983   else   // Hist_data::ALL
 984     get_metrics (root_idx, 0);
 985
 986   delete[] obj_list;
 987   if ((type == Histable::LINE || type == Histable::INSTR)
 988       && mode == Hist_data::CALLERS)
 989     delete[] node_list;
 990
 991   // Postprocess; find total
 992   for (long mind = 0, sz = mlist->get_items ()->size (); mind < sz; mind++)
 993     {
 994       Metric *mtr = mlist->get_items ()->get (mind);
 995       Metric::SubType subtype = mtr->get_subtype ();
 996       ValueTag vtype = mtr->get_vtype ();
 997       hist_data->total->value[mind].tag = vtype;
 998
 999       switch (vtype)
1000         {
1001           // ignoring the following cases (why?)
1002         case VT_SHORT:
1003         case VT_FLOAT:
1004         case VT_HRTIME:
1005         case VT_LABEL:
1006         case VT_ADDRESS:
1007         case VT_OFFSET:
1008           break;
1009
1010         case VT_INT:
1011           // Calculate total as the sum of all values in hist_data for
1012           // ATTRIBUTED metrics only. For all others, use root node values.
1013           //
1014           if ((mode == Hist_data::CALLERS || mode == Hist_data::CALLEES)
1015               && subtype == Metric::ATTRIBUTED)
1016             {
1017               hist_data->total->value[mind].i = 0;
1018               Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi)
1019               {
1020                 hist_data->total->value[mind].i += hi->value[mind].i;
1021               }
1022               if (mode == Hist_data::CALLEES)
1023                 hist_data->total->value[mind].i += hist_data->gprof_item->value[mind].i;
1024             }
1025           else if (xlate[mind] != -1)
1026             ASN_METRIC_VAL (hist_data->total->value[mind], slots[xlate[mind]],
1027                             root_idx);
1028           break;
1029
1030         case VT_LLONG:
1031           Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi)
1032           {
1033             hi->value[mind].tag = vtype;
1034           }
1035
1036           if ((mode == Hist_data::CALLERS || mode == Hist_data::CALLEES)
1037               && subtype == Metric::ATTRIBUTED)
1038             {
1039               hist_data->total->value[mind].ll = 0;
1040               Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi)
1041               {
1042                 hist_data->total->value[mind].ll += hi->value[mind].ll;
1043               }
1044               if (mode == Hist_data::CALLEES)
1045                 hist_data->total->value[mind].ll += hist_data->gprof_item->value[mind].ll;
1046             }
1047           else if (xlate[mind] != -1)
1048             ASN_METRIC_VAL (hist_data->total->value[mind], slots[xlate[mind]], root_idx);
1049           break;
1050
1051         case VT_ULLONG:
1052           Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi)
1053           {
1054             hi->value[mind].tag = vtype;
1055           }
1056           if ((mode == Hist_data::CALLERS || mode == Hist_data::CALLEES)
1057               && subtype == Metric::ATTRIBUTED)
1058             {
1059               hist_data->total->value[mind].ull = 0;
1060               Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi)
1061               {
1062                 hist_data->total->value[mind].ull += hi->value[mind].ull;
1063               }
1064               if (mode == Hist_data::CALLEES)
1065                 hist_data->total->value[mind].ull += hist_data->gprof_item->value[mind].ull;
1066             }
1067           else if (xlate[mind] != -1)
1068             ASN_METRIC_VAL (hist_data->total->value[mind], slots[xlate[mind]], root_idx);
1069           break;
1070
1071         case VT_DOUBLE:
1072           double prec = mtr->get_precision ();
1073           ValueTag vt = (xlate[mind] != -1) ? slots[xlate[mind]].vtype : VT_INT;
1074           Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi)
1075           {
1076             double val = (vt == VT_LLONG ? hi->value[mind].ll :
1077                           (vt == VT_ULLONG ? hi->value[mind].ull
1078                            : hi->value[mind].i));
1079             hi->value[mind].tag = vtype;
1080             hi->value[mind].d = val / prec;
1081           }
1082
1083           if ((mode == Hist_data::CALLERS || mode == Hist_data::CALLEES)
1084                && subtype == Metric::ATTRIBUTED)
1085             {
1086               hist_data->total->value[mind].d = 0.0;
1087               Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi)
1088               {
1089                 hist_data->total->value[mind].d += hi->value[mind].d;
1090               }
1091               if (mode == Hist_data::CALLEES)
1092                 hist_data->total->value[mind].d +=
1093                       (double) (vt == VT_LLONG ? hist_data->gprof_item->value[mind].ll :
1094                                 (vt == VT_ULLONG ? hist_data->gprof_item->value[mind].ull :
1095                                  hist_data->gprof_item->value[mind].i)) / prec;
1096             }
1097           else if (xlate[mind] != -1)
1098             {
1099               TValue& total = hist_data->total->value[mind];
1100               ASN_METRIC_VAL (total, slots[xlate[mind]], root_idx);
1101               double val = (vt == VT_LLONG ? total.ll :
1102                             (vt == VT_ULLONG ? total.ll : total.i));
1103               total.d = val / prec;
1104             }
1105           break;
1106         }
1107     }
1108   delete[] xlate;
1109
1110   // Determine by which metric to sort if any
1111   bool rev_sort = mlist->get_sort_rev ();
1112   for (long mind = 0, sz = mlist->get_items ()->size (); mind < sz; mind++)
1113     {
1114       Metric *mtr = mlist->get_items ()->get (mind);
1115       if (mlist->get_sort_ref_index () == mind)
1116         sort_ind = mind;
1117
1118       switch (mtr->get_type ())
1119         {
1120         case BaseMetric::SIZES:
1121           Vec_loop (Hist_data::HistItem *, hist_data->hist_items, index, hi)
1122           {
1123             Histable *h = mtr->get_comparable_obj (hi->obj);
1124             hi->value[mind].tag = VT_LLONG;
1125             hi->value[mind].ll = h ? h->get_size () : 0;
1126           }
1127           break;
1128         case BaseMetric::ADDRESS:
1129           Vec_loop (Hist_data::HistItem *, hist_data->hist_items, index, hi)
1130           {
1131             Histable *h = mtr->get_comparable_obj (hi->obj);
1132             hi->value[mind].tag = VT_ADDRESS;
1133             hi->value[mind].ll = h ? h->get_addr () : 0;
1134           }
1135           break;
1136         case BaseMetric::DERIVED:
1137           {
1138             Definition *def = mtr->get_definition ();
1139             long *map = def->get_map ();
1140             for (long i1 = 0, sz1 = hist_data->hist_items->size (); i1 < sz1; i1++)
1141               {
1142                 /* Hist_data::HistItem * */hi = hist_data->hist_items->get (i1);
1143                 hi->value[mind].tag = VT_DOUBLE;
1144                 hi->value[mind].d = def->eval (map, hi->value);
1145               }
1146             hist_data->total->value[mind].tag = VT_DOUBLE;
1147             hist_data->total->value[mind].d = def->eval (map, hist_data->total->value);
1148           }
1149           break;
1150         default:
1151           break;
1152         }
1153     }
1154
1155   hist_data->sort (sort_ind, rev_sort);
1156   hist_data->compute_minmax ();
1157   if (dbeSession->is_interactive () && mode != Hist_data::CALLERS)
1158     theApplication->set_progress (0, GTXT (""));
1159
1160 #if DEBUG_FTREE
1161   if (ftree_hist_data)
1162     {
1163       bool matches = ftree_debug_match_hist_data (hist_data, ftree_hist_data);
1164       if (!matches)
1165         assert (false);
1166       delete hist_data;
1167       hist_data = ftree_hist_data; // return the debug version
1168     }
1169 #endif
1170   return hist_data;
1171 }
1172
1173 #if DEBUG_FTREE
1174 bool
1175 PathTree::ftree_debug_match_hist_data (Hist_data *data /* ref */,
1176                                        Hist_data *data_tmp)
1177 {
1178   if (data->get_status () != Hist_data::SUCCESS)
1179     {
1180       DBG (assert (false));
1181       return false;
1182     }
1183   if (data == NULL && data != data_tmp)
1184     {
1185       DBG (assert (false));
1186       return false;
1187     }
1188
1189   MetricList *mlist;
1190   mlist = data->get_metric_list ();
1191   MetricList *mlist_tmp;
1192   mlist_tmp = data_tmp->get_metric_list ();
1193   if (mlist->size () != mlist_tmp->size ())
1194     {
1195       DBG (assert (false));
1196       return false;
1197     }
1198
1199   // Get table size: count visible metrics
1200   int nitems = data->size ();
1201   if (data->size () != data_tmp->size ())
1202     {
1203       DBG (assert (false));
1204       return false;
1205     }
1206
1207   for (int i = 0; i < nitems; ++i)
1208     {
1209       Hist_data::HistItem *item = data->fetch (i);
1210       Hist_data::HistItem *item_tmp = data_tmp->fetch (i);
1211       if (item->obj->id != item_tmp->obj->id)
1212         {
1213           DBG (assert (false));
1214           return false;
1215         }
1216     }
1217
1218   for (long i = 0, sz = mlist->size (); i < sz; i++)
1219     {
1220       long met_ind = i;
1221       Metric *mitem = mlist->get (i);
1222       Metric *mitem_tmp = mlist_tmp->get (i);
1223
1224       if (mitem->get_id () != mitem_tmp->get_id ())
1225         {
1226           DBG (assert (false));
1227           return false;
1228         }
1229       if (mitem->get_visbits () != mitem_tmp->get_visbits ())
1230         {
1231           DBG (assert (false));
1232           return false;
1233         }
1234       if (mitem->get_vtype () != mitem_tmp->get_vtype ())
1235         {
1236           DBG (assert (false));
1237           return false;
1238         }
1239
1240       if (!mitem->is_visible () && !mitem->is_tvisible ()
1241           && !mitem->is_pvisible ())
1242         continue;
1243       // table->append(dbeGetTableDataOneColumn(data, i));
1244       for (long row = 0, sz_row = data->size (); row < sz_row; row++)
1245         {
1246           Metric *m = mitem;
1247           TValue res;
1248           TValue res_tmp;
1249           TValue *v = data->get_value (&res, met_ind, row);
1250           TValue *v_tmp = data_tmp->get_value (&res_tmp, met_ind, row);
1251           if ((m->get_visbits () & VAL_RATIO) != 0)
1252             {
1253               if (v->tag != VT_LABEL)
1254                 {
1255                   if (v->to_double () != v_tmp->to_double ())
1256                     {
1257                       DBG (assert (false));
1258                       return false;
1259                     }
1260                 }
1261               continue;
1262             }
1263           switch (m->get_vtype ())
1264             {
1265             case VT_DOUBLE:
1266               {
1267                 double diff = v->d - v_tmp->d;
1268                 if (diff < 0) diff = -diff;
1269                 if (diff > 0.0001)
1270                   {
1271                     DBG (assert (false));
1272                     return false;
1273                   }
1274                 else
1275                   DBG (assert (true));
1276                 break;
1277               }
1278             case VT_INT:
1279               if (v->i != v_tmp->i)
1280                 {
1281                   DBG (assert (false));
1282                   return false;
1283                 }
1284               break;
1285             case VT_ULLONG:
1286             case VT_LLONG:
1287             case VT_ADDRESS:
1288               if (v->ll != v_tmp->ll)
1289                 {
1290                   DBG (assert (false));
1291                   return false;
1292                 }
1293               break;
1294
1295             case VT_LABEL:
1296               if (dbe_strcmp (v->l, v_tmp->l))
1297                 {
1298                   DBG (assert (false));
1299                   return false;
1300                 }
1301               break;
1302             default:
1303               DBG (assert (false));
1304               return false;
1305             }
1306         }
1307     }
1308   return true;
1309 }
1310 #endif
1311
1312 Histable *
1313 PathTree::get_hist_func_obj (Node *node)
1314 {
1315   LoadObject *lo;
1316   Function *func;
1317   func = (Function*) (node->instr->convertto (Histable::FUNCTION));
1318   // LIBRARY VISIBILITY
1319   lo = func->module->loadobject;
1320   if (dbev->get_lo_expand (lo->seg_idx) == LIBEX_HIDE)
1321     return lo->get_hide_function ();
1322   return get_compare_obj (func);
1323 }
1324
1325 Histable *
1326 PathTree::get_hist_obj (Node *node, Histable* context)
1327 {
1328   LoadObject *lo;
1329   Function *func;
1330   switch (hist_data->type)
1331     {
1332     case Histable::INSTR:
1333       if (hist_data->mode == Hist_data::MODL)
1334         {
1335           if (node->instr->get_type () != Histable::INSTR)
1336             return NULL;
1337         }
1338       else
1339         {
1340           // LIBRARY VISIBILITY
1341           func = (Function*) (node->instr->convertto (Histable::FUNCTION));
1342           lo = func->module->loadobject;
1343           if (dbev->get_lo_expand (lo->seg_idx) == LIBEX_HIDE)
1344             return lo->get_hide_function ();
1345         }
1346       return node->instr;
1347
1348     case Histable::LINE:
1349       if (hist_data->mode != Hist_data::MODL)
1350         {
1351           func = (Function*) (node->instr->convertto (Histable::FUNCTION));
1352           lo = func->module->loadobject;
1353           // LIBRARY VISIBILITY
1354           if (dbev->get_lo_expand (lo->seg_idx) == LIBEX_HIDE)
1355             return lo->get_hide_function ();
1356         }
1357       // For openmp user mode - the stack is already made with dbelines,
1358       // no need to convert it
1359       if (node->instr->get_type () == Histable::LINE)
1360         return node->instr;
1361       return node->instr->convertto (Histable::LINE, context);
1362
1363     case Histable::FUNCTION:
1364       if (pathTreeType == PATHTREE_INTERNAL_FUNCTREE && node->ancestor != 0)
1365         func = (Function*) node->instr;
1366       else
1367         func = (Function*) (node->instr->convertto (Histable::FUNCTION));
1368       lo = func->module->loadobject;
1369       // LIBRARY VISIBILITY
1370       if (dbev->get_lo_expand (lo->seg_idx) == LIBEX_HIDE)
1371         return lo->get_hide_function ();
1372       return get_compare_obj (func);
1373     case Histable::MODULE:
1374       func = (Function*) (node->instr->convertto (Histable::FUNCTION));
1375       return func->module;
1376     case Histable::LOADOBJECT:
1377       func = (Function*) (node->instr->convertto (Histable::FUNCTION));
1378       return func->module->loadobject;
1379     case Histable::INDEXOBJ:
1380     case Histable::MEMOBJ:
1381       return node->instr;
1382     default:
1383       DBG (assert (0));
1384     }
1385   return NULL;
1386 }
1387
1388 Histable *
1389 PathTree::get_compare_obj (Histable *obj)
1390 {
1391   if (obj && dbev->comparingExperiments ())
1392     obj = dbev->get_compare_obj (obj);
1393   return obj;
1394 }
1395
1396 void
1397 PathTree::get_metrics (NodeIdx node_idx, int dpth)
1398 {
1399   Node *node = NODE_IDX (node_idx);
1400   Histable *cur_obj = get_hist_obj (node);
1401   obj_list[dpth] = cur_obj;
1402
1403   // Check for recursion (inclusive metrics)
1404   int incl_ok = 1;
1405   for (int i = dpth - 1; i >= 0; i--)
1406     if (cur_obj == obj_list[i])
1407       {
1408         incl_ok = 0;
1409         break;
1410       }
1411
1412   // Check for leaf nodes (exclusive metrics)
1413   int excl_ok = 0;
1414   if (IS_LEAF (node) || node == NODE_IDX (root_idx))
1415     excl_ok = 1;
1416
1417   // We shouldn't eliminate empty subtrees here because
1418   // we create the list of hist items dynamically and want
1419   // one for each object in the tree.
1420   cur_obj = get_compare_obj (cur_obj);
1421   Hist_data::HistItem *hi = hist_data->append_hist_item (cur_obj);
1422   DBG (assert (hi != NULL));
1423
1424   MetricList *mlist = hist_data->get_metric_list ();
1425   for (long ind = 0, sz = mlist->size (); ind < sz; ind++)
1426     {
1427       if (xlate[ind] == -1)
1428         continue;
1429       Metric *mtr = mlist->get (ind);
1430       Metric::SubType subtype = mtr->get_subtype ();
1431       if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx))
1432         continue;
1433
1434       switch (subtype)
1435         {
1436         case Metric::INCLUSIVE:
1437           if (incl_ok && hi)
1438             ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
1439           break;
1440         case Metric::EXCLUSIVE:
1441           if (excl_ok && hi)
1442             ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
1443           break;
1444           // ignoring the following cases (why?)
1445         case Metric::STATIC:
1446         case Metric::ATTRIBUTED:
1447           break;
1448         case Metric::DATASPACE:
1449           if (hi)
1450             ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
1451           break;
1452         }
1453     }
1454
1455   if (dbeSession->is_interactive ())
1456     {
1457       ndone++;
1458       int new_percent = 95 * ndone / nodes;
1459       if (new_percent > percent)
1460         {
1461           percent = new_percent;
1462           theApplication->set_progress (percent, NULL);
1463         }
1464     }
1465
1466   // Recursively process all descendants
1467   int index;
1468   int dsize = NUM_DESCENDANTS (node);
1469   for (index = 0; index < dsize; index++)
1470     get_metrics (node->descendants->fetch (index), dpth + 1);
1471 }
1472
1473 void
1474 PathTree::get_clr_metrics (Vector<Histable*> *objs, NodeIdx node_idx,
1475                            int pmatch, int dpth)
1476 {
1477   Node *node = NODE_IDX (node_idx);
1478   Histable *cur_obj;
1479   if (hist_data->type == Histable::LINE || hist_data->type == Histable::INSTR)
1480     {
1481       cur_obj = get_hist_func_obj (node);
1482       node_list[dpth] = node;
1483     }
1484   else
1485     cur_obj = get_hist_obj (node);
1486   obj_list[dpth] = cur_obj;
1487
1488   bool match = false;
1489   int nobj = objs->size ();
1490   if (dpth + 1 >= nobj)
1491     {
1492       match = true;
1493       for (int i = 0; i < nobj; ++i)
1494         {
1495           if (objs->fetch (i) != obj_list[dpth - nobj + 1 + i])
1496             {
1497               match = false;
1498               break;
1499             }
1500         }
1501     }
1502
1503   Hist_data::HistItem *hi = NULL;
1504   Hist_data::HistItem *hi_adj = NULL;
1505   if (match && dpth >= nobj)
1506     {
1507       if (hist_data->type == Histable::LINE
1508           || hist_data->type == Histable::INSTR)
1509         hi = hist_data->append_hist_item (get_hist_obj (node_list[dpth - nobj]));
1510       else
1511         hi = hist_data->append_hist_item (obj_list[dpth - nobj]);
1512
1513       if (pmatch >= 0 && pmatch >= nobj)
1514         {
1515           if (hist_data->type == Histable::LINE
1516               || hist_data->type == Histable::INSTR)
1517             hi_adj = hist_data->append_hist_item (get_hist_obj (
1518                                                     node_list[pmatch - nobj]));
1519           else
1520             hi_adj = hist_data->append_hist_item (obj_list[pmatch - nobj]);
1521         }
1522     }
1523
1524   if (hi != NULL)
1525     {
1526       MetricList *mlist = hist_data->get_metric_list ();
1527       for (long ind = 0, sz = mlist->size (); ind < sz; ind++)
1528         {
1529           if (xlate[ind] == -1)
1530             continue;
1531           if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx))
1532             continue;
1533           Metric *mtr = mlist->get (ind);
1534           Metric::SubType subtype = mtr->get_subtype ();
1535
1536           switch (subtype)
1537             {
1538             case Metric::ATTRIBUTED:
1539               if (hi)
1540                 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
1541               if (hi_adj)
1542                 SUB_METRIC_VAL (hi_adj->value[ind], slots[xlate[ind]], node_idx);
1543               break;
1544             case Metric::STATIC:
1545             case Metric::EXCLUSIVE:
1546             case Metric::INCLUSIVE:
1547             case Metric::DATASPACE:
1548               break;
1549             }
1550         }
1551     }
1552
1553   // Recursively process all descendants
1554   int dsize = NUM_DESCENDANTS (node);
1555   for (int index = 0; index < dsize; index++)
1556     get_clr_metrics (objs, node->descendants->fetch (index),
1557                      match ? dpth : pmatch, dpth + 1);
1558 }
1559
1560 void
1561 PathTree::get_clr_metrics (Vector<Histable*> *objs)
1562 {
1563   get_clr_metrics (objs, root_idx, -1, 0);
1564 }
1565
1566 void
1567 PathTree::get_cle_metrics (Vector<Histable*> *objs, NodeIdx node_idx, int pcle,
1568                            int pmatch, int dpth)
1569 {
1570   Node *node = NODE_IDX (node_idx);
1571   Histable *cur_obj = get_hist_obj (node);
1572   obj_list[dpth] = cur_obj;
1573
1574   bool match = false;
1575   int nobj = objs->size ();
1576   if (dpth + 1 >= nobj)
1577     {
1578       match = true;
1579       for (int i = 0; i < nobj; ++i)
1580         if (objs->fetch (i) != obj_list[dpth - nobj + 1 + i])
1581           {
1582             match = false;
1583             break;
1584           }
1585     }
1586
1587   Hist_data::HistItem *hi = NULL;
1588   Hist_data::HistItem *hi_adj = NULL;
1589   if (pmatch >= 0 && dpth == pmatch + 1)
1590     hi = hist_data->append_hist_item (cur_obj);
1591   if (match && IS_LEAF (node))
1592     hi = hist_data->gprof_item;
1593   if (pcle >= 0)
1594     hi_adj = hist_data->append_hist_item (obj_list[pcle]);
1595
1596   if (hi != NULL)
1597     {
1598       MetricList *mlist = hist_data->get_metric_list ();
1599       for (long ind = 0, sz = mlist->size (); ind < sz; ind++)
1600         {
1601           if (xlate[ind] == -1)
1602             continue;
1603           if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx))
1604             continue;
1605           Metric *mtr = mlist->get (ind);
1606           Metric::SubType subtype = mtr->get_subtype ();
1607           if (subtype == Metric::ATTRIBUTED)
1608             {
1609               ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
1610               if (hi_adj)
1611                 SUB_METRIC_VAL (hi_adj->value[ind], slots[xlate[ind]], node_idx);
1612             }
1613         }
1614     }
1615
1616   // Recursively process all descendants
1617   int dsize = NUM_DESCENDANTS (node);
1618   for (int index = 0; index < dsize; index++)
1619     get_cle_metrics (objs, node->descendants->fetch (index),
1620                      pmatch >= 0 && dpth == pmatch + 1 ? dpth : pcle,
1621                      match ? dpth : pmatch, dpth + 1);
1622 }
1623
1624 void
1625 PathTree::get_cle_metrics (Vector<Histable*> *objs, NodeIdx node_idx, int dpth)
1626 {
1627   Node *node = NODE_IDX (node_idx);
1628   Histable *cur_obj = get_hist_obj (node);
1629   Hist_data::HistItem *hi = NULL;
1630   if (NULL == objs)   // Special case: get root
1631     hi = hist_data->append_hist_item (cur_obj);
1632   else
1633     {
1634       if (dpth == objs->size ())
1635         hi = hist_data->append_hist_item (cur_obj);
1636       else if (cur_obj == objs->fetch (dpth))
1637         {
1638           // Recursively process all descendants
1639           int dsize = NUM_DESCENDANTS (node);
1640           for (int index = 0; index < dsize; index++)
1641             get_cle_metrics (objs, node->descendants->fetch (index), dpth + 1);
1642           if (dpth == objs->size () - 1 && dsize == 0)
1643             hi = hist_data->gprof_item;
1644         }
1645     }
1646
1647   if (hi != NULL)
1648     {
1649       MetricList *mlist = hist_data->get_metric_list ();
1650       for (long ind = 0, sz = mlist->size (); ind < sz; ind++)
1651         {
1652           if (xlate[ind] == -1)
1653             continue;
1654           if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx))
1655             continue;
1656           Metric *mtr = mlist->get (ind);
1657           Metric::SubType subtype = mtr->get_subtype ();
1658           if (subtype == Metric::ATTRIBUTED)
1659             ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
1660         }
1661     }
1662 }
1663
1664 void
1665 PathTree::ftree_reset ()
1666 {
1667   if (pathTreeType == PATHTREE_MAIN && indxtype < 0)
1668     {
1669       reset ();
1670       if (ftree_needs_update)
1671         {
1672           if (ftree_internal == NULL)
1673             {
1674               ftree_internal = new PathTree (dbev, indxtype,
1675                                              PATHTREE_INTERNAL_FUNCTREE);
1676               if (ftree_internal == NULL)
1677                 return;
1678             }
1679           ftree_internal->ftree_build (this);
1680           ftree_needs_update = false;
1681         }
1682     }
1683 }
1684
1685 void
1686 PathTree::ftree_build (PathTree * mstr)
1687 {
1688   fini ();
1689   init ();
1690   allocate_slots (mstr->slots, mstr->nslots);
1691   ftree_build (mstr, mstr->root_idx, root_idx);
1692   depth = mstr->depth;
1693   depth_map_build ();
1694 }
1695
1696 #if DEBUG_FTREE // possibly TBR
1697 void
1698 PathTree::ftree_dump ()
1699 {
1700   hrtime_t starttime, endtime;
1701   int nmetrics = 1;
1702   // int nmetrics = nslots;
1703   for (int kk = 0; kk < nmetrics; kk++)
1704     {
1705       int id = slots[kk].id;
1706       starttime = gethrtime ();
1707       long nodecnt = 0;
1708       for (int ii = 0; ii < depth; ii++)
1709         {
1710           Vector<Vector<void*>*> *tmp = (Vector<Vector<void*>*>*)get_ftree_level
1711                   (id, ii);
1712           if (tmp == NULL)
1713             continue;
1714           long sz = tmp->get (0)->size ();
1715           nodecnt += sz;
1716 #if 1
1717           //   fprintf(stderr, "... finished (%ld nodes)\n", sz);
1718 #else
1719           Vector<NodeIdx> *nodeIdxList = (Vector<NodeIdx> *)tmp->get (0);
1720           Vector<NodeIdx> *ancestorNodeIdxList = (Vector<NodeIdx> *)tmp->get (1);
1721           Vector<uint64_t> *idList = (Vector<uint64_t> *)tmp->get (2);
1722           Vector<uint64_t> *vals = (Vector<uint64_t> *)tmp->get (3);
1723           for (int jj = 0; jj < sz; jj++)
1724             fprintf (stderr, " ...%d:%d node=%ld, anc=%ld, id=%llu, val=%llu\n",
1725                      sz, jj, nodeIdxList->get (jj),
1726                      ancestorNodeIdxList->get (jj),
1727                      idList->get (jj), vals->get (jj));
1728 #endif
1729           destroy (tmp);
1730         }
1731       endtime = gethrtime ();
1732       fprintf (stderr, "====================== %ld nodes time=%llu\n",
1733                nodecnt, (endtime - starttime) / 1000 / 1000);
1734     }
1735 }
1736 #endif
1737
1738 // ftree: translate mstr Histable::INSTR to Histable::FUNCTION
1739 void
1740 PathTree::ftree_build (PathTree *mstr, NodeIdx mstr_node_idx,
1741                        NodeIdx local_node_idx)
1742 {
1743   // requires: slots, nslots
1744   Node *mstr_node = mstr->NODE_IDX (mstr_node_idx);
1745   int dsize = NUM_DESCENDANTS (mstr_node);
1746
1747   // Add metrics
1748   for (int i = 0; i < nslots; i++)
1749     {
1750       if (i >= mstr->nslots)
1751         continue; //weird
1752       if (slots[i].vtype != mstr->slots[i].vtype)
1753         continue; //weird
1754       TValue val;
1755       val.ll = 0;
1756       mstr->ASN_METRIC_VAL (val, mstr->slots[i], mstr_node_idx);
1757       int64_t mval;
1758       switch (slots[i].vtype)
1759         {
1760         case VT_ULLONG:
1761         case VT_LLONG:
1762           mval = val.ll;
1763           break;
1764         case VT_INT:
1765           mval = val.i;
1766           break;
1767         default:
1768           mval = 0;
1769           break;
1770         }
1771       if (mval)
1772         {
1773           Slot * mslot = SLOT_IDX (i);
1774           if (mslot)
1775             INCREMENT_METRIC (mslot, local_node_idx, mval);
1776         }
1777     }
1778
1779   // Recursively process all descendants
1780   for (int index = 0; index < dsize; index++)
1781     {
1782       NodeIdx mstr_desc_node_idx = mstr_node->descendants->fetch (index);
1783       Node *mstr_desc_node = mstr->NODE_IDX (mstr_desc_node_idx);
1784       Function *func = (Function*) mstr_desc_node->instr->convertto (Histable::FUNCTION);
1785       int mstr_desc_dsize = NUM_DESCENDANTS (mstr_desc_node);
1786       bool leaf = (mstr_desc_dsize == 0);
1787       NodeIdx local_desc_node_idx = find_desc_node (local_node_idx, func, leaf);
1788       ftree_build (mstr, mstr_desc_node_idx, local_desc_node_idx);
1789     }
1790 }
1791
1792 void
1793 PathTree::depth_map_build ()
1794 {
1795   destroy (depth_map);
1796   depth_map = new Vector<Vector<NodeIdx>*>(depth);
1797   if (depth)
1798     {
1799       depth_map->put (depth - 1, 0); // fill vector with nulls
1800       depth_map_build (root_idx, 0);
1801     }
1802 }
1803
1804 void
1805 PathTree::depth_map_build (NodeIdx node_idx, int dpth)
1806 {
1807   Node *node = NODE_IDX (node_idx);
1808
1809   Vector<NodeIdx> *node_idxs = depth_map->get (dpth);
1810   if (node_idxs == NULL)
1811     {
1812       node_idxs = new Vector<NodeIdx>();
1813       depth_map->store (dpth, node_idxs);
1814     }
1815   node_idxs->append (node_idx);
1816
1817   // Recursively process all descendants
1818   int dsize = NUM_DESCENDANTS (node);
1819   for (int index = 0; index < dsize; index++)
1820     {
1821       NodeIdx desc_node_idx = node->descendants->fetch (index);
1822       depth_map_build (desc_node_idx, dpth + 1);
1823     }
1824 }
1825
1826 int
1827 PathTree::get_ftree_depth ()
1828 { // external use only
1829   ftree_reset ();
1830   if (!ftree_internal)
1831     return 0;
1832   return ftree_internal->get_depth ();
1833 }
1834
1835 Vector<Function*>*
1836 PathTree::get_ftree_funcs ()
1837 { // external use only
1838   ftree_reset ();
1839   if (!ftree_internal)
1840     return NULL;
1841   return ftree_internal->get_funcs ();
1842 }
1843
1844 Vector<Function*>*
1845 PathTree::get_funcs ()
1846 {
1847   // get unique functions
1848   if (fn_map == NULL)
1849     return NULL;
1850   return fn_map->keySet ();
1851 }
1852
1853 Vector<void*>*
1854 PathTree::get_ftree_level (BaseMetric *bm, int dpth)
1855 { // external use only
1856   ftree_reset ();
1857   if (!ftree_internal)
1858     return NULL;
1859   return ftree_internal->get_level (bm, dpth);
1860 }
1861
1862 Vector<void*>*
1863 PathTree::get_level (BaseMetric *bm, int dpth)
1864 {
1865   // Nodes at tree depth dpth
1866   if (dpth < 0 || dpth >= depth)
1867     return NULL;
1868   if (depth_map == NULL)
1869     return NULL;
1870   Vector<NodeIdx> *node_idxs = depth_map->get (dpth);
1871   return get_nodes (bm, node_idxs);
1872 }
1873
1874 Vector<void*>*
1875 PathTree::get_ftree_node_children (BaseMetric *bm, NodeIdx node_idx)
1876 { // external use only
1877   ftree_reset ();
1878   if (!ftree_internal)
1879     return NULL;
1880   return ftree_internal->get_node_children (bm, node_idx);
1881 }
1882
1883 Vector<void*>*
1884 PathTree::get_node_children (BaseMetric *bm, NodeIdx node_idx)
1885 {
1886   // Nodes that are children of node_idx
1887   if (depth_map == NULL)
1888     return NULL;
1889   if (node_idx == 0)  // special case for root
1890     return get_nodes (bm, depth_map->get (0));
1891   if (node_idx < 0 || node_idx >= nodes)
1892     return NULL;
1893   Node *node = NODE_IDX (node_idx);
1894   if (node == NULL)
1895     return NULL;
1896   Vector<NodeIdx> *node_idxs = node->descendants;
1897   return get_nodes (bm, node_idxs);
1898 }
1899
1900 Vector<void*>*
1901 PathTree::get_nodes (BaseMetric *bm, Vector<NodeIdx> *node_idxs)
1902 { // used for ftree
1903   // capture info for node_idxs:
1904   //   node's idx
1905   //   node->ancestor idx
1906   //   node->instr->id
1907   //   mind metric value // in the future, could instead accept vector of mind
1908   if (node_idxs == NULL)
1909     return NULL;
1910   long sz = node_idxs->size ();
1911   if (sz <= 0)
1912     return NULL;
1913
1914   bool calculate_metric = false;
1915   ValueTag vtype;
1916   int slot_idx;
1917   double prec;
1918   if (bm != NULL)
1919     {
1920       int mind = bm->get_id ();
1921       slot_idx = find_slot (mind); // may be -1 (CPI and IPC)
1922       prec = bm->get_precision ();
1923       vtype = bm->get_vtype ();
1924     }
1925   else
1926     {
1927       slot_idx = -1;
1928       prec = 1.0;
1929       vtype = VT_INT;
1930     }
1931
1932   if (slot_idx >= 0)
1933     {
1934       switch (vtype)
1935         {
1936         case VT_ULLONG:
1937         case VT_LLONG:
1938         case VT_INT:
1939           if (slots[slot_idx].vtype == vtype)
1940             calculate_metric = true;
1941           else
1942             DBG (assert (false));
1943           break;
1944         case VT_DOUBLE:
1945           calculate_metric = true;
1946           break;
1947         default:
1948           break;
1949         }
1950     }
1951
1952   Vector<void*> *results = new Vector<void*>(4);
1953   if (!calculate_metric)
1954     results->store (3, NULL);
1955   else
1956     {
1957       // Code below cribbed from Dbe.cc:dbeGetTableDataV2Data.
1958       // TBD: possibly create an intermediate HistData and instead call that routine
1959       switch (vtype)
1960         {
1961         case VT_ULLONG:
1962         case VT_LLONG:
1963           {
1964             Vector<long long> *vals = new Vector<long long>(sz);
1965             for (long i = 0; i < sz; i++)
1966               {
1967                 NodeIdx node_idx = node_idxs->get (i);
1968                 TValue val;
1969                 val.ll = 0;
1970                 ASN_METRIC_VAL (val, slots[slot_idx], node_idx);
1971                 vals->append (val.ll);
1972               }
1973             results->store (3, vals);
1974             break;
1975           }
1976         case VT_DOUBLE:
1977           {
1978             Vector<double> *vals = new Vector<double>(sz);
1979             TValue val;
1980             val.tag = slots[slot_idx].vtype; // required for to_double();
1981             for (long i = 0; i < sz; i++)
1982               {
1983                 NodeIdx node_idx = node_idxs->get (i);
1984                 val.ll = 0;
1985                 ASN_METRIC_VAL (val, slots[slot_idx], node_idx);
1986                 double dval = val.to_double ();
1987                 dval /= prec;
1988                 vals->append (dval);
1989               }
1990             results->store (3, vals);
1991             break;
1992           }
1993         case VT_INT:
1994           {
1995             Vector<int> *vals = new Vector<int>(sz);
1996             for (long i = 0; i < sz; i++)
1997               {
1998                 NodeIdx node_idx = node_idxs->get (i);
1999                 TValue val;
2000                 val.i = 0;
2001                 ASN_METRIC_VAL (val, slots[slot_idx], node_idx);
2002                 vals->append (val.i);
2003               }
2004             results->store (3, vals);
2005             break;
2006           }
2007         default:
2008           results->store (3, NULL);
2009           break;
2010         }
2011     }
2012
2013   Vector<int> *nodeIdxList = new Vector<int>(sz);
2014   Vector<int> *ancestorNodeIdxList = new Vector<int>(sz);
2015   Vector<uint64_t> *idList = new Vector<uint64_t>(sz);
2016   for (long i = 0; i < sz; i++)
2017     {
2018       NodeIdx node_idx = node_idxs->get (i);
2019       Node *node = NODE_IDX (node_idx);
2020       NodeIdx ancestor_idx = node->ancestor;
2021       Histable *func = node->instr;
2022       nodeIdxList->append (node_idx);
2023       ancestorNodeIdxList->append (ancestor_idx);
2024       idList->append (func->id);
2025     }
2026
2027   results->store (0, nodeIdxList);
2028   results->store (1, ancestorNodeIdxList);
2029   results->store (2, idList);
2030   return results;
2031 }
2032
2033 void
2034 PathTree::get_cle_metrics (Vector<Histable*> *objs)
2035 {
2036   if (NULL == objs || objs->fetch (0) == get_hist_obj (NODE_IDX (root_idx)))
2037     // Call Tree optimization
2038     get_cle_metrics (objs, root_idx, 0);
2039   else
2040     // General case
2041     get_cle_metrics (objs, root_idx, -1, -1, 0);
2042 }
2043
2044 void
2045 PathTree::get_metrics (Vector<Function*> *functions, Histable *context)
2046 {
2047   Function *fitem;
2048   int excl_ok, incl_ok;
2049   NodeIdx node_idx;
2050   Node *node, *anc;
2051   int index;
2052
2053   Vec_loop (Function*, functions, index, fitem)
2054   {
2055     node_idx = fn_map->get (fitem);
2056     for (; node_idx; node_idx = node->funclist)
2057       {
2058         node = NODE_IDX (node_idx);
2059         Histable *h_obj = get_hist_obj (node, context);
2060         if (h_obj == NULL)
2061           continue;
2062
2063         // Check for recursion (inclusive metrics)
2064         incl_ok = 1;
2065         for (anc = NODE_IDX (node->ancestor); anc;
2066                 anc = NODE_IDX (anc->ancestor))
2067           {
2068             if (h_obj == get_hist_obj (anc, context))
2069               {
2070                 incl_ok = 0;
2071                 break;
2072               }
2073           }
2074
2075         // Check for leaf nodes (exclusive metrics)
2076         excl_ok = 0;
2077         if (IS_LEAF (node))
2078           excl_ok = 1;
2079
2080         h_obj = get_compare_obj (h_obj);
2081         Hist_data::HistItem *hi = hist_data->append_hist_item (h_obj);
2082
2083         if (!excl_ok)
2084           hist_data->get_callsite_mark ()->put (h_obj, 1);
2085         MetricList *mlist = hist_data->get_metric_list ();
2086         for (long ind = 0, sz = mlist->size (); ind < sz; ind++)
2087           {
2088             if (xlate[ind] == -1)
2089               continue;
2090             Metric *mtr = mlist->get (ind);
2091             Metric::SubType subtype = mtr->get_subtype ();
2092             if (subtype == Metric::INCLUSIVE && !incl_ok)
2093               continue;
2094             if (subtype == Metric::EXCLUSIVE && !excl_ok)
2095               continue;
2096             if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx))
2097               continue;
2098             ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
2099           }
2100       }
2101   }
2102 }
2103
2104 void
2105 PathTree::get_self_metrics (Vector<Histable*> *objs, NodeIdx node_idx,
2106                             bool seen, int dpth)
2107 {
2108   Node *node = NODE_IDX (node_idx);
2109   Histable *cur_obj = get_hist_obj (node);
2110   obj_list[dpth] = cur_obj;
2111
2112   bool match = false;
2113   int nobj = objs->size ();
2114   if (dpth + 1 >= nobj)
2115     {
2116       match = true;
2117       for (int i = 0; i < nobj; ++i)
2118         {
2119           if (objs->fetch (i) != obj_list[dpth - nobj + 1 + i])
2120             {
2121               match = false;
2122               break;
2123             }
2124         }
2125     }
2126
2127   if (match)
2128     {
2129       Hist_data::HistItem *hi = hist_data->append_hist_item (cur_obj);
2130       int incl_ok = !seen;
2131       int excl_ok = 0;
2132       if (IS_LEAF (node) || node == NODE_IDX (root_idx))
2133         excl_ok = 1;
2134       MetricList *mlist = hist_data->get_metric_list ();
2135       for (long ind = 0, sz = mlist->size (); ind < sz; ind++)
2136         {
2137           if (xlate[ind] == -1)
2138             continue;
2139           if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx))
2140             continue;
2141           Metric *mtr = mlist->get (ind);
2142           Metric::SubType subtype = mtr->get_subtype ();
2143           switch (subtype)
2144             {
2145             case Metric::INCLUSIVE:
2146               if (incl_ok && hi)
2147                 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
2148               break;
2149             case Metric::EXCLUSIVE:
2150             case Metric::ATTRIBUTED:
2151               if (excl_ok && hi)
2152                 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
2153               break;
2154             case Metric::DATASPACE:
2155               if (hi)
2156                 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
2157               break;
2158               // ignoring the following cases (why?)
2159             case Metric::STATIC:
2160               break;
2161             }
2162         }
2163     }
2164
2165   if (dbeSession->is_interactive ())
2166     {
2167       ndone++;
2168       int new_percent = 95 * ndone / nodes;
2169       if (new_percent > percent)
2170         {
2171           percent = new_percent;
2172           theApplication->set_progress (percent, NULL);
2173         }
2174     }
2175
2176   // Recursively process all descendants
2177   int index;
2178   int dsize = NUM_DESCENDANTS (node);
2179   for (index = 0; index < dsize; index++)
2180     get_self_metrics (objs, node->descendants->fetch (index),
2181                       seen || match, dpth + 1);
2182 }
2183
2184 void
2185 PathTree::get_self_metrics (Vector<Histable*> *objs)
2186 {
2187   get_self_metrics (objs, root_idx, false, 0);
2188 }
2189
2190 void
2191 PathTree::get_self_metrics (Histable *obj, Vector<Function*> *funclist,
2192                             Vector<Histable*>* sel_objs)
2193 {
2194   int excl_ok, incl_ok;
2195   NodeIdx node_idx;
2196   Node *node, *anc;
2197
2198   if (obj == NULL)
2199     return;
2200
2201   SourceFile *src = NULL;
2202   if (obj && obj->get_type () == Histable::LINE)
2203     {
2204       DbeLine *dbeline = (DbeLine*) obj;
2205       src = dbeline->sourceFile;
2206     }
2207
2208   Hist_data::HistItem *hi = hist_data->append_hist_item (obj);
2209   for (int i = 0, sz = funclist ? funclist->size () : 0; i < sz; i++)
2210     {
2211       Function *fitem = (Function*) get_compare_obj (funclist->fetch (i));
2212       node_idx = fn_map->get (fitem);
2213       for (; node_idx; node_idx = node->funclist)
2214         {
2215           node = NODE_IDX (node_idx);
2216           if (obj && obj->get_type () == Histable::LINE)
2217             {
2218               Histable *h = get_hist_obj (node, src);
2219               if (h == NULL)
2220                 continue;
2221               if (h->convertto (Histable::LINE) != obj->convertto (Histable::LINE))
2222                 continue;
2223             }
2224           else if (get_hist_obj (node, src) != obj)
2225             continue;
2226
2227           // Check for recursion (inclusive metrics)
2228           incl_ok = 1;
2229           for (anc = NODE_IDX (node->ancestor); anc;
2230                   anc = NODE_IDX (anc->ancestor))
2231             {
2232               if (get_hist_obj (anc, src) == obj)
2233                 {
2234                   incl_ok = 0;
2235                   break;
2236                 }
2237               if (sel_objs != NULL)
2238                 for (int k = 0; k < sel_objs->size (); k++)
2239                   if (sel_objs->fetch (k) == get_hist_obj (anc, src))
2240                     {
2241                       incl_ok = 0;
2242                       break;
2243                     }
2244             }
2245
2246           // Check for leaf nodes (exclusive metrics)
2247           excl_ok = 0;
2248           if (IS_LEAF (node) || node == NODE_IDX (root_idx))
2249             excl_ok = 1;
2250
2251           MetricList *mlist = hist_data->get_metric_list ();
2252           for (long ind = 0, ind_sz = mlist->size (); ind < ind_sz; ind++)
2253             {
2254               if (xlate[ind] == -1)
2255                 continue;
2256               Metric *mtr = mlist->get (ind);
2257               Metric::SubType subtype = mtr->get_subtype ();
2258               if (subtype == Metric::INCLUSIVE && !incl_ok)
2259                 continue;
2260               if (subtype == Metric::EXCLUSIVE && !excl_ok)
2261                 continue;
2262               if (subtype == Metric::ATTRIBUTED && !excl_ok)
2263                 continue;
2264               if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx))
2265                 continue;
2266               ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx);
2267             }
2268         }
2269     }
2270 }
2271
2272 Vector<Histable*> *
2273 PathTree::get_clr_instr (Histable * func)
2274 {
2275   Vector<Histable*> * instrs = NULL;
2276   if (func->get_type () != Histable::FUNCTION)
2277     return NULL;
2278   NodeIdx node_idx = fn_map->get ((Function*) func);
2279   Node *node = NODE_IDX (node_idx);
2280   if (node == NULL)
2281     return new Vector<Histable*>();
2282   int instr_num = 0;
2283   for (; node; node = NODE_IDX (node->funclist))
2284     instr_num++;
2285   instrs = new Vector<Histable*>(instr_num);
2286   node = NODE_IDX (node_idx);
2287   Histable *instr = NODE_IDX (node->ancestor)->instr;
2288   instr_num = 0;
2289   instrs->store (instr_num, instr);
2290   node = NODE_IDX (node->funclist);
2291   for (; node; node = NODE_IDX (node->funclist))
2292     {
2293       instr = NODE_IDX (node->ancestor)->instr;
2294       instr_num++;
2295       instrs->store (instr_num, instr);
2296     }
2297   return instrs;
2298 }
2299
2300 Vector<void*> *
2301 PathTree::get_cle_instr (Histable * func, Vector<Histable*>*&instrs)
2302 {
2303   if (func->get_type () != Histable::FUNCTION)
2304     return NULL;
2305   NodeIdx node_idx = fn_map->get ((Function*) func);
2306   Node *node = NODE_IDX (node_idx);
2307   if (node == NULL)
2308     {
2309       instrs = new Vector<Histable*>();
2310       return new Vector<void*>();
2311     }
2312   int instr_num = 0;
2313   for (; node; node = NODE_IDX (node->funclist))
2314     instr_num++;
2315   instrs = new Vector<Histable*>(instr_num);
2316   Vector<void*> *callee_info = new Vector<void*>(instr_num);
2317   node = NODE_IDX (node_idx);
2318   Histable *instr = node->instr;
2319   instr_num = 0;
2320   instrs->store (instr_num, instr);
2321   int dec_num = 0;
2322   NodeIdx dec_idx = 0;
2323   if (NUM_DESCENDANTS (node) > 0)
2324     {
2325       Vector<Histable*> * callee_instrs = new Vector<Histable*>(node->descendants->size ());
2326       Vec_loop (NodeIdx, node->descendants, dec_num, dec_idx)
2327       {
2328         Node * dec_node = NODE_IDX (dec_idx);
2329         //XXXX Note: there can be more than one instrs in one leaf function
2330         callee_instrs->store (dec_num, dec_node->instr);
2331       }
2332       callee_info->store (instr_num, callee_instrs);
2333     }
2334   else
2335     callee_info->store (instr_num, NULL);
2336   node = NODE_IDX (node->funclist);
2337   for (; node; node = NODE_IDX (node->funclist))
2338     {
2339       instr = node->instr;
2340       instr_num++;
2341       instrs->store (instr_num, instr);
2342       if (NUM_DESCENDANTS (node) > 0)
2343         {
2344           Vector<Histable*> * callee_instrs = new Vector<Histable*>(node->descendants->size ());
2345           Vec_loop (NodeIdx, node->descendants, dec_num, dec_idx)
2346           {
2347             Node * dec_node = NODE_IDX (dec_idx);
2348             //XXXX Note: there can be more than one instrs in one leaf function
2349             callee_instrs->store (dec_num, dec_node->instr);
2350           }
2351           callee_info->store (instr_num, callee_instrs);
2352         }
2353       else
2354         callee_info->store (instr_num, NULL);
2355     }
2356   return callee_info;
2357 }
2358
2359 //
2360 //
2361 // The following methods are used for debugging purpose only.
2362 //
2363 //
2364 static int maxdepth;
2365 static int maxwidth;
2366
2367 void
2368 PathTree::print (FILE *fd)
2369 {
2370   (void) reset ();
2371   fprintf (fd, NTXT ("n = %lld, dn = %lld, MD = %lld\n\n"),
2372            (long long) nodes, (long long) dnodes, (long long) depth);
2373   maxdepth = 0;
2374   maxwidth = 0;
2375   print (fd, root, 0);
2376   fprintf (fd, NTXT ("md = %lld, mw = %lld\n"),
2377            (long long) maxdepth, (long long) maxwidth);
2378 }
2379
2380 void
2381 PathTree::print (FILE *fd, PathTree::Node *node, int lvl)
2382 {
2383   const char *t;
2384   char *n;
2385   if (lvl + 1 > maxdepth)
2386     maxdepth = lvl + 1;
2387   for (int i = 0; i < lvl; i++)
2388     fprintf (fd, NTXT ("-"));
2389   Histable *instr = node->instr;
2390   if (instr->get_type () == Histable::LINE)
2391     {
2392       t = "L";
2393       n = ((DbeLine *) instr)->func->get_name ();
2394     }
2395   else if (instr->get_type () == Histable::INSTR)
2396     {
2397       t = "I";
2398       n = ((DbeInstr *) instr)->func->get_name ();
2399     }
2400   else
2401     {
2402       t = "O";
2403       n = instr->get_name ();
2404     }
2405   long long addr = (long long) instr->get_addr ();
2406   fprintf (fd, NTXT ("%s %s (0x%08llx) -- ndesc = %lld\n"),
2407            t, n, addr, (long long) (NUM_DESCENDANTS (node)));
2408
2409   // Recursively process all descendants
2410   int dsize = NUM_DESCENDANTS (node);
2411   if (dsize > maxwidth)
2412     maxwidth = dsize;
2413   for (int index = 0; index < dsize; index++)
2414     print (fd, NODE_IDX (node->descendants->fetch (index)), lvl + 1);
2415 }
2416
2417 void
2418 PathTree::printn (FILE *fd)
2419 {
2420   int n = dbg_nodes (root);
2421   fprintf (fd, GTXT ("Number of nodes: %d, total size: %d\n"), n, (int) (n * sizeof (Node)));
2422 }
2423
2424 void
2425 PathTree::dumpNodes (FILE *fd, Histable *obj)
2426 {
2427   const char *t;
2428   char *n;
2429   NodeIdx node_idx = fn_map->get ((Function*) obj);
2430   Node *node = NODE_IDX (node_idx);
2431   if (node == NULL)
2432     {
2433       fprintf (fd, GTXT ("No nodes associated with %s\n"), obj->get_name ());
2434       return;
2435     }
2436   Histable *instr = node->instr;
2437   for (; node; node = NODE_IDX (node->funclist))
2438     {
2439       instr = node->instr;
2440       if (instr->get_type () == Histable::LINE)
2441         {
2442           t = "L";
2443           n = ((DbeLine *) instr)->func->get_name ();
2444         }
2445       else if (instr->get_type () == Histable::INSTR)
2446         {
2447           t = "I";
2448           n = ((DbeInstr *) instr)->func->get_name ();
2449         }
2450       else
2451         {
2452           t = "O";
2453           n = instr->get_name ();
2454         }
2455       long long addr = (long long) instr->get_addr ();
2456       if (addr <= 0xFFFFFFFFU)
2457         fprintf (fd, NTXT ("0x%08x -- %s %s\n"), (uint32_t) addr, t, n);
2458       else
2459         fprintf (fd, NTXT ("0x%016llX -- %s %s\n"), addr, t, n);
2460     }
2461 }
2462
2463 int
2464 PathTree::dbg_nodes (PathTree::Node *node)
2465 {
2466   int res = 1;
2467   int dsize = NUM_DESCENDANTS (node);
2468   for (int index = 0; index < dsize; index++)
2469     res += dbg_nodes (NODE_IDX (node->descendants->fetch (index)));
2470   return res;
2471 }
2472
2473 static int mind_g;
2474
2475 int
2476 leak_alloc_comp (const void *s1, const void *s2)
2477 {
2478   // See Hist_data::sort_compare() for duplicate code
2479   int result = 0;
2480   CStack_data::CStack_item *t1, *t2;
2481   t1 = *(CStack_data::CStack_item **)s1;
2482   t2 = *(CStack_data::CStack_item **)s2;
2483
2484   switch (t1->value[mind_g].tag)
2485     {
2486     case VT_INT:
2487       if (t1->value[mind_g].i < t2->value[mind_g].i)
2488         result = -1;
2489       else if (t1->value[mind_g].i > t2->value[mind_g].i)
2490         result = 1;
2491       else
2492         result = 0;
2493       break;
2494     case VT_LLONG:
2495       if (t1->value[mind_g].ll < t2->value[mind_g].ll)
2496         result = -1;
2497       else if (t1->value[mind_g].ll > t2->value[mind_g].ll)
2498         result = 1;
2499       else
2500         result = 0;
2501       break;
2502     case VT_ULLONG:
2503       if (t1->value[mind_g].ull < t2->value[mind_g].ull)
2504         result = -1;
2505       else if (t1->value[mind_g].ull > t2->value[mind_g].ull)
2506         result = 1;
2507       else
2508         result = 0;
2509       break;
2510       // ignoring the following cases (why?)
2511     case VT_SHORT:
2512     case VT_FLOAT:
2513     case VT_DOUBLE:
2514     case VT_HRTIME:
2515     case VT_LABEL:
2516     case VT_ADDRESS:
2517     case VT_OFFSET:
2518       break;
2519     }
2520   // Sort in descending order
2521   return -result;
2522 }
2523
2524 CStack_data *
2525 PathTree::get_cstack_data (MetricList *mlist)
2526 {
2527   (void) reset ();
2528   CStack_data *lam = new CStack_data (mlist);
2529   int nmetrics = mlist->get_items ()->size ();
2530   mind_g = -1;
2531   xlate = new int[nmetrics];
2532   for (int mind = 0; mind < nmetrics; mind++)
2533     {
2534       xlate[mind] = -1;
2535       Metric *mtr = mlist->get_items ()->fetch (mind);
2536       if (mlist->get_sort_ref_index () == mind)
2537         mind_g = mind;
2538       xlate[mind] = find_slot (mtr->get_id ());
2539     }
2540
2541   // now fill in the actual data
2542   obj_list = new Histable*[depth];
2543   get_cstack_list (lam, root_idx, 0);
2544   delete[] obj_list;
2545
2546   if (mind_g >= 0)
2547     lam->cstack_items->sort (leak_alloc_comp);
2548   delete[] xlate;
2549   return lam;
2550 }
2551
2552 void
2553 PathTree::get_cstack_list (CStack_data *lam, NodeIdx node_idx, int dpth)
2554 {
2555
2556   Node *node = NODE_IDX (node_idx);
2557   obj_list[dpth] = node->instr;
2558
2559   CStack_data::CStack_item *item = NULL;
2560   if (IS_LEAF (node))
2561     item = lam->new_cstack_item ();
2562   int nmetrics = lam->metrics->get_items ()->size ();
2563   bool subtree_empty = true;
2564
2565   for (int mind = 0; mind < nmetrics; mind++)
2566     {
2567       if (xlate[mind] == -1)
2568         continue;
2569       if (IS_MVAL_ZERO (slots[xlate[mind]], node_idx))
2570         continue;
2571       else
2572         subtree_empty = false;
2573       if (item)
2574         {
2575           ADD_METRIC_VAL (item->value[mind], slots[xlate[mind]], node_idx);
2576           ADD_METRIC_VAL (lam->total->value[mind], slots[xlate[mind]], node_idx);
2577         }
2578     }
2579
2580   if (subtree_empty)
2581     {
2582       delete item;
2583       return;
2584     }
2585
2586   if (item)
2587     {
2588       // Finish processing a leaf node
2589       item->stack = new Vector<DbeInstr*>(dpth);
2590       for (int i = 1; i <= dpth; i++)
2591         item->stack->append ((DbeInstr*) obj_list[i]);
2592       lam->cstack_items->append (item);
2593     }
2594   else
2595     {
2596       // Recursively process all descendants
2597       int dsize = NUM_DESCENDANTS (node);
2598       for (int index = 0; index < dsize; index++)
2599         get_cstack_list (lam, node->descendants->fetch (index), dpth + 1);
2600     }
2601 }
2602
2603 Emsg *
2604 PathTree::fetch_stats ()
2605 {
2606   if (statsq == NULL)
2607     return NULL;
2608   return statsq->fetch ();
2609 }
2610
2611 void
2612 PathTree::delete_stats ()
2613 {
2614   if (statsq != NULL)
2615     {
2616       delete statsq;
2617       statsq = new Emsgqueue (NTXT ("statsq"));
2618     }
2619 }
2620
2621 Emsg *
2622 PathTree::fetch_warnings ()
2623 {
2624   if (warningq == NULL)
2625     return NULL;
2626   return warningq->fetch ();
2627 }
2628
2629 void
2630 PathTree::delete_warnings ()
2631 {
2632   if (warningq != NULL)
2633     {
2634       delete warningq;
2635       warningq = new Emsgqueue (NTXT ("warningq"));
2636     }
2637 }