203 region = _gvn.transform(region); |
203 region = _gvn.transform(region); |
204 set_control (region); |
204 set_control (region); |
205 return region; |
205 return region; |
206 } |
206 } |
207 |
207 |
|
208 // sentinel value for the target bci to mark never taken branches |
|
209 // (according to profiling) |
|
210 static const int never_reached = INT_MAX; |
208 |
211 |
209 //------------------------------helper for tableswitch------------------------- |
212 //------------------------------helper for tableswitch------------------------- |
210 void Parse::jump_if_true_fork(IfNode *iff, int dest_bci_if_true, int prof_table_index) { |
213 void Parse::jump_if_true_fork(IfNode *iff, int dest_bci_if_true, int prof_table_index, bool unc) { |
211 // True branch, use existing map info |
214 // True branch, use existing map info |
212 { PreserveJVMState pjvms(this); |
215 { PreserveJVMState pjvms(this); |
213 Node *iftrue = _gvn.transform( new IfTrueNode (iff) ); |
216 Node *iftrue = _gvn.transform( new IfTrueNode (iff) ); |
214 set_control( iftrue ); |
217 set_control( iftrue ); |
215 profile_switch_case(prof_table_index); |
218 if (unc) { |
216 merge_new_path(dest_bci_if_true); |
219 repush_if_args(); |
|
220 uncommon_trap(Deoptimization::Reason_unstable_if, |
|
221 Deoptimization::Action_reinterpret, |
|
222 NULL, |
|
223 "taken always"); |
|
224 } else { |
|
225 assert(dest_bci_if_true != never_reached, "inconsistent dest"); |
|
226 profile_switch_case(prof_table_index); |
|
227 merge_new_path(dest_bci_if_true); |
|
228 } |
217 } |
229 } |
218 |
230 |
219 // False branch |
231 // False branch |
220 Node *iffalse = _gvn.transform( new IfFalseNode(iff) ); |
232 Node *iffalse = _gvn.transform( new IfFalseNode(iff) ); |
221 set_control( iffalse ); |
233 set_control( iffalse ); |
222 } |
234 } |
223 |
235 |
224 void Parse::jump_if_false_fork(IfNode *iff, int dest_bci_if_true, int prof_table_index) { |
236 void Parse::jump_if_false_fork(IfNode *iff, int dest_bci_if_true, int prof_table_index, bool unc) { |
225 // True branch, use existing map info |
237 // True branch, use existing map info |
226 { PreserveJVMState pjvms(this); |
238 { PreserveJVMState pjvms(this); |
227 Node *iffalse = _gvn.transform( new IfFalseNode (iff) ); |
239 Node *iffalse = _gvn.transform( new IfFalseNode (iff) ); |
228 set_control( iffalse ); |
240 set_control( iffalse ); |
229 profile_switch_case(prof_table_index); |
241 if (unc) { |
230 merge_new_path(dest_bci_if_true); |
242 repush_if_args(); |
|
243 uncommon_trap(Deoptimization::Reason_unstable_if, |
|
244 Deoptimization::Action_reinterpret, |
|
245 NULL, |
|
246 "taken never"); |
|
247 } else { |
|
248 assert(dest_bci_if_true != never_reached, "inconsistent dest"); |
|
249 profile_switch_case(prof_table_index); |
|
250 merge_new_path(dest_bci_if_true); |
|
251 } |
231 } |
252 } |
232 |
253 |
233 // False branch |
254 // False branch |
234 Node *iftrue = _gvn.transform( new IfTrueNode(iff) ); |
255 Node *iftrue = _gvn.transform( new IfTrueNode(iff) ); |
235 set_control( iftrue ); |
256 set_control( iftrue ); |
236 } |
257 } |
237 |
258 |
238 void Parse::jump_if_always_fork(int dest_bci, int prof_table_index) { |
259 void Parse::jump_if_always_fork(int dest_bci, int prof_table_index, bool unc) { |
239 // False branch, use existing map and control() |
260 // False branch, use existing map and control() |
240 profile_switch_case(prof_table_index); |
261 if (unc) { |
241 merge_new_path(dest_bci); |
262 repush_if_args(); |
|
263 uncommon_trap(Deoptimization::Reason_unstable_if, |
|
264 Deoptimization::Action_reinterpret, |
|
265 NULL, |
|
266 "taken never"); |
|
267 } else { |
|
268 assert(dest_bci != never_reached, "inconsistent dest"); |
|
269 profile_switch_case(prof_table_index); |
|
270 merge_new_path(dest_bci); |
|
271 } |
242 } |
272 } |
243 |
273 |
244 |
274 |
245 extern "C" { |
275 extern "C" { |
246 static int jint_cmp(const void *i, const void *j) { |
276 static int jint_cmp(const void *i, const void *j) { |
259 // a range of integers coupled with a bci destination |
289 // a range of integers coupled with a bci destination |
260 jint _lo; // inclusive lower limit |
290 jint _lo; // inclusive lower limit |
261 jint _hi; // inclusive upper limit |
291 jint _hi; // inclusive upper limit |
262 int _dest; |
292 int _dest; |
263 int _table_index; // index into method data table |
293 int _table_index; // index into method data table |
|
294 float _cnt; // how many times this range was hit according to profiling |
264 |
295 |
265 public: |
296 public: |
266 jint lo() const { return _lo; } |
297 jint lo() const { return _lo; } |
267 jint hi() const { return _hi; } |
298 jint hi() const { return _hi; } |
268 int dest() const { return _dest; } |
299 int dest() const { return _dest; } |
269 int table_index() const { return _table_index; } |
300 int table_index() const { return _table_index; } |
270 bool is_singleton() const { return _lo == _hi; } |
301 bool is_singleton() const { return _lo == _hi; } |
271 |
302 float cnt() const { return _cnt; } |
272 void setRange(jint lo, jint hi, int dest, int table_index) { |
303 |
|
304 void setRange(jint lo, jint hi, int dest, int table_index, float cnt) { |
273 assert(lo <= hi, "must be a non-empty range"); |
305 assert(lo <= hi, "must be a non-empty range"); |
274 _lo = lo, _hi = hi; _dest = dest; _table_index = table_index; |
306 _lo = lo, _hi = hi; _dest = dest; _table_index = table_index; _cnt = cnt; |
275 } |
307 assert(_cnt >= 0, ""); |
276 bool adjoinRange(jint lo, jint hi, int dest, int table_index) { |
308 } |
|
309 bool adjoinRange(jint lo, jint hi, int dest, int table_index, float cnt, bool trim_ranges) { |
277 assert(lo <= hi, "must be a non-empty range"); |
310 assert(lo <= hi, "must be a non-empty range"); |
278 if (lo == _hi+1 && dest == _dest && table_index == _table_index) { |
311 if (lo == _hi+1 && table_index == _table_index) { |
|
312 // see merge_ranges() comment below |
|
313 if (trim_ranges) { |
|
314 if (cnt == 0) { |
|
315 if (_cnt != 0) { |
|
316 return false; |
|
317 } |
|
318 if (dest != _dest) { |
|
319 _dest = never_reached; |
|
320 } |
|
321 } else { |
|
322 if (_cnt == 0) { |
|
323 return false; |
|
324 } |
|
325 if (dest != _dest) { |
|
326 return false; |
|
327 } |
|
328 } |
|
329 } else { |
|
330 if (dest != _dest) { |
|
331 return false; |
|
332 } |
|
333 } |
279 _hi = hi; |
334 _hi = hi; |
|
335 _cnt += cnt; |
280 return true; |
336 return true; |
281 } |
337 } |
282 return false; |
338 return false; |
283 } |
339 } |
284 |
340 |
285 void set (jint value, int dest, int table_index) { |
341 void set (jint value, int dest, int table_index, float cnt) { |
286 setRange(value, value, dest, table_index); |
342 setRange(value, value, dest, table_index, cnt); |
287 } |
343 } |
288 bool adjoin(jint value, int dest, int table_index) { |
344 bool adjoin(jint value, int dest, int table_index, float cnt, bool trim_ranges) { |
289 return adjoinRange(value, value, dest, table_index); |
345 return adjoinRange(value, value, dest, table_index, cnt, trim_ranges); |
|
346 } |
|
347 bool adjoin(SwitchRange& other) { |
|
348 return adjoinRange(other._lo, other._hi, other._dest, other._table_index, other._cnt, false); |
290 } |
349 } |
291 |
350 |
292 void print() { |
351 void print() { |
293 if (is_singleton()) |
352 if (is_singleton()) |
294 tty->print(" {%d}=>%d", lo(), dest()); |
353 tty->print(" {%d}=>%d (cnt=%f)", lo(), dest(), cnt()); |
295 else if (lo() == min_jint) |
354 else if (lo() == min_jint) |
296 tty->print(" {..%d}=>%d", hi(), dest()); |
355 tty->print(" {..%d}=>%d (cnt=%f)", hi(), dest(), cnt()); |
297 else if (hi() == max_jint) |
356 else if (hi() == max_jint) |
298 tty->print(" {%d..}=>%d", lo(), dest()); |
357 tty->print(" {%d..}=>%d (cnt=%f)", lo(), dest(), cnt()); |
299 else |
358 else |
300 tty->print(" {%d..%d}=>%d", lo(), hi(), dest()); |
359 tty->print(" {%d..%d}=>%d (cnt=%f)", lo(), hi(), dest(), cnt()); |
301 } |
360 } |
302 }; |
361 }; |
303 |
362 |
|
363 // We try to minimize the number of ranges and the size of the taken |
|
364 // ones using profiling data. When ranges are created, |
|
365 // SwitchRange::adjoinRange() only allows 2 adjoining ranges to merge |
|
366 // if both were never hit or both were hit to build longer unreached |
|
367 // ranges. Here, we now merge adjoining ranges with the same |
|
368 // destination and finally set destination of unreached ranges to the |
|
369 // special value never_reached because it can help minimize the number |
|
370 // of tests that are necessary. |
|
371 // |
|
372 // For instance: |
|
373 // [0, 1] to target1 sometimes taken |
|
374 // [1, 2] to target1 never taken |
|
375 // [2, 3] to target2 never taken |
|
376 // would lead to: |
|
377 // [0, 1] to target1 sometimes taken |
|
378 // [1, 3] never taken |
|
379 // |
|
380 // (first 2 ranges to target1 are not merged) |
|
381 static void merge_ranges(SwitchRange* ranges, int& rp) { |
|
382 if (rp == 0) { |
|
383 return; |
|
384 } |
|
385 int shift = 0; |
|
386 for (int j = 0; j < rp; j++) { |
|
387 SwitchRange& r1 = ranges[j-shift]; |
|
388 SwitchRange& r2 = ranges[j+1]; |
|
389 if (r1.adjoin(r2)) { |
|
390 shift++; |
|
391 } else if (shift > 0) { |
|
392 ranges[j+1-shift] = r2; |
|
393 } |
|
394 } |
|
395 rp -= shift; |
|
396 for (int j = 0; j <= rp; j++) { |
|
397 SwitchRange& r = ranges[j]; |
|
398 if (r.cnt() == 0 && r.dest() != never_reached) { |
|
399 r.setRange(r.lo(), r.hi(), never_reached, r.table_index(), r.cnt()); |
|
400 } |
|
401 } |
|
402 } |
304 |
403 |
305 //-------------------------------do_tableswitch-------------------------------- |
404 //-------------------------------do_tableswitch-------------------------------- |
306 void Parse::do_tableswitch() { |
405 void Parse::do_tableswitch() { |
307 Node* lookup = pop(); |
406 Node* lookup = pop(); |
308 |
|
309 // Get information about tableswitch |
407 // Get information about tableswitch |
310 int default_dest = iter().get_dest_table(0); |
408 int default_dest = iter().get_dest_table(0); |
311 int lo_index = iter().get_int_table(1); |
409 int lo_index = iter().get_int_table(1); |
312 int hi_index = iter().get_int_table(2); |
410 int hi_index = iter().get_int_table(2); |
313 int len = hi_index - lo_index + 1; |
411 int len = hi_index - lo_index + 1; |
316 // If this is a backward branch, add safepoint |
414 // If this is a backward branch, add safepoint |
317 maybe_add_safepoint(default_dest); |
415 maybe_add_safepoint(default_dest); |
318 merge(default_dest); |
416 merge(default_dest); |
319 return; |
417 return; |
320 } |
418 } |
|
419 |
|
420 ciMethodData* methodData = method()->method_data(); |
|
421 ciMultiBranchData* profile = NULL; |
|
422 if (methodData->is_mature() && UseSwitchProfiling) { |
|
423 ciProfileData* data = methodData->bci_to_data(bci()); |
|
424 if (data != NULL && data->is_MultiBranchData()) { |
|
425 profile = (ciMultiBranchData*)data; |
|
426 } |
|
427 } |
|
428 bool trim_ranges = !method_data_update() && !C->too_many_traps(method(), bci(), Deoptimization::Reason_unstable_if); |
321 |
429 |
322 // generate decision tree, using trichotomy when possible |
430 // generate decision tree, using trichotomy when possible |
323 int rnum = len+2; |
431 int rnum = len+2; |
324 bool makes_backward_branch = false; |
432 bool makes_backward_branch = false; |
325 SwitchRange* ranges = NEW_RESOURCE_ARRAY(SwitchRange, rnum); |
433 SwitchRange* ranges = NEW_RESOURCE_ARRAY(SwitchRange, rnum); |
326 int rp = -1; |
434 int rp = -1; |
327 if (lo_index != min_jint) { |
435 if (lo_index != min_jint) { |
328 ranges[++rp].setRange(min_jint, lo_index-1, default_dest, NullTableIndex); |
436 uint cnt = 1; |
|
437 if (profile != NULL) { |
|
438 cnt = profile->default_count() / (hi_index != max_jint ? 2 : 1); |
|
439 } |
|
440 ranges[++rp].setRange(min_jint, lo_index-1, default_dest, NullTableIndex, cnt); |
329 } |
441 } |
330 for (int j = 0; j < len; j++) { |
442 for (int j = 0; j < len; j++) { |
331 jint match_int = lo_index+j; |
443 jint match_int = lo_index+j; |
332 int dest = iter().get_dest_table(j+3); |
444 int dest = iter().get_dest_table(j+3); |
333 makes_backward_branch |= (dest <= bci()); |
445 makes_backward_branch |= (dest <= bci()); |
334 int table_index = method_data_update() ? j : NullTableIndex; |
446 int table_index = method_data_update() ? j : NullTableIndex; |
335 if (rp < 0 || !ranges[rp].adjoin(match_int, dest, table_index)) { |
447 uint cnt = 1; |
336 ranges[++rp].set(match_int, dest, table_index); |
448 if (profile != NULL) { |
|
449 cnt = profile->count_at(j); |
|
450 } |
|
451 if (rp < 0 || !ranges[rp].adjoin(match_int, dest, table_index, cnt, trim_ranges)) { |
|
452 ranges[++rp].set(match_int, dest, table_index, cnt); |
337 } |
453 } |
338 } |
454 } |
339 jint highest = lo_index+(len-1); |
455 jint highest = lo_index+(len-1); |
340 assert(ranges[rp].hi() == highest, ""); |
456 assert(ranges[rp].hi() == highest, ""); |
341 if (highest != max_jint |
457 if (highest != max_jint) { |
342 && !ranges[rp].adjoinRange(highest+1, max_jint, default_dest, NullTableIndex)) { |
458 uint cnt = 1; |
343 ranges[++rp].setRange(highest+1, max_jint, default_dest, NullTableIndex); |
459 if (profile != NULL) { |
|
460 cnt = profile->default_count() / (lo_index != min_jint ? 2 : 1); |
|
461 } |
|
462 if (!ranges[rp].adjoinRange(highest+1, max_jint, default_dest, NullTableIndex, cnt, trim_ranges)) { |
|
463 ranges[++rp].setRange(highest+1, max_jint, default_dest, NullTableIndex, cnt); |
|
464 } |
344 } |
465 } |
345 assert(rp < len+2, "not too many ranges"); |
466 assert(rp < len+2, "not too many ranges"); |
|
467 |
|
468 if (trim_ranges) { |
|
469 merge_ranges(ranges, rp); |
|
470 } |
346 |
471 |
347 // Safepoint in case if backward branch observed |
472 // Safepoint in case if backward branch observed |
348 if( makes_backward_branch && UseLoopSafepoints ) |
473 if( makes_backward_branch && UseLoopSafepoints ) |
349 add_safepoint(); |
474 add_safepoint(); |
350 |
475 |
363 maybe_add_safepoint(default_dest); |
488 maybe_add_safepoint(default_dest); |
364 merge(default_dest); |
489 merge(default_dest); |
365 return; |
490 return; |
366 } |
491 } |
367 |
492 |
|
493 ciMethodData* methodData = method()->method_data(); |
|
494 ciMultiBranchData* profile = NULL; |
|
495 if (methodData->is_mature() && UseSwitchProfiling) { |
|
496 ciProfileData* data = methodData->bci_to_data(bci()); |
|
497 if (data != NULL && data->is_MultiBranchData()) { |
|
498 profile = (ciMultiBranchData*)data; |
|
499 } |
|
500 } |
|
501 bool trim_ranges = !method_data_update() && !C->too_many_traps(method(), bci(), Deoptimization::Reason_unstable_if); |
|
502 |
368 // generate decision tree, using trichotomy when possible |
503 // generate decision tree, using trichotomy when possible |
369 jint* table = NEW_RESOURCE_ARRAY(jint, len*2); |
504 jint* table = NEW_RESOURCE_ARRAY(jint, len*3); |
370 { |
505 { |
371 for( int j = 0; j < len; j++ ) { |
506 for (int j = 0; j < len; j++) { |
372 table[j+j+0] = iter().get_int_table(2+j+j); |
507 table[3*j+0] = iter().get_int_table(2+2*j); |
373 table[j+j+1] = iter().get_dest_table(2+j+j+1); |
508 table[3*j+1] = iter().get_dest_table(2+2*j+1); |
374 } |
509 table[3*j+2] = profile == NULL ? 1 : profile->count_at(j); |
375 qsort( table, len, 2*sizeof(table[0]), jint_cmp ); |
510 } |
|
511 qsort(table, len, 3*sizeof(table[0]), jint_cmp); |
|
512 } |
|
513 |
|
514 float defaults = 0; |
|
515 jint prev = min_jint; |
|
516 for (int j = 0; j < len; j++) { |
|
517 jint match_int = table[3*j+0]; |
|
518 if (match_int != prev) { |
|
519 defaults += (float)match_int - prev; |
|
520 } |
|
521 prev = match_int+1; |
|
522 } |
|
523 if (prev-1 != max_jint) { |
|
524 defaults += (float)max_jint - prev + 1; |
|
525 } |
|
526 float default_cnt = 1; |
|
527 if (profile != NULL) { |
|
528 default_cnt = profile->default_count()/defaults; |
376 } |
529 } |
377 |
530 |
378 int rnum = len*2+1; |
531 int rnum = len*2+1; |
379 bool makes_backward_branch = false; |
532 bool makes_backward_branch = false; |
380 SwitchRange* ranges = NEW_RESOURCE_ARRAY(SwitchRange, rnum); |
533 SwitchRange* ranges = NEW_RESOURCE_ARRAY(SwitchRange, rnum); |
381 int rp = -1; |
534 int rp = -1; |
382 for( int j = 0; j < len; j++ ) { |
535 for (int j = 0; j < len; j++) { |
383 jint match_int = table[j+j+0]; |
536 jint match_int = table[3*j+0]; |
384 int dest = table[j+j+1]; |
537 int dest = table[3*j+1]; |
|
538 int cnt = table[3*j+2]; |
385 int next_lo = rp < 0 ? min_jint : ranges[rp].hi()+1; |
539 int next_lo = rp < 0 ? min_jint : ranges[rp].hi()+1; |
386 int table_index = method_data_update() ? j : NullTableIndex; |
540 int table_index = method_data_update() ? j : NullTableIndex; |
387 makes_backward_branch |= (dest <= bci()); |
541 makes_backward_branch |= (dest <= bci()); |
388 if( match_int != next_lo ) { |
542 float c = default_cnt * ((float)match_int - next_lo); |
389 ranges[++rp].setRange(next_lo, match_int-1, default_dest, NullTableIndex); |
543 if (match_int != next_lo && (rp < 0 || !ranges[rp].adjoinRange(next_lo, match_int-1, default_dest, NullTableIndex, c, trim_ranges))) { |
390 } |
544 assert(default_dest != never_reached, "sentinel value for dead destinations"); |
391 if( rp < 0 || !ranges[rp].adjoin(match_int, dest, table_index) ) { |
545 ranges[++rp].setRange(next_lo, match_int-1, default_dest, NullTableIndex, c); |
392 ranges[++rp].set(match_int, dest, table_index); |
546 } |
393 } |
547 if (rp < 0 || !ranges[rp].adjoin(match_int, dest, table_index, cnt, trim_ranges)) { |
394 } |
548 assert(dest != never_reached, "sentinel value for dead destinations"); |
395 jint highest = table[2*(len-1)]; |
549 ranges[++rp].set(match_int, dest, table_index, cnt); |
|
550 } |
|
551 } |
|
552 jint highest = table[3*(len-1)]; |
396 assert(ranges[rp].hi() == highest, ""); |
553 assert(ranges[rp].hi() == highest, ""); |
397 if( highest != max_jint |
554 if (highest != max_jint && |
398 && !ranges[rp].adjoinRange(highest+1, max_jint, default_dest, NullTableIndex) ) { |
555 !ranges[rp].adjoinRange(highest+1, max_jint, default_dest, NullTableIndex, default_cnt * ((float)max_jint - highest), trim_ranges)) { |
399 ranges[++rp].setRange(highest+1, max_jint, default_dest, NullTableIndex); |
556 ranges[++rp].setRange(highest+1, max_jint, default_dest, NullTableIndex, default_cnt * ((float)max_jint - highest)); |
400 } |
557 } |
401 assert(rp < rnum, "not too many ranges"); |
558 assert(rp < rnum, "not too many ranges"); |
402 |
559 |
|
560 if (trim_ranges) { |
|
561 merge_ranges(ranges, rp); |
|
562 } |
|
563 |
403 // Safepoint in case backward branch observed |
564 // Safepoint in case backward branch observed |
404 if( makes_backward_branch && UseLoopSafepoints ) |
565 if (makes_backward_branch && UseLoopSafepoints) |
405 add_safepoint(); |
566 add_safepoint(); |
406 |
567 |
407 jump_switch_ranges(lookup, &ranges[0], &ranges[rp]); |
568 jump_switch_ranges(lookup, &ranges[0], &ranges[rp]); |
|
569 } |
|
570 |
|
571 static float if_prob(float taken_cnt, float total_cnt) { |
|
572 assert(taken_cnt <= total_cnt, ""); |
|
573 if (total_cnt == 0) { |
|
574 return PROB_FAIR; |
|
575 } |
|
576 float p = taken_cnt / total_cnt; |
|
577 return MIN2(MAX2(p, PROB_MIN), PROB_MAX); |
|
578 } |
|
579 |
|
580 static float if_cnt(float cnt) { |
|
581 if (cnt == 0) { |
|
582 return COUNT_UNKNOWN; |
|
583 } |
|
584 return cnt; |
|
585 } |
|
586 |
|
587 static float sum_of_cnts(SwitchRange *lo, SwitchRange *hi) { |
|
588 float total_cnt = 0; |
|
589 for (SwitchRange* sr = lo; sr <= hi; sr++) { |
|
590 total_cnt += sr->cnt(); |
|
591 } |
|
592 return total_cnt; |
|
593 } |
|
594 |
|
595 class SwitchRanges : public ResourceObj { |
|
596 public: |
|
597 SwitchRange* _lo; |
|
598 SwitchRange* _hi; |
|
599 SwitchRange* _mid; |
|
600 float _cost; |
|
601 |
|
602 enum { |
|
603 Start, |
|
604 LeftDone, |
|
605 RightDone, |
|
606 Done |
|
607 } _state; |
|
608 |
|
609 SwitchRanges(SwitchRange *lo, SwitchRange *hi) |
|
610 : _lo(lo), _hi(hi), _mid(NULL), |
|
611 _cost(0), _state(Start) { |
|
612 } |
|
613 |
|
614 SwitchRanges() |
|
615 : _lo(NULL), _hi(NULL), _mid(NULL), |
|
616 _cost(0), _state(Start) {} |
|
617 }; |
|
618 |
|
619 // Estimate cost of performing a binary search on lo..hi |
|
620 static float compute_tree_cost(SwitchRange *lo, SwitchRange *hi, float total_cnt) { |
|
621 GrowableArray<SwitchRanges> tree; |
|
622 SwitchRanges root(lo, hi); |
|
623 tree.push(root); |
|
624 |
|
625 float cost = 0; |
|
626 do { |
|
627 SwitchRanges& r = *tree.adr_at(tree.length()-1); |
|
628 if (r._hi != r._lo) { |
|
629 if (r._mid == NULL) { |
|
630 float r_cnt = sum_of_cnts(r._lo, r._hi); |
|
631 |
|
632 if (r_cnt == 0) { |
|
633 tree.pop(); |
|
634 cost = 0; |
|
635 continue; |
|
636 } |
|
637 |
|
638 SwitchRange* mid = NULL; |
|
639 mid = r._lo; |
|
640 for (float cnt = 0; ; ) { |
|
641 assert(mid <= r._hi, "out of bounds"); |
|
642 cnt += mid->cnt(); |
|
643 if (cnt > r_cnt / 2) { |
|
644 break; |
|
645 } |
|
646 mid++; |
|
647 } |
|
648 assert(mid <= r._hi, "out of bounds"); |
|
649 r._mid = mid; |
|
650 r._cost = r_cnt / total_cnt; |
|
651 } |
|
652 r._cost += cost; |
|
653 if (r._state < SwitchRanges::LeftDone && r._mid > r._lo) { |
|
654 cost = 0; |
|
655 r._state = SwitchRanges::LeftDone; |
|
656 tree.push(SwitchRanges(r._lo, r._mid-1)); |
|
657 } else if (r._state < SwitchRanges::RightDone) { |
|
658 cost = 0; |
|
659 r._state = SwitchRanges::RightDone; |
|
660 tree.push(SwitchRanges(r._mid == r._lo ? r._mid+1 : r._mid, r._hi)); |
|
661 } else { |
|
662 tree.pop(); |
|
663 cost = r._cost; |
|
664 } |
|
665 } else { |
|
666 tree.pop(); |
|
667 cost = r._cost; |
|
668 } |
|
669 } while (tree.length() > 0); |
|
670 |
|
671 |
|
672 return cost; |
|
673 } |
|
674 |
|
675 // It sometimes pays off to test most common ranges before the binary search |
|
676 void Parse::linear_search_switch_ranges(Node* key_val, SwitchRange*& lo, SwitchRange*& hi) { |
|
677 uint nr = hi - lo + 1; |
|
678 float total_cnt = sum_of_cnts(lo, hi); |
|
679 |
|
680 float min = compute_tree_cost(lo, hi, total_cnt); |
|
681 float extra = 1; |
|
682 float sub = 0; |
|
683 |
|
684 SwitchRange* array1 = lo; |
|
685 SwitchRange* array2 = NEW_RESOURCE_ARRAY(SwitchRange, nr); |
|
686 |
|
687 SwitchRange* ranges = NULL; |
|
688 |
|
689 while (nr >= 2) { |
|
690 assert(lo == array1 || lo == array2, "one the 2 already allocated arrays"); |
|
691 ranges = (lo == array1) ? array2 : array1; |
|
692 |
|
693 // Find highest frequency range |
|
694 SwitchRange* candidate = lo; |
|
695 for (SwitchRange* sr = lo+1; sr <= hi; sr++) { |
|
696 if (sr->cnt() > candidate->cnt()) { |
|
697 candidate = sr; |
|
698 } |
|
699 } |
|
700 SwitchRange most_freq = *candidate; |
|
701 if (most_freq.cnt() == 0) { |
|
702 break; |
|
703 } |
|
704 |
|
705 // Copy remaining ranges into another array |
|
706 int shift = 0; |
|
707 for (uint i = 0; i < nr; i++) { |
|
708 SwitchRange* sr = &lo[i]; |
|
709 if (sr != candidate) { |
|
710 ranges[i-shift] = *sr; |
|
711 } else { |
|
712 shift++; |
|
713 if (i > 0 && i < nr-1) { |
|
714 SwitchRange prev = lo[i-1]; |
|
715 prev.setRange(prev.lo(), sr->hi(), prev.dest(), prev.table_index(), prev.cnt()); |
|
716 if (prev.adjoin(lo[i+1])) { |
|
717 shift++; |
|
718 i++; |
|
719 } |
|
720 ranges[i-shift] = prev; |
|
721 } |
|
722 } |
|
723 } |
|
724 nr -= shift; |
|
725 |
|
726 // Evaluate cost of testing the most common range and performing a |
|
727 // binary search on the other ranges |
|
728 float cost = extra + compute_tree_cost(&ranges[0], &ranges[nr-1], total_cnt); |
|
729 if (cost >= min) { |
|
730 break; |
|
731 } |
|
732 // swap arrays |
|
733 lo = &ranges[0]; |
|
734 hi = &ranges[nr-1]; |
|
735 |
|
736 // It pays off: emit the test for the most common range |
|
737 assert(most_freq.cnt() > 0, "must be taken"); |
|
738 Node* val = _gvn.transform(new SubINode(key_val, _gvn.intcon(most_freq.lo()))); |
|
739 Node* cmp = _gvn.transform(new CmpUNode(val, _gvn.intcon(most_freq.hi() - most_freq.lo()))); |
|
740 Node* tst = _gvn.transform(new BoolNode(cmp, BoolTest::le)); |
|
741 IfNode* iff = create_and_map_if(control(), tst, if_prob(most_freq.cnt(), total_cnt), if_cnt(most_freq.cnt())); |
|
742 jump_if_true_fork(iff, most_freq.dest(), most_freq.table_index(), false); |
|
743 |
|
744 sub += most_freq.cnt() / total_cnt; |
|
745 extra += 1 - sub; |
|
746 min = cost; |
|
747 } |
408 } |
748 } |
409 |
749 |
410 //----------------------------create_jump_tables------------------------------- |
750 //----------------------------create_jump_tables------------------------------- |
411 bool Parse::create_jump_tables(Node* key_val, SwitchRange* lo, SwitchRange* hi) { |
751 bool Parse::create_jump_tables(Node* key_val, SwitchRange* lo, SwitchRange* hi) { |
412 // Are jumptables enabled |
752 // Are jumptables enabled |
437 } else { |
779 } else { |
438 total_outlier_size = hi_size; |
780 total_outlier_size = hi_size; |
439 default_dest = hi->dest(); |
781 default_dest = hi->dest(); |
440 } |
782 } |
441 |
783 |
|
784 float total = sum_of_cnts(lo, hi); |
|
785 float cost = compute_tree_cost(lo, hi, total); |
|
786 |
442 // If a guard test will eliminate very sparse end ranges, then |
787 // If a guard test will eliminate very sparse end ranges, then |
443 // it is worth the cost of an extra jump. |
788 // it is worth the cost of an extra jump. |
|
789 float trimmed_cnt = 0; |
444 if (total_outlier_size > (MaxJumpTableSparseness * 4)) { |
790 if (total_outlier_size > (MaxJumpTableSparseness * 4)) { |
445 needs_guard = true; |
791 needs_guard = true; |
446 if (default_dest == lo->dest()) lo++; |
792 if (default_dest == lo->dest()) { |
447 if (default_dest == hi->dest()) hi--; |
793 trimmed_cnt += lo->cnt(); |
|
794 lo++; |
|
795 } |
|
796 if (default_dest == hi->dest()) { |
|
797 trimmed_cnt += hi->cnt(); |
|
798 hi--; |
|
799 } |
448 } |
800 } |
449 |
801 |
450 // Find the total number of cases and ranges |
802 // Find the total number of cases and ranges |
451 int64_t num_cases = ((int64_t)hi->hi()) - ((int64_t)lo->lo()) + 1; |
803 int64_t num_cases = ((int64_t)hi->hi()) - ((int64_t)lo->lo()) + 1; |
452 int num_range = hi - lo + 1; |
804 int num_range = hi - lo + 1; |
453 |
805 |
454 // Don't create table if: too large, too small, or too sparse. |
806 // Don't create table if: too large, too small, or too sparse. |
455 if (num_cases < MinJumpTableSize || num_cases > MaxJumpTableSize) |
807 if (num_cases > MaxJumpTableSize) |
456 return false; |
808 return false; |
|
809 if (UseSwitchProfiling) { |
|
810 // MinJumpTableSize is set so with a well balanced binary tree, |
|
811 // when the number of ranges is MinJumpTableSize, it's cheaper to |
|
812 // go through a JumpNode that a tree of IfNodes. Average cost of a |
|
813 // tree of IfNodes with MinJumpTableSize is |
|
814 // log2f(MinJumpTableSize) comparisons. So if the cost computed |
|
815 // from profile data is less than log2f(MinJumpTableSize) then |
|
816 // going with the binary search is cheaper. |
|
817 if (cost < log2f(MinJumpTableSize)) { |
|
818 return false; |
|
819 } |
|
820 } else { |
|
821 if (num_cases < MinJumpTableSize) |
|
822 return false; |
|
823 } |
457 if (num_cases > (MaxJumpTableSparseness * num_range)) |
824 if (num_cases > (MaxJumpTableSparseness * num_range)) |
458 return false; |
825 return false; |
459 |
826 |
460 // Normalize table lookups to zero |
827 // Normalize table lookups to zero |
461 int lowval = lo->lo(); |
828 int lowval = lo->lo(); |
487 // than a switch value |
856 // than a switch value |
488 Node *shiftWord = _gvn.MakeConX(wordSize); |
857 Node *shiftWord = _gvn.MakeConX(wordSize); |
489 key_val = _gvn.transform( new MulXNode( key_val, shiftWord)); |
858 key_val = _gvn.transform( new MulXNode( key_val, shiftWord)); |
490 |
859 |
491 // Create the JumpNode |
860 // Create the JumpNode |
492 Node* jtn = _gvn.transform( new JumpNode(control(), key_val, num_cases) ); |
861 Arena* arena = C->comp_arena(); |
|
862 float* probs = (float*)arena->Amalloc(sizeof(float)*num_cases); |
|
863 int i = 0; |
|
864 if (total == 0) { |
|
865 for (SwitchRange* r = lo; r <= hi; r++) { |
|
866 for (int64_t j = r->lo(); j <= r->hi(); j++, i++) { |
|
867 probs[i] = 1.0F / num_cases; |
|
868 } |
|
869 } |
|
870 } else { |
|
871 for (SwitchRange* r = lo; r <= hi; r++) { |
|
872 float prob = r->cnt()/total; |
|
873 for (int64_t j = r->lo(); j <= r->hi(); j++, i++) { |
|
874 probs[i] = prob / (r->hi() - r->lo() + 1); |
|
875 } |
|
876 } |
|
877 } |
|
878 |
|
879 ciMethodData* methodData = method()->method_data(); |
|
880 ciMultiBranchData* profile = NULL; |
|
881 if (methodData->is_mature()) { |
|
882 ciProfileData* data = methodData->bci_to_data(bci()); |
|
883 if (data != NULL && data->is_MultiBranchData()) { |
|
884 profile = (ciMultiBranchData*)data; |
|
885 } |
|
886 } |
|
887 |
|
888 Node* jtn = _gvn.transform(new JumpNode(control(), key_val, num_cases, probs, profile == NULL ? COUNT_UNKNOWN : total)); |
493 |
889 |
494 // These are the switch destinations hanging off the jumpnode |
890 // These are the switch destinations hanging off the jumpnode |
495 int i = 0; |
891 i = 0; |
496 for (SwitchRange* r = lo; r <= hi; r++) { |
892 for (SwitchRange* r = lo; r <= hi; r++) { |
497 for (int64_t j = r->lo(); j <= r->hi(); j++, i++) { |
893 for (int64_t j = r->lo(); j <= r->hi(); j++, i++) { |
498 Node* input = _gvn.transform(new JumpProjNode(jtn, i, r->dest(), (int)(j - lowval))); |
894 Node* input = _gvn.transform(new JumpProjNode(jtn, i, r->dest(), (int)(j - lowval))); |
499 { |
895 { |
500 PreserveJVMState pjvms(this); |
896 PreserveJVMState pjvms(this); |
501 set_control(input); |
897 set_control(input); |
502 jump_if_always_fork(r->dest(), r->table_index()); |
898 jump_if_always_fork(r->dest(), r->table_index(), trim_ranges && r->cnt() == 0); |
503 } |
899 } |
504 } |
900 } |
505 } |
901 } |
506 assert(i == num_cases, "miscount of cases"); |
902 assert(i == num_cases, "miscount of cases"); |
507 stop_and_kill_map(); // no more uses for this JVMS |
903 stop_and_kill_map(); // no more uses for this JVMS |
509 } |
905 } |
510 |
906 |
511 //----------------------------jump_switch_ranges------------------------------- |
907 //----------------------------jump_switch_ranges------------------------------- |
512 void Parse::jump_switch_ranges(Node* key_val, SwitchRange *lo, SwitchRange *hi, int switch_depth) { |
908 void Parse::jump_switch_ranges(Node* key_val, SwitchRange *lo, SwitchRange *hi, int switch_depth) { |
513 Block* switch_block = block(); |
909 Block* switch_block = block(); |
|
910 bool trim_ranges = !method_data_update() && !C->too_many_traps(method(), bci(), Deoptimization::Reason_unstable_if); |
514 |
911 |
515 if (switch_depth == 0) { |
912 if (switch_depth == 0) { |
516 // Do special processing for the top-level call. |
913 // Do special processing for the top-level call. |
517 assert(lo->lo() == min_jint, "initial range must exhaust Type::INT"); |
914 assert(lo->lo() == min_jint, "initial range must exhaust Type::INT"); |
518 assert(hi->hi() == max_jint, "initial range must exhaust Type::INT"); |
915 assert(hi->hi() == max_jint, "initial range must exhaust Type::INT"); |
519 |
916 |
520 // Decrement pred-numbers for the unique set of nodes. |
917 // Decrement pred-numbers for the unique set of nodes. |
521 #ifdef ASSERT |
918 #ifdef ASSERT |
522 // Ensure that the block's successors are a (duplicate-free) set. |
919 if (!trim_ranges) { |
523 int successors_counted = 0; // block occurrences in [hi..lo] |
920 // Ensure that the block's successors are a (duplicate-free) set. |
524 int unique_successors = switch_block->num_successors(); |
921 int successors_counted = 0; // block occurrences in [hi..lo] |
525 for (int i = 0; i < unique_successors; i++) { |
922 int unique_successors = switch_block->num_successors(); |
526 Block* target = switch_block->successor_at(i); |
923 for (int i = 0; i < unique_successors; i++) { |
527 |
924 Block* target = switch_block->successor_at(i); |
528 // Check that the set of successors is the same in both places. |
925 |
529 int successors_found = 0; |
926 // Check that the set of successors is the same in both places. |
530 for (SwitchRange* p = lo; p <= hi; p++) { |
927 int successors_found = 0; |
531 if (p->dest() == target->start()) successors_found++; |
928 for (SwitchRange* p = lo; p <= hi; p++) { |
|
929 if (p->dest() == target->start()) successors_found++; |
|
930 } |
|
931 assert(successors_found > 0, "successor must be known"); |
|
932 successors_counted += successors_found; |
532 } |
933 } |
533 assert(successors_found > 0, "successor must be known"); |
934 assert(successors_counted == (hi-lo)+1, "no unexpected successors"); |
534 successors_counted += successors_found; |
935 } |
535 } |
|
536 assert(successors_counted == (hi-lo)+1, "no unexpected successors"); |
|
537 #endif |
936 #endif |
538 |
937 |
539 // Maybe prune the inputs, based on the type of key_val. |
938 // Maybe prune the inputs, based on the type of key_val. |
540 jint min_val = min_jint; |
939 jint min_val = min_jint; |
541 jint max_val = max_jint; |
940 jint max_val = max_jint; |
558 } |
967 } |
559 #endif |
968 #endif |
560 |
969 |
561 assert(lo <= hi, "must be a non-empty set of ranges"); |
970 assert(lo <= hi, "must be a non-empty set of ranges"); |
562 if (lo == hi) { |
971 if (lo == hi) { |
563 jump_if_always_fork(lo->dest(), lo->table_index()); |
972 jump_if_always_fork(lo->dest(), lo->table_index(), trim_ranges && lo->cnt() == 0); |
564 } else { |
973 } else { |
565 assert(lo->hi() == (lo+1)->lo()-1, "contiguous ranges"); |
974 assert(lo->hi() == (lo+1)->lo()-1, "contiguous ranges"); |
566 assert(hi->lo() == (hi-1)->hi()+1, "contiguous ranges"); |
975 assert(hi->lo() == (hi-1)->hi()+1, "contiguous ranges"); |
567 |
976 |
568 if (create_jump_tables(key_val, lo, hi)) return; |
977 if (create_jump_tables(key_val, lo, hi)) return; |
569 |
978 |
|
979 SwitchRange* mid = NULL; |
|
980 float total_cnt = sum_of_cnts(lo, hi); |
|
981 |
570 int nr = hi - lo + 1; |
982 int nr = hi - lo + 1; |
571 |
983 if (UseSwitchProfiling) { |
572 SwitchRange* mid = lo + nr/2; |
984 // Don't keep the binary search tree balanced: pick up mid point |
573 // if there is an easy choice, pivot at a singleton: |
985 // that split frequencies in half. |
574 if (nr > 3 && !mid->is_singleton() && (mid-1)->is_singleton()) mid--; |
986 float cnt = 0; |
575 |
987 for (SwitchRange* sr = lo; sr <= hi; sr++) { |
576 assert(lo < mid && mid <= hi, "good pivot choice"); |
988 cnt += sr->cnt(); |
577 assert(nr != 2 || mid == hi, "should pick higher of 2"); |
989 if (cnt >= total_cnt / 2) { |
578 assert(nr != 3 || mid == hi-1, "should pick middle of 3"); |
990 mid = sr; |
579 |
991 break; |
580 Node *test_val = _gvn.intcon(mid->lo()); |
992 } |
|
993 } |
|
994 } else { |
|
995 mid = lo + nr/2; |
|
996 |
|
997 // if there is an easy choice, pivot at a singleton: |
|
998 if (nr > 3 && !mid->is_singleton() && (mid-1)->is_singleton()) mid--; |
|
999 |
|
1000 assert(lo < mid && mid <= hi, "good pivot choice"); |
|
1001 assert(nr != 2 || mid == hi, "should pick higher of 2"); |
|
1002 assert(nr != 3 || mid == hi-1, "should pick middle of 3"); |
|
1003 } |
|
1004 |
|
1005 |
|
1006 Node *test_val = _gvn.intcon(mid == lo ? mid->hi() : mid->lo()); |
581 |
1007 |
582 if (mid->is_singleton()) { |
1008 if (mid->is_singleton()) { |
583 IfNode *iff_ne = jump_if_fork_int(key_val, test_val, BoolTest::ne); |
1009 IfNode *iff_ne = jump_if_fork_int(key_val, test_val, BoolTest::ne, 1-if_prob(mid->cnt(), total_cnt), if_cnt(mid->cnt())); |
584 jump_if_false_fork(iff_ne, mid->dest(), mid->table_index()); |
1010 jump_if_false_fork(iff_ne, mid->dest(), mid->table_index(), trim_ranges && mid->cnt() == 0); |
585 |
1011 |
586 // Special Case: If there are exactly three ranges, and the high |
1012 // Special Case: If there are exactly three ranges, and the high |
587 // and low range each go to the same place, omit the "gt" test, |
1013 // and low range each go to the same place, omit the "gt" test, |
588 // since it will not discriminate anything. |
1014 // since it will not discriminate anything. |
589 bool eq_test_only = (hi == lo+2 && hi->dest() == lo->dest()); |
1015 bool eq_test_only = (hi == lo+2 && hi->dest() == lo->dest() && mid == hi-1) || mid == lo; |
590 if (eq_test_only) { |
|
591 assert(mid == hi-1, ""); |
|
592 } |
|
593 |
1016 |
594 // if there is a higher range, test for it and process it: |
1017 // if there is a higher range, test for it and process it: |
595 if (mid < hi && !eq_test_only) { |
1018 if (mid < hi && !eq_test_only) { |
596 // two comparisons of same values--should enable 1 test for 2 branches |
1019 // two comparisons of same values--should enable 1 test for 2 branches |
597 // Use BoolTest::le instead of BoolTest::gt |
1020 // Use BoolTest::le instead of BoolTest::gt |
598 IfNode *iff_le = jump_if_fork_int(key_val, test_val, BoolTest::le); |
1021 float cnt = sum_of_cnts(lo, mid-1); |
|
1022 IfNode *iff_le = jump_if_fork_int(key_val, test_val, BoolTest::le, if_prob(cnt, total_cnt), if_cnt(cnt)); |
599 Node *iftrue = _gvn.transform( new IfTrueNode(iff_le) ); |
1023 Node *iftrue = _gvn.transform( new IfTrueNode(iff_le) ); |
600 Node *iffalse = _gvn.transform( new IfFalseNode(iff_le) ); |
1024 Node *iffalse = _gvn.transform( new IfFalseNode(iff_le) ); |
601 { PreserveJVMState pjvms(this); |
1025 { PreserveJVMState pjvms(this); |
602 set_control(iffalse); |
1026 set_control(iffalse); |
603 jump_switch_ranges(key_val, mid+1, hi, switch_depth+1); |
1027 jump_switch_ranges(key_val, mid+1, hi, switch_depth+1); |
605 set_control(iftrue); |
1029 set_control(iftrue); |
606 } |
1030 } |
607 |
1031 |
608 } else { |
1032 } else { |
609 // mid is a range, not a singleton, so treat mid..hi as a unit |
1033 // mid is a range, not a singleton, so treat mid..hi as a unit |
610 IfNode *iff_ge = jump_if_fork_int(key_val, test_val, BoolTest::ge); |
1034 float cnt = sum_of_cnts(mid == lo ? mid+1 : mid, hi); |
|
1035 IfNode *iff_ge = jump_if_fork_int(key_val, test_val, mid == lo ? BoolTest::gt : BoolTest::ge, if_prob(cnt, total_cnt), if_cnt(cnt)); |
611 |
1036 |
612 // if there is a higher range, test for it and process it: |
1037 // if there is a higher range, test for it and process it: |
613 if (mid == hi) { |
1038 if (mid == hi) { |
614 jump_if_true_fork(iff_ge, mid->dest(), mid->table_index()); |
1039 jump_if_true_fork(iff_ge, mid->dest(), mid->table_index(), trim_ranges && cnt == 0); |
615 } else { |
1040 } else { |
616 Node *iftrue = _gvn.transform( new IfTrueNode(iff_ge) ); |
1041 Node *iftrue = _gvn.transform( new IfTrueNode(iff_ge) ); |
617 Node *iffalse = _gvn.transform( new IfFalseNode(iff_ge) ); |
1042 Node *iffalse = _gvn.transform( new IfFalseNode(iff_ge) ); |
618 { PreserveJVMState pjvms(this); |
1043 { PreserveJVMState pjvms(this); |
619 set_control(iftrue); |
1044 set_control(iftrue); |
620 jump_switch_ranges(key_val, mid, hi, switch_depth+1); |
1045 jump_switch_ranges(key_val, mid == lo ? mid+1 : mid, hi, switch_depth+1); |
621 } |
1046 } |
622 set_control(iffalse); |
1047 set_control(iffalse); |
623 } |
1048 } |
624 } |
1049 } |
625 |
1050 |
626 // in any case, process the lower range |
1051 // in any case, process the lower range |
627 jump_switch_ranges(key_val, lo, mid-1, switch_depth+1); |
1052 if (mid == lo) { |
|
1053 if (mid->is_singleton()) { |
|
1054 jump_switch_ranges(key_val, lo+1, hi, switch_depth+1); |
|
1055 } else { |
|
1056 jump_if_always_fork(lo->dest(), lo->table_index(), trim_ranges && lo->cnt() == 0); |
|
1057 } |
|
1058 } else { |
|
1059 jump_switch_ranges(key_val, lo, mid-1, switch_depth+1); |
|
1060 } |
628 } |
1061 } |
629 |
1062 |
630 // Decrease pred_count for each successor after all is done. |
1063 // Decrease pred_count for each successor after all is done. |
631 if (switch_depth == 0) { |
1064 if (switch_depth == 0) { |
632 int unique_successors = switch_block->num_successors(); |
1065 int unique_successors = switch_block->num_successors(); |