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 
/*
62 
$Log: inlinechoice.c,v $
63 
 * Revision 1.1.1.1  1998/01/17  15:56:02  release
64 
 * First version to be checked into rolling release.
65 
 *
66 
 * Revision 1.2  1995/12/18  13:11:37  wfs
67 
 * Put hppatrans uder cvs control. Major Changes made since last release
68 
 * include:
69 
 * (i) PIC code generation.
70 
 * (ii) Profiling.
71 
 * (iii) Dynamic Initialization.
72 
 * (iv) Debugging of Exception Handling and Diagnostics.
73 
 *
74 
 * Revision 5.0  1995/08/25  13:42:58  wfs
75 
 * Preperation for August 25 Glue release
76 
 *
77 
 * Revision 3.4  1995/08/25  09:39:31  wfs
78 
 * A 4.0 "general_env_offset_tag" case added.
79 
 *
80 
 * Revision 3.4  1995/08/25  09:39:31  wfs
81 
 * A 4.0 "general_env_offset_tag" case added.
82 
 *
83 
 * Revision 3.1  95/04/10  16:26:51  16:26:51  wfs (William Simmonds)
84 
 * Apr95 tape version.
6 7u83 85 
 *
2 7u83 86 
 * Revision 3.0  95/03/30  11:17:28  11:17:28  wfs (William Simmonds)
87 
 * Mar95 tape version with CRCR95_178 bug fix.
6 7u83 88 
 *
2 7u83 89 
 * Revision 2.0  95/03/15  15:27:35  15:27:35  wfs (William Simmonds)
90 
 * spec 3.1 changes implemented, tests outstanding.
6 7u83 91 
 *
2 7u83 92 
 * Revision 1.1  95/01/11  13:09:12  13:09:12  wfs (William Simmonds)
93 
 * Initial revision
6 7u83 94 
 *
2 7u83 95 
*/
96 
 
97 
 
98 
#include "config.h"
99 
#include "common_types.h"
100 
#include "installglob.h"
101 
#include "exp.h"
102 
#include "expmacs.h"
103 
#include "tags.h"
104 
#include "flags.h"
105 
#include "shapemacs.h"
106 
#include "inl_norm.h"
107 
 
108 
#define crit_inline	300
109 
#define crit_decs	5
110 
#define crit_decsatapp	5
111 
#define apply_cost      3
112 
 
6 7u83 113 
static int  complexity(exp e, int count, int newdecs);
2 7u83 114 
static last_new_decs = -999;
115 
 
116 
/*
117 
    APPLY COMPLEXITY TO A LIST OF EXPRESSIONS
118 
*/
119 
 
6 7u83 120 
int sbl
121 
(exp e, int count, int newdecs)
2 7u83 122 
{
6 7u83 123 
    int c = complexity(e, count, newdecs);
124 
    if (c < 0) return(c);
125 
    if (last(e)) return(c);
126 
    return(sbl(bro(e), c, newdecs));
2 7u83 127 
}
128 
 
129 
 
130 
/*
131 
    FIND THE COMPLEXITY OF AN EXPRESSION
132 
 
133 
    This routine examines the structure of e to see if its complexity
134 
    (roughly the number of nodes) is greater than count.  As soon as the
135 
    complexity exceeds this value it stops.  It returns the difference
136 
    between count and the calculated complexity.
137 
*/
138 
 
