Subversion Repositories tendra.SVN

Rev

Rev 5 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 7u83 1 
/*
6 7u83 2 
 * Copyright (c) 2002-2005 The TenDRA Project <http://www.tendra.org/>.
3 
 * All rights reserved.
4 
 *
5 
 * Redistribution and use in source and binary forms, with or without
6 
 * modification, are permitted provided that the following conditions are met:
7 
 *
8 
 * 1. Redistributions of source code must retain the above copyright notice,
9 
 *    this list of conditions and the following disclaimer.
10 
 * 2. Redistributions in binary form must reproduce the above copyright notice,
11 
 *    this list of conditions and the following disclaimer in the documentation
12 
 *    and/or other materials provided with the distribution.
13 
 * 3. Neither the name of The TenDRA Project nor the names of its contributors
14 
 *    may be used to endorse or promote products derived from this software
15 
 *    without specific, prior written permission.
16 
 *
17 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS
18 
 * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
19 
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
21 
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 
 * EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
24 
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
25 
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
26 
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
27 
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 
 *
29 
 * $Id$
30 
 */
31 
/*
2 7u83 32 
    		 Crown Copyright (c) 1997
6 7u83 33 
 
2 7u83 34 
    This TenDRA(r) Computer Program is subject to Copyright
35 
    owned by the United Kingdom Secretary of State for Defence
36 
    acting through the Defence Evaluation and Research Agency
37 
    (DERA).  It is made available to Recipients with a
38 
    royalty-free licence for its use, reproduction, transfer
39 
    to other parties and amendment for any purpose not excluding
40 
    product development provided that any such use et cetera
41 
    shall be deemed to be acceptance of the following conditions:-
6 7u83 42 
 
2 7u83 43 
        (1) Its Recipients shall ensure that this Notice is
44 
        reproduced upon any copies or amended versions of it;
6 7u83 45 
 
2 7u83 46 
        (2) Any amended version of it shall be clearly marked to
47 
        show both the nature of and the organisation responsible
48 
        for the relevant amendment or amendments;
6 7u83 49 
 
2 7u83 50 
        (3) Its onward transfer from a recipient to another
51 
        party shall be deemed to be that party's acceptance of
52 
        these conditions;
6 7u83 53 
 
2 7u83 54 
        (4) DERA gives no warranty or assurance as to its
55 
        quality or suitability for any purpose and DERA accepts
56 
        no liability whatsoever in relation to any use to which
57 
        it may be put.
58 
*/
59 
 
60 
 
61 
/*** rule-tail.c --- Tail recursion elimination routines.
62 
 *
63 
 ** Author: Steve Folkes <smf@hermes.mod.uk>
64 
 *
65 
 *** Commentary:
66 
 *
67 
 * This file implements the SID inlining routines.
68 
 *
69 
 * There are five separate phases implemented in this file.
70 
 *
71 
 * The first phase is to find and eliminate all tail recursive cycles that
72 
 * each rule is involved in.  The cycles are detected by the
73 
 * ``grammar_compute_inlining'' function in the file "grammar.c".  For each
74 
 * cyclic group that is found, the ``rule_handle_tails'' function is called to
75 
 * remove the cycle.  All rules in the cycle are marked as being cyclic, and
76 
 * are given a unique identification that is the same for all members of the
77 
 * cycle (but different for members of different cycles).  The tail recursive
78 
 * calls are marked as inlinable and tail recursive, and the rules' call
79 
 * graphs are computed (this is the set of rules that will make tail calls).
80 
 * This phase is only performed if tail recursion inlining is enabled.
81 
 *
82 
 * The second phase is implemented by the ``rule_compute_all_basics''
83 
 * function.  This marks a rule that only contains basics as such.  This phase
84 
 * is only performed if all basic inlining is enabled.
85 
 *
86 
 * The third phase is implemented by the ``rule_compute_inlining'' function.
87 
 * This marks all calls to all basic rules as inlinable.  If single
88 
 * alternative rule inlining is enabled, then all calls to single alternative
89 
 * rules are marked as inlinable.  If non tail recursion inlining is enabled,
90 
 * it also marks all other calls as inlinable, and computes their call count
91 
 * if functions that are called more than once are not to be inlined (the
92 
 * output routines won't inline rules with a call count greater than one).
93 
 *
94 
 * The fourth phase is implemented by the ``rule_compute_needed_functions''
95 
 * function.  It marks all required functions, and functions that are called
96 
 * from a non-inlinable position as requiring function implementations.
97 
 *
98 
 * The final phase is implemented by the ``rule_handle_need_functions''
99 
 * function.  The cycle detection routines are used in the
100 
 * ``grammar_compute_inlining'' function to find cycles in the function call
101 
 * graph.  If any such cycles are found, then all of the rules in the cycle
102 
 * are marked as needing a function implementation.
103 
 *
104 
 *** Change Log:
105 
 * $Log: rule-tail.c,v $
106 
 * Revision 1.1.1.1  1998/01/17  15:57:47  release
107 
 * First version to be checked into rolling release.
108 
 *
109 
 * Revision 1.3  1994/12/15  09:58:53  smf
110 
 * Brought into line with OSSG C Coding Standards Document, as per
111 
 * "CR94_178.sid+tld-update".
112 
 *
113 
 * Revision 1.2  1994/11/11  11:47:09  smf
114 
 * Fixed a bug in the tail recursion elimination, for bug fix
115 
 * CR94_127.sid-tail-rec.
116 
 * There was a problem with tail calls that had reference parameters in an
117 
 * earlier version of SID, and they had been disabled.  This should have been
118 
 * fixed when the output routines were fixed to do references properly, but the
119 
 * check wasn't removed.  It has been now.
120 
 *
121 
 * Revision 1.1.1.1  1994/07/25  16:04:41  smf
122 
 * Initial import of SID 1.8 non shared files.
123 
 *
124 
**/
125 
 
