src/vm/jit/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(methodinfo *m, u1 *blocks,
  53                                                                                                          basicblock *bptr)
  54 {
  55         basicblock *tbptr;
  56         s4          i;
  57
  58         for (i = 0; i < m->basicblockcount; i++) {
  59                 if (blocks[i] == false) {
  60                         tbptr = &m->basicblocks[i];
  61
  62                         /* place the block */
  63
  64                         blocks[tbptr->debug_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         method_println(m);
 105
 106         /* get the codeinfo of the previous method */
 107
 108         pcode = m->code;
 109
 110         /* XXX debug */
 111         if (m->basicblockcount > 8)
 112                 return true;
 113
 114         /* allocate flag array for blocks which are placed */
 115
 116         blocks = DMNEW(u1, m->basicblockcount);
 117
 118         MZERO(blocks, u1, m->basicblockcount);
 119
 120         /* Get the entry block and iterate over all basic blocks until we
 121            have placed all blocks. */
 122
 123         bptr   = m->basicblocks;
 124         placed = 0;
 125
 126         /* the first block is always placed as the first one */
 127
 128         blocks[0] = true;
 129         placed++;
 130
 131         while (placed <= m->basicblockcount) {
 132                 /* get last instruction of basic block */
 133
 134                 iptr = bptr->iinstr + bptr->icount - 1;
 135
 136                 printf("L%03d, ", bptr->debug_nr);
 137
 138                 switch (bptr->type) {
 139                 case BBTYPE_STD:
 140                         printf("STD");
 141                         break;
 142                 case BBTYPE_EXH:
 143                         printf("EXH");
 144                         break;
 145                 case BBTYPE_SBR:
 146                         printf("SBR");
 147                         break;
 148                 }
 149
 150                 printf(", predecessors: %d, successors: %d, frequency: %d -> ",
 151                            bptr->predecessorcount, bptr->successorcount,
 152                            pcode->bbfrequency[bptr->debug_nr]);
 153
 154                 switch (iptr->opc) {
 155                 case ICMD_RETURN:
 156                 case ICMD_IRETURN:
 157                 case ICMD_LRETURN:
 158                 case ICMD_FRETURN:
 159                 case ICMD_DRETURN:
 160                 case ICMD_ARETURN:
 161                 case ICMD_ATHROW:
 162                         puts("return");
 163
 164                         tbptr = reorder_place_next_unplaced_block(m, blocks, bptr);
 165
 166                         placed++;
 167
 168                         /* all blocks placed? return. */
 169
 170                         if (tbptr == NULL)
 171                                 continue;
 172
 173                         /* set last placed block */
 174
 175                         bptr = tbptr;
 176                         break;
 177
 178                 case ICMD_IFEQ:
 179                 case ICMD_IFNE:
 180                 case ICMD_IFLT:
 181                 case ICMD_IFGE:
 182                 case ICMD_IFGT:
 183                 case ICMD_IFLE:
 184
 185                 case ICMD_IF_ICMPEQ:
 186                 case ICMD_IF_ICMPNE:
 187                 case ICMD_IF_ICMPLT:
 188                 case ICMD_IF_ICMPGE:
 189                 case ICMD_IF_ICMPGT:
 190                 case ICMD_IF_ICMPLE:
 191
 192                 case ICMD_IF_ACMPEQ:
 193                 case ICMD_IF_ACMPNE:
 194
 195                 case ICMD_IFNULL:
 196                 case ICMD_IFNONNULL:
 197
 198                 case ICMD_IF_LEQ:
 199                 case ICMD_IF_LNE:
 200                 case ICMD_IF_LLT:
 201                 case ICMD_IF_LGE:
 202                 case ICMD_IF_LGT:
 203                 case ICMD_IF_LLE:
 204
 205                 case ICMD_IF_LCMPEQ:
 206                 case ICMD_IF_LCMPNE:
 207                 case ICMD_IF_LCMPLT:
 208                 case ICMD_IF_LCMPGE:
 209                 case ICMD_IF_LCMPGT:
 210                 case ICMD_IF_LCMPLE:
 211                         tbptr  = (basicblock *) iptr->target;
 212                         ntbptr = bptr->next;
 213
 214                         printf("cond. L%03d\n", tbptr->debug_nr);
 215
 216                         tfreq  = pcode->bbfrequency[tbptr->debug_nr];
 217                         ntfreq = pcode->bbfrequency[ntbptr->debug_nr];
 218
 219                         /* check which branch is more frequently */
 220
 221                         if ((blocks[tbptr->debug_nr] == false) && (tfreq > ntfreq)) {
 222                                 /* If we place the taken block, we need to change the
 223                                    conditional instruction (opcode and target). */
 224
 225                                 iptr->opc    = jit_complement_condition(iptr->opc);
 226                                 iptr->target = ntbptr;
 227
 228                                 /* change the basic block order */
 229
 230                                 bptr->next = tbptr;
 231
 232                                 /* place taken block */
 233
 234                                 blocks[tbptr->debug_nr] = true;
 235                                 placed++;
 236
 237                                 /* set last placed block */
 238
 239                                 bptr = tbptr;
 240                         }
 241                         else if (blocks[ntbptr->debug_nr] == false) {
 242                                 /* place not-taken block */
 243
 244                                 blocks[ntbptr->debug_nr] = true;
 245                                 placed++;
 246
 247                                 /* set last placed block */
 248
 249                                 bptr = ntbptr;
 250                         }
 251                         else {
 252                                 tbptr = reorder_place_next_unplaced_block(m, blocks, bptr);
 253
 254                                 placed++;
 255
 256                                 /* all blocks placed? return. */
 257
 258                                 if (tbptr == NULL)
 259                                         continue;
 260
 261                                 /* set last placed block */
 262
 263                                 bptr = tbptr;
 264                         }
 265                         break;
 266
 267                 case ICMD_GOTO:
 268                         tbptr = (basicblock *) iptr->target;
 269
 270                         printf("L%03d\n", tbptr->debug_nr);
 271
 272                         /* If next block is already placed, search for another
 273                            one. */
 274
 275                         if (blocks[tbptr->debug_nr] == true) {
 276                                 tbptr = reorder_place_next_unplaced_block(m, blocks, bptr);
 277
 278                                 placed++;
 279
 280                                 /* all block placed? return. */
 281
 282                                 if (tbptr == NULL)
 283                                         continue;
 284                         }
 285                         else if (tbptr->predecessorcount > 1) {
 286                                 /* Check if the target block has other predecessors.
 287                                    And if the other predecessors have a higher
 288                                    frequency, don't place it. */
 289
 290                                 freq = pcode->bbfrequency[bptr->debug_nr];
 291
 292                                 for (i = 0; i < tbptr->predecessorcount; i++) {
 293                                         pbptr = tbptr->predecessors[i];
 294
 295                                         /* skip the current basic block */
 296
 297                                         if (pbptr->debug_nr != bptr->debug_nr) {
 298                                                 pfreq = pcode->bbfrequency[pbptr->debug_nr];
 299
 300                                                 /* Other predecessor has a higher frequency?
 301                                                    Search for another block to place. */
 302
 303                                                 if (pfreq > freq) {
 304                                                         tbptr = reorder_place_next_unplaced_block(m, blocks,
 305                                                                                                                                           bptr);
 306
 307                                                         placed++;
 308
 309                                                         /* all block placed? return. */
 310
 311                                                         if (tbptr == NULL)
 312                                                                 break;
 313
 314                                                         goto goto_continue;
 315                                                 }
 316                                         }
 317                                 }
 318
 319                         goto_continue:
 320                                 /* place block */
 321
 322                                 blocks[tbptr->debug_nr] = true;
 323                                 placed++;
 324                         }
 325
 326                         /* set last placed block */
 327
 328                         bptr = tbptr;
 329                         break;
 330
 331                 default:
 332                         /* No control flow instruction at the end of the basic
 333                            block (fall-through).  Just place the block. */
 334
 335                         puts("next");
 336
 337                         tbptr = bptr->next;
 338
 339                         /* If next block is already placed, search for another
 340                            one. */
 341
 342                         if (blocks[tbptr->debug_nr] == true) {
 343                                 tbptr = reorder_place_next_unplaced_block(m, blocks, bptr);
 344
 345                                 placed++;
 346
 347                                 /* all block placed? return. */
 348
 349                                 if (tbptr == NULL)
 350                                         continue;
 351                         }
 352                         else {
 353                                 /* place block */
 354
 355                                 blocks[tbptr->debug_nr] = true;
 356                                 placed++;
 357                         }
 358
 359                         /* set last placed block */
 360
 361                         bptr = tbptr;
 362                         break;
 363                 }
 364         }
 365
 366         /* close the basic block chain with the last dummy basic block */
 367
 368         bptr->next = &m->basicblocks[m->basicblockcount];
 369
 370         puts("");
 371
 372         for (bptr = m->basicblocks; bptr != NULL; bptr = bptr->next) {
 373                 printf("L%03d\n", bptr->debug_nr);
 374         }
 375
 376         /* everything's ok */
 377
 378         return true;
 379 }
 380
 381
 382 /*
 383  * These are local overrides for various environment variables in Emacs.
 384  * Please do not remove this and leave it at the end of the file, where
 385  * Emacs will automagically detect them.
 386  * ---------------------------------------------------------------------
 387  * Local variables:
 388  * mode: c
 389  * indent-tabs-mode: t
 390  * c-basic-offset: 4
 391  * tab-width: 4
 392  * End:
 393  * vim:noexpandtab:sw=4:ts=4:
 394  */