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