126 
/****************************************************************************/
127 
 
128 
#include "rule.h"
129 
#include "action.h"
130 
#include "basic.h"
131 
#include "entry-list.h"
132 
#include "name.h"
133 
#include "type.h"
134 
 
135 
/*--------------------------------------------------------------------------*/
136 
 
137 
typedef struct CycleHeadT {
138 
    RuleP			head;
139 
    RuleP		       *tail;
140 
} CycleHeadT, *CycleHeadP;
141 
 
142 
typedef struct RuleStackT {
143 
    struct RuleStackT	       *next;
144 
    RuleP			rule;
145 
} RuleStackT, *RuleStackP;
146 
 
147 
/*--------------------------------------------------------------------------*/
148 
 
6 7u83 149 
static BoolT	rule_do_inline_tail_calls     = TRUE;
150 
static BoolT	rule_do_inline_all_basics     = TRUE;
151 
static BoolT	rule_do_inline_singles        = FALSE;
152 
static BoolT	rule_do_inline_non_tail_calls = FALSE;
153 
static BoolT	rule_do_multiple_inlining     = FALSE;
2 7u83 154 
 
155 
/*--------------------------------------------------------------------------*/
156 
 
157 
static void
6 7u83 158 
rule_inline_tail_calls_1(RuleP rule, AltP alt, RuleP tail_group)
2 7u83 159 
{
6 7u83 160 
    ItemP item = alt_item_head(alt);
2 7u83 161 
    ItemP next;
162 
 
6 7u83 163 
    while ((next = item_next(item)) != NIL(ItemP)) {
2 7u83 164 
	item = next;
165 
    }
6 7u83 166 
    if (item_is_rule(item)) {
167 
	RuleP item_rule = entry_get_rule(item_entry(item));
2 7u83 168 
 
6 7u83 169 
	if ((rule_get_tail_group(item_rule) == tail_group) &&
170 
	    (types_equal_names(rule_result(rule), item_result(item)))) {
171 
	    item_inlinable(item);
172 
	    item_tail_call(item);
2 7u83 173 
	}
174 
    }
175 
}
176 
 
177 
static void
6 7u83 178 
rule_inline_tail_calls(RuleP rule)
2 7u83 179 
{
6 7u83 180 
    RuleP tail_group = rule_get_tail_group(rule);
2 7u83 181 
    AltP  alt;
182 
 
6 7u83 183 
    if ((alt = rule_get_handler(rule)) != NIL(AltP)) {
184 
	rule_inline_tail_calls_1(rule, alt, tail_group);
2 7u83 185 
    }
6 7u83 186 
    for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
187 
	rule_inline_tail_calls_1(rule, alt, tail_group);
2 7u83 188 
    }
189 
}
190 
 
6 7u83 191 
static void	rule_compute_call_graph(RuleP, EntryListP, RuleStackP);
2 7u83 192 
 
193 
static void
6 7u83 194 
rule_compute_call_graph_1(AltP alt, EntryListP call_list, RuleStackP next)
2 7u83 195 
{
6 7u83 196 
    ItemP item = alt_item_head(alt);
2 7u83 197 
    ItemP next_item;
198 
 
6 7u83 199 
    while ((next_item = item_next(item)) != NIL(ItemP)) {
2 7u83 200 
	item = next_item;
201 
    }
6 7u83 202 
    if (item_is_tail_call(item)) {
203 
	EntryP entry     = item_entry(item);
204 
	RuleP  item_rule = entry_get_rule(entry);
2 7u83 205 
 
6 7u83 206 
	rule_compute_call_graph(item_rule, call_list, next);
2 7u83 207 
    }
208 
}
209 
 
