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
construct(DbeView * _dbev,int _indxtype,PathTreeType _pathTreeType)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
~PathTree()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
init()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
fini()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
reset()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
allocate_slot(int id,ValueTag vtype)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
allocate_slots(Slot * new_slots,int new_nslots)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
find_slot(int id)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
new_Node(NodeIdx anc,Histable * instr,bool leaf)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
find_path(Experiment * exp,DataView * dview,long recIdx)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
desc_node_comp(const void * s1,const void * s2,const void * ptree)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
find_in_desc_htable(NodeIdx node_idx,Histable * instr,bool leaf)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
find_desc_node(NodeIdx node_idx,Histable * instr,bool leaf)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
process_packets(Experiment * exp,DataView * packets,int data_type)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 *
get_filtered_events(int exp_index,int data_type)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
add_experiment(int exp_index)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 *
compute_metrics(MetricList * mlist,Histable::Type type,Hist_data::Mode mode,Vector<Histable * > * objs,Histable * context,Vector<Histable * > * sel_objs,PtreeComputeOption computeOpt)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
ftree_debug_match_hist_data(Hist_data * data,Hist_data * data_tmp)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 *
get_hist_func_obj(Node * node)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 *
get_hist_obj(Node * node,Histable * context)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 *
get_compare_obj(Histable * obj)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
get_metrics(NodeIdx node_idx,int dpth)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
get_clr_metrics(Vector<Histable * > * objs,NodeIdx node_idx,int pmatch,int dpth)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
get_clr_metrics(Vector<Histable * > * objs)1561 PathTree::get_clr_metrics (Vector<Histable*> *objs)
1562 {
1563 get_clr_metrics (objs, root_idx, -1, 0);
1564 }
1565
1566 void
get_cle_metrics(Vector<Histable * > * objs,NodeIdx node_idx,int pcle,int pmatch,int dpth)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
get_cle_metrics(Vector<Histable * > * objs,NodeIdx node_idx,int dpth)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
ftree_reset()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
ftree_build(PathTree * mstr)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
ftree_dump()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
ftree_build(PathTree * mstr,NodeIdx mstr_node_idx,NodeIdx local_node_idx)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
depth_map_build()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
depth_map_build(NodeIdx node_idx,int dpth)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
get_ftree_depth()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*>*
get_ftree_funcs()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*>*
get_funcs()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*>*
get_ftree_level(BaseMetric * bm,int dpth)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*>*
get_level(BaseMetric * bm,int dpth)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*>*
get_ftree_node_children(BaseMetric * bm,NodeIdx node_idx)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*>*
get_node_children(BaseMetric * bm,NodeIdx node_idx)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*>*
get_nodes(BaseMetric * bm,Vector<NodeIdx> * node_idxs)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
get_cle_metrics(Vector<Histable * > * objs)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
get_metrics(Vector<Function * > * functions,Histable * context)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
get_self_metrics(Vector<Histable * > * objs,NodeIdx node_idx,bool seen,int dpth)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
get_self_metrics(Vector<Histable * > * objs)2185 PathTree::get_self_metrics (Vector<Histable*> *objs)
2186 {
2187 get_self_metrics (objs, root_idx, false, 0);
2188 }
2189
2190 void
get_self_metrics(Histable * obj,Vector<Function * > * funclist,Vector<Histable * > * sel_objs)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*> *
get_clr_instr(Histable * func)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*> *
get_cle_instr(Histable * func,Vector<Histable * > * & instrs)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
print(FILE * fd)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
print(FILE * fd,PathTree::Node * node,int lvl)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
printn(FILE * fd)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
dumpNodes(FILE * fd,Histable * obj)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
dbg_nodes(PathTree::Node * node)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
leak_alloc_comp(const void * s1,const void * s2)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 *
get_cstack_data(MetricList * mlist)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
get_cstack_list(CStack_data * lam,NodeIdx node_idx,int dpth)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 *
fetch_stats()2604 PathTree::fetch_stats ()
2605 {
2606 if (statsq == NULL)
2607 return NULL;
2608 return statsq->fetch ();
2609 }
2610
2611 void
delete_stats()2612 PathTree::delete_stats ()
2613 {
2614 if (statsq != NULL)
2615 {
2616 delete statsq;
2617 statsq = new Emsgqueue (NTXT ("statsq"));
2618 }
2619 }
2620
2621 Emsg *
fetch_warnings()2622 PathTree::fetch_warnings ()
2623 {
2624 if (warningq == NULL)
2625 return NULL;
2626 return warningq->fetch ();
2627 }
2628
2629 void
delete_warnings()2630 PathTree::delete_warnings ()
2631 {
2632 if (warningq != NULL)
2633 {
2634 delete warningq;
2635 warningq = new Emsgqueue (NTXT ("warningq"));
2636 }
2637 }
2638