+++ /dev/null
-/* -----------------------------------------------------------------------------
- *
- * (c) The GHC Team, 2001
- * Author: Sungwoo Park
- *
- * Retainer set interface for retainer profiling.
- *
- * ---------------------------------------------------------------------------*/
-
-#ifndef RETAINERSET_H
-#define RETAINERSET_H
-
-#include <stdio.h>
-
-#ifdef PROFILING
-
-/*
- Type 'retainer' defines the retainer identity.
-
- Invariant:
- 1. The retainer identity of a given retainer cannot change during
- program execution, no matter where it is actually stored.
- For instance, the memory address of a retainer cannot be used as
- its retainer identity because its location may change during garbage
- collections.
- 2. Type 'retainer' must come with comparison operations as well as
- an equality operation. That it, <, >, and == must be supported -
- this is necessary to store retainers in a sorted order in retainer sets.
- Therefore, you cannot use a huge structure type as 'retainer', for instance.
-
- We illustrate three possibilities of defining 'retainer identity'.
- Choose one of the following three compiler directives:
-
- Retainer scheme 1 (RETAINER_SCHEME_INFO) : retainer = info table
- Retainer scheme 2 (RETAINER_SCHEME_CCS) : retainer = cost centre stack
- Retainer scheme 3 (RETAINER_SCHEME_CC) : retainer = cost centre
-*/
-
-// #define RETAINER_SCHEME_INFO
-#define RETAINER_SCHEME_CCS
-// #define RETAINER_SCHEME_CC
-
-#ifdef RETAINER_SCHEME_INFO
-struct _StgInfoTable;
-typedef struct _StgInfoTable *retainer;
-#endif
-
-#ifdef RETAINER_SCHEME_CCS
-typedef CostCentreStack *retainer;
-#endif
-
-#ifdef RETAINER_SCHEME_CC
-typedef CostCentre *retainer;
-#endif
-
-/*
- Type 'retainerSet' defines an abstract datatype for sets of retainers.
-
- Invariants:
- A retainer set stores its elements in increasing order (in element[] array).
- */
-
-typedef struct _RetainerSet {
- nat num; // number of elements
- StgWord hashKey; // hash key for this retainer set
- struct _RetainerSet *link; // link to the next retainer set in the bucket
- int id; // unique id of this retainer set (used when printing)
- // Its absolute value is interpreted as its true id; if id is
- // negative, it indicates that this retainer set has had a postive
- // cost after some retainer profiling.
- retainer element[0]; // elements of this retainer set
- // do not put anything below here!
-} RetainerSet;
-
-/*
- Note:
- There are two ways of maintaining all retainer sets. The first is simply by
- freeing all the retainer sets and re-initialize the hash table at each
- retainer profiling. The second is by setting the cost field of each
- retainer set. The second is preferred to the first if most retainer sets
- are likely to be observed again during the next retainer profiling. Note
- that in the first approach, we do not free the memory allocated for
- retainer sets; we just invalidate all retainer sets.
- */
-#ifdef DEBUG_RETAINER
-// In thise case, FIRST_APPROACH must be turned on because the memory pool
-// for retainer sets is freed each time.
-#define FIRST_APPROACH
-#else
-// #define FIRST_APPROACH
-#define SECOND_APPROACH
-#endif
-
-// Creates the first pool and initializes a hash table. Frees all pools if any.
-void initializeAllRetainerSet(void);
-
-// Refreshes all pools for reuse and initializes a hash table.
-void refreshAllRetainerSet(void);
-
-// Frees all pools.
-void closeAllRetainerSet(void);
-
-// Finds or creates if needed a singleton retainer set.
-RetainerSet *singleton(retainer r);
-
-extern RetainerSet rs_MANY;
-
-// Checks if a given retainer is a memeber of the retainer set.
-//
-// Note & (maybe) Todo:
-// This function needs to be declared as an inline function, so it is declared
-// as an inline static function here.
-// This make the interface really bad, but isMember() returns a value, so
-// it is not easy either to write it as a macro (due to my lack of C
-// programming experience). Sungwoo
-//
-// rtsBool isMember(retainer, retainerSet *);
-/*
- Returns rtsTrue if r is a member of *rs.
- Invariants:
- rs is not NULL.
- Note:
- The efficiency of this function is subject to the typical size of
- retainer sets. If it is small, linear scan is better. If it
- is large in most cases, binary scan is better.
- The current implementation mixes the two search strategies.
- */
-
-#define BINARY_SEARCH_THRESHOLD 8
-INLINE_HEADER rtsBool
-isMember(retainer r, RetainerSet *rs)
-{
- int i, left, right; // must be int, not nat (because -1 can appear)
- retainer ri;
-
- if (rs == &rs_MANY) { return rtsTrue; }
-
- if (rs->num < BINARY_SEARCH_THRESHOLD) {
- for (i = 0; i < (int)rs->num; i++) {
- ri = rs->element[i];
- if (r == ri) return rtsTrue;
- else if (r < ri) return rtsFalse;
- }
- } else {
- left = 0;
- right = rs->num - 1;
- while (left <= right) {
- i = (left + right) / 2;
- ri = rs->element[i];
- if (r == ri) return rtsTrue;
- else if (r < ri) right = i - 1;
- else left = i + 1;
- }
- }
- return rtsFalse;
-}
-
-// Finds or creates a retainer set augmented with a new retainer.
-RetainerSet *addElement(retainer, RetainerSet *);
-
-// Call f() for each retainer set.
-void traverseAllRetainerSet(void (*f)(RetainerSet *));
-
-#ifdef SECOND_APPROACH
-// Prints a single retainer set.
-void printRetainerSetShort(FILE *, RetainerSet *);
-#endif
-
-// Print the statistics on all the retainer sets.
-// store the sum of all costs and the number of all retainer sets.
-void outputRetainerSet(FILE *, nat *, nat *);
-
-#ifdef SECOND_APPROACH
-// Print all retainer sets at the exit of the program.
-void outputAllRetainerSet(FILE *);
-#endif
-
-// Hashing functions
-/*
- Invariants:
- Once either initializeAllRetainerSet() or refreshAllRetainerSet()
- is called, there exists only one copy of any retainer set created
- through singleton() and addElement(). The pool (the storage for
- retainer sets) is consumed linearly. All the retainer sets of the
- same hash function value are linked together from an element in
- hashTable[]. See the invariants of allocateInPool() for the
- maximum size of retainer sets. The hashing function is defined by
- hashKeySingleton() and hashKeyAddElement(). The hash key for a set
- must be unique regardless of the order its elements are inserted,
- i.e., the hashing function must be additive(?).
-*/
-#define hashKeySingleton(r) ((StgWord)(r))
-#define hashKeyAddElement(r, s) (hashKeySingleton((r)) + (s)->hashKey)
-
-// Prints the full information on a given retainer.
-// Note: This function is not part of retainerSet interface, but this is
-// the best place to define it.
-void printRetainer(FILE *, retainer);
-
-#endif /* PROFILING */
-#endif /* RETAINERSET_H */
projects / ghc-hetmet.git / blobdiff