210 
static void
6 7u83 211 
rule_compute_call_graph(RuleP rule, EntryListP call_list, RuleStackP next)
2 7u83 212 
{
213 
    RuleStackT stack;
214 
    AltP       alt;
215 
 
216 
    stack.rule = rule;
217 
    stack.next = next;
218 
    while (next) {
219 
	if (next->rule == rule) {
6 7u83 220 
	    entry_list_add_if_missing(call_list, rule_entry(rule));
2 7u83 221 
	    return;
222 
	}
223 
	next = next->next;
224 
    }
6 7u83 225 
    if ((alt = rule_get_handler(rule)) != NIL(AltP)) {
226 
	rule_compute_call_graph_1(alt, call_list, &stack);
2 7u83 227 
    }
6 7u83 228 
    for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
229 
	rule_compute_call_graph_1(alt, call_list, &stack);
2 7u83 230 
    }
231 
}
232 
 
233 
static void
6 7u83 234 
rule_compute_all_basics_1(RuleP rule)
2 7u83 235 
{
6 7u83 236 
    if ((!rule_has_empty_alt(rule)) &&
237 
	(rule_get_handler(rule) == NIL(AltP))) {
2 7u83 238 
	AltP alt;
239 
 
6 7u83 240 
	for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
2 7u83 241 
	    ItemP item;
242 
 
6 7u83 243 
	    for (item = alt_item_head(alt); item; item = item_next(item)) {
244 
		if (!item_is_basic(item)) {
2 7u83 245 
		    return;
246 
		}
247 
	    }
248 
	}
6 7u83 249 
	rule_all_basics(rule);
2 7u83 250 
    }
251 
}
252 
 
6 7u83 253 
static void	rule_compute_inlining_1(RuleP);
2 7u83 254 
 
255 
static void
6 7u83 256 
rule_compute_inlining_2(AltP alt)
2 7u83 257 
{
258 
    ItemP item;
259 
 
6 7u83 260 
    for (item = alt_item_head(alt); item; item = item_next(item)) {
261 
	if ((item_is_rule(item)) && (!item_is_tail_call(item))) {
262 
	    EntryP entry     = item_entry(item);
263 
	    RuleP  item_rule = entry_get_rule(entry);
2 7u83 264 
 
6 7u83 265 
	    if (rule_is_all_basics(item_rule)) {
266 
		item_inlinable(item);
2 7u83 267 
	    } else if (rule_do_inline_singles &&
6 7u83 268 
		       rule_has_one_alt(item_rule)) {
269 
		item_inlinable(item);
2 7u83 270 
	    } else if (!rule_do_multiple_inlining) {
6 7u83 271 
		rule_inc_call_count(item_rule);
2 7u83 272 
	    }
273 
	    if (rule_do_inline_non_tail_calls) {
6 7u83 274 
		item_inlinable(item);
2 7u83 275 
	    }
6 7u83 276 
	    rule_compute_inlining_1(item_rule);
2 7u83 277 
	}
278 
    }
279 
}
280 
 
281 
static void
6 7u83 282 
rule_compute_inlining_1(RuleP rule)
2 7u83 283 
{
6 7u83 284 
    if (!rule_is_checked_for_inlining(rule)) {
285 
	if (!rule_is_being_inlined(rule)) {
2 7u83 286 
	    AltP alt;
287 
 
6 7u83 288 
	    rule_being_inlined(rule);
289 
	    if ((alt = rule_get_handler(rule)) != NIL(AltP)) {
290 
		rule_compute_inlining_2(alt);
2 7u83 291 
	    }
6 7u83 292 
	    for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
293 
		rule_compute_inlining_2(alt);
2 7u83 294 
	    }
6 7u83 295 
	    rule_checked_for_inlining(rule);
2 7u83 296 
	}
297 
    }
298 
}
299 
 
300 
static void
6 7u83 301 
rule_compute_needed_functions_2(AltP alt)
2 7u83 302 
{
303 
    ItemP item;
304 
 
6 7u83 305 
    for (item = alt_item_head(alt); item; item = item_next(item)) {
306 
	if (item_is_rule(item)) {
307 
	    RuleP item_rule = entry_get_rule(item_entry(item));
2 7u83 308 
 
6 7u83 309 
	    if ((!item_is_inlinable(item)) ||
310 
		(rule_get_call_count(item_rule) > 1)) {
311 
		rule_will_need_function(item_rule);
2 7u83 312 
	    }
313 
	}
314 
    }
315 
}
316 
 
