src/vm/jit/optimizing/reorder.c

   1 /* src/vm/reorder.c - basic block reordering
   2
   3    Copyright (C) 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    J. Wenninger, Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Christian Thalinger
  28
  29    Changes:
  30
  31    $Id: cacao.c 4357 2006-01-22 23:33:38Z twisti $
  32
  33 */
  34
  35
  36 #include "config.h"
  37
  38 #include <assert.h>
  39
  40 #include "vm/types.h"
  41
  42 #include "mm/memory.h"
  43 #include "vm/jit/jit.h"
  44
  45
  46 /* reorder_place_next_unplaced_block *******************************************
  47
  48    Find next unplaced basic block in the array and place it.
  49
  50 *******************************************************************************/
  51
  52 static basicblock *reorder_place_next_unplaced_block(jitdata *jd, u1 *blocks,
  53                                                                                                          basicblock *bptr)
  54 {
  55         basicblock *tbptr;
  56         s4          i;
  57
  58         for (i = 0; i < jd->basicblockcount; i++) {
  59                 if (blocks[i] == false) {
  60                         tbptr = &jd->basicblocks[i];
  61
  62                         /* place the block */
  63
  64                         blocks[tbptr->nr] = true;
  65
  66                         /* change the basic block order */
  67
  68                         bptr->next = tbptr;
  69
  70                         return tbptr;
  71                 }
  72         }
  73
  74         return NULL;
  75 }
  76
  77
  78 /* reorder *********************************************************************
  79
  80    Reorders basic blocks in respect to their execution frequency.
  81
  82 *******************************************************************************/
  83
  84 bool reorder(jitdata *jd)
  85 {
  86         methodinfo  *m;
  87         codeinfo    *pcode;
  88         basicblock  *bptr;
  89         basicblock  *tbptr;                 /* taken basic block pointer          */
  90         basicblock  *ntbptr;                /* not-taken basic block pointer      */
  91         basicblock  *pbptr;                 /* predecessor basic block pointer    */
  92         u4           freq;
  93         u4           tfreq;
  94         u4           ntfreq;
  95         u4           pfreq;
  96         instruction *iptr;
  97         u1          *blocks;                /* flag array                         */
  98         s4           placed;                /* number of placed basic blocks      */
  99         s4           i;
 100
 101         /* get required compiler data */
 102
 103         m = jd->m;
 104
 105 #if !defined(NDEBUG)
 106         method_println(m);
 107 #endif
 108
 109         /* get the codeinfo of the previous method */
 110
 111         pcode = m->code;
 112
 113         /* XXX debug */
 114         if (jd->basicblockcount > 8)
 115                 return true;
 116
 117         /* allocate flag array for blocks which are placed */
 118
 119         blocks = DMNEW(u1, jd->basicblockcount);
 120
 121         MZERO(blocks, u1, jd->basicblockcount);
 122
 123         /* Get the entry block and iterate over all basic blocks until we
 124            have placed all blocks. */
 125
 126         bptr   = jd->basicblocks;
 127         placed = 0;
 128
 129         /* the first block is always placed as the first one */
 130
 131         blocks[0] = true;
 132         placed++;
 133
 134         while (placed <= jd->basicblockcount + 1) {
 135                 /* get last instruction of basic block */
 136
 137                 iptr = bptr->iinstr + bptr->icount - 1;
 138
 139                 printf("L%03d, ", bptr->nr);
 140
 141                 switch (bptr->type) {
 142                 case BBTYPE_STD:
 143                         printf("STD");
 144                         break;
 145                 case BBTYPE_EXH:
 146                         printf("EXH");
 147                         break;
 148                 case BBTYPE_SBR:
 149                         printf("SBR");
 150                         break;
 151                 }
 152
 153                 printf(", predecessors: %d, successors: %d, frequency: %d -> ",
 154                            bptr->predecessorcount, bptr->successorcount,
 155                            pcode->bbfrequency[bptr->nr]);
 156
 157                 switch (iptr->opc) {
 158                 case ICMD_RETURN:
 159                 case ICMD_IRETURN:
 160                 case ICMD_LRETURN:
 161                 case ICMD_FRETURN:
 162                 case ICMD_DRETURN:
 163                 case ICMD_ARETURN:
 164                 case ICMD_ATHROW:
 165                         puts("return");
 166
 167                         tbptr = reorder_place_next_unplaced_block(jd, blocks, bptr);
 168
 169                         placed++;
 170
 171                         /* all blocks placed? return. */
 172
 173                         if (tbptr == NULL)
 174                                 continue;
 175
 176                         /* set last placed block */
 177
 178                         bptr = tbptr;
 179                         break;
 180
 181                 case ICMD_IFEQ:
 182                 case ICMD_IFNE:
 183                 case ICMD_IFLT:
 184                 case ICMD_IFGE:
 185                 case ICMD_IFGT:
 186                 case ICMD_IFLE:
 187
 188                 case ICMD_IF_ICMPEQ:
 189                 case ICMD_IF_ICMPNE:
 190                 case ICMD_IF_ICMPLT:
 191                 case ICMD_IF_ICMPGE:
 192                 case ICMD_IF_ICMPGT:
 193                 case ICMD_IF_ICMPLE:
 194
 195                 case ICMD_IF_ACMPEQ:
 196                 case ICMD_IF_ACMPNE:
 197
 198                 case ICMD_IFNULL:
 199                 case ICMD_IFNONNULL:
 200
 201                 case ICMD_IF_LEQ:
 202                 case ICMD_IF_LNE:
 203                 case ICMD_IF_LLT:
 204                 case ICMD_IF_LGE:
 205                 case ICMD_IF_LGT:
 206                 case ICMD_IF_LLE:
 207
 208                 case ICMD_IF_LCMPEQ:
 209                 case ICMD_IF_LCMPNE:
 210                 case ICMD_IF_LCMPLT:
 211                 case ICMD_IF_LCMPGE:
 212                 case ICMD_IF_LCMPGT:
 213                 case ICMD_IF_LCMPLE:
 214                         tbptr  = iptr->dst.block;
 215                         ntbptr = bptr->next;
 216
 217                         printf("cond. L%03d\n", tbptr->nr);
 218
 219                         tfreq  = pcode->bbfrequency[tbptr->nr];
 220                         ntfreq = pcode->bbfrequency[ntbptr->nr];
 221
 222                         /* check which branch is more frequently */
 223
 224                         if ((blocks[tbptr->nr] == false) && (tfreq > ntfreq)) {
 225                                 /* If we place the taken block, we need to change the
 226                                    conditional instruction (opcode and target). */
 227
 228                                 iptr->opc       = jit_complement_condition(iptr->opc);
 229                                 iptr->dst.block = ntbptr;
 230
 231                                 /* change the basic block order */
 232
 233                                 bptr->next = tbptr;
 234
 235                                 /* place taken block */
 236
 237                                 blocks[tbptr->nr] = true;
 238                                 placed++;
 239
 240                                 /* set last placed block */
 241
 242                                 bptr = tbptr;
 243                         }
 244                         else if (blocks[ntbptr->nr] == false) {
 245                                 /* place not-taken block */
 246
 247                                 blocks[ntbptr->nr] = true;
 248                                 placed++;
 249
 250                                 /* set last placed block */
 251
 252                                 bptr = ntbptr;
 253                         }
 254                         else {
 255                                 tbptr = reorder_place_next_unplaced_block(jd, blocks, bptr);
 256
 257                                 placed++;
 258
 259                                 /* all blocks placed? return. */
 260
 261                                 if (tbptr == NULL)
 262                                         continue;
 263
 264                                 /* set last placed block */
 265
 266                                 bptr = tbptr;
 267                         }
 268                         break;
 269
 270                 case ICMD_GOTO:
 271                         tbptr = iptr->dst.block;
 272
 273                         printf("L%03d\n", tbptr->nr);
 274
 275                         /* If next block is already placed, search for another
 276                            one. */
 277
 278                         if (blocks[tbptr->nr] == true) {
 279                                 tbptr = reorder_place_next_unplaced_block(jd, blocks, bptr);
 280
 281                                 placed++;
 282
 283                                 /* all block placed? return. */
 284
 285                                 if (tbptr == NULL)
 286                                         continue;
 287                         }
 288                         else if (tbptr->predecessorcount > 1) {
 289                                 /* Check if the target block has other predecessors.
 290                                    And if the other predecessors have a higher
 291                                    frequency, don't place it. */
 292
 293                                 freq = pcode->bbfrequency[bptr->nr];
 294
 295                                 for (i = 0; i < tbptr->predecessorcount; i++) {
 296                                         pbptr = tbptr->predecessors[i];
 297
 298                                         /* skip the current basic block */
 299
 300                                         if (pbptr->nr != bptr->nr) {
 301                                                 pfreq = pcode->bbfrequency[pbptr->nr];
 302
 303                                                 /* Other predecessor has a higher frequency?
 304                                                    Search for another block to place. */
 305
 306                                                 if (pfreq > freq) {
 307                                                         tbptr = reorder_place_next_unplaced_block(jd,
 308                                                                                                                                           blocks,
 309                                                                                                                                           bptr);
 310
 311                                                         placed++;
 312
 313                                                         /* all block placed? return. */
 314
 315                                                         if (tbptr == NULL)
 316                                                                 break;
 317
 318                                                         goto goto_continue;
 319                                                 }
 320                                         }
 321                                 }
 322
 323                         goto_continue:
 324                                 /* place block */
 325
 326                                 blocks[tbptr->nr] = true;
 327                                 placed++;
 328                         }
 329
 330                         /* set last placed block */
 331
 332                         bptr = tbptr;
 333                         break;
 334
 335                 default:
 336                         /* No control flow instruction at the end of the basic
 337                            block (fall-through).  Just place the block. */
 338
 339                         puts("next");
 340
 341                         tbptr = bptr->next;
 342
 343                         /* If next block is already placed, search for another
 344                            one. */
 345
 346                         if (blocks[tbptr->nr] == true) {
 347                                 tbptr = reorder_place_next_unplaced_block(jd, blocks, bptr);
 348
 349                                 placed++;
 350
 351                                 /* all block placed? return. */
 352
 353                                 if (tbptr == NULL)
 354                                         continue;
 355                         }
 356                         else {
 357                                 /* place block */
 358
 359                                 blocks[tbptr->nr] = true;
 360                                 placed++;
 361                         }
 362
 363                         /* set last placed block */
 364
 365                         bptr = tbptr;
 366                         break;
 367                 }
 368         }
 369
 370         /* close the basic block chain with the last dummy basic block */
 371
 372         bptr->next = &jd->basicblocks[jd->basicblockcount];
 373
 374         puts("");
 375
 376         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 377                 printf("L%03d\n", bptr->nr);
 378         }
 379
 380         /* everything's ok */
 381
 382         return true;
 383 }
 384
 385
 386 /*
 387  * These are local overrides for various environment variables in Emacs.
 388  * Please do not remove this and leave it at the end of the file, where
 389  * Emacs will automagically detect them.
 390  * ---------------------------------------------------------------------
 391  * Local variables:
 392  * mode: c
 393  * indent-tabs-mode: t
 394  * c-basic-offset: 4
 395  * tab-width: 4
 396  * End:
 397  * vim:noexpandtab:sw=4:ts=4:
 398  */