aboutsummaryrefslogtreecommitdiff
path: root/gprofng/src/PathTree.h
blob: 542e40fa0a2a37aaa5ac8a44b695bf909ba16085 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
/* Copyright (C) 2021-2024 Free Software Foundation, Inc.
   Contributed by Oracle.

   This file is part of GNU Binutils.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, 51 Franklin Street - Fifth Floor, Boston,
   MA 02110-1301, USA.  */

#ifndef _PATH_TREE_H
#define _PATH_TREE_H

#include <vec.h>
#include <Map.h>

#include "dbe_structs.h"
#include "Hist_data.h"
#include "Histable.h"
#include "Metric.h"

typedef enum
{
  NORMAL = 0, CANCELED
} PtreePhaseStatus;

class PathTree
{
public:

  PathTree (DbeView *_dbev, int _indxtype = -1)
  {
    construct (_dbev, _indxtype, PATHTREE_MAIN);
  }

  ~PathTree ();

  static void make_deltas (int vtype, TValue *v1, TValue *v2);
  static void make_ratios (int vtype, TValue *v1, TValue *v2);

  typedef enum
  {
    COMPUTEOPT_NONE = 0,
    COMPUTEOPT_OMP_CALLEE
  } PtreeComputeOption;

  Hist_data *compute_metrics (MetricList *, Histable::Type,
			      Hist_data::Mode, Vector<Histable*>*,
			      Histable*, Vector<Histable*>* sel_objs = NULL,
			      PtreeComputeOption flag = COMPUTEOPT_NONE);
  // Get aggregated callstack data
  CStack_data *get_cstack_data (MetricList *);

  Vector<Histable*> *get_clr_instr (Histable *);
  Vector<void*> *get_cle_instr (Histable *, Vector<Histable*>*&);

  int
  get_status ()
  {
    return status;
  }

  int
  get_depth ()
  {
    return depth;
  }

  int
  getStackProp ()
  {
    return stack_prop;
  }

  typedef long NodeIdx;

  struct Node
  {
    inline void
    reset ()
    {
      ancestor = 0;
      descendants = NULL;
      instr = NULL;
      funclist = 0;
    }

    NodeIdx ancestor;
    Vector<NodeIdx> *descendants;
    Histable *instr;
    NodeIdx funclist;
  };

  static const int CHUNKSZ = 16384;

  inline Node *
  NODE_IDX (NodeIdx idx)
  {
    return idx ? &chunks[idx / CHUNKSZ][idx % CHUNKSZ] : NULL;
  }

  // queue for messages (statistics for pathtree processing)
  Emsg *fetch_stats (void);     // fetch the queue of comment messages
  void delete_stats (void);     // delete the queue of stats messages
  Emsg *fetch_warnings (void);  // fetch the queue of warnings messages
  void delete_warnings (void);  // delete the queue of warnings messages

  NodeIdx
  get_func_nodeidx (Function * func)
  {
    return fn_map == NULL ? (NodeIdx) 0 : fn_map->get (func);
  }

  void print (FILE *);
  void dumpNodes (FILE *, Histable *);

  // flame charts functions - get values from ftree_internal
  int get_ftree_depth ();   // Depth of tree
  Vector<void*>* get_ftree_level (BaseMetric *bm, int dpth);
  Vector<void*>* get_ftree_node_children (BaseMetric *bm, NodeIdx node_idx);
  Vector<Function*>* get_ftree_funcs ();
  Vector<Function*>* get_funcs ();      // Unique functions in tree

private:

  enum
  {
    MAX_DESC_HTABLE_SZ = 65535
  };

  typedef struct hash_node
  {
    NodeIdx nd;
    struct hash_node *next;
  } hash_node_t;

  int desc_htable_size;
  int desc_htable_nelem;
  hash_node_t **descHT;

  struct Slot
  {
    int id;
    ValueTag vtype;
    union
    {
      int **mvals;
      int64_t **mvals64;
    };
  };

  typedef enum
  {
    PATHTREE_MAIN = 0,
    PATHTREE_INTERNAL_OMP,
    PATHTREE_INTERNAL_FUNCTREE
  } PathTreeType;