317 
static void
6 7u83 318 
rule_compute_needed_functions_1(RuleP rule)
2 7u83 319 
{
320 
    AltP     alt;
321 
 
6 7u83 322 
    if ((alt = rule_get_handler(rule)) != NIL(AltP)) {
323 
	rule_compute_needed_functions_2(alt);
2 7u83 324 
    }
6 7u83 325 
    for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
326 
	rule_compute_needed_functions_2(alt);
2 7u83 327 
    }
328 
}
329 
 
330 
/*--------------------------------------------------------------------------*/
331 
 
332 
void
6 7u83 333 
rule_handle_tails(RuleP rule_list)
2 7u83 334 
{
335 
    RuleP rule;
336 
 
6 7u83 337 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {
338 
	rule_set_tail_group(rule, rule_list);
339 
	rule_no_cycles(rule);
2 7u83 340 
    }
6 7u83 341 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {
342 
	rule_inline_tail_calls(rule);
2 7u83 343 
    }
6 7u83 344 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {
345 
	rule_compute_call_graph(rule, rule_call_list(rule),
346 
				 NIL(RuleStackP));
2 7u83 347 
    }
348 
}
349 
 
350 
void
6 7u83 351 
rule_compute_all_basics(EntryP entry, GenericP gclosure)
2 7u83 352 
{
6 7u83 353 
    UNUSED(gclosure);
354 
    if (rule_do_inline_all_basics && entry_is_rule(entry)) {
355 
	RuleP rule = entry_get_rule(entry);
2 7u83 356 
 
6 7u83 357 
	rule_compute_all_basics_1(rule);
2 7u83 358 
    }
359 
}
360 
 
361 
void
6 7u83 362 
rule_compute_inlining(EntryP entry, GenericP gclosure)
2 7u83 363 
{
6 7u83 364 
    UNUSED(gclosure);
365 
    if (entry_is_rule(entry)) {
366 
	RuleP rule = entry_get_rule(entry);
2 7u83 367 
 
6 7u83 368 
	rule_compute_inlining_1(rule);
2 7u83 369 
    }
370 
}
371 
 
372 
void
6 7u83 373 
rule_compute_needed_functions(EntryP entry, GenericP gclosure)
2 7u83 374 
{
6 7u83 375 
    UNUSED(gclosure);
376 
    if (entry_is_rule(entry)) {
377 
	RuleP rule = entry_get_rule(entry);
2 7u83 378 
 
6 7u83 379 
	rule_compute_needed_functions_1(rule);
2 7u83 380 
    }
381 
}
382 
 
383 
void
6 7u83 384 
rule_handle_need_functions(RuleP rule_list)
2 7u83 385 
{
386 
    RuleP rule;
387 
 
6 7u83 388 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {
389 
	rule_will_need_function(rule);
2 7u83 390 
    }
391 
}
392 
 
393 
BoolT
6 7u83 394 
rule_get_inline_tail_calls(void)
2 7u83 395 
{
6 7u83 396 
    return(rule_do_inline_tail_calls);
2 7u83 397 
}
398 
 
399 
void
6 7u83 400 
rule_set_inline_tail_calls(BoolT enable)
2 7u83 401 
{
402 
    rule_do_inline_tail_calls = enable;
403 
}
404 
 
405 
void
6 7u83 406 
rule_set_inline_all_basics(BoolT enable)
2 7u83 407 
{
408 
    rule_do_inline_all_basics = enable;
409 
}
410 
 
411 
void
6 7u83 412 
rule_set_inline_singles(BoolT enable)
2 7u83 413 
{
414 
    rule_do_inline_singles = enable;
415 
}
416 
 
417 
void
6 7u83 418 
rule_set_inline_non_tail_calls(BoolT enable)
2 7u83 419 
{
420 
    if (enable) {
421 
	rule_do_inline_non_tail_calls = TRUE;
422 
    } else {
423 
	rule_do_inline_non_tail_calls = FALSE;
424 
	rule_do_multiple_inlining     = FALSE;
425 
    }
426 
}
427 
 
428 
void
6 7u83 429 
rule_set_multiple_inlining(BoolT enable)
2 7u83 430 
{
431 
    if (enable) {
432 
	rule_do_inline_non_tail_calls = TRUE;
433 
	rule_do_multiple_inlining     = TRUE;
434 
    } else {
435 
	rule_do_multiple_inlining     = FALSE;
436 
    }
437 
}
438 
 
439 
/*
440 
 * Local variables(smf):
441 
 * eval: (include::add-path-entry "../os-interface" "../library")
442 
 * eval: (include::add-path-entry "../generated")
443 
 * end:
444 
**/