src/vm/jit/optimizing/ssa.c

   1 /* src/vm/jit/optimizing/ssa.c - static single-assignment form
   2
   3    Copyright (C) 2005, 2006, 2007, 2008
   4    CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
   5
   6    This file is part of CACAO.
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2, or (at
  11    your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  21    02111-1307, USA.
  22
  23 */
  24
  25
  26 #include "config.h"
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30
  31 #include "mm/memory.h"
  32
  33 #include "toolbox/bitvector.h"
  34 #include "toolbox/worklist.h"
  35
  36 #include "vm/builtin.h"
  37
  38 #include "vm/jit/jit.h" /* icmd_table */
  39
  40 #include "vm/jit/ir/bytecode.h"
  41
  42 #include "vm/jit/optimizing/dominators.h"
  43 #include "vm/jit/optimizing/graph.h"
  44 #include "vm/jit/optimizing/lifetimes.h"
  45 #include "vm/jit/optimizing/lsra.h"
  46
  47 #include "vm/jit/optimizing/ssa.h"
  48 #include "vm/jit/optimizing/ssa_rename.h"
  49 #include "vm/jit/optimizing/ssa_phi.h"
  50
  51 #include "vm/jit/python.h"
  52
  53 #if defined(SSA_DEBUG_VERBOSE)
  54 #include "vmcore/options.h"   /* compileverbose */
  55 #endif
  56
  57 /* function prototypes */
  58 void ssa_set_local_def(lsradata *, int , int);
  59 void ssa_set_interface(jitdata *, basicblock *, s4 *);
  60
  61 void dead_code_elimination(jitdata *jd, graphdata *gd);
  62 void copy_propagation(jitdata *jd, graphdata *gd);
  63 void ssa_replace_use_sites(jitdata *, graphdata *, struct lifetime *,
  64                                                 int , worklist *);
  65
  66 void ssa_set_def(lsradata *, int , int );
  67 void ssa_set_local_def(lsradata *, int , int );
  68 void ssa_set_iovar(lsradata *, s4 , int , s4 *);
  69 void ssa_set_interface(jitdata *, basicblock *, s4 *);
  70
  71
  72 #ifdef SSA_DEBUG_VERBOSE
  73 void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd);
  74 void ssa_print_lt(lsradata *ls);
  75 void _ssa_print_lt(struct lifetime *lt);
  76 void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage);
  77 void ssa_print_phi(lsradata *, graphdata *);
  78 #endif
  79
  80 /* ssa ************************************************************************
  81
  82 SSA main procedure:
  83
  84 SSA Algorithms are based on "modern compiler implementation in C" from andrew
  85 w. appel, edition 2004
  86
  87 Corrections:
  88 page 441 Algorithm 19.6. Inserting phi-functions:
  89
  90 ...
  91     for each Y in DF[n]
  92 -       if Y not element of A phi [n]
  93 +       if a not element of A phi [n]
  94             insert the statment a <- ...
  95 ...
  96 ...
  97 -       A phi [n] <- A phi [n] join {Y}
  98 +       A phi [n] <- A phi [n] join {a}
  99 -      if Y not element of A orig [n]
 100 +      if a not element of A orig [Y]
 101            W <- W join {Y}
 102
 103 ******************************************************************************/
 104 void xssa(jitdata *jd);
 105 void yssa(jitdata *jd);
 106 void ssa(jitdata *jd) {
 107         struct dominatordata *dd;
 108         lsradata *ls;
 109         graphdata *gd;
 110
 111 #if defined(ENABLE_LOOPS)
 112         /* Loop optimization "destroys" the basicblock array */
 113         /* TODO: work with the basicblock list               */
 114         if (opt_loops) {
 115                 log_text("lsra not possible with loop optimization\n");
 116                 exit(1);
 117         }
 118 #endif
 119
 120         cfg_add_root(jd);
 121         cfg_add_exceptional_edges(jd);
 122         /*pythonpass_run(jd, "foo", "cfg_print");*/
 123         /*dominator_tree_validate(jd, dd);*/
 124         /*pythonpass_run(jd, "ssa2", "main");*/
 125         /*pythonpass_run(jd, "alt_ssa", "main");*/
 126         /*pythonpass_run(jd, "foo", "before");*/
 127
 128         /*if (getenv("XSSA")) {
 129                 dominator_tree_build(jd);
 130                 dominance_frontier_build(jd);
 131                 xssa(jd);
 132         } else */{
 133                 yssa(jd);
 134         }
 135         /*pythonpass_run(jd, "foo", "after");*/
 136         return;
 137
 138         ls = jd->ls;
 139
 140     ssa_init(jd);
 141         /* Generate the Control Flow Graph */
 142         /* Add one for a Basic Block 0 to be inserted, so lateron */
 143         /* with SSA Parameter initialization is handled right */
 144
 145         gd = graph_init(jd->basicblockcount + 1);
 146         graph_make_cfg(jd, gd);
 147
 148         dd = compute_Dominators(gd, ls->basicblockcount);
 149         computeDF(gd, dd, ls->basicblockcount, 0);
 150
 151         ssa_place_phi_functions(jd, gd, dd);
 152         ssa_rename(jd, gd, dd);
 153 #ifdef SSA_DEBUG_VERBOSE
 154         if (compileverbose) {
 155                 printf("Phi before Cleanup\n");
 156                 ssa_print_phi(ls, gd);
 157                 ssa_print_lt(ls);
 158         }
 159 #endif
 160         lt_scanlifetimes(jd, gd, dd);
 161 #ifdef SSA_DEBUG_VERBOSE
 162         if (compileverbose) {
 163                 ssa_print_lt(ls);
 164         }
 165 #endif
 166         if (opt_ssa_dce) {
 167                 dead_code_elimination(jd, gd);
 168 #ifdef SSA_DEBUG_VERBOSE
 169                 if (compileverbose) {
 170                         printf("Phi after dead code elemination\n");
 171                         ssa_print_phi(ls, gd);
 172                         ssa_print_lt(ls);
 173                 }
 174 #endif
 175         }
 176         if (opt_ssa_cp) {
 177                 copy_propagation(jd, gd);
 178 #ifdef SSA_DEBUG_VERBOSE
 179                 if (compileverbose) {
 180                         printf("Phi after copy propagation\n");
 181                         ssa_print_phi(ls, gd);
 182                         ssa_print_lt(ls);
 183                 }
 184 #endif
 185         }
 186
 187         ssa_generate_phi_moves(jd, gd);
 188         transform_BB(jd, gd);
 189
 190         lt_lifeness_analysis(jd, gd);
 191
 192 #ifdef SSA_DEBUG_CHECK
 193         {
 194                 int i, j, pred, in_d, out_d;
 195                 graphiterator iter_pred;
 196                 s4 *in, *out;
 197                 bool phi_define;
 198                 methodinfo *m;
 199
 200                 m = jd->m;
 201
 202                 for(i = 0; i < ls->basicblockcount; i++) {
 203                         if (ls->basicblocks[i]->indepth != 0) {
 204                                 pred = graph_get_first_predecessor(gd, i, &iter_pred);
 205                                 for (; (pred != -1); pred = graph_get_next(&iter_pred)) {
 206                                         in_d = ls->basicblocks[i]->indepth - 1;
 207                                         in = ls->basicblocks[i]->invars;
 208                                         for (; in_d >= 0; in_d--) {
 209                                                 phi_define = false;
 210                                                 for (j = 0; (!phi_define) && (j<ls->ssavarcount); j++) {
 211                                                         if (ls->phi[i][j] != NULL)
 212                                                                 if (ls->phi[i][j][0] == in[in_d])
 213                                                                         phi_define = true;
 214                                                 }
 215                                                 if (!phi_define) {
 216                                                         /* in not defined in phi function -> check with */
 217                                                         /* outstack(s)  of predecessor(s) */
 218                                                         out_d = ls->basicblocks[pred]->outdepth - 1;
 219                                                         out = ls->basicblocks[pred]->outvars;
 220                                                         _SSA_ASSERT(out_d >= in_d);
 221                                                         for(; out_d > in_d; out_d--);
 222                                                         if ((in[in_d] != out[out_d]) ||
 223                                                         (VAR(in[in_d])->flags != VAR(out[out_d])->flags)) {
 224                                                                 printf("Method: %s %s\n",
 225                                                                            m->clazz->name->text, m->name->text);
 226                                                                         printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
 227                                                                 if (compileverbose)
 228                                                                         printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
 229 /*                                                              else */
 230 /*                                                                      _SSA_ASSERT(0); */
 231                                                         }
 232                                                 }
 233                                         }
 234                                 }
 235                         }
 236                 }
 237         }
 238
 239 #endif
 240
 241 #ifdef SSA_DEBUG_VERBOSE
 242         if (compileverbose)
 243                 ssa_print_trees(jd, gd, dd);
 244 #endif
 245
 246 }
 247
 248 /* ssa_init *******************************************************************
 249
 250 Initialise data structures for ssa
 251
 252 IOVARS of same stackdepth and same type are coalesced:
 253 interface_map[ 5 * stackdepth + type ] = new_varindex with
 254 0 <= new_varindex < ls->ssavarcount
 255
 256 TODO: check if coalescing of IOVARS of same stackdepth and type only of adjacent
 257 basic blocks could decrease the number of phi functions and so improve ssa
 258 analysis performance!
 259
 260 All LOCALVARS and IOVARS get a new unique varindex:
 261 ls->new_varindex[0..jd->varcount[ = new_varindex with
 262 0 <= new_varindex < ls->ssavarcount
 263
 264 The jd->varcount bits long bitvectors ls->var_def[0..jd->basicblockindex+1[
 265  are set  to the definitions of LOCALVARS and IOVARS. (So the only the first
 266 ls->ssavarcount bits of each of these vectors contain valid data, but
 267 ls->ssavarcount is computed at the same time as the definitons are stored.)
 268
 269 The basic block number used as index for the bitvector array ls->var_def is
 270 already shifted by one to make space for the new basic block 0 for parameter
 271 initialization.
 272
 273 ******************************************************************************/
 274
 275 void ssa_init(jitdata *jd) {
 276         int         p, t, v;
 277         methoddesc  *md;
 278         int         i, l, b_index, len;
 279         instruction *iptr;
 280         basicblock  *bptr;
 281         s4          *interface_map; /* holds an new unique index for every used  */
 282                                     /* basic block inoutvar described by a dupel */
 283                                 /*(depth,type). Used to coalesce the inoutvars*/
 284         methodinfo   *m;
 285         lsradata     *ls;
 286         builtintable_entry *bte;
 287
 288         ls = jd->ls;
 289         m = jd->m;
 290         md = m->parseddesc;
 291
 292
 293 #if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
 294 # if defined(SSA_DEBUG_VERBOSE)
 295         if (compileverbose) {
 296                 printf("%s %s ",m->clazz->name->text, m->name->text);
 297                 if (code_is_leafmethod(jd->code))
 298                         printf("**Leafmethod**");
 299                 printf("\n");
 300         }
 301 # endif
 302         if (strcmp(m->clazz->name->text,"spec/benchmarks/_213_javac/Parser")==0)
 303                 if (strcmp(m->name->text,"parseTerm")==0)
 304 # if defined(SSA_DEBUG_VERBOSE)
 305                         if (compileverbose)
 306                                 printf("12-------------------12\n");
 307 # else
 308                 { int dummy=1; dummy++; }
 309 # endif
 310 #endif
 311
 312 #ifdef SSA_DEBUG_VERBOSE
 313     if (compileverbose)
 314                 printf("ssa_init: basicblockcount %3i localcount %3i\n",
 315                            jd->basicblockcount, jd->localcount);
 316 #endif
 317
 318         /* As first step all definitions of local variables and in/out vars are   */
 319         /* gathered. in/outvars are coalesced for same type and depth             */
 320         /* "normal" tempvars (just living within one basicblock are) ignored      */
 321
 322         ls->num_defs = DMNEW(int, jd->varcount);
 323         ls->new_varindex = DMNEW(int , jd->varcount);
 324
 325         for(p = 0; p < jd->varcount; p++) {
 326                 ls->num_defs[p] = 0;
 327                 ls->new_varindex[p] = UNUSED;
 328         }
 329
 330         /* init Var Definition bitvectors */
 331
 332         ls->var_def = DMNEW(int *, jd->basicblockcount + 1);
 333         for(i = 0; i < jd->basicblockcount + 1; i++) {
 334                 ls->var_def[i] =  bv_new(jd->varcount);
 335         }
 336
 337         ls->ssavarcount = 0;
 338
 339         /* Add parameters first in right order, so the new local indices          */
 340         /* 0..p will correspond to "their" parameters                             */
 341         /* They get defined at the artificial Block 0, the real method bbs will   */
 342         /* be ed to start at block 1                                              */
 343
 344         /* don't look at already eliminated (not used) parameters (locals) */
 345
 346         for (p = 0, l = 0; p < md->paramcount; p++) {
 347                 t = md->paramtypes[p].type;
 348                 i = jd->local_map[l * 5 + t];
 349                 l++;
 350                 if (IS_2_WORD_TYPE(t))    /* increment local counter a second time  */
 351                         l++;                  /* for 2 word types */
 352                 if (i == UNUSED)
 353                         continue;
 354                 ssa_set_local_def(ls, -1, i);
 355         }
 356
 357         _SSA_ASSERT(ls->ssavarcount < jd->varcount);
 358
 359         /* coalesce bb in/out vars */
 360
 361         interface_map = DMNEW(s4, jd->stackcount * 5);
 362         for(i = 0; i < jd->stackcount * 5; i++)
 363                 interface_map[i] = UNUSED;
 364
 365         bptr = jd->basicblocks;
 366
 367         for(; bptr != NULL; bptr = bptr->next) {
 368 #ifdef SSA_DEBUG_VERBOSE
 369         if (compileverbose)
 370                 printf("ssa_init: BB %3i flags %3x\n",bptr->nr, bptr->flags);
 371 #endif
 372                 if (bptr->flags >= BBREACHED) {
 373
 374                         /* 'valid' Basic Block */
 375
 376                         b_index = bptr->nr;
 377
 378                         len = bptr->icount;
 379                         iptr = bptr->iinstr;
 380                         ssa_set_interface(jd, bptr, interface_map);
 381
 382                         /* !!!!!!!!! not true for now !!!!!!!!! */
 383                         /* All baseline optimizations from stack.c are turned off for */
 384                         /* SSA! */
 385
 386                         for (; len > 0; len--, iptr++) {
 387
 388                                 /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
 389                                 /* an optional dst - so they to be checked first */
 390
 391                                 v = UNUSED;
 392                                 if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
 393                                                 INSTRUCTION_GET_METHODDESC(iptr,md);
 394                                                 if (md->returntype.type != TYPE_VOID)
 395                                                         v = iptr->dst.varindex;
 396                                 }
 397                                 else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
 398                                                 bte = iptr->sx.s23.s3.bte;
 399                                                 md = bte->md;
 400                                                 if (md->returntype.type != TYPE_VOID)
 401                                                         v = iptr->dst.varindex;
 402                                 }
 403                                 else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
 404                                         v = iptr->dst.varindex;
 405                                 }
 406
 407                                 if (v != UNUSED) {
 408                                         if (( v < jd->localcount) || ( VAR(v)->flags & INOUT )) {
 409
 410                                   /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
 411
 412                                                 ssa_set_local_def(ls, b_index, v);
 413                                         }
 414                                 }
 415                         }
 416                 }
 417         }
 418         _SSA_ASSERT(ls->ssavarcount < jd->varcount);
 419
 420 #ifdef SSA_DEBUG_VERBOSE
 421         if (compileverbose) {
 422                 printf("ssa_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
 423                            ls->ssavarcount);
 424                 for(i = 0; i < jd->varcount; i++) {
 425                         if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
 426                                 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
 427                                 ssa_show_variable(jd, i, VAR(i),0);
 428                                 if (i < ls->ssavarcount) {
 429                                         printf(" -> %3i", ls->new_varindex[i]);
 430                                 }
 431                                 printf("\n");
 432                         }
 433                 }
 434         }
 435 #endif
 436 }
 437
 438 /* ssa_set_def ****************************************************************
 439
 440 Helper for ssa_set_local_def and ssa_set_interface
 441
 442 The definition of a var is stored in the bitvector array ls->var_def.
 443
 444 The number of definitons of each var is counted, so the number of new vars with
 445 SSA is known.
 446
 447 ******************************************************************************/
 448
 449 void ssa_set_def(lsradata *ls, int b_index, int varindex) {
 450
 451         /* b_index + 1 to leave space for the param init block 0 */
 452
 453         bv_set_bit(ls->var_def[b_index + 1], varindex);
 454
 455         /* count number of defs for every var since SSA */
 456         /* will create a new var for every definition */
 457
 458         ls->num_defs[varindex]++;
 459 }
 460
 461 /* ssa_set_local_def **********************************************************
 462
 463 Helper for ssa_init
 464
 465 Assigns a new unique index for the local var varindex (if not already done so)
 466 and then calls ssa_set_def to remember the definition in the bitvector array
 467 ls->var_def
 468
 469 ******************************************************************************/
 470
 471 void ssa_set_local_def(lsradata *ls, int b_index, int varindex) {
 472
 473         if (ls->new_varindex[varindex] == UNUSED) {
 474                 ls->new_varindex[varindex] = ls->ssavarcount++;
 475         }
 476
 477         ssa_set_def(ls, b_index, ls->new_varindex[varindex]);
 478 }
 479
 480 /* ssa_set_local_def **********************************************************
 481
 482 Helper for ssa_set_interface
 483
 484 IN: ls              pointer to lsradata structure
 485     iovar           varindex of INOUTVAR to process
 486         map_index       stackdepth * 5 + type, used for coalescing IOVARS.
 487
 488 IN/OUT
 489         interface_map   used for coalescing IOVARS. interface_map[map_index] ==
 490                         UNUSED, if this map_index (==stackdepth,type tupel) did not
 491                                         occur till now. Then interface_map[map_index] will be set
 492                                         to a new unique index.
 493         ls->new_varindex will be set to this new unique index to map the old
 494                          varindizes to the new ones.
 495
 496 Assigns a new unique index for the local var varindex (if not already done so)
 497 and then calls ssa_set_def to remember the definition in the bitvector array
 498 ls->var_def
 499
 500 ******************************************************************************/
 501
 502 void ssa_set_iovar(lsradata *ls, s4 iovar, int map_index, s4 *interface_map) {
 503                 if (interface_map[map_index] == UNUSED)
 504                         interface_map[map_index] = ls->ssavarcount++;
 505
 506                 ls->new_varindex[iovar] = interface_map[map_index];
 507 }
 508
 509
 510 /* ssa_set_interface ***********************************************************
 511
 512 Helper for ssa_init
 513
 514 IN: ls              pointer to lsradata structure
 515     *bptr           pointer to the basic block to be processed
 516
 517 IN/OUT
 518         interface_map   used for coalescing IOVARS. interface_map[map_index] ==
 519                         UNUSED, if this map_index (==stackdepth,type tupel) did not
 520                                         occur till now. Then interface_map[map_index] will be set
 521                                         to a new unique index. (see ssa_set_iovar)
 522
 523 Searches the basic block given by *bptr for IN and OUTVARS and coalesces them
 524 for each unique stackdepth,type dupel. For each OUTVAR with a different or no
 525 INVAR at the same stackdepth the definition of this OUTVAR in this basic block
 526 is remembered in ls->var_def. (see ssa_set_def)
 527
 528 ******************************************************************************/
 529
 530 void ssa_set_interface(jitdata *jd, basicblock *bptr, s4 *interface_map) {
 531         s4 *out, *in;
 532         int in_d, out_d;
 533         int o_map_index, i_map_index;
 534         lsradata *ls;
 535
 536         ls = jd->ls;
 537
 538         out = bptr->outvars;
 539         in = bptr->invars;
 540         in_d = bptr->indepth - 1;
 541         out_d = bptr->outdepth - 1;
 542
 543         /* ignore top Stackelement of instack in case of EXH or SBR blocks */
 544         /* These are no Interface stackslots! */
 545         if ((bptr->type == BBTYPE_EXH) ||
 546                 (bptr->type == BBTYPE_SBR)) {
 547                 in_d--;
 548         }
 549
 550         /* invars with no corresponding outvars are not defined here */
 551         /* just set up the interface_map */
 552
 553         for(;(in_d > out_d); in_d--) {
 554                 i_map_index = in_d * 5 + VAR(in[in_d])->type;
 555                 ssa_set_iovar(ls, in[in_d], i_map_index, interface_map);
 556         }
 557
 558         while((out_d >= 0)) {
 559                 /* set up interface_map */
 560
 561                 o_map_index = out_d * 5 + VAR(out[out_d])->type;
 562                 if (in_d >= 0) {
 563                         i_map_index = in_d * 5 + VAR(in[in_d])->type;
 564                         ssa_set_iovar(ls, in[in_d], i_map_index, interface_map);
 565                 }
 566                 ssa_set_iovar(ls, out[out_d], o_map_index, interface_map);
 567                 if (in_d == out_d) {
 568                         out_d--;
 569                         in_d--;
 570                 }
 571                 else {
 572                         out_d--;
 573                 }
 574         }
 575 }
 576
 577 #ifdef SSA_DEBUG_VERBOSE
 578 void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd) {
 579         int i,j;
 580         lsradata *ls;
 581
 582         ls = jd->ls;
 583
 584         printf("ssa_printtrees: maxlocals %3i", jd->localcount);
 585
 586         printf("Dominator Tree: \n");
 587         for(i = 0; i < ls->basicblockcount; i++) {
 588                 printf("%3i:",i);
 589                 for(j = 0; j < ls->basicblockcount; j++) {
 590                         if (dd->idom[j] == i) {
 591                                 printf(" %3i", j);
 592                         }
 593                 }
 594                 printf("\n");
 595         }
 596
 597         printf("Dominator Forest:\n");
 598         for(i = 0; i < ls->basicblockcount; i++) {
 599                 printf("%3i:",i);
 600                 for(j = 0; j < dd->num_DF[i]; j++) {
 601                                 printf(" %3i", dd->DF[i][j]);
 602                 }
 603                 printf("\n");
 604         }
 605 #if 0
 606         if (ls->ssavarcount > 0) {
 607         printf("Use Sites\n");
 608         for(i = 0; i < ls->ssavarcount; i++) {
 609                 printf("use_sites[%3i]=%p:",i,(void *)ls->use_sites[i]);
 610                 for(j = 0; j < ls->basicblockcount; j++) {
 611                         if ((j % 5) == 0) printf(" ");
 612                         if (bv_get_bit(ls->use_sites[i], j))
 613                                 printf("1");
 614                         else
 615                                 printf("0");
 616                 }
 617                 printf("\n");
 618         }
 619         }
 620 #endif
 621         printf("var Definitions:\n");
 622         for(i = 0; i < jd->basicblockcount; i++) {
 623                 printf("var_def[%3i]=%p:",i,(void *)ls->var_def[i]);
 624                 for(j = 0; j < ls->ssavarcount; j++) {
 625                         if ((j % 5) == 0) printf(" ");
 626                         if (bv_get_bit(ls->var_def[i], j))
 627                                 printf("1");
 628                         else
 629                                 printf("0");
 630                 }
 631                 printf(" (");
 632                 for(j=0; j < ((((ls->ssavarcount * 5+7)/8) + sizeof(int) - 1)/sizeof(int));
 633                         j++)
 634                         printf("%8x",ls->var_def[i][j]);
 635                 printf(")\n");
 636         }
 637 }
 638 #endif
 639
 640
 641 /****************************************************************************
 642 Optimizations
 643 ****************************************************************************/
 644
 645
 646 /****************************************************************************
 647 Dead Code Elimination
 648 ****************************************************************************/
 649 void dead_code_elimination(jitdata *jd, graphdata *gd) {
 650         int a, i, source;
 651         worklist *W;
 652
 653         instruction *iptr;
 654         struct lifetime *lt, *s_lt;
 655
 656         bool remove_statement;
 657         struct site *use;
 658
 659         lsradata *ls;
 660 #ifdef SSA_DEBUG_VERBOSE
 661         methodinfo *m;
 662
 663         m  = jd->m;
 664 #endif
 665         ls = jd->ls;
 666
 667         W = wl_new(ls->lifetimecount);
 668         if (ls->lifetimecount > 0) {
 669
 670                 /* put all lifetimes into Worklist W */
 671
 672                 for(a = 0; a < ls->lifetimecount; a++) {
 673                         if (ls->lifetime[a].type != UNUSED) {
 674                                 wl_add(W, a);
 675                         }
 676                 }
 677         }
 678
 679         /* Remove unused lifetimes */
 680
 681         while(!wl_is_empty(W)) {
 682
 683                 /* take a var out of Worklist */
 684
 685                 a = wl_get(W);
 686
 687                 lt = &(ls->lifetime[a]);
 688                 if ((lt->def == NULL) || (lt->type == UNUSED))
 689
 690                         /* lifetime was already removed -> no defs anymore */
 691
 692                         continue;
 693
 694                 /* Remove lifetimes, which are only used in the phi function which */
 695                 /* defines them! */
 696
 697                 remove_statement = (lt->use != NULL) && (lt->use->iindex < 0);
 698                 for(use = lt->use; (remove_statement && (use != NULL));
 699                         use = use->next)
 700                 {
 701                         remove_statement = remove_statement &&
 702                                 (use->b_index == lt->def->b_index) &&
 703                                 (use->iindex == lt->def->iindex);
 704                 }
 705
 706                 if (remove_statement) {
 707 #ifdef SSA_DEBUG_CHECK
 708
 709                         /* def == use can only happen in phi functions */
 710
 711                         if (remove_statement)
 712                                 _SSA_ASSERT(lt->use->iindex < 0);
 713 #endif
 714
 715                         /* give it free for removal */
 716
 717                         lt->use = NULL;
 718                 }
 719
 720                 if (lt->use == NULL) {
 721
 722                         /* Look at statement of definition of a and remove it,           */
 723                         /* if the Statement has no sideeffects other than the assignemnt */
 724                         /* of a */
 725
 726                         if (lt->def->iindex < 0 ) {
 727
 728                                 /* phi function */
 729                                 /* delete use of sources , delete phi functions  */
 730
 731                                 _SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] !=
 732                                                         NULL);
 733
 734                                 for (i = 1;i <= graph_get_num_predecessor(gd, lt->def->b_index);
 735                                          i++) {
 736                                         source =
 737                                                 ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
 738                                         if ((source != ls->varcount_with_indices) &&
 739                                                 (source != lt->v_index) &&
 740                                                 (source != UNUSED)) {
 741
 742                                                 /* phi Argument was not already removed (already in
 743                                                    because of "selfdefinition") */
 744
 745                                                 s_lt = &(ls->lifetime[source]);
 746
 747                                                 /* remove it */
 748
 749                                                 lt_remove_use_site(s_lt,lt->def->b_index,
 750                                                                                    lt->def->iindex);
 751
 752                                                 /*  put it on the Worklist */
 753
 754                                                 wl_add(W, source);
 755                                         }
 756                                 }
 757
 758                                 /* now delete phi function itself */
 759 #ifdef SSA_DEBUG_VERBOSE
 760                                         if (compileverbose) {
 761                                                 printf("dce: BB%3i phi for var %3i=%3i removed \n",
 762                                                            lt->def->b_index, -lt->def->iindex - 1,
 763                                                            lt->v_index);
 764                                         }
 765 #endif
 766
 767                                 ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
 768                         }
 769                         else {
 770
 771                                 /* "normal" Use by ICMD */
 772
 773                                 remove_statement = false;
 774                                 if (lt->def->b_index != 0) {
 775
 776                                         /* do not look at artificial block 0 (parameter init) */
 777
 778                                         iptr = ls->basicblocks[lt->def->b_index]->iinstr +
 779                                                 lt->def->iindex;
 780
 781                                         if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
 782
 783                                                 /* if ICMD could throw an exception do not remove it! */
 784
 785                                                 remove_statement = false;
 786 #ifdef SSA_DEBUG_VERBOSE
 787                                                 if (compileverbose) {
 788                                                         printf("dce: PEI: BB%3i II%3i %s not removed \n",
 789                                                                    lt->def->b_index, lt->def->iindex,
 790                                                                    bytecode[iptr->opc].mnemonic);
 791                                                 }
 792 #endif
 793
 794                                         }
 795                                         else {
 796                                                 remove_statement = true;
 797
 798                                                 switch (icmd_table[iptr->opc].dataflow) {
 799                                                 case DF_3_TO_0:
 800                                                 case DF_3_TO_1: /* icmd has s1, s2 and s3 */
 801                                                         a = iptr->sx.s23.s3.varindex;
 802                                                         s_lt = ls->lifetime + a;
 803                                                         lt_remove_use_site(s_lt, lt->def->b_index,
 804                                                                                            lt->def->iindex);
 805                                                         wl_add(W, a);
 806
 807                                                         /* "fall through" for handling of s2 and s1 */
 808
 809                                                 case DF_2_TO_0:
 810                                                 case DF_2_TO_1: /* icmd has s1 and s2 */
 811                                                         a = iptr->sx.s23.s2.varindex;
 812                                                         s_lt = ls->lifetime + a;
 813                                                         lt_remove_use_site(s_lt, lt->def->b_index,
 814                                                                                            lt->def->iindex);
 815                                                         wl_add(W, a);
 816
 817                                                         /* "fall through" for handling of s1 */
 818
 819                                                         /* DF_{IINC,STORE,LOAD} are DF_{1_TO_1,MOVE,COPY} */
 820
 821                                                 case DF_1_TO_0:
 822                                                 case DF_1_TO_1:
 823                                                 case DF_MOVE:
 824                                                 case DF_COPY:
 825                                                         a = iptr->s1.varindex;
 826                                                         s_lt = ls->lifetime + a;
 827                                                         lt_remove_use_site(s_lt, lt->def->b_index,
 828                                                                                            lt->def->iindex);
 829                                                         wl_add(W, a);
 830                                                 }
 831 #ifdef SSA_DEBUG_VERBOSE
 832                                                 if (compileverbose) {
 833                                                         printf("dce: BB%3i II%3i %s removed \n",
 834                                                                    lt->def->b_index, lt->def->iindex,
 835                                                                    bytecode[iptr->opc].mnemonic);
 836                                                 }
 837 #endif
 838                                         }
 839
 840                                         if (remove_statement) {
 841
 842                                                 /* remove statement */
 843
 844 #ifdef SSA_DEBUG_VERBOSE
 845                                                 if (compileverbose)
 846                                                         printf("dce: %s %s:at BB %3i II %3i NOP-<%s\n",
 847                                                                    m->clazz->name->text, m->name->text,
 848                                                                    lt->def->b_index, lt->def->iindex,
 849                                                                    icmd_table[iptr->opc].name);
 850 #endif
 851                                                 iptr->opc = ICMD_NOP;
 852                                         }
 853                                 } /* (lt->def->b_index != 0) */
 854                         } /* if (lt->def->iindex < 0 ) else */
 855
 856                         /* remove definition of a */
 857
 858 #ifdef SSA_DEBUG_VERBOSE
 859                         if (compileverbose)
 860                                 printf("dce: var %3i removed\n", lt->v_index);
 861 #endif
 862                         VAR(lt->v_index)->type = UNUSED;
 863                         lt->type = UNUSED;
 864                         lt->def = NULL;
 865 /*                      jd->var */
 866                 } /* if (lt->use == NULL) */
 867         } /* while(!wl_is_empty(W)) */
 868 } /* dead_code_elimination */
 869
 870 /****************************************************************************
 871 Simple Constant Propagation
 872 ****************************************************************************/
 873
 874 void simple_constant_propagation() {
 875 }
 876
 877 /****************************************************************************
 878 Optimization
 879 *******************************************************************************/
 880 void copy_propagation(jitdata *jd, graphdata *gd) {
 881         int a, i, source;
 882         int only_source;
 883
 884         worklist *W;
 885
 886         instruction *iptr;
 887         struct lifetime *lt, *s_lt;
 888
 889         lsradata *ls;
 890
 891         ls = jd->ls;
 892
 893         W = wl_new(ls->lifetimecount);
 894         if (ls->lifetimecount > 0) {
 895                 /* put all lifetimes on Worklist */
 896                 for(a = 0; a < ls->lifetimecount; a++) {
 897                         if (ls->lifetime[a].type != UNUSED) {
 898                                 wl_add(W, a);
 899                         }
 900                 }
 901         }
 902
 903         while(!wl_is_empty(W)) {
 904                 /* take a var out of Worklist */
 905                 a = wl_get(W);
 906
 907                 lt = ls->lifetime + a;
 908                 if (lt->type == UNUSED)
 909                         continue;
 910                 _SSA_ASSERT(lt->def != NULL);
 911 #if 0
 912                 _SSA_ASSERT(lt->use != NULL);
 913 #endif
 914                 if (lt->def->iindex < 0 ) {
 915
 916                         /* phi function */
 917                         /* look, if phi function degenerated to a x = phi(y) */
 918                         /* and if so, substitute y for every use of x */
 919
 920                         _SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] != NULL);
 921
 922                         only_source = ls->varcount_with_indices;
 923                         for (i = 1; i <= graph_get_num_predecessor(gd, lt->def->b_index);
 924                                  i++) {
 925                                         source = ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
 926                                         if ((source != ls->varcount_with_indices) &&
 927                                                 (source != UNUSED)) {
 928                                                 if (only_source == ls->varcount_with_indices) {
 929
 930                                                         /* first valid source argument of phi function */
 931
 932                                                         only_source = source;
 933                                                 } else {
 934
 935                                                         /* second valid source argument of phi function */
 936                                                         /* exit for loop */
 937
 938                                                         only_source = ls->varcount_with_indices;
 939                                                         break;
 940                                                 }
 941                                         }
 942                         }
 943
 944                         if (only_source != ls->varcount_with_indices) {
 945
 946 #ifdef SSA_DEBUG_VERBOSE
 947                                 if (compileverbose)
 948                                         printf(
 949                                                    "-- copy propagation phi-func: BB %3i II %3i: %3i -> %3i\n",
 950                                                    lt->def->b_index, lt->def->iindex,
 951                                                    only_source, lt->v_index);
 952 #endif
 953                                 s_lt = ls->lifetime + only_source;
 954
 955                                 /* replace all use sites of lt with the var_index only_source */
 956
 957                                 ssa_replace_use_sites( jd, gd, lt, only_source, W);
 958
 959                                 /* delete def of lt */
 960
 961                                 ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
 962
 963                                 /* remove this deleted use site of s_lt */
 964
 965                                 lt_remove_use_site(s_lt, lt->def->b_index, lt->def->iindex);
 966
 967                                 lt->def = NULL;
 968
 969                                 /* move use sites from lt to s_lt */
 970
 971                                 lt_move_use_sites(lt, s_lt);
 972
 973                                 /* invalidate lt */
 974
 975                                 lt->type = UNUSED;
 976                                 VAR(lt->v_index)->type = UNUSED;
 977
 978                                 /* add s_lt again to Worklist W */
 979
 980                                 wl_add(W, s_lt->v_index);
 981 #ifdef SSA_DEBUG_VERBOSE
 982                                 if (compileverbose)
 983                                         _ssa_print_lt(s_lt);
 984 #endif
 985                         } /* if (only_source != ls->varcount_with_indices) */
 986                 }
 987                 else { /* if (lt->def->iindex < 0 ) */
 988
 989                         /* def in argument passing - no propagation possible */
 990                         /* (there is no ICMD for this... */
 991
 992                         if (lt->def->b_index == 0)
 993                                 continue;
 994
 995                         /* def in "normal" ICMD */
 996
 997                         iptr = ls->basicblocks[lt->def->b_index]->iinstr +
 998                                 lt->def->iindex;
 999
1000                         switch(iptr->opc) {
1001                         case ICMD_ISTORE:
1002                         case ICMD_LSTORE:
1003                         case ICMD_FSTORE:
1004                         case ICMD_DSTORE:
1005                         case ICMD_ASTORE:
1006                         case ICMD_ILOAD:
1007                         case ICMD_LLOAD:
1008                         case ICMD_FLOAD:
1009                         case ICMD_DLOAD:
1010                         case ICMD_ALOAD:
1011                         case ICMD_MOVE:
1012 #ifdef SSA_DEBUG_VERBOSE
1013                                 if (compileverbose)
1014                                         printf(
1015                                                    "-- copy propagation %3i %s: BB %3i II %3i: %3i -> %3i\n",
1016                                                    iptr->opc, bytecode[iptr->opc].mnemonic,
1017                                                    lt->def->b_index, lt->def->iindex,
1018                                                    iptr->s1.varindex, iptr->dst.varindex);
1019 #endif
1020                                 s_lt = ls->lifetime + iptr->s1.varindex;
1021
1022                                 _SSA_ASSERT( lt->v_index == iptr->dst.varindex);
1023
1024                                 /* replace all use sites of lt with the var_index */
1025                                 /* iptr->s1.varindex (==lt->v_index) */
1026
1027                                 ssa_replace_use_sites(jd, gd, lt, iptr->s1.varindex, W);
1028
1029                                 _SSA_ASSERT(lt->def->next == NULL);
1030                                 _SSA_ASSERT(s_lt->def != NULL);
1031                                 _SSA_ASSERT(s_lt->def->next == NULL);
1032
1033                                 /* this ICMD is not a PEI -> so no danger in deleting it!     */
1034                                 /* delete def of lt (ICMD_NOP) */
1035
1036                                 /* lt->def->iindex > 0 -> ICMD */
1037
1038                                 iptr->opc = ICMD_NOP;
1039
1040                                 /* remove this deleted use site of s_lt */
1041
1042                                 lt_remove_use_site(s_lt, lt->def->b_index, lt->def->iindex);
1043
1044                                 /* invalidate def site of lt */
1045
1046                                 lt->def = NULL;
1047
1048                                 /* move use sites from lt to s_lt */
1049
1050                                 lt_move_use_sites(lt, s_lt);
1051
1052                                 /* invalidate lt */
1053
1054                                 lt->type = UNUSED;
1055                                 VAR(lt->v_index)->type = UNUSED;
1056
1057                                 /* add s_lt again to Worklist W */
1058                                 wl_add(W, s_lt->v_index);
1059 #ifdef SSA_DEBUG_VERBOSE
1060                                 if (compileverbose)
1061                                         _ssa_print_lt(s_lt);
1062 #endif
1063                                 break;
1064                         }
1065                 } /* if (lt->def->iindex < 0 ) */
1066         } /* while(!wl_is_empty(W)) */
1067 }
1068
1069 void ssa_replace_use_sites(jitdata *jd, graphdata *gd, struct lifetime *lt,
1070                                                    int new_v_index, worklist *W) {
1071         struct site *s;
1072         int i, source;
1073         instruction *iptr;
1074         s4 *argp;
1075
1076         methoddesc *md;
1077         builtintable_entry *bte;
1078         lsradata *ls;
1079
1080         ls = jd->ls;
1081         md = jd->m->parseddesc;
1082
1083
1084         for(s = lt->use; s != NULL; s = s->next) {
1085                 if (s->iindex < 0) {
1086
1087                         /* Use in phi function */
1088
1089                         for (i = 1;i <= graph_get_num_predecessor(gd, s->b_index); i++) {
1090                                 source = ls->phi[s->b_index][-s->iindex-1][i];
1091                                 if (source == lt->v_index) {
1092
1093                                         /* check if this use in this phi function is a     */
1094                                         /* "selfdefinition" (x = phi(...,x,...))           */
1095                                         /* if so replace the use with -1 (x=phi(...,-1,...)*/
1096
1097                                         if (new_v_index == ls->phi[s->b_index][-s->iindex-1][0]) {
1098 #ifdef SSA_DEBUG_VERBOSE
1099                                                 if (W != NULL) {
1100                                                         if (compileverbose)
1101                                                                 printf(
1102                                                          "copy propagation phi: BB %3i I %3i: %3i -> %3i\n",
1103                                                          s->b_index, s->iindex, -1, source);
1104                                                 }
1105 #endif
1106                                                 ls->phi[s->b_index][-s->iindex-1][i] = -1;
1107
1108                                                 /* remove this use site of use site */
1109                                                 lt_remove_use_site(lt, s->b_index, s->iindex);
1110                                         }
1111                                         else {
1112 #ifdef SSA_DEBUG_VERBOSE
1113                                                 if (W != NULL) {
1114                                                         if (compileverbose)
1115                                                                 printf(
1116                                                          "copy propagation phi: BB %3i I %3i: %3i -> %3i\n",
1117                                                          s->b_index, s->iindex, new_v_index, source);
1118                                                 }
1119 #endif
1120                                                 ls->phi[s->b_index][-s->iindex-1][i] = new_v_index;
1121                                         }
1122                                 }
1123                         }
1124                         if (W != NULL) {
1125
1126                                 /* Add var, which is defined by this phi function to */
1127                                 /* the worklist */
1128
1129                                 source = ls->phi[s->b_index][-s->iindex-1][0];
1130                                 wl_add(W, source);
1131                         }
1132                 }
1133                 else { /* use in ICMD */
1134
1135                         iptr = ls->basicblocks[s->b_index]->iinstr +
1136                                 s->iindex;
1137
1138                 /* check for use (s1, s2, s3 or special (argp) ) */
1139
1140                         i = UNUSED;
1141                         switch (icmd_table[iptr->opc].dataflow) {
1142                         case DF_3_TO_0:
1143                         case DF_3_TO_1: /* icmd has s1, s2 and s3 */
1144                                 if (iptr->sx.s23.s3.varindex == lt->v_index) {
1145 #ifdef SSA_DEBUG_VERBOSE
1146                                         if (W != NULL) {
1147                                                 if (compileverbose)
1148                                                         printf("copy propagation loc3: BB %3i I %3i: %3i -> \
1149                                     %3i\n", s->b_index, s->iindex,
1150                                                                    new_v_index, iptr->sx.s23.s3.varindex);
1151                                         }
1152 #endif
1153                                         iptr->sx.s23.s3.varindex = new_v_index;
1154                                 }
1155
1156                                 /* now "fall through" for handling of s2 and s1 */
1157
1158                         case DF_2_TO_0:
1159                         case DF_2_TO_1: /* icmd has s1 and s2 */
1160                                 if (iptr->sx.s23.s2.varindex == lt->v_index) {
1161 #ifdef SSA_DEBUG_VERBOSE
1162                                         if (W != NULL) {
1163                                                 if (compileverbose)
1164                                                         printf("copy propagation loc2: BB %3i I %3i: %3i -> \
1165                                     %3i\n", s->b_index, s->iindex,
1166                                                                    new_v_index, iptr->sx.s23.s2.varindex);
1167                                         }
1168 #endif
1169                                         iptr->sx.s23.s2.varindex = new_v_index;
1170                                 }
1171
1172                                 /* now "fall through" for handling of s1 */
1173
1174                         case DF_1_TO_0:
1175                         case DF_1_TO_1:
1176                         case DF_MOVE:
1177                         case DF_COPY:
1178                                 if (iptr->s1.varindex == lt->v_index) {
1179 #ifdef SSA_DEBUG_VERBOSE
1180                                         if (W != NULL) {
1181                                                 if (compileverbose)
1182                                                         printf(
1183                                                         "copy propagation loc1: BB %3i I %3i: %3i -> %3i\n",
1184                                                         s->b_index, s->iindex, new_v_index,
1185                                                         iptr->s1.varindex);
1186                                         }
1187 #endif
1188                                         iptr->s1.varindex = new_v_index;
1189                                 }
1190                                 break;
1191
1192                                 /* TODO: */
1193                                 /* ? really look at md->paramcount or iptr->s1.argcount */
1194                                 /* has to be taken, so that pass-through stackslots get */
1195                                 /* renamed, too? */
1196
1197                         case DF_INVOKE:
1198                                 INSTRUCTION_GET_METHODDESC(iptr,md);
1199                                 i = md->paramcount;
1200                                 break;
1201                         case DF_BUILTIN:
1202                                 bte = iptr->sx.s23.s3.bte;
1203                                 md = bte->md;
1204                                 i = md->paramcount;
1205                                 break;
1206                         case DF_N_TO_1:
1207                                 i = iptr->s1.argcount;
1208                                 break;
1209                         }
1210                         if (i != UNUSED) {
1211                                 argp = iptr->sx.s23.s2.args;
1212                                 while (--i >= 0) {
1213                                         if (*argp == lt->v_index) {
1214 #ifdef SSA_DEBUG_VERBOSE
1215                                                 if (W != NULL) {
1216                                                         if (compileverbose)
1217                                                                 printf(
1218                                                                            "copy propagation locN: BB %3i I %3i: %3i -> %3i\n"
1219                                                                            , s->b_index, s->iindex, new_v_index, *argp);
1220                                                 }
1221 #endif
1222                                                 *argp = new_v_index;
1223
1224                                         }
1225                                         argp++;
1226                                 }
1227                         }
1228
1229                 } /* if (s->iindex < 0) */
1230         } /* for(s = lt->use; s != NULL; s = s->next) */
1231 }
1232
1233 #ifdef SSA_DEBUG_VERBOSE
1234 void ssa_print_lt(lsradata *ls) {
1235         int i;
1236         struct lifetime *lt;
1237
1238         printf("SSA LT Def/Use\n");
1239         for(i = 0; i < ls->lifetimecount; i++) {
1240                 lt = ls->lifetime + i;
1241                 _ssa_print_lt(lt);
1242         }
1243 }
1244
1245 void _ssa_print_lt(struct lifetime *lt) {
1246         struct site *use;
1247
1248         if (lt->type != UNUSED) {
1249                 printf("VI %3i Type %3i Def: ",lt->v_index, lt->type);
1250                 if (lt->def != NULL)
1251                         printf("%3i,%3i Use: ",lt->def->b_index, lt->def->iindex);
1252                 else
1253                         printf("%3i,%3i Use: ",0,0);
1254                 for(use = lt->use; use != NULL; use = use->next)
1255                         printf("%3i,%3i ",use->b_index, use->iindex);
1256                 printf("\n");
1257         }
1258 }
1259
1260 void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage)
1261 {
1262         char type;
1263         char kind;
1264
1265         switch (v->type) {
1266                 case TYPE_INT: type = 'i'; break;
1267                 case TYPE_LNG: type = 'l'; break;
1268                 case TYPE_FLT: type = 'f'; break;
1269                 case TYPE_DBL: type = 'd'; break;
1270                 case TYPE_ADR: type = 'a'; break;
1271                 case TYPE_RET: type = 'r'; break;
1272                 default:       type = '?';
1273         }
1274
1275         if (index < jd->localcount) {
1276                 kind = 'L';
1277                 if (v->flags & (PREALLOC | INOUT))
1278                                 printf("<INVALID FLAGS!>");
1279         }
1280         else {
1281                 if (v->flags & PREALLOC) {
1282                         kind = 'A';
1283                         if (v->flags & INOUT)
1284                                 printf("<INVALID FLAGS!>");
1285                 }
1286                 else if (v->flags & INOUT)
1287                         kind = 'I';
1288                 else
1289                         kind = 'T';
1290         }
1291
1292         printf("%c%c%3d", kind, type, index);
1293
1294         if (v->flags & SAVEDVAR)
1295                 putchar('!');
1296
1297         putchar(' ');
1298         fflush(stdout);
1299 }
1300 #endif
1301
1302 /****************************************************************************
1303 Optimization
1304 ****************************************************************************/
1305
1306 /*
1307  * These are local overrides for various environment variables in Emacs.
1308  * Please do not remove this and leave it at the end of the file, where
1309  * Emacs will automagically detect them.
1310  * ---------------------------------------------------------------------
1311  * Local variables:
1312  * mode: c
1313  * indent-tabs-mode: t
1314  * c-basic-offset: 4
1315  * tab-width: 4
1316  * End:
1317  */