1 /*
   2  * Copyright (c) 2005, 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "c1/c1_Instruction.hpp"
  27 #include "c1/c1_LinearScan.hpp"
  28 #include "utilities/bitMap.inline.hpp"
  29 
  30 
  31 //----------------------------------------------------------------------
  32 // Allocation of FPU stack slots (Intel x86 only)
  33 //----------------------------------------------------------------------
  34 
  35 void LinearScan::allocate_fpu_stack() {
  36   // First compute which FPU registers are live at the start of each basic block
  37   // (To minimize the amount of work we have to do if we have to merge FPU stacks)
  38   if (ComputeExactFPURegisterUsage) {
  39     Interval* intervals_in_register, *intervals_in_memory;
  40     create_unhandled_lists(&intervals_in_register, &intervals_in_memory, is_in_fpu_register, NULL);
  41 
  42     // ignore memory intervals by overwriting intervals_in_memory
  43     // the dummy interval is needed to enforce the walker to walk until the given id:
  44     // without it, the walker stops when the unhandled-list is empty -> live information
  45     // beyond this point would be incorrect.
  46     Interval* dummy_interval = new Interval(any_reg);
  47     dummy_interval->add_range(max_jint - 2, max_jint - 1);
  48     dummy_interval->set_next(Interval::end());
  49     intervals_in_memory = dummy_interval;
  50 
  51     IntervalWalker iw(this, intervals_in_register, intervals_in_memory);
  52 
  53     const int num_blocks = block_count();
  54     for (int i = 0; i < num_blocks; i++) {
  55       BlockBegin* b = block_at(i);
  56 
  57       // register usage is only needed for merging stacks -> compute only
  58       // when more than one predecessor.
  59       // the block must not have any spill moves at the beginning (checked by assertions)
  60       // spill moves would use intervals that are marked as handled and so the usage bit
  61       // would been set incorrectly
  62 
  63       // NOTE: the check for number_of_preds > 1 is necessary. A block with only one
  64       //       predecessor may have spill moves at the begin of the block.
  65       //       If an interval ends at the current instruction id, it is not possible
  66       //       to decide if the register is live or not at the block begin -> the
  67       //       register information would be incorrect.
  68       if (b->number_of_preds() > 1) {
  69         int id = b->first_lir_instruction_id();
  70         ResourceBitMap regs(FrameMap::nof_fpu_regs);
  71 
  72         iw.walk_to(id);   // walk after the first instruction (always a label) of the block
  73         assert(iw.current_position() == id, "did not walk completely to id");
  74 
  75         // Only consider FPU values in registers
  76         Interval* interval = iw.active_first(fixedKind);
  77         while (interval != Interval::end()) {
  78           int reg = interval->assigned_reg();
  79           assert(reg >= pd_first_fpu_reg && reg <= pd_last_fpu_reg, "no fpu register");
  80           assert(interval->assigned_regHi() == -1, "must not have hi register (doubles stored in one register)");
  81           assert(interval->from() <= id && id < interval->to(), "interval out of range");
  82 
  83 #ifndef PRODUCT
  84           if (TraceFPURegisterUsage) {
  85             tty->print("fpu reg %d is live because of ", reg - pd_first_fpu_reg); interval->print();
  86           }
  87 #endif
  88 
  89           regs.set_bit(reg - pd_first_fpu_reg);
  90           interval = interval->next();
  91         }
  92 
  93         b->set_fpu_register_usage(regs);
  94 
  95 #ifndef PRODUCT
  96         if (TraceFPURegisterUsage) {
  97           tty->print("FPU regs for block %d, LIR instr %d): ", b->block_id(), id); regs.print_on(tty); tty->cr();
  98         }
  99 #endif
 100       }
 101     }
 102   }
 103 
 104   FpuStackAllocator alloc(ir()->compilation(), this);
 105   _fpu_stack_allocator = &alloc;
 106   alloc.allocate();
 107   _fpu_stack_allocator = NULL;
 108 }
 109 
 110 
 111 FpuStackAllocator::FpuStackAllocator(Compilation* compilation, LinearScan* allocator)
 112   : _compilation(compilation)
 113   , _lir(NULL)
 114   , _pos(-1)
 115   , _allocator(allocator)
 116   , _sim(compilation)
 117   , _temp_sim(compilation)
 118 {}
 119 
 120 void FpuStackAllocator::allocate() {
 121   int num_blocks = allocator()->block_count();
 122   for (int i = 0; i < num_blocks; i++) {
 123     // Set up to process block
 124     BlockBegin* block = allocator()->block_at(i);
 125     intArray* fpu_stack_state = block->fpu_stack_state();
 126 
 127 #ifndef PRODUCT
 128     if (TraceFPUStack) {
 129       tty->cr();
 130       tty->print_cr("------- Begin of new Block %d -------", block->block_id());
 131     }
 132 #endif
 133 
 134     assert(fpu_stack_state != NULL ||
 135            block->end()->as_Base() != NULL ||
 136            block->is_set(BlockBegin::exception_entry_flag),
 137            "FPU stack state must be present due to linear-scan order for FPU stack allocation");
 138     // note: exception handler entries always start with an empty fpu stack
 139     //       because stack merging would be too complicated
 140 
 141     if (fpu_stack_state != NULL) {
 142       sim()->read_state(fpu_stack_state);
 143     } else {
 144       sim()->clear();
 145     }
 146 
 147 #ifndef PRODUCT
 148     if (TraceFPUStack) {
 149       tty->print("Reading FPU state for block %d:", block->block_id());
 150       sim()->print();
 151       tty->cr();
 152     }
 153 #endif
 154 
 155     allocate_block(block);
 156     CHECK_BAILOUT();
 157   }
 158 }
 159 
 160 void FpuStackAllocator::allocate_block(BlockBegin* block) {
 161   bool processed_merge = false;
 162   LIR_OpList* insts = block->lir()->instructions_list();
 163   set_lir(block->lir());
 164   set_pos(0);
 165 
 166 
 167   // Note: insts->length() may change during loop
 168   while (pos() < insts->length()) {
 169     LIR_Op* op = insts->at(pos());
 170     _debug_information_computed = false;
 171 
 172 #ifndef PRODUCT
 173     if (TraceFPUStack) {
 174       op->print();
 175     }
 176     check_invalid_lir_op(op);
 177 #endif
 178 
 179     LIR_OpBranch* branch = op->as_OpBranch();
 180     LIR_Op1* op1 = op->as_Op1();
 181     LIR_Op2* op2 = op->as_Op2();
 182     LIR_OpCall* opCall = op->as_OpCall();
 183 
 184     if (branch != NULL && branch->block() != NULL) {
 185       if (!processed_merge) {
 186         // propagate stack at first branch to a successor
 187         processed_merge = true;
 188         bool required_merge = merge_fpu_stack_with_successors(block);
 189 
 190         assert(!required_merge || branch->cond() == lir_cond_always, "splitting of critical edges should prevent FPU stack mismatches at cond branches");
 191       }
 192 
 193     } else if (op1 != NULL) {
 194       handle_op1(op1);
 195     } else if (op2 != NULL) {
 196       handle_op2(op2);
 197     } else if (opCall != NULL) {
 198       handle_opCall(opCall);
 199     }
 200 
 201     compute_debug_information(op);
 202 
 203     set_pos(1 + pos());
 204   }
 205 
 206   // Propagate stack when block does not end with branch
 207   if (!processed_merge) {
 208     merge_fpu_stack_with_successors(block);
 209   }
 210 }
 211 
 212 
 213 void FpuStackAllocator::compute_debug_information(LIR_Op* op) {
 214   if (!_debug_information_computed && op->id() != -1 && allocator()->has_info(op->id())) {
 215     visitor.visit(op);
 216 
 217     // exception handling
 218     if (allocator()->compilation()->has_exception_handlers()) {
 219       XHandlers* xhandlers = visitor.all_xhandler();
 220       int n = xhandlers->length();
 221       for (int k = 0; k < n; k++) {
 222         allocate_exception_handler(xhandlers->handler_at(k));
 223       }
 224     } else {
 225       assert(visitor.all_xhandler()->length() == 0, "missed exception handler");
 226     }
 227 
 228     // compute debug information
 229     int n = visitor.info_count();
 230     assert(n > 0, "should not visit operation otherwise");
 231 
 232     for (int j = 0; j < n; j++) {
 233       CodeEmitInfo* info = visitor.info_at(j);
 234       // Compute debug information
 235       allocator()->compute_debug_info(info, op->id());
 236     }
 237   }
 238   _debug_information_computed = true;
 239 }
 240 
 241 void FpuStackAllocator::allocate_exception_handler(XHandler* xhandler) {
 242   if (!sim()->is_empty()) {
 243     LIR_List* old_lir = lir();
 244     int old_pos = pos();
 245     intArray* old_state = sim()->write_state();
 246 
 247 #ifndef PRODUCT
 248     if (TraceFPUStack) {
 249       tty->cr();
 250       tty->print_cr("------- begin of exception handler -------");
 251     }
 252 #endif
 253 
 254     if (xhandler->entry_code() == NULL) {
 255       // need entry code to clear FPU stack
 256       LIR_List* entry_code = new LIR_List(_compilation);
 257       entry_code->jump(xhandler->entry_block());
 258       xhandler->set_entry_code(entry_code);
 259     }
 260 
 261     LIR_OpList* insts = xhandler->entry_code()->instructions_list();
 262     set_lir(xhandler->entry_code());
 263     set_pos(0);
 264 
 265     // Note: insts->length() may change during loop
 266     while (pos() < insts->length()) {
 267       LIR_Op* op = insts->at(pos());
 268 
 269 #ifndef PRODUCT
 270       if (TraceFPUStack) {
 271         op->print();
 272       }
 273       check_invalid_lir_op(op);
 274 #endif
 275 
 276       switch (op->code()) {
 277         case lir_move:
 278           assert(op->as_Op1() != NULL, "must be LIR_Op1");
 279           assert(pos() != insts->length() - 1, "must not be last operation");
 280 
 281           handle_op1((LIR_Op1*)op);
 282           break;
 283 
 284         case lir_branch:
 285           assert(op->as_OpBranch()->cond() == lir_cond_always, "must be unconditional branch");
 286           assert(pos() == insts->length() - 1, "must be last operation");
 287 
 288           // remove all remaining dead registers from FPU stack
 289           clear_fpu_stack(LIR_OprFact::illegalOpr);
 290           break;
 291 
 292         default:
 293           // other operations not allowed in exception entry code
 294           ShouldNotReachHere();
 295       }
 296 
 297       set_pos(pos() + 1);
 298     }
 299 
 300 #ifndef PRODUCT
 301     if (TraceFPUStack) {
 302       tty->cr();
 303       tty->print_cr("------- end of exception handler -------");
 304     }
 305 #endif
 306 
 307     set_lir(old_lir);
 308     set_pos(old_pos);
 309     sim()->read_state(old_state);
 310   }
 311 }
 312 
 313 
 314 int FpuStackAllocator::fpu_num(LIR_Opr opr) {
 315   assert(opr->is_fpu_register() && !opr->is_xmm_register(), "shouldn't call this otherwise");
 316   return opr->is_single_fpu() ? opr->fpu_regnr() : opr->fpu_regnrLo();
 317 }
 318 
 319 int FpuStackAllocator::tos_offset(LIR_Opr opr) {
 320   return sim()->offset_from_tos(fpu_num(opr));
 321 }
 322 
 323 
 324 LIR_Opr FpuStackAllocator::to_fpu_stack(LIR_Opr opr) {
 325   assert(opr->is_fpu_register() && !opr->is_xmm_register(), "shouldn't call this otherwise");
 326 
 327   int stack_offset = tos_offset(opr);
 328   if (opr->is_single_fpu()) {
 329     return LIR_OprFact::single_fpu(stack_offset)->make_fpu_stack_offset();
 330   } else {
 331     assert(opr->is_double_fpu(), "shouldn't call this otherwise");
 332     return LIR_OprFact::double_fpu(stack_offset)->make_fpu_stack_offset();
 333   }
 334 }
 335 
 336 LIR_Opr FpuStackAllocator::to_fpu_stack_top(LIR_Opr opr, bool dont_check_offset) {
 337   assert(opr->is_fpu_register() && !opr->is_xmm_register(), "shouldn't call this otherwise");
 338   assert(dont_check_offset || tos_offset(opr) == 0, "operand is not on stack top");
 339 
 340   int stack_offset = 0;
 341   if (opr->is_single_fpu()) {
 342     return LIR_OprFact::single_fpu(stack_offset)->make_fpu_stack_offset();
 343   } else {
 344     assert(opr->is_double_fpu(), "shouldn't call this otherwise");
 345     return LIR_OprFact::double_fpu(stack_offset)->make_fpu_stack_offset();
 346   }
 347 }
 348 
 349 
 350 
 351 void FpuStackAllocator::insert_op(LIR_Op* op) {
 352   lir()->insert_before(pos(), op);
 353   set_pos(1 + pos());
 354 }
 355 
 356 
 357 void FpuStackAllocator::insert_exchange(int offset) {
 358   if (offset > 0) {
 359     LIR_Op1* fxch_op = new LIR_Op1(lir_fxch, LIR_OprFact::intConst(offset), LIR_OprFact::illegalOpr);
 360     insert_op(fxch_op);
 361     sim()->swap(offset);
 362 
 363 #ifndef PRODUCT
 364     if (TraceFPUStack) {
 365       tty->print("Exchanged register: %d         New state: ", sim()->get_slot(0)); sim()->print(); tty->cr();
 366     }
 367 #endif
 368 
 369   }
 370 }
 371 
 372 void FpuStackAllocator::insert_exchange(LIR_Opr opr) {
 373   insert_exchange(tos_offset(opr));
 374 }
 375 
 376 
 377 void FpuStackAllocator::insert_free(int offset) {
 378   // move stack slot to the top of stack and then pop it
 379   insert_exchange(offset);
 380 
 381   LIR_Op* fpop = new LIR_Op0(lir_fpop_raw);
 382   insert_op(fpop);
 383   sim()->pop();
 384 
 385 #ifndef PRODUCT
 386     if (TraceFPUStack) {
 387       tty->print("Inserted pop                   New state: "); sim()->print(); tty->cr();
 388     }
 389 #endif
 390 }
 391 
 392 
 393 void FpuStackAllocator::insert_free_if_dead(LIR_Opr opr) {
 394   if (sim()->contains(fpu_num(opr))) {
 395     int res_slot = tos_offset(opr);
 396     insert_free(res_slot);
 397   }
 398 }
 399 
 400 void FpuStackAllocator::insert_free_if_dead(LIR_Opr opr, LIR_Opr ignore) {
 401   if (fpu_num(opr) != fpu_num(ignore) && sim()->contains(fpu_num(opr))) {
 402     int res_slot = tos_offset(opr);
 403     insert_free(res_slot);
 404   }
 405 }
 406 
 407 void FpuStackAllocator::insert_copy(LIR_Opr from, LIR_Opr to) {
 408   int offset = tos_offset(from);
 409   LIR_Op1* fld = new LIR_Op1(lir_fld, LIR_OprFact::intConst(offset), LIR_OprFact::illegalOpr);
 410   insert_op(fld);
 411 
 412   sim()->push(fpu_num(to));
 413 
 414 #ifndef PRODUCT
 415   if (TraceFPUStack) {
 416     tty->print("Inserted copy (%d -> %d)         New state: ", fpu_num(from), fpu_num(to)); sim()->print(); tty->cr();
 417   }
 418 #endif
 419 }
 420 
 421 void FpuStackAllocator::do_rename(LIR_Opr from, LIR_Opr to) {
 422   sim()->rename(fpu_num(from), fpu_num(to));
 423 }
 424 
 425 void FpuStackAllocator::do_push(LIR_Opr opr) {
 426   sim()->push(fpu_num(opr));
 427 }
 428 
 429 void FpuStackAllocator::pop_if_last_use(LIR_Op* op, LIR_Opr opr) {
 430   assert(op->fpu_pop_count() == 0, "fpu_pop_count alredy set");
 431   assert(tos_offset(opr) == 0, "can only pop stack top");
 432 
 433   if (opr->is_last_use()) {
 434     op->set_fpu_pop_count(1);
 435     sim()->pop();
 436   }
 437 }
 438 
 439 void FpuStackAllocator::pop_always(LIR_Op* op, LIR_Opr opr) {
 440   assert(op->fpu_pop_count() == 0, "fpu_pop_count alredy set");
 441   assert(tos_offset(opr) == 0, "can only pop stack top");
 442 
 443   op->set_fpu_pop_count(1);
 444   sim()->pop();
 445 }
 446 
 447 void FpuStackAllocator::clear_fpu_stack(LIR_Opr preserve) {
 448   int result_stack_size = (preserve->is_fpu_register() && !preserve->is_xmm_register() ? 1 : 0);
 449   while (sim()->stack_size() > result_stack_size) {
 450     assert(!sim()->slot_is_empty(0), "not allowed");
 451 
 452     if (result_stack_size == 0 || sim()->get_slot(0) != fpu_num(preserve)) {
 453       insert_free(0);
 454     } else {
 455       // move "preserve" to bottom of stack so that all other stack slots can be popped
 456       insert_exchange(sim()->stack_size() - 1);
 457     }
 458   }
 459 }
 460 
 461 
 462 void FpuStackAllocator::handle_op1(LIR_Op1* op1) {
 463   LIR_Opr in  = op1->in_opr();
 464   LIR_Opr res = op1->result_opr();
 465 
 466   LIR_Opr new_in  = in;  // new operands relative to the actual fpu stack top
 467   LIR_Opr new_res = res;
 468 
 469   // Note: this switch is processed for all LIR_Op1, regardless if they have FPU-arguments,
 470   //       so checks for is_float_kind() are necessary inside the cases
 471   switch (op1->code()) {
 472 
 473     case lir_return: {
 474       // FPU-Stack must only contain the (optional) fpu return value.
 475       // All remaining dead values are popped from the stack
 476       // If the input operand is a fpu-register, it is exchanged to the bottom of the stack
 477 
 478       clear_fpu_stack(in);
 479       if (in->is_fpu_register() && !in->is_xmm_register()) {
 480         new_in = to_fpu_stack_top(in);
 481       }
 482 
 483       break;
 484     }
 485 
 486     case lir_move: {
 487       if (in->is_fpu_register() && !in->is_xmm_register()) {
 488         if (res->is_xmm_register()) {
 489           // move from fpu register to xmm register (necessary for operations that
 490           // are not available in the SSE instruction set)
 491           insert_exchange(in);
 492           new_in = to_fpu_stack_top(in);
 493           pop_always(op1, in);
 494 
 495         } else if (res->is_fpu_register() && !res->is_xmm_register()) {
 496           // move from fpu-register to fpu-register:
 497           // * input and result register equal:
 498           //   nothing to do
 499           // * input register is last use:
 500           //   rename the input register to result register -> input register
 501           //   not present on fpu-stack afterwards
 502           // * input register not last use:
 503           //   duplicate input register to result register to preserve input
 504           //
 505           // Note: The LIR-Assembler does not produce any code for fpu register moves,
 506           //       so input and result stack index must be equal
 507 
 508           if (fpu_num(in) == fpu_num(res)) {
 509             // nothing to do
 510           } else if (in->is_last_use()) {
 511             insert_free_if_dead(res);//, in);
 512             do_rename(in, res);
 513           } else {
 514             insert_free_if_dead(res);
 515             insert_copy(in, res);
 516           }
 517           new_in = to_fpu_stack(res);
 518           new_res = new_in;
 519 
 520         } else {
 521           // move from fpu-register to memory
 522           // input operand must be on top of stack
 523 
 524           insert_exchange(in);
 525 
 526           // create debug information here because afterwards the register may have been popped
 527           compute_debug_information(op1);
 528 
 529           new_in = to_fpu_stack_top(in);
 530           pop_if_last_use(op1, in);
 531         }
 532 
 533       } else if (res->is_fpu_register() && !res->is_xmm_register()) {
 534         // move from memory/constant to fpu register
 535         // result is pushed on the stack
 536 
 537         insert_free_if_dead(res);
 538 
 539         // create debug information before register is pushed
 540         compute_debug_information(op1);
 541 
 542         do_push(res);
 543         new_res = to_fpu_stack_top(res);
 544       }
 545       break;
 546     }
 547 
 548     case lir_neg: {
 549       if (in->is_fpu_register() && !in->is_xmm_register()) {
 550         assert(res->is_fpu_register() && !res->is_xmm_register(), "must be");
 551         assert(in->is_last_use(), "old value gets destroyed");
 552 
 553         insert_free_if_dead(res, in);
 554         insert_exchange(in);
 555         new_in = to_fpu_stack_top(in);
 556 
 557         do_rename(in, res);
 558         new_res = to_fpu_stack_top(res);
 559       }
 560       break;
 561     }
 562 
 563     case lir_convert: {
 564       Bytecodes::Code bc = op1->as_OpConvert()->bytecode();
 565       switch (bc) {
 566         case Bytecodes::_d2f:
 567         case Bytecodes::_f2d:
 568           assert(res->is_fpu_register(), "must be");
 569           assert(in->is_fpu_register(), "must be");
 570 
 571           if (!in->is_xmm_register() && !res->is_xmm_register()) {
 572             // this is quite the same as a move from fpu-register to fpu-register
 573             // Note: input and result operands must have different types
 574             if (fpu_num(in) == fpu_num(res)) {
 575               // nothing to do
 576               new_in = to_fpu_stack(in);
 577             } else if (in->is_last_use()) {
 578               insert_free_if_dead(res);//, in);
 579               new_in = to_fpu_stack(in);
 580               do_rename(in, res);
 581             } else {
 582               insert_free_if_dead(res);
 583               insert_copy(in, res);
 584               new_in = to_fpu_stack_top(in, true);
 585             }
 586             new_res = to_fpu_stack(res);
 587           }
 588 
 589           break;
 590 
 591         case Bytecodes::_i2f:
 592         case Bytecodes::_l2f:
 593         case Bytecodes::_i2d:
 594         case Bytecodes::_l2d:
 595           assert(res->is_fpu_register(), "must be");
 596           if (!res->is_xmm_register()) {
 597             insert_free_if_dead(res);
 598             do_push(res);
 599             new_res = to_fpu_stack_top(res);
 600           }
 601           break;
 602 
 603         case Bytecodes::_f2i:
 604         case Bytecodes::_d2i:
 605           assert(in->is_fpu_register(), "must be");
 606           if (!in->is_xmm_register()) {
 607             insert_exchange(in);
 608             new_in = to_fpu_stack_top(in);
 609 
 610             // TODO: update registes of stub
 611           }
 612           break;
 613 
 614         case Bytecodes::_f2l:
 615         case Bytecodes::_d2l:
 616           assert(in->is_fpu_register(), "must be");
 617           if (!in->is_xmm_register()) {
 618             insert_exchange(in);
 619             new_in = to_fpu_stack_top(in);
 620             pop_always(op1, in);
 621           }
 622           break;
 623 
 624         case Bytecodes::_i2l:
 625         case Bytecodes::_l2i:
 626         case Bytecodes::_i2b:
 627         case Bytecodes::_i2c:
 628         case Bytecodes::_i2s:
 629           // no fpu operands
 630           break;
 631 
 632         default:
 633           ShouldNotReachHere();
 634       }
 635       break;
 636     }
 637 
 638     case lir_roundfp: {
 639       assert(in->is_fpu_register() && !in->is_xmm_register(), "input must be in register");
 640       assert(res->is_stack(), "result must be on stack");
 641 
 642       insert_exchange(in);
 643       new_in = to_fpu_stack_top(in);
 644       pop_if_last_use(op1, in);
 645       break;
 646     }
 647 
 648     default: {
 649       assert(!in->is_float_kind() && !res->is_float_kind(), "missed a fpu-operation");
 650     }
 651   }
 652 
 653   op1->set_in_opr(new_in);
 654   op1->set_result_opr(new_res);
 655 }
 656 
 657 void FpuStackAllocator::handle_op2(LIR_Op2* op2) {
 658   LIR_Opr left  = op2->in_opr1();
 659   if (!left->is_float_kind()) {
 660     return;
 661   }
 662   if (left->is_xmm_register()) {
 663     return;
 664   }
 665 
 666   LIR_Opr right = op2->in_opr2();
 667   LIR_Opr res   = op2->result_opr();
 668   LIR_Opr new_left  = left;  // new operands relative to the actual fpu stack top
 669   LIR_Opr new_right = right;
 670   LIR_Opr new_res   = res;
 671 
 672   assert(!left->is_xmm_register() && !right->is_xmm_register() && !res->is_xmm_register(), "not for xmm registers");
 673 
 674   switch (op2->code()) {
 675     case lir_cmp:
 676     case lir_cmp_fd2i:
 677     case lir_ucmp_fd2i:
 678     case lir_assert: {
 679       assert(left->is_fpu_register(), "invalid LIR");
 680       assert(right->is_fpu_register(), "invalid LIR");
 681 
 682       // the left-hand side must be on top of stack.
 683       // the right-hand side is never popped, even if is_last_use is set
 684       insert_exchange(left);
 685       new_left = to_fpu_stack_top(left);
 686       new_right = to_fpu_stack(right);
 687       pop_if_last_use(op2, left);
 688       break;
 689     }
 690 
 691     case lir_mul_strictfp:
 692     case lir_div_strictfp: {
 693       assert(op2->tmp1_opr()->is_fpu_register(), "strict operations need temporary fpu stack slot");
 694       insert_free_if_dead(op2->tmp1_opr());
 695       assert(sim()->stack_size() <= 7, "at least one stack slot must be free");
 696       // fall-through: continue with the normal handling of lir_mul and lir_div
 697     }
 698     case lir_add:
 699     case lir_sub:
 700     case lir_mul:
 701     case lir_div: {
 702       assert(left->is_fpu_register(), "must be");
 703       assert(res->is_fpu_register(), "must be");
 704       assert(left->is_equal(res), "must be");
 705 
 706       // either the left-hand or the right-hand side must be on top of stack
 707       // (if right is not a register, left must be on top)
 708       if (!right->is_fpu_register()) {
 709         insert_exchange(left);
 710         new_left = to_fpu_stack_top(left);
 711       } else {
 712         // no exchange necessary if right is alredy on top of stack
 713         if (tos_offset(right) == 0) {
 714           new_left = to_fpu_stack(left);
 715           new_right = to_fpu_stack_top(right);
 716         } else {
 717           insert_exchange(left);
 718           new_left = to_fpu_stack_top(left);
 719           new_right = to_fpu_stack(right);
 720         }
 721 
 722         if (right->is_last_use()) {
 723           op2->set_fpu_pop_count(1);
 724 
 725           if (tos_offset(right) == 0) {
 726             sim()->pop();
 727           } else {
 728             // if left is on top of stack, the result is placed in the stack
 729             // slot of right, so a renaming from right to res is necessary
 730             assert(tos_offset(left) == 0, "must be");
 731             sim()->pop();
 732             do_rename(right, res);
 733           }
 734         }
 735       }
 736       new_res = to_fpu_stack(res);
 737 
 738       break;
 739     }
 740 
 741     case lir_rem: {
 742       assert(left->is_fpu_register(), "must be");
 743       assert(right->is_fpu_register(), "must be");
 744       assert(res->is_fpu_register(), "must be");
 745       assert(left->is_equal(res), "must be");
 746 
 747       // Must bring both operands to top of stack with following operand ordering:
 748       // * fpu stack before rem: ... right left
 749       // * fpu stack after rem:  ... left
 750       if (tos_offset(right) != 1) {
 751         insert_exchange(right);
 752         insert_exchange(1);
 753       }
 754       insert_exchange(left);
 755       assert(tos_offset(right) == 1, "check");
 756       assert(tos_offset(left) == 0, "check");
 757 
 758       new_left = to_fpu_stack_top(left);
 759       new_right = to_fpu_stack(right);
 760 
 761       op2->set_fpu_pop_count(1);
 762       sim()->pop();
 763       do_rename(right, res);
 764 
 765       new_res = to_fpu_stack_top(res);
 766       break;
 767     }
 768 
 769     case lir_abs:
 770     case lir_sqrt: {
 771       // Right argument appears to be unused
 772       assert(right->is_illegal(), "must be");
 773       assert(left->is_fpu_register(), "must be");
 774       assert(res->is_fpu_register(), "must be");
 775       assert(left->is_last_use(), "old value gets destroyed");
 776 
 777       insert_free_if_dead(res, left);
 778       insert_exchange(left);
 779       do_rename(left, res);
 780 
 781       new_left = to_fpu_stack_top(res);
 782       new_res = new_left;
 783 
 784       op2->set_fpu_stack_size(sim()->stack_size());
 785       break;
 786     }
 787 
 788     default: {
 789       assert(false, "missed a fpu-operation");
 790     }
 791   }
 792 
 793   op2->set_in_opr1(new_left);
 794   op2->set_in_opr2(new_right);
 795   op2->set_result_opr(new_res);
 796 }
 797 
 798 void FpuStackAllocator::handle_opCall(LIR_OpCall* opCall) {
 799   LIR_Opr res = opCall->result_opr();
 800 
 801   // clear fpu-stack before call
 802   // it may contain dead values that could not have been remved by previous operations
 803   clear_fpu_stack(LIR_OprFact::illegalOpr);
 804   assert(sim()->is_empty(), "fpu stack must be empty now");
 805 
 806   // compute debug information before (possible) fpu result is pushed
 807   compute_debug_information(opCall);
 808 
 809   if (res->is_fpu_register() && !res->is_xmm_register()) {
 810     do_push(res);
 811     opCall->set_result_opr(to_fpu_stack_top(res));
 812   }
 813 }
 814 
 815 #ifndef PRODUCT
 816 void FpuStackAllocator::check_invalid_lir_op(LIR_Op* op) {
 817   switch (op->code()) {
 818     case lir_24bit_FPU:
 819     case lir_reset_FPU:
 820     case lir_ffree:
 821       assert(false, "operations not allowed in lir. If one of these operations is needed, check if they have fpu operands");
 822       break;
 823 
 824     case lir_fpop_raw:
 825     case lir_fxch:
 826     case lir_fld:
 827       assert(false, "operations only inserted by FpuStackAllocator");
 828       break;
 829     default:
 830       break;
 831   }
 832 }
 833 #endif
 834 
 835 
 836 void FpuStackAllocator::merge_insert_add(LIR_List* instrs, FpuStackSim* cur_sim, int reg) {
 837   LIR_Op1* move = new LIR_Op1(lir_move, LIR_OprFact::doubleConst(0), LIR_OprFact::double_fpu(reg)->make_fpu_stack_offset());
 838 
 839   instrs->instructions_list()->push(move);
 840 
 841   cur_sim->push(reg);
 842   move->set_result_opr(to_fpu_stack(move->result_opr()));
 843 
 844   #ifndef PRODUCT
 845     if (TraceFPUStack) {
 846       tty->print("Added new register: %d         New state: ", reg); cur_sim->print(); tty->cr();
 847     }
 848   #endif
 849 }
 850 
 851 void FpuStackAllocator::merge_insert_xchg(LIR_List* instrs, FpuStackSim* cur_sim, int slot) {
 852   assert(slot > 0, "no exchange necessary");
 853 
 854   LIR_Op1* fxch = new LIR_Op1(lir_fxch, LIR_OprFact::intConst(slot));
 855   instrs->instructions_list()->push(fxch);
 856   cur_sim->swap(slot);
 857 
 858   #ifndef PRODUCT
 859     if (TraceFPUStack) {
 860       tty->print("Exchanged register: %d         New state: ", cur_sim->get_slot(slot)); cur_sim->print(); tty->cr();
 861     }
 862   #endif
 863 }
 864 
 865 void FpuStackAllocator::merge_insert_pop(LIR_List* instrs, FpuStackSim* cur_sim) {
 866   int reg = cur_sim->get_slot(0);
 867 
 868   LIR_Op* fpop = new LIR_Op0(lir_fpop_raw);
 869   instrs->instructions_list()->push(fpop);
 870   cur_sim->pop(reg);
 871 
 872   #ifndef PRODUCT
 873     if (TraceFPUStack) {
 874       tty->print("Removed register: %d           New state: ", reg); cur_sim->print(); tty->cr();
 875     }
 876   #endif
 877 }
 878 
 879 bool FpuStackAllocator::merge_rename(FpuStackSim* cur_sim, FpuStackSim* sux_sim, int start_slot, int change_slot) {
 880   int reg = cur_sim->get_slot(change_slot);
 881 
 882   for (int slot = start_slot; slot >= 0; slot--) {
 883     int new_reg = sux_sim->get_slot(slot);
 884 
 885     if (!cur_sim->contains(new_reg)) {
 886       cur_sim->set_slot(change_slot, new_reg);
 887 
 888       #ifndef PRODUCT
 889         if (TraceFPUStack) {
 890           tty->print("Renamed register %d to %d       New state: ", reg, new_reg); cur_sim->print(); tty->cr();
 891         }
 892       #endif
 893 
 894       return true;
 895     }
 896   }
 897   return false;
 898 }
 899 
 900 
 901 void FpuStackAllocator::merge_fpu_stack(LIR_List* instrs, FpuStackSim* cur_sim, FpuStackSim* sux_sim) {
 902 #ifndef PRODUCT
 903   if (TraceFPUStack) {
 904     tty->cr();
 905     tty->print("before merging: pred: "); cur_sim->print(); tty->cr();
 906     tty->print("                 sux: "); sux_sim->print(); tty->cr();
 907   }
 908 
 909   int slot;
 910   for (slot = 0; slot < cur_sim->stack_size(); slot++) {
 911     assert(!cur_sim->slot_is_empty(slot), "not handled by algorithm");
 912   }
 913   for (slot = 0; slot < sux_sim->stack_size(); slot++) {
 914     assert(!sux_sim->slot_is_empty(slot), "not handled by algorithm");
 915   }
 916 #endif
 917 
 918   // size difference between cur and sux that must be resolved by adding or removing values form the stack
 919   int size_diff = cur_sim->stack_size() - sux_sim->stack_size();
 920 
 921   if (!ComputeExactFPURegisterUsage) {
 922     // add slots that are currently free, but used in successor
 923     // When the exact FPU register usage is computed, the stack does
 924     // not contain dead values at merging -> no values must be added
 925 
 926     int sux_slot = sux_sim->stack_size() - 1;
 927     while (size_diff < 0) {
 928       assert(sux_slot >= 0, "slot out of bounds -> error in algorithm");
 929 
 930       int reg = sux_sim->get_slot(sux_slot);
 931       if (!cur_sim->contains(reg)) {
 932         merge_insert_add(instrs, cur_sim, reg);
 933         size_diff++;
 934 
 935         if (sux_slot + size_diff != 0) {
 936           merge_insert_xchg(instrs, cur_sim, sux_slot + size_diff);
 937         }
 938       }
 939      sux_slot--;
 940     }
 941   }
 942 
 943   assert(cur_sim->stack_size() >= sux_sim->stack_size(), "stack size must be equal or greater now");
 944   assert(size_diff == cur_sim->stack_size() - sux_sim->stack_size(), "must be");
 945 
 946   // stack merge algorithm:
 947   // 1) as long as the current stack top is not in the right location (that meens
 948   //    it should not be on the stack top), exchange it into the right location
 949   // 2) if the stack top is right, but the remaining stack is not ordered correctly,
 950   //    the stack top is exchanged away to get another value on top ->
 951   //    now step 1) can be continued
 952   // the stack can also contain unused items -> these items are removed from stack
 953 
 954   int finished_slot = sux_sim->stack_size() - 1;
 955   while (finished_slot >= 0 || size_diff > 0) {
 956     while (size_diff > 0 || (cur_sim->stack_size() > 0 && cur_sim->get_slot(0) != sux_sim->get_slot(0))) {
 957       int reg = cur_sim->get_slot(0);
 958       if (sux_sim->contains(reg)) {
 959         int sux_slot = sux_sim->offset_from_tos(reg);
 960         merge_insert_xchg(instrs, cur_sim, sux_slot + size_diff);
 961 
 962       } else if (!merge_rename(cur_sim, sux_sim, finished_slot, 0)) {
 963         assert(size_diff > 0, "must be");
 964 
 965         merge_insert_pop(instrs, cur_sim);
 966         size_diff--;
 967       }
 968       assert(cur_sim->stack_size() == 0 || cur_sim->get_slot(0) != reg, "register must have been changed");
 969     }
 970 
 971     while (finished_slot >= 0 && cur_sim->get_slot(finished_slot) == sux_sim->get_slot(finished_slot)) {
 972       finished_slot--;
 973     }
 974 
 975     if (finished_slot >= 0) {
 976       int reg = cur_sim->get_slot(finished_slot);
 977 
 978       if (sux_sim->contains(reg) || !merge_rename(cur_sim, sux_sim, finished_slot, finished_slot)) {
 979         assert(sux_sim->contains(reg) || size_diff > 0, "must be");
 980         merge_insert_xchg(instrs, cur_sim, finished_slot);
 981       }
 982       assert(cur_sim->get_slot(finished_slot) != reg, "register must have been changed");
 983     }
 984   }
 985 
 986 #ifndef PRODUCT
 987   if (TraceFPUStack) {
 988     tty->print("after merging:  pred: "); cur_sim->print(); tty->cr();
 989     tty->print("                 sux: "); sux_sim->print(); tty->cr();
 990     tty->cr();
 991   }
 992 #endif
 993   assert(cur_sim->stack_size() == sux_sim->stack_size(), "stack size must be equal now");
 994 }
 995 
 996 
 997 void FpuStackAllocator::merge_cleanup_fpu_stack(LIR_List* instrs, FpuStackSim* cur_sim, BitMap& live_fpu_regs) {
 998 #ifndef PRODUCT
 999   if (TraceFPUStack) {
1000     tty->cr();
1001     tty->print("before cleanup: state: "); cur_sim->print(); tty->cr();
1002     tty->print("                live:  "); live_fpu_regs.print_on(tty); tty->cr();
1003   }
1004 #endif
1005 
1006   int slot = 0;
1007   while (slot < cur_sim->stack_size()) {
1008     int reg = cur_sim->get_slot(slot);
1009     if (!live_fpu_regs.at(reg)) {
1010       if (slot != 0) {
1011         merge_insert_xchg(instrs, cur_sim, slot);
1012       }
1013       merge_insert_pop(instrs, cur_sim);
1014     } else {
1015       slot++;
1016     }
1017   }
1018 
1019 #ifndef PRODUCT
1020   if (TraceFPUStack) {
1021     tty->print("after cleanup:  state: "); cur_sim->print(); tty->cr();
1022     tty->print("                live:  "); live_fpu_regs.print_on(tty); tty->cr();
1023     tty->cr();
1024   }
1025 
1026   // check if fpu stack only contains live registers
1027   for (unsigned int i = 0; i < live_fpu_regs.size(); i++) {
1028     if (live_fpu_regs.at(i) != cur_sim->contains(i)) {
1029       tty->print_cr("mismatch between required and actual stack content");
1030       break;
1031     }
1032   }
1033 #endif
1034 }
1035 
1036 
1037 bool FpuStackAllocator::merge_fpu_stack_with_successors(BlockBegin* block) {
1038 #ifndef PRODUCT
1039   if (TraceFPUStack) {
1040     tty->print_cr("Propagating FPU stack state for B%d at LIR_Op position %d to successors:",
1041                   block->block_id(), pos());
1042     sim()->print();
1043     tty->cr();
1044   }
1045 #endif
1046 
1047   bool changed = false;
1048   int number_of_sux = block->number_of_sux();
1049 
1050   if (number_of_sux == 1 && block->sux_at(0)->number_of_preds() > 1) {
1051     // The successor has at least two incoming edges, so a stack merge will be necessary
1052     // If this block is the first predecessor, cleanup the current stack and propagate it
1053     // If this block is not the first predecessor, a stack merge will be necessary
1054 
1055     BlockBegin* sux = block->sux_at(0);
1056     intArray* state = sux->fpu_stack_state();
1057     LIR_List* instrs = new LIR_List(_compilation);
1058 
1059     if (state != NULL) {
1060       // Merge with a successors that already has a FPU stack state
1061       // the block must only have one successor because critical edges must been split
1062       FpuStackSim* cur_sim = sim();
1063       FpuStackSim* sux_sim = temp_sim();
1064       sux_sim->read_state(state);
1065 
1066       merge_fpu_stack(instrs, cur_sim, sux_sim);
1067 
1068     } else {
1069       // propagate current FPU stack state to successor without state
1070       // clean up stack first so that there are no dead values on the stack
1071       if (ComputeExactFPURegisterUsage) {
1072         FpuStackSim* cur_sim = sim();
1073         ResourceBitMap live_fpu_regs = block->sux_at(0)->fpu_register_usage();
1074         assert(live_fpu_regs.size() == FrameMap::nof_fpu_regs, "missing register usage");
1075 
1076         merge_cleanup_fpu_stack(instrs, cur_sim, live_fpu_regs);
1077       }
1078 
1079       intArray* state = sim()->write_state();
1080       if (TraceFPUStack) {
1081         tty->print_cr("Setting FPU stack state of B%d (merge path)", sux->block_id());
1082         sim()->print(); tty->cr();
1083       }
1084       sux->set_fpu_stack_state(state);
1085     }
1086 
1087     if (instrs->instructions_list()->length() > 0) {
1088       lir()->insert_before(pos(), instrs);
1089       set_pos(instrs->instructions_list()->length() + pos());
1090       changed = true;
1091     }
1092 
1093   } else {
1094     // Propagate unmodified Stack to successors where a stack merge is not necessary
1095     intArray* state = sim()->write_state();
1096     for (int i = 0; i < number_of_sux; i++) {
1097       BlockBegin* sux = block->sux_at(i);
1098 
1099 #ifdef ASSERT
1100       for (int j = 0; j < sux->number_of_preds(); j++) {
1101         assert(block == sux->pred_at(j), "all critical edges must be broken");
1102       }
1103 
1104       // check if new state is same
1105       if (sux->fpu_stack_state() != NULL) {
1106         intArray* sux_state = sux->fpu_stack_state();
1107         assert(state->length() == sux_state->length(), "overwriting existing stack state");
1108         for (int j = 0; j < state->length(); j++) {
1109           assert(state->at(j) == sux_state->at(j), "overwriting existing stack state");
1110         }
1111       }
1112 #endif
1113 #ifndef PRODUCT
1114       if (TraceFPUStack) {
1115         tty->print_cr("Setting FPU stack state of B%d", sux->block_id());
1116         sim()->print(); tty->cr();
1117       }
1118 #endif
1119 
1120       sux->set_fpu_stack_state(state);
1121     }
1122   }
1123 
1124 #ifndef PRODUCT
1125   // assertions that FPU stack state conforms to all successors' states
1126   intArray* cur_state = sim()->write_state();
1127   for (int i = 0; i < number_of_sux; i++) {
1128     BlockBegin* sux = block->sux_at(i);
1129     intArray* sux_state = sux->fpu_stack_state();
1130 
1131     assert(sux_state != NULL, "no fpu state");
1132     assert(cur_state->length() == sux_state->length(), "incorrect length");
1133     for (int i = 0; i < cur_state->length(); i++) {
1134       assert(cur_state->at(i) == sux_state->at(i), "element not equal");
1135     }
1136   }
1137 #endif
1138 
1139   return changed;
1140 }