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
|
/* -----------------------------------------------------------------------------
*
* (c) The GHC Team, 2001
* Author: Sungwoo Park
*
* Retainer set interface for retainer profiling.
*
* ---------------------------------------------------------------------------*/
#pragma once
#include <stdio.h>
#if defined(PROFILING)
#include "BeginPrivate.h"
/*
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 is, <, >, 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.
*/
typedef CostCentreStack *retainer;
/*
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 {
uint32_t 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 positive
// 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.
*/
#if defined(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 member 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
//
// bool isMember(retainer, retainerSet *);
/*
Returns true 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 bool
isMember(retainer r, RetainerSet *rs)
{
int i, left, right; // must be int, not uint32_t (because -1 can appear)
retainer ri;
if (rs == &rs_MANY) { return true; }
if (rs->num < BINARY_SEARCH_THRESHOLD) {
for (i = 0; i < (int)rs->num; i++) {
ri = rs->element[i];
if (r == ri) return true;
else if (r < ri) return false;
}
} else {
left = 0;
right = rs->num - 1;
while (left <= right) {
i = (left + right) / 2;
ri = rs->element[i];
if (r == ri) return true;
else if (r < ri) right = i - 1;
else left = i + 1;
}
}
return false;
}
// Finds or creates a retainer set augmented with a new retainer.
RetainerSet *addElement(retainer, RetainerSet *);
#if defined(SECOND_APPROACH)
// Prints a single retainer set.
void printRetainerSetShort(FILE *, RetainerSet *, W_, uint32_t);
#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 *, uint32_t *, uint32_t *);
#if defined(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)
#include "EndPrivate.h"
#endif /* PROFILING */
|