  DbeView *dbev;
  int indxtype;
  int stack_prop;
  Expression *indx_expr;
  Histable *total_obj;
  Map<Function*, NodeIdx> *fn_map;
  Map<uint64_t, NodeIdx> *pathMap;
  Map<uint64_t, uint64_t> *hideMap;
  int status;
  NodeIdx root_idx;
  Node *root;
  int depth;
  long nodes;
  long dnodes;
  long nchunks;
  Node **chunks;
  int nslots;
  Slot *slots;
  int phaseIdx;
  int nexps;
  Emsgqueue *statsq;
  Emsgqueue *warningq;
  Hist_data *hist_data;
  int percent;
  int ndone;
  Histable **obj_list;
  Node **node_list;
  int *xlate;
  bool cancel_ok;
  PathTreeType pathTreeType;
  PathTree *ptree_internal;
  PathTree *ftree_internal;             // function-based pathtree
  bool ftree_needs_update;
  Vector<Vector<NodeIdx>*> *depth_map; // for each depth level, list of nodes

  void init ();
  void fini ();
  PtreePhaseStatus reset ();
  PtreePhaseStatus add_experiment (int);
  PtreePhaseStatus process_packets (Experiment*, DataView*, int);
  DataView *get_filtered_events (int exp_index, int data_type);
  void construct (DbeView *_dbev, int _indxtype, PathTreeType _pathTreeType);

  PathTree (DbeView *_dbev, int _indxtype, PathTreeType _pathTreeType)
  {
    construct (_dbev, _indxtype, _pathTreeType);
  }

  inline int *
  allocate_chunk (int **p, NodeIdx idx)
  {
    int *res = new int[CHUNKSZ];
    for (int i = 0; i < CHUNKSZ; i++)
      res[i] = 0;
    p[idx] = res;
    return res;
  };

  inline int64_t *
  allocate_chunk (int64_t **p, NodeIdx idx)
  {
    int64_t *res = new int64_t[CHUNKSZ];
    for (int i = 0; i < CHUNKSZ; i++)
      res[i] = 0;
    p[idx] = res;
    return res;
  };

  inline Node *
  allocate_chunk (Node **p, NodeIdx idx)
  {
    Node *res = new Node[CHUNKSZ];
    for (int i = 0; i < CHUNKSZ; i++)
      res[i].reset ();
    p[idx] = res;
    return res;
  };

  inline bool
  IS_MVAL_ZERO (Slot& slot, NodeIdx idx)
  {
    if (slot.vtype == VT_LLONG || slot.vtype == VT_ULLONG)
      {
	int64_t *tmp = slot.mvals64[idx / CHUNKSZ];
	return tmp ? tmp[idx % CHUNKSZ] == 0 : true;
      }
    else
      {
	int *tmp = slot.mvals[idx / CHUNKSZ];
	return tmp ? tmp[idx % CHUNKSZ] == 0 : true;
      }
  }

  inline void
  ASN_METRIC_VAL (TValue& v, Slot& slot, NodeIdx idx)
  {
    if (slot.vtype == VT_LLONG)
      {
	int64_t *tmp = slot.mvals64[idx / CHUNKSZ];
	if (tmp)
	  v.ll = tmp[idx % CHUNKSZ];
      }
    else if (slot.vtype == VT_ULLONG)
      {
	uint64_t *tmp = (uint64_t *) slot.mvals64[idx / CHUNKSZ];
	if (tmp)
	  v.ull = tmp[idx % CHUNKSZ];
      }
    else
      {
	int *tmp = slot.mvals[idx / CHUNKSZ];
	if (tmp)
	  v.i = tmp[idx % CHUNKSZ];
      }
  }

  inline void
  ADD_METRIC_VAL (TValue& v, Slot& slot, NodeIdx idx)
  {
    if (slot.vtype == VT_LLONG)
      {
	int64_t *tmp = slot.mvals64[idx / CHUNKSZ];
	if (tmp)
	  v.ll += tmp[idx % CHUNKSZ];
      }
    else if (slot.vtype == VT_ULLONG)
      {
	uint64_t *tmp = (uint64_t *) slot.mvals64[idx / CHUNKSZ];
	if (tmp)
	  v.ull += tmp[idx % CHUNKSZ];
      }
    else
      {
	int *tmp = slot.mvals[idx / CHUNKSZ];
	if (tmp) v.i += tmp[idx % CHUNKSZ];
      }
  }

  inline void
  SUB_METRIC_VAL (TValue& v, Slot& slot, NodeIdx idx)
  {
    if (slot.vtype == VT_LLONG)
      {
	int64_t *tmp = slot.mvals64[idx / CHUNKSZ];
	if (tmp)
	  v.ll -= tmp[idx % CHUNKSZ];
      }
    else if (slot.vtype == VT_ULLONG)
      {
	uint64_t *tmp = (uint64_t *) slot.mvals64[idx / CHUNKSZ];
	if (tmp)
	  v.ull -= tmp[idx % CHUNKSZ];
      }
    else
      {
	int *tmp = slot.mvals[idx / CHUNKSZ];
	if (tmp)
	  v.i -= tmp[idx % CHUNKSZ];
      }
  }

  inline void
  INCREMENT_METRIC (Slot *slot, NodeIdx idx, int64_t val)
  {
    if (slot->vtype == VT_LLONG)
      {
	int64_t *tmp = slot->mvals64[idx / CHUNKSZ];
	if (tmp == NULL)
	  tmp = allocate_chunk (slot->mvals64, idx / CHUNKSZ);
	tmp[idx % CHUNKSZ] += val;
      }
    else if (slot->vtype == VT_ULLONG)
      {
	uint64_t *tmp = (uint64_t *) slot->mvals64[idx / CHUNKSZ];
	if (tmp == NULL)
	  tmp = (uint64_t *) allocate_chunk (slot->mvals64, idx / CHUNKSZ);
	tmp[idx % CHUNKSZ] += val;
      }
    else
      {
	int *tmp = slot->mvals[idx / CHUNKSZ];
	if (tmp == NULL)
	  tmp = allocate_chunk (slot->mvals, idx / CHUNKSZ);
	tmp[idx % CHUNKSZ] += (int) val;
      }
  }

  inline Slot *
  SLOT_IDX (int idx)
  {
    if (idx < 0 || idx >= nslots)
      return NULL;
    return &slots[idx];
  }

  int allocate_slot (int id, ValueTag vtype);
  void allocate_slots (Slot *slots, int nslots);
  int find_slot (int);
  NodeIdx new_Node (NodeIdx, Histable*, bool);
  NodeIdx find_path (Experiment*, DataView*, long);
  NodeIdx find_desc_node (NodeIdx, Histable*, bool);
  NodeIdx find_in_desc_htable (NodeIdx, Histable*, bool);
  Histable *get_hist_obj (Node *, Histable* = NULL);
  Histable *get_hist_func_obj (Node *);
  Histable *get_compare_obj (Histable *obj);
  void get_metrics (NodeIdx, int);
  void get_metrics (Vector<Function*> *, Histable *);
  void get_clr_metrics (Vector<Histable*>*, NodeIdx, int, int);
  void get_clr_metrics (Vector<Histable*>*);
  void get_cle_metrics (Vector<Histable*>*, NodeIdx, int, int, int);
  void get_cle_metrics (Vector<Histable*>*, NodeIdx, int);
  void get_cle_metrics (Vector<Histable*>*);
  void get_self_metrics (Vector<Histable*>*, NodeIdx, bool, int);
  void get_self_metrics (Vector<Histable*>*);
  void get_self_metrics (Histable *, Vector<Function*> *funclist,
			 Vector<Histable*>* sel_objs = NULL);
  void get_cstack_list (CStack_data *, NodeIdx, int);

  // Generate PathTree based on Functions instead of Instructions // Used for flame chart
  void ftree_reset ();
  void ftree_build (PathTree *mstr);
  void ftree_build (PathTree *mstr, NodeIdx mstr_node_idx, NodeIdx local_node_idx);
  void depth_map_build ();
  void depth_map_build (NodeIdx node_idx, int depth);
  Vector<void*>* get_level (BaseMetric *bm, int dpth);
  Vector<void*>* get_nodes (BaseMetric *bm, Vector<NodeIdx> *node_idxs);
  Vector<void*>* get_node_children (BaseMetric *bm, NodeIdx node_idx);
  bool ftree_debug_match_hist_data (Hist_data *data, Hist_data *data_tmp);
  void ftree_dump ();

  // Debugging functions
  void print (FILE *, PathTree::Node*, int);
  void printn (FILE *);
  int dbg_nodes (PathTree::Node*);
};

#endif /* _PATH_TREE_H */