6 7u83 139 
static int complexity
140 
(exp e, int count, int newdecs)
2 7u83 141 
{
6 7u83 142 
    unsigned char n = name(e);
143 
 
2 7u83 144 
    last_new_decs = newdecs;
145 
 
6 7u83 146 
    if (count < 0)
147 
      return(-1);
148 
    if (newdecs > crit_decs)
149 
      return(-2);
150 
    if (son(e) == nilexp)
151 
      return(count);
2 7u83 152 
 
6 7u83 153 
    switch (n) {
154 
 
155 
	case apply_tag: {
156 
	    if (newdecs > crit_decsatapp)
157 
	      return(-3);
158 
	    return(sbl(son(e), (count - apply_cost),
159 
			 (newdecs + 1)));
2 7u83 160 
	}
161 
 
6 7u83 162 
	case rep_tag: {
163 
	    return(complexity(bro(son(e)), (count - 1),
164 
		     (newdecs + 1)
165 
				));
2 7u83 166 
	}
167 
 
6 7u83 168 
	case res_tag: {
169 
	    return(complexity(son(e), (count + 1),
170 
				  newdecs));
2 7u83 171 
	}
172 
 
6 7u83 173 
	case ident_tag: {
174 
	    return(sbl(son(e), (count - 1),
175 
			   (newdecs + 1)));
2 7u83 176 
	}
177 
 
6 7u83 178 
	case top_tag:
179 
	case clear_tag:
180 
	case val_tag: {
181 
	    return(count);
2 7u83 182 
	}
183 
 
6 7u83 184 
	case case_tag: {
185 
	    return(complexity(son(e), (count - 1),
186 
				  newdecs));
2 7u83 187 
	}
188 
 
6 7u83 189 
	case name_tag:
190 
	case string_tag:
191 
	case env_offset_tag:
2 7u83 192 
	case general_env_offset_tag:
193 
	{
6 7u83 194 
	    return(count - 1);
2 7u83 195 
	}
196 
 
6 7u83 197 
	case labst_tag: {
198 
	    return(complexity(bro(son(e)), count, newdecs));
2 7u83 199 
	}
200 
 
6 7u83 201 
	case solve_tag:
202 
	case seq_tag:
203 
	case cond_tag: {
204 
	    return(sbl(son(e), count, newdecs));
2 7u83 205 
	}
206 
 
207 
	default : {
6 7u83 208 
	    return(sbl(son(e), (count - 1), newdecs));
2 7u83 209 
	}
210 
    }
211 
    /* NOT REACHED */
212 
}
213 
 
214 
#define MASK 3
6 7u83 215 
#define REJ_ONCE(1)
216 
#define OK_ONCE (2)
2 7u83 217 
 
6 7u83 218 
 
2 7u83 219 
int inlinechoice
6 7u83 220 
(exp t, exp def, int total_uses)
2 7u83 221 
	/* delivers 0 if no uses of this proc can be inlined.
222 
	   delivers 1 if this use cannot be inlined
223 
	   delivers 2 if this use can be inlined.
224 
	*/
225 
{
226 
  int res;
6 7u83 227 
 
2 7u83 228 
  exp apars;
229 
  exp fpars;
6 7u83 230 
 
2 7u83 231 
  int newdecs = 0;
232 
 
233 
  int max_complexity;
234 
 
6 7u83 235 
  int nparam;
236 
  CONST unsigned int CONST_BONUS_UNIT = 16;
237 
  int const_param_bonus;
238 
  int adjusted_max_complexity;
2 7u83 239 
 
240 
#if 1
241 
  shape shdef = pt(def);
6 7u83 242 
  if (!eq_shape(sh(father(t)), shdef))
2 7u83 243 
  {
244 
    /* shape required by application is different from definition */
245 
    return 1;
246 
  }
247 
#endif
248 
 
6 7u83 249 
  nparam = 0;
250 
  const_param_bonus = 0;
2 7u83 251 
 
252 
 
6 7u83 253 
  max_complexity = (crit_inline / total_uses);
2 7u83 254 
 
6 7u83 255 
 
256 
 
257 
#if ishppa
2 7u83 258 
  {
259 
#define QQQ 2
260 
    int i;
6 7u83 261 
    if (total_uses >= (1<<QQQ))
2 7u83 262 
    {
6 7u83 263 
      for (i= total_uses >> QQQ; i>0; i >>=1)
2 7u83 264 
      {
265 
	max_complexity *= 3;
266 
	max_complexity /= 2;
267 
      }
268 
    }
269 
#undef QQQ
270 
  }
271 
#endif
6 7u83 272 
 
273 
  if (max_complexity < 15) {
274 
    max_complexity = 15;
275 
  } else if (max_complexity > 120) {
276 
    max_complexity = 120;
2 7u83 277 
  }
278 
 
279 
  apars = bro(t); /* only uses are applications */
6 7u83 280 
  fpars = son(def);
2 7u83 281 
 
6 7u83 282 
  for (;;) {
2 7u83 283 
     if (name(fpars)!=ident_tag || !isparam(fpars)) {
6 7u83 284 
       if (name(apars)!= top_tag)newdecs = 10;
2 7u83 285 
      	 break;
286 
     }
6 7u83 287 
     nparam++;
2 7u83 288 
 
289 
     switch (name(apars)) {
6 7u83 290 
      case val_tag: case real_tag: case string_tag: case name_tag:
2 7u83 291 
      	   break;
292 
      case cont_tag: {
6 7u83 293 
      	   if (name(son(apars)) ==name_tag && isvar(son(son(apars))) &&
294 
      	        		!isvar(fpars))break;
2 7u83 295 
      	   } /* ... else continue */
296 
      default: newdecs++;
297 
     }
6 7u83 298 
     switch (name(apars))
2 7u83 299 
     {
6 7u83 300 
      case val_tag: {
301 
	int n = no(apars);
302 
 
2 7u83 303 
	/* Simple constant param. Increase desire to
304 
	   inline since a constant may cause further
305 
	   optimisation, eg strength reduction (mul
306 
	   to shift) or dead code savings */
307 
 
6 7u83 308 
#define IS_POW2(c)	((c)!= 0 && ((c) & ((c) - 1)) == 0)
309 
 
310 
	if (0) {
2 7u83 311 
	  /* needs a register - poor */
6 7u83 312 
	  const_param_bonus += CONST_BONUS_UNIT / 4;
313 
	} else if (n == 0 || (n > 0 && IS_POW2(n))) {
2 7u83 314 
	  /* very good */
6 7u83 315 
	  const_param_bonus += CONST_BONUS_UNIT;
2 7u83 316 
	} else {
317 
	  /* less good */
6 7u83 318 
	  const_param_bonus += CONST_BONUS_UNIT / 2;
2 7u83 319 
	}
6 7u83 320 
	break;
2 7u83 321 
      }
322 
 
323 
#undef IS_POW2
6 7u83 324 
 
325 
      case real_tag:
2 7u83 326 
	/* reals not that useful */
6 7u83 327 
	const_param_bonus += CONST_BONUS_UNIT / 4;
328 
	break;
2 7u83 329 
 
6 7u83 330 
      case string_tag:
331 
       case name_tag:
332 
	 break;
333 
 
334 
      case cont_tag:
335 
	if (name(son(apars)) == name_tag &&
336 
	    isvar(son(son(apars))) &&
337 
	    !isvar(fpars)) {
338 
	  break;
2 7u83 339 
	}
340 
	/* FALL THROUGH */
6 7u83 341 
 
2 7u83 342 
      default : {
6 7u83 343 
	newdecs++;
344 
	break;
2 7u83 345 
      }
346 
     }
347 
     fpars = bro(son(fpars));
6 7u83 348 
     if (last(apars))break;
2 7u83 349 
     apars = bro(apars);
350 
   }
351 
 
6 7u83 352 
  adjusted_max_complexity = max_complexity;
353 
 
2 7u83 354 
  /* increase to up to 3 times (average around 2) according
355 
     to const params */
6 7u83 356 
  if (nparam != 0) {
357 
    adjusted_max_complexity +=
358 
     (2 * max_complexity * const_param_bonus) /
359 
	(CONST_BONUS_UNIT * nparam);
2 7u83 360 
  }
6 7u83 361 
 
2 7u83 362 
  /* increase by number of instructions saved for call */
6 7u83 363 
    adjusted_max_complexity += nparam - newdecs + 1;
364 
 
365 
  if ((complexity(fpars,  adjusted_max_complexity, newdecs)) >= 0)
2 7u83 366 
    res = 2;
367 
  else if (newdecs == 0)
368 
    res = 0;
369 
  else
370 
    res = 1;
371 
 
372 
 
373 
  switch (res)
374 
  {
375 
   case 2:
6 7u83 376 
   (ptno(def)) |= OK_ONCE;
2 7u83 377 
    break;
378 
   case 1:
379 
 
6 7u83 380 
   (ptno(def)) |= REJ_ONCE;
2 7u83 381 
    break;
382 
   case 0:
6 7u83 383 
   ;
2 7u83 384 
  }
385 
 
386 
  return res;
6 7u83 387 
 
2 7u83 388 
}
389