Profiling.c 28.4 KB
Newer Older
1 2
/* -----------------------------------------------------------------------------
 *
3
 * (c) The GHC Team, 1998-2000
4 5 6 7 8
 *
 * Support for profiling
 *
 * ---------------------------------------------------------------------------*/

Ben Gamari's avatar
Ben Gamari committed
9
#if defined(PROFILING)
10

11
#include "PosixSource.h"
12
#include "Rts.h"
Simon Marlow's avatar
Simon Marlow committed
13

14
#include "RtsUtils.h"
15
#include "Profiling.h"
16
#include "Proftimer.h"
17
#include "ProfHeap.h"
18
#include "Arena.h"
19
#include "RetainerProfile.h"
20
#include "ProfilerReport.h"
Ben Gamari's avatar
Ben Gamari committed
21
#include "ProfilerReportJson.h"
22
#include "Printer.h"
23
#include "Capability.h"
24

25
#include <fs_rts.h>
26 27
#include <string.h>

Ben Gamari's avatar
Ben Gamari committed
28
#if defined(DEBUG)
29 30 31
#include "Trace.h"
#endif

32 33 34
/*
 * Profiling allocation arena.
 */
35 36 37
#if defined(DEBUG)
Arena *prof_arena;
#else
38
static Arena *prof_arena;
39
#endif
40 41

/*
42
 * Global variables used to assign unique IDs to cc's, ccs's, and
43 44 45
 * closure_cats
 */

46 47
static unsigned int CC_ID  = 1;
static unsigned int CCS_ID = 1;
48

49
/* Globals for opening the profiling log file(s)
50 51
 */
static char *prof_filename; /* prof report file name = <program>.prof */
52
FILE *prof_file;
53

54
static char *hp_filename;       /* heap profile (hp2ps style) log file */
55 56
FILE *hp_file;

57
// List of all cost centres. Used for reporting.
58
CostCentre      *CC_LIST  = NULL;
59 60 61
// All cost centre stacks temporarily appear here, to be able to make CCS_MAIN a
// parent of all cost centres stacks (done in initProfiling2()).
static CostCentreStack *CCS_LIST = NULL;
62

Ben Gamari's avatar
Ben Gamari committed
63
#if defined(THREADED_RTS)
64
static Mutex ccs_mutex;
65 66
#endif

67 68 69 70
/*
 * Built-in cost centres and cost-centre stacks:
 *
 *    MAIN   is the root of the cost-centre stack tree.  If there are
71
 *           no {-# SCC #-}s in the program, all costs will be attributed
72 73 74 75 76 77 78 79 80 81 82 83 84 85
 *           to MAIN.
 *
 *    SYSTEM is the RTS in general (scheduler, etc.).  All costs for
 *           RTS operations apart from garbage collection are attributed
 *           to SYSTEM.
 *
 *    GC     is the storage manager / garbage collector.
 *
 *    OVERHEAD gets all costs generated by the profiling system
 *           itself.  These are costs that would not be incurred
 *           during non-profiled execution of the program.
 *
 *    DONT_CARE is a placeholder cost-centre we assign to static
 *           constructors.  It should *never* accumulate any costs.
86 87 88 89
 *
 *    PINNED accumulates memory allocated to pinned objects, which
 *           cannot be profiled separately because we cannot reliably
 *           traverse pinned memory.
90 91
 */

92 93 94 95 96 97 98
CC_DECLARE(CC_MAIN,      "MAIN",        "MAIN",      "<built-in>", CC_NOT_CAF, );
CC_DECLARE(CC_SYSTEM,    "SYSTEM",      "SYSTEM",    "<built-in>", CC_NOT_CAF, );
CC_DECLARE(CC_GC,        "GC",          "GC",        "<built-in>", CC_NOT_CAF, );
CC_DECLARE(CC_OVERHEAD,  "OVERHEAD_of", "PROFILING", "<built-in>", CC_NOT_CAF, );
CC_DECLARE(CC_DONT_CARE, "DONT_CARE",   "MAIN",      "<built-in>", CC_NOT_CAF, );
CC_DECLARE(CC_PINNED,    "PINNED",      "SYSTEM",    "<built-in>", CC_NOT_CAF, );
CC_DECLARE(CC_IDLE,      "IDLE",        "IDLE",      "<built-in>", CC_NOT_CAF, );
99

100 101
CCS_DECLARE(CCS_MAIN,       CC_MAIN,       );
CCS_DECLARE(CCS_SYSTEM,     CC_SYSTEM,     );
102 103
CCS_DECLARE(CCS_GC,         CC_GC,         );
CCS_DECLARE(CCS_OVERHEAD,   CC_OVERHEAD,   );
104 105
CCS_DECLARE(CCS_DONT_CARE,  CC_DONT_CARE,  );
CCS_DECLARE(CCS_PINNED,     CC_PINNED,     );
106
CCS_DECLARE(CCS_IDLE,       CC_IDLE,       );
107

108
/*
109 110 111
 * Static Functions
 */

112 113 114 115 116
static  CostCentreStack * appendCCS       ( CostCentreStack *ccs1,
                                            CostCentreStack *ccs2 );
static  CostCentreStack * actualPush_     ( CostCentreStack *ccs, CostCentre *cc,
                                            CostCentreStack *new_ccs );
static  void              inheritCosts    ( CostCentreStack *ccs );
117
static  ProfilerTotals    countTickss     ( CostCentreStack const *ccs );
118 119
static  CostCentreStack * checkLoop       ( CostCentreStack *ccs,
                                            CostCentre *cc );
120
static  void              sortCCSTree     ( CostCentreStack *ccs );
121
static  CostCentreStack * pruneCCSTree    ( CostCentreStack *ccs );
122 123 124
static  CostCentreStack * actualPush      ( CostCentreStack *, CostCentre * );
static  CostCentreStack * isInIndexTable  ( IndexTable *, CostCentre * );
static  IndexTable *      addToIndexTable ( IndexTable *, CostCentreStack *,
125
                                            CostCentre *, bool );
126
static  void              ccsSetSelected  ( CostCentreStack *ccs );
Ben Gamari's avatar
Ben Gamari committed
127
static  void              aggregateCCCosts( CostCentreStack *ccs );
128 129
static  void              registerCC      ( CostCentre *cc );
static  void              registerCCS     ( CostCentreStack *ccs );
130

131 132
static  void              initTimeProfiling    ( void );
static  void              initProfilingLogFile ( void );
133 134 135 136 137

/* -----------------------------------------------------------------------------
   Initialise the profiling environment
   -------------------------------------------------------------------------- */

138
void initProfiling (void)
139
{
140 141
    // initialise our arena
    prof_arena = newArena();
142

143
    /* for the benefit of allocate()... */
144
    {
145
        uint32_t n;
146
        for (n=0; n < n_capabilities; n++) {
147
            capabilities[n]->r.rCCCS = CCS_SYSTEM;
148 149
        }
    }
150

Ben Gamari's avatar
Ben Gamari committed
151
#if defined(THREADED_RTS)
152 153
    initMutex(&ccs_mutex);
#endif
154 155 156 157 158 159 160 161 162

    /* Set up the log file, and dump the header and cost centre
     * information into it.
     */
    initProfilingLogFile();

    /* Register all the cost centres / stacks in the program
     * CC_MAIN gets link = 0, all others have non-zero link.
     */
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
    registerCC(CC_MAIN);
    registerCC(CC_SYSTEM);
    registerCC(CC_GC);
    registerCC(CC_OVERHEAD);
    registerCC(CC_DONT_CARE);
    registerCC(CC_PINNED);
    registerCC(CC_IDLE);

    registerCCS(CCS_SYSTEM);
    registerCCS(CCS_GC);
    registerCCS(CCS_OVERHEAD);
    registerCCS(CCS_DONT_CARE);
    registerCCS(CCS_PINNED);
    registerCCS(CCS_IDLE);
    registerCCS(CCS_MAIN);
178 179 180 181 182 183 184 185 186 187

    /* find all the registered cost centre stacks, and make them
     * children of CCS_MAIN.
     */
    ASSERT(CCS_LIST == CCS_MAIN);
    CCS_LIST = CCS_LIST->prevStack;
    CCS_MAIN->prevStack = NULL;
    CCS_MAIN->root = CCS_MAIN;
    ccsSetSelected(CCS_MAIN);

188
    initProfiling2();
189 190 191

    if (RtsFlags.CcFlags.doCostCentres) {
        initTimeProfiling();
192 193
    }

194 195 196
    if (RtsFlags.ProfFlags.doHeapProfile) {
        initHeapProfiling();
    }
197 198
}

199 200 201 202 203 204
//
// Should be called after loading any new Haskell code.
//
void initProfiling2 (void)
{
    // make CCS_MAIN the parent of all the pre-defined CCSs.
205 206
    CostCentreStack *next;
    for (CostCentreStack *ccs = CCS_LIST; ccs != NULL; ) {
207 208 209 210 211 212 213 214 215 216 217 218 219 220
        next = ccs->prevStack;
        ccs->prevStack = NULL;
        actualPush_(CCS_MAIN,ccs->cc,ccs);
        ccs->root = ccs;
        ccs = next;
    }
    CCS_LIST = NULL;
}

void
freeProfiling (void)
{
    arenaFree(prof_arena);
}
221

222 223 224 225 226 227
CostCentre *mkCostCentre (char *label, char *module, char *srcloc)
{
    CostCentre *cc = stgMallocBytes (sizeof(CostCentre), "mkCostCentre");
    cc->label = label;
    cc->module = module;
    cc->srcloc = srcloc;
Simon Marlow's avatar
Simon Marlow committed
228 229 230 231
    cc->is_caf = 0;
    cc->mem_alloc = 0;
    cc->time_ticks = 0;
    cc->link = NULL;
232 233 234
    return cc;
}

235 236
static void
initProfilingLogFile(void)
237
{
238 239 240 241 242 243 244 245 246
    // Figure out output file name stem.
    char const *stem;
    if (RtsFlags.CcFlags.outputFileNameStem) {
        stem = RtsFlags.CcFlags.outputFileNameStem;
    } else {
        char *prog;

        prog = arenaAlloc(prof_arena, strlen(prog_name) + 1);
        strcpy(prog, prog_name);
Ben Gamari's avatar
Ben Gamari committed
247
#if defined(mingw32_HOST_OS)
248 249 250 251 252 253 254
        // on Windows, drop the .exe suffix if there is one
        {
            char *suff;
            suff = strrchr(prog,'.');
            if (suff != NULL && !strcmp(suff,".exe")) {
                *suff = '\0';
            }
255 256
        }
#endif
257 258
        stem = prog;
    }
259

260
    if (RtsFlags.CcFlags.doCostCentres == 0 && !doingRetainerProfiling())
261
    {
262
        /* No need for the <stem>.prof file */
263 264
        prof_filename = NULL;
        prof_file = NULL;
265
    }
266 267 268
    else
    {
        /* Initialise the log file name */
269 270
        prof_filename = arenaAlloc(prof_arena, strlen(stem) + 6);
        sprintf(prof_filename, "%s.prof", stem);
271 272

        /* open the log file */
273
        if ((prof_file = __rts_fopen(prof_filename, "w")) == NULL) {
274 275
            debugBelch("Can't open profiling report file %s\n", prof_filename);
            RtsFlags.CcFlags.doCostCentres = 0;
276 277 278
            // Retainer profiling (`-hr` or `-hr<cc> -h<x>`) writes to
            // both <program>.hp as <program>.prof.
            if (doingRetainerProfiling()) {
279
                RtsFlags.ProfFlags.doHeapProfile = 0;
280
            }
281
        }
282
    }
283

284
    if (RtsFlags.ProfFlags.doHeapProfile) {
285
        /* Initialise the log file name */
286 287
        hp_filename = arenaAlloc(prof_arena, strlen(stem) + 6);
        sprintf(hp_filename, "%s.hp", stem);
288 289

        /* open the log file */
290
        if ((hp_file = __rts_fopen(hp_filename, "w")) == NULL) {
291
            debugBelch("Can't open profiling report file %s\n",
292
                       hp_filename);
293 294
            RtsFlags.ProfFlags.doHeapProfile = 0;
        }
295 296 297 298 299 300
    }
}

void
initTimeProfiling(void)
{
301 302
    /* Start ticking */
    startProfTimer();
303 304
};

305
void
306 307
endProfiling ( void )
{
308 309 310 311 312 313
    if (RtsFlags.CcFlags.doCostCentres) {
        stopProfTimer();
    }
    if (RtsFlags.ProfFlags.doHeapProfile) {
        endHeapProfiling();
    }
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
/* -----------------------------------------------------------------------------
   Registering CCs and CCSs

   Registering a CC or CCS consists of
     - assigning it a unique ID
     - linking it onto the list of registered CCs/CCSs

   Cost centres are registered at startup by a C constructor function
   generated by the compiler (ProfInit.hs) in the _stub.c file for each module.
 -------------------------------------------------------------------------- */

static void
registerCC(CostCentre *cc)
{
    if (cc->link == NULL) {
        cc->link = CC_LIST;
        CC_LIST = cc;
        cc->ccID = CC_ID++;
    }
}

static void registerCCS(CostCentreStack *ccs)
{
    if (ccs->prevStack == NULL) {
        ccs->prevStack = CCS_LIST;
        CCS_LIST = ccs;
        ccs->ccsID = CCS_ID++;
    }
}
345 346 347 348

void registerCcList(CostCentre **cc_list)
{
    for (CostCentre **i = cc_list; *i != NULL; i++) {
349
        registerCC(*i);
350 351 352 353 354 355
    }
}

void registerCcsList(CostCentreStack **cc_list)
{
    for (CostCentreStack **i = cc_list; *i != NULL; i++) {
356
        registerCCS(*i);
357 358 359
    }
}

360
/* -----------------------------------------------------------------------------
361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380
   Set CCCS when entering a function.

   The algorithm is as follows.

     ccs ++> ccsfn  =  ccs ++ dropCommonPrefix ccs ccsfn

   where

     dropCommonPrefix A B
        -- returns the suffix of B after removing any prefix common
        -- to both A and B.

   e.g.

     <a,b,c> ++> <>      = <a,b,c>
     <a,b,c> ++> <d>     = <a,b,c,d>
     <a,b,c> ++> <a,b>   = <a,b,c>
     <a,b>   ++> <a,b,c> = <a,b,c>
     <a,b,c> ++> <a,b,d> = <a,b,c,d>

381 382
   -------------------------------------------------------------------------- */

383 384
// implements  c1 ++> c2,  where c1 and c2 are equal depth
//
385 386 387 388
static CostCentreStack *
enterFunEqualStacks (CostCentreStack *ccs0,
                     CostCentreStack *ccsapp,
                     CostCentreStack *ccsfn)
389
{
390 391 392 393 394 395
    ASSERT(ccsapp->depth == ccsfn->depth);
    if (ccsapp == ccsfn) return ccs0;
    return pushCostCentre(enterFunEqualStacks(ccs0,
                                              ccsapp->prevStack,
                                              ccsfn->prevStack),
                          ccsfn->cc);
396 397 398 399 400 401 402
}

// implements  c1 ++> c2,  where c2 is deeper than c1.
// Drop elements of c2 until we have equal stacks, call
// enterFunEqualStacks(), and then push on the elements that we
// dropped in reverse order.
//
403 404
static CostCentreStack *
enterFunCurShorter (CostCentreStack *ccsapp, CostCentreStack *ccsfn, StgWord n)
405 406
{
    if (n == 0) {
407 408 409 410 411 412
        ASSERT(ccsfn->depth == ccsapp->depth);
        return enterFunEqualStacks(ccsapp,ccsapp,ccsfn);;
    } else {
        ASSERT(ccsfn->depth > ccsapp->depth);
        return pushCostCentre(enterFunCurShorter(ccsapp, ccsfn->prevStack, n-1),
                              ccsfn->cc);
413 414 415
    }
}

416
void enterFunCCS (StgRegTable *reg, CostCentreStack *ccsfn)
417
{
418 419
    CostCentreStack *ccsapp;

420
    // common case 1: both stacks are the same
421
    if (ccsfn == reg->rCCCS) {
422 423 424 425
        return;
    }

    // common case 2: the function stack is empty, or just CAF
Simon Marlow's avatar
Simon Marlow committed
426
    if (ccsfn->cc->is_caf) {
427 428 429
        return;
    }

430 431 432
    ccsapp = reg->rCCCS;
    reg->rCCCS = CCS_OVERHEAD;

433 434 435
    // common case 3: the stacks are completely different (e.g. one is a
    // descendent of MAIN and the other of a CAF): we append the whole
    // of the function stack to the current CCS.
436 437
    if (ccsfn->root != ccsapp->root) {
        reg->rCCCS = appendCCS(ccsapp,ccsfn);
438 439 440
        return;
    }

441 442
    // uncommon case 4: ccsapp is deeper than ccsfn
    if (ccsapp->depth > ccsfn->depth) {
443
        uint32_t i, n;
444 445
        CostCentreStack *tmp = ccsapp;
        n = ccsapp->depth - ccsfn->depth;
446 447 448
        for (i = 0; i < n; i++) {
            tmp = tmp->prevStack;
        }
449
        reg->rCCCS = enterFunEqualStacks(ccsapp,tmp,ccsfn);
450 451 452 453
        return;
    }

    // uncommon case 5: ccsfn is deeper than CCCS
454 455 456
    if (ccsfn->depth > ccsapp->depth) {
        reg->rCCCS = enterFunCurShorter(ccsapp, ccsfn,
                                        ccsfn->depth - ccsapp->depth);
457 458
        return;
    }
459

460
    // uncommon case 6: stacks are equal depth, but different
461
    reg->rCCCS = enterFunEqualStacks(ccsapp,ccsapp,ccsfn);
462 463 464 465 466 467 468 469 470 471 472 473 474
}

/* -----------------------------------------------------------------------------
   Decide whether closures with this CCS should contribute to the heap
   profile.
   -------------------------------------------------------------------------- */

static void
ccsSetSelected (CostCentreStack *ccs)
{
    if (RtsFlags.ProfFlags.modSelector) {
        if (! strMatchesSelector (ccs->cc->module,
                                  RtsFlags.ProfFlags.modSelector) ) {
475
            ccs->selected = 0;
476 477 478 479 480 481
            return;
        }
    }
    if (RtsFlags.ProfFlags.ccSelector) {
        if (! strMatchesSelector (ccs->cc->label,
                                  RtsFlags.ProfFlags.ccSelector) ) {
482
            ccs->selected = 0;
483 484 485 486
            return;
        }
    }
    if (RtsFlags.ProfFlags.ccsSelector) {
487
        CostCentreStack *c;
488 489 490 491
        for (c = ccs; c != NULL; c = c->prevStack)
        {
            if ( strMatchesSelector (c->cc->label,
                                     RtsFlags.ProfFlags.ccsSelector) ) {
492 493 494
                break;
            }
        }
495 496 497 498 499 500 501 502
        if (c == NULL) {
            ccs->selected = 0;
            return;
        }
    }

    ccs->selected = 1;
    return;
503 504
}

505 506 507 508
/* -----------------------------------------------------------------------------
   Cost-centre stack manipulation
   -------------------------------------------------------------------------- */

509 510
/* Append ccs1 to ccs2 (ignoring any CAF cost centre at the root of ccs1 */
CostCentreStack *
511 512
appendCCS ( CostCentreStack *ccs1, CostCentreStack *ccs2 )
{
513 514 515 516 517 518 519
    IF_DEBUG(prof,
            if (ccs1 != ccs2) {
              debugBelch("Appending ");
              debugCCS(ccs1);
              debugBelch(" to ");
              debugCCS(ccs2);
              debugBelch("\n");});
520

521 522 523 524
    if (ccs1 == ccs2) {
        return ccs1;
    }

525
    if (ccs2 == CCS_MAIN || ccs2->cc->is_caf) {
526 527 528
        // stop at a CAF element
        return ccs1;
    }
529

530 531
    return pushCostCentre(appendCCS(ccs1, ccs2->prevStack), ccs2->cc);
}
532

533 534 535
// Pick one:
// #define RECURSION_DROPS
#define RECURSION_TRUNCATES
536

537 538 539
CostCentreStack *
pushCostCentre (CostCentreStack *ccs, CostCentre *cc)
{
540 541 542 543 544 545
    IF_DEBUG(prof,
             traceBegin("pushing %s on ", cc->label);
             debugCCS(ccs);
             traceEnd(););

    CostCentreStack *ret;
546 547 548 549 550 551 552 553

    if (ccs == EMPTY_STACK) {
        ACQUIRE_LOCK(&ccs_mutex);
        ret = actualPush(ccs,cc);
    }
    else
    {
        if (ccs->cc == cc) {
554
            return ccs;
555
        } else {
556
            // check if we've already memoized this stack
557 558
            IndexTable *ixtable = ccs->indexTable;
            CostCentreStack *temp_ccs = isInIndexTable(ixtable,cc);
559

560
            if (temp_ccs != EMPTY_STACK) {
561
                return temp_ccs;
562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578
            } else {

                // not in the IndexTable, now we take the lock:
                ACQUIRE_LOCK(&ccs_mutex);

                if (ccs->indexTable != ixtable)
                {
                    // someone modified ccs->indexTable while
                    // we did not hold the lock, so we must
                    // check it again:
                    temp_ccs = isInIndexTable(ixtable,cc);
                    if (temp_ccs != EMPTY_STACK)
                    {
                        RELEASE_LOCK(&ccs_mutex);
                        return temp_ccs;
                    }
                }
579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596
                temp_ccs = checkLoop(ccs,cc);
                if (temp_ccs != NULL) {
                    // This CC is already in the stack somewhere.
                    // This could be recursion, or just calling
                    // another function with the same CC.
                    // A number of policies are possible at this
                    // point, we implement two here:
                    //   - truncate the stack to the previous instance
                    //     of this CC
                    //   - ignore this push, return the same stack.
                    //
                    CostCentreStack *new_ccs;
#if defined(RECURSION_TRUNCATES)
                    new_ccs = temp_ccs;
#else // defined(RECURSION_DROPS)
                    new_ccs = ccs;
#endif
                    ccs->indexTable = addToIndexTable (ccs->indexTable,
597
                                                       new_ccs, cc, true);
598
                    ret = new_ccs;
599
                } else {
600
                    ret = actualPush (ccs,cc);
601 602 603 604
                }
            }
        }
    }
605 606 607

    RELEASE_LOCK(&ccs_mutex);
    return ret;
608
}
609

610
static CostCentreStack *
611
checkLoop (CostCentreStack *ccs, CostCentre *cc)
612
{
613 614 615 616 617 618
    while (ccs != EMPTY_STACK) {
        if (ccs->cc == cc)
            return ccs;
        ccs = ccs->prevStack;
    }
    return NULL;
619 620 621
}

static CostCentreStack *
622
actualPush (CostCentreStack *ccs, CostCentre *cc)
623
{
624
    CostCentreStack *new_ccs;
625

626 627
    // allocate space for a new CostCentreStack
    new_ccs = (CostCentreStack *) arenaAlloc(prof_arena, sizeof(CostCentreStack));
628

629
    return actualPush_(ccs, cc, new_ccs);
630 631
}

632
static CostCentreStack *
633
actualPush_ (CostCentreStack *ccs, CostCentre *cc, CostCentreStack *new_ccs)
634
{
635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659
    /* assign values to each member of the structure */
    new_ccs->ccsID = CCS_ID++;
    new_ccs->cc = cc;
    new_ccs->prevStack = ccs;
    new_ccs->root = ccs->root;
    new_ccs->depth = ccs->depth + 1;

    new_ccs->indexTable = EMPTY_TABLE;

    /* Initialise the various _scc_ counters to zero
     */
    new_ccs->scc_count        = 0;

    /* Initialize all other stats here.  There should be a quick way
     * that's easily used elsewhere too
     */
    new_ccs->time_ticks = 0;
    new_ccs->mem_alloc = 0;
    new_ccs->inherited_ticks = 0;
    new_ccs->inherited_alloc = 0;

    // Set the selected field.
    ccsSetSelected(new_ccs);

    /* update the memoization table for the parent stack */
660
    ccs->indexTable = addToIndexTable(ccs->indexTable, new_ccs, cc,
661
                                      false/*not a back edge*/);
662 663 664

    /* return a pointer to the new stack */
    return new_ccs;
665 666 667
}


668 669
static CostCentreStack *
isInIndexTable(IndexTable *it, CostCentre *cc)
670
{
671 672 673 674 675 676 677
    while (it!=EMPTY_TABLE)
    {
        if (it->cc == cc)
            return it->ccs;
        else
            it = it->next;
    }
678

679 680
    /* otherwise we never found it so return EMPTY_TABLE */
    return EMPTY_TABLE;
681 682 683
}


684 685
static IndexTable *
addToIndexTable (IndexTable *it, CostCentreStack *new_ccs,
686
                 CostCentre *cc, bool back_edge)
687
{
688
    IndexTable *new_it;
689

690 691 692 693 694 695 696
    new_it = arenaAlloc(prof_arena, sizeof(IndexTable));

    new_it->cc = cc;
    new_it->ccs = new_ccs;
    new_it->next = it;
    new_it->back_edge = back_edge;
    return new_it;
697 698
}

699 700 701 702
/* -----------------------------------------------------------------------------
   Generating a time & allocation profiling report.
   -------------------------------------------------------------------------- */

703 704 705
/* We omit certain system-related CCs and CCSs from the default
 * reports, so as not to cause confusion.
 */
706 707
bool
ignoreCC (CostCentre const *cc)
708
{
Ben Gamari's avatar
Ben Gamari committed
709
    return RtsFlags.CcFlags.doCostCentres < COST_CENTRES_ALL &&
710
        (   cc == CC_OVERHEAD
711 712
         || cc == CC_DONT_CARE
         || cc == CC_GC
713
         || cc == CC_SYSTEM
Ben Gamari's avatar
Ben Gamari committed
714
         || cc == CC_IDLE);
715 716
}

717
bool
718
ignoreCCS (CostCentreStack const *ccs)
719
{
Ben Gamari's avatar
Ben Gamari committed
720
    return RtsFlags.CcFlags.doCostCentres < COST_CENTRES_ALL &&
721 722 723
        (   ccs == CCS_OVERHEAD
         || ccs == CCS_DONT_CARE
         || ccs == CCS_GC
724
         || ccs == CCS_SYSTEM
Ben Gamari's avatar
Ben Gamari committed
725
         || ccs == CCS_IDLE);
726 727
}

728
void
729
reportCCSProfiling( void )
730 731
{
    stopProfTimer();
732
    if (RtsFlags.CcFlags.doCostCentres == 0) return;
733

734
    ProfilerTotals totals = countTickss(CCS_MAIN);
Ben Gamari's avatar
Ben Gamari committed
735
    aggregateCCCosts(CCS_MAIN);
736
    inheritCosts(CCS_MAIN);
737 738
    CostCentreStack *stack = pruneCCSTree(CCS_MAIN);
    sortCCSTree(stack);
Ben Gamari's avatar
Ben Gamari committed
739 740 741 742 743 744

    if (RtsFlags.CcFlags.doCostCentres == COST_CENTRES_JSON) {
        writeCCSReportJson(prof_file, stack, totals);
    } else {
        writeCCSReport(prof_file, stack, totals);
    }
745 746
}

747 748 749 750 751
/* -----------------------------------------------------------------------------
 * Accumulating total allocatinos and tick count
   -------------------------------------------------------------------------- */

/* Helper */
752
static void
753
countTickss_(CostCentreStack const *ccs, ProfilerTotals *totals)
754
{
755
    if (!ignoreCCS(ccs)) {
756 757
        totals->total_alloc += ccs->mem_alloc;
        totals->total_prof_ticks += ccs->time_ticks;
758
    }
759
    for (IndexTable *i = ccs->indexTable; i != NULL; i = i->next) {
760
        if (!i->back_edge) {
761
            countTickss_(i->ccs, totals);
762
        }
763 764 765 766 767 768 769 770 771 772 773 774
    }
}

/* Traverse the cost centre stack tree and accumulate
 * total ticks/allocations.
 */
static ProfilerTotals
countTickss(CostCentreStack const *ccs)
{
    ProfilerTotals totals = {0,0};
    countTickss_(ccs, &totals);
    return totals;
775 776
}

777 778 779
/* Traverse the cost centre stack tree and inherit ticks & allocs.
 */
static void
780
inheritCosts(CostCentreStack *ccs)
781
{
782
    IndexTable *i;
783

784
    if (ignoreCCS(ccs)) { return; }
785

786 787
    ccs->inherited_ticks += ccs->time_ticks;
    ccs->inherited_alloc += ccs->mem_alloc;
788

789 790 791 792 793 794 795 796
    for (i = ccs->indexTable; i != NULL; i = i->next)
        if (!i->back_edge) {
            inheritCosts(i->ccs);
            ccs->inherited_ticks += i->ccs->inherited_ticks;
            ccs->inherited_alloc += i->ccs->inherited_alloc;
        }

    return;
797 798
}

Ben Gamari's avatar
Ben Gamari committed
799 800 801 802 803 804 805 806 807 808 809 810 811 812 813
static void
aggregateCCCosts( CostCentreStack *ccs )
{
    IndexTable *i;

    ccs->cc->mem_alloc += ccs->mem_alloc;
    ccs->cc->time_ticks += ccs->time_ticks;

    for (i = ccs->indexTable; i != 0; i = i->next) {
        if (!i->back_edge) {
            aggregateCCCosts(i->ccs);
        }
    }
}

814 815 816 817
//
// Prune CCSs with zero entries, zero ticks or zero allocation from
// the tree, unless COST_CENTRES_ALL is on.
//
818
static CostCentreStack *
819
pruneCCSTree (CostCentreStack *ccs)
820
{
821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837
    CostCentreStack *ccs1;
    IndexTable *i, **prev;

    prev = &ccs->indexTable;
    for (i = ccs->indexTable; i != 0; i = i->next) {
        if (i->back_edge) { continue; }

        ccs1 = pruneCCSTree(i->ccs);
        if (ccs1 == NULL) {
            *prev = i->next;
        } else {
            prev = &(i->next);
        }
    }

    if ( (RtsFlags.CcFlags.doCostCentres >= COST_CENTRES_ALL
          /* force printing of *all* cost centres if -P -P */ )
838

839 840 841 842
         || ( ccs->indexTable != 0 )
         || ( ccs->scc_count || ccs->time_ticks || ccs->mem_alloc )
        ) {
        return ccs;
843
    } else {
844
        return NULL;
845 846 847
    }
}

848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904
static IndexTable*
insertIndexTableInSortedList(IndexTable* tbl, IndexTable* sortedList)
{
    StgWord tbl_ticks = tbl->ccs->scc_count;
    char*   tbl_label = tbl->ccs->cc->label;

    IndexTable *prev   = NULL;
    IndexTable *cursor = sortedList;

    while (cursor != NULL) {
        StgWord cursor_ticks = cursor->ccs->scc_count;
        char*   cursor_label = cursor->ccs->cc->label;

        if (tbl_ticks > cursor_ticks ||
                (tbl_ticks == cursor_ticks && strcmp(tbl_label, cursor_label) < 0)) {
            if (prev == NULL) {
                tbl->next = sortedList;
                return tbl;
            } else {
                prev->next = tbl;
                tbl->next = cursor;
                return sortedList;
            }
        } else {
            prev   = cursor;
            cursor = cursor->next;
        }
    }

    prev->next = tbl;
    return sortedList;
}

static void
sortCCSTree(CostCentreStack *ccs)
{
    if (ccs->indexTable == NULL) return;

    for (IndexTable *tbl = ccs->indexTable; tbl != NULL; tbl = tbl->next)
        if (!tbl->back_edge)
            sortCCSTree(tbl->ccs);

    IndexTable *sortedList    = ccs->indexTable;
    IndexTable *nonSortedList = sortedList->next;
    sortedList->next = NULL;

    while (nonSortedList != NULL)
    {
        IndexTable *nonSortedTail = nonSortedList->next;
        nonSortedList->next = NULL;
        sortedList = insertIndexTableInSortedList(nonSortedList, sortedList);
        nonSortedList = nonSortedTail;
    }

    ccs->indexTable = sortedList;
}

905
void
906
fprintCCS( FILE *f, CostCentreStack *ccs )
907
{
908 909 910 911 912 913 914 915
    fprintf(f,"<");
    for (; ccs && ccs != CCS_MAIN; ccs = ccs->prevStack ) {
        fprintf(f,"%s.%s", ccs->cc->module, ccs->cc->label);
        if (ccs->prevStack && ccs->prevStack != CCS_MAIN) {
            fprintf(f,",");
        }
    }
    fprintf(f,">");
916 917
}

918
// Returns: True if the call stack ended with CAF
Ben Gamari's avatar
Ben Gamari committed
919
static bool fprintCallStack (CostCentreStack *ccs)
920
{
921 922 923 924 925 926 927 928 929
    CostCentreStack *prev;

    fprintf(stderr,"%s.%s", ccs->cc->module, ccs->cc->label);
    prev = ccs->prevStack;
    while (prev && prev != CCS_MAIN) {
        ccs = prev;
        fprintf(stderr, ",\n  called from %s.%s",
                ccs->cc->module, ccs->cc->label);
        prev = ccs->prevStack;
930
    }
931
    fprintf(stderr, "\n");
932

933
    return (!strncmp(ccs->cc->label, "CAF", 3));
934 935
}

936 937
/* For calling from .cmm code, where we can't reliably refer to stderr */
void
938
fprintCCS_stderr (CostCentreStack *ccs, StgClosure *exception, StgTSO *tso)
939
{
Ben Gamari's avatar
Ben Gamari committed
940
    bool is_caf;
941 942 943
    StgPtr frame;
    StgStack *stack;
    CostCentreStack *prev_ccs;
944 945
    uint32_t depth = 0;
    const uint32_t MAX_DEPTH = 10; // don't print gigantic chains of stacks
946

947
    {
948 949 950
        const char *desc;
        const StgInfoTable *info;
        info = get_itbl(UNTAG_CONST_CLOSURE(exception));
951 952 953 954 955 956 957
        switch (info->type) {
        case CONSTR:
        case CONSTR_1_0:
        case CONSTR_0_1:
        case CONSTR_2_0:
        case CONSTR_1_1:
        case CONSTR_0_2:
Simon Marlow's avatar
Simon Marlow committed
958
        case CONSTR_NOCAF:
959
            desc = GET_CON_DESC(itbl_to_con_itbl(info));
960 961
            break;
       default:
962
            desc = closure_type_names[info->type];
963
            break;
964 965 966 967
        }
        fprintf(stderr, "*** Exception (reporting due to +RTS -xc): (%s), stack trace: \n  ", desc);
    }

968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010
    is_caf = fprintCallStack(ccs);

    // traverse the stack down to the enclosing update frame to
    // find out where this CCS was evaluated from...

    stack = tso->stackobj;
    frame = stack->sp;
    prev_ccs = ccs;

    for (; is_caf && depth < MAX_DEPTH; depth++)
    {
        switch (get_itbl((StgClosure*)frame)->type)
        {
        case UPDATE_FRAME:
            ccs = ((StgUpdateFrame*)frame)->header.prof.ccs;
            frame += sizeofW(StgUpdateFrame);
            if (ccs == CCS_MAIN) {
                goto done;
            }
            if (ccs == prev_ccs) {
                // ignore if this is the same as the previous stack,
                // we're probably in library code and haven't
                // accumulated any more interesting stack items
                // since the last update frame.
                break;
            }
            prev_ccs = ccs;
            fprintf(stderr, "  --> evaluated by: ");
            is_caf = fprintCallStack(ccs);
            break;
        case UNDERFLOW_FRAME:
            stack = ((StgUnderflowFrame*)frame)->next_chunk;
            frame = stack->sp;
            break;
        case STOP_FRAME:
            goto done;
        default:
            frame += stack_frame_sizeW((StgClosure*)frame);
            break;
        }
    }
done:
    return;
1011 1012
}

Ben Gamari's avatar
Ben Gamari committed
1013
#if defined(DEBUG)
1014 1015 1016
void
debugCCS( CostCentreStack *ccs )
{
1017 1018 1019 1020 1021 1022 1023 1024
    debugBelch("<");
    for (; ccs && ccs != CCS_MAIN; ccs = ccs->prevStack ) {
        debugBelch("%s.%s", ccs->cc->module, ccs->cc->label);
        if (ccs->prevStack && ccs->prevStack != CCS_MAIN) {
            debugBelch(",");
        }
    }
    debugBelch(">");
1025
}
1026
#endif /* DEBUG */
1027

1028
#endif /* PROFILING */