1 /* |
1 /* |
2 * Copyright (c) 1999, 2015, Oracle and/or its affiliates. All rights reserved. |
2 * Copyright (c) 1999, 2016, Oracle and/or its affiliates. All rights reserved. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 * |
4 * |
5 * This code is free software; you can redistribute it and/or modify it |
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 |
6 * under the terms of the GNU General Public License version 2 only, as |
7 * published by the Free Software Foundation. |
7 * published by the Free Software Foundation. |
528 _num_loops(0), |
528 _num_loops(0), |
529 _iterative_dominators(false), |
529 _iterative_dominators(false), |
530 _visited_blocks(_max_block_id), |
530 _visited_blocks(_max_block_id), |
531 _active_blocks(_max_block_id), |
531 _active_blocks(_max_block_id), |
532 _dominator_blocks(_max_block_id), |
532 _dominator_blocks(_max_block_id), |
533 _forward_branches(_max_block_id, 0), |
533 _forward_branches(_max_block_id, _max_block_id, 0), |
534 _loop_end_blocks(8), |
534 _loop_end_blocks(8), |
535 _work_list(8), |
535 _work_list(8), |
536 _linear_scan_order(NULL), // initialized later with correct size |
536 _linear_scan_order(NULL), // initialized later with correct size |
537 _loop_map(0, 0), // initialized later with correct size |
537 _loop_map(0, 0), // initialized later with correct size |
538 _compilation(c) |
538 _compilation(c) |
846 // When the number drops to zero, all forward branches were processed |
846 // When the number drops to zero, all forward branches were processed |
847 if (dec_forward_branches(cur) != 0) { |
847 if (dec_forward_branches(cur) != 0) { |
848 return false; |
848 return false; |
849 } |
849 } |
850 |
850 |
851 assert(_linear_scan_order->index_of(cur) == -1, "block already processed (block can be ready only once)"); |
851 assert(_linear_scan_order->find(cur) == -1, "block already processed (block can be ready only once)"); |
852 assert(_work_list.index_of(cur) == -1, "block already in work-list (block can be ready only once)"); |
852 assert(_work_list.find(cur) == -1, "block already in work-list (block can be ready only once)"); |
853 return true; |
853 return true; |
854 } |
854 } |
855 |
855 |
856 void ComputeLinearScanOrder::sort_into_work_list(BlockBegin* cur) { |
856 void ComputeLinearScanOrder::sort_into_work_list(BlockBegin* cur) { |
857 assert(_work_list.index_of(cur) == -1, "block already in work list"); |
857 assert(_work_list.find(cur) == -1, "block already in work list"); |
858 |
858 |
859 int cur_weight = compute_weight(cur); |
859 int cur_weight = compute_weight(cur); |
860 |
860 |
861 // the linear_scan_number is used to cache the weight of a block |
861 // the linear_scan_number is used to cache the weight of a block |
862 cur->set_linear_scan_number(cur_weight); |
862 cur->set_linear_scan_number(cur_weight); |
888 #endif |
888 #endif |
889 } |
889 } |
890 |
890 |
891 void ComputeLinearScanOrder::append_block(BlockBegin* cur) { |
891 void ComputeLinearScanOrder::append_block(BlockBegin* cur) { |
892 TRACE_LINEAR_SCAN(3, tty->print_cr("appending block B%d (weight 0x%6x) to linear-scan order", cur->block_id(), cur->linear_scan_number())); |
892 TRACE_LINEAR_SCAN(3, tty->print_cr("appending block B%d (weight 0x%6x) to linear-scan order", cur->block_id(), cur->linear_scan_number())); |
893 assert(_linear_scan_order->index_of(cur) == -1, "cannot add the same block twice"); |
893 assert(_linear_scan_order->find(cur) == -1, "cannot add the same block twice"); |
894 |
894 |
895 // currently, the linear scan order and code emit order are equal. |
895 // currently, the linear scan order and code emit order are equal. |
896 // therefore the linear_scan_number and the weight of a block must also |
896 // therefore the linear_scan_number and the weight of a block must also |
897 // be equal. |
897 // be equal. |
898 cur->set_linear_scan_number(_linear_scan_order->length()); |
898 cur->set_linear_scan_number(_linear_scan_order->length()); |
1113 int i; |
1113 int i; |
1114 for (i = 0; i < _linear_scan_order->length(); i++) { |
1114 for (i = 0; i < _linear_scan_order->length(); i++) { |
1115 BlockBegin* cur = _linear_scan_order->at(i); |
1115 BlockBegin* cur = _linear_scan_order->at(i); |
1116 |
1116 |
1117 assert(cur->linear_scan_number() == i, "incorrect linear_scan_number"); |
1117 assert(cur->linear_scan_number() == i, "incorrect linear_scan_number"); |
1118 assert(cur->linear_scan_number() >= 0 && cur->linear_scan_number() == _linear_scan_order->index_of(cur), "incorrect linear_scan_number"); |
1118 assert(cur->linear_scan_number() >= 0 && cur->linear_scan_number() == _linear_scan_order->find(cur), "incorrect linear_scan_number"); |
1119 |
1119 |
1120 int j; |
1120 int j; |
1121 for (j = cur->number_of_sux() - 1; j >= 0; j--) { |
1121 for (j = cur->number_of_sux() - 1; j >= 0; j--) { |
1122 BlockBegin* sux = cur->sux_at(j); |
1122 BlockBegin* sux = cur->sux_at(j); |
1123 |
1123 |
1124 assert(sux->linear_scan_number() >= 0 && sux->linear_scan_number() == _linear_scan_order->index_of(sux), "incorrect linear_scan_number"); |
1124 assert(sux->linear_scan_number() >= 0 && sux->linear_scan_number() == _linear_scan_order->find(sux), "incorrect linear_scan_number"); |
1125 if (!sux->is_set(BlockBegin::backward_branch_target_flag)) { |
1125 if (!sux->is_set(BlockBegin::backward_branch_target_flag)) { |
1126 assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order"); |
1126 assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order"); |
1127 } |
1127 } |
1128 if (cur->loop_depth() == sux->loop_depth()) { |
1128 if (cur->loop_depth() == sux->loop_depth()) { |
1129 assert(cur->loop_index() == sux->loop_index() || sux->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index"); |
1129 assert(cur->loop_index() == sux->loop_index() || sux->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index"); |
1131 } |
1131 } |
1132 |
1132 |
1133 for (j = cur->number_of_preds() - 1; j >= 0; j--) { |
1133 for (j = cur->number_of_preds() - 1; j >= 0; j--) { |
1134 BlockBegin* pred = cur->pred_at(j); |
1134 BlockBegin* pred = cur->pred_at(j); |
1135 |
1135 |
1136 assert(pred->linear_scan_number() >= 0 && pred->linear_scan_number() == _linear_scan_order->index_of(pred), "incorrect linear_scan_number"); |
1136 assert(pred->linear_scan_number() >= 0 && pred->linear_scan_number() == _linear_scan_order->find(pred), "incorrect linear_scan_number"); |
1137 if (!cur->is_set(BlockBegin::backward_branch_target_flag)) { |
1137 if (!cur->is_set(BlockBegin::backward_branch_target_flag)) { |
1138 assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order"); |
1138 assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order"); |
1139 } |
1139 } |
1140 if (cur->loop_depth() == pred->loop_depth()) { |
1140 if (cur->loop_depth() == pred->loop_depth()) { |
1141 assert(cur->loop_index() == pred->loop_index() || cur->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index"); |
1141 assert(cur->loop_index() == pred->loop_index() || cur->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index"); |
1268 } |
1267 } |
1269 |
1268 |
1270 public: |
1269 public: |
1271 PredecessorValidator(IR* hir) { |
1270 PredecessorValidator(IR* hir) { |
1272 ResourceMark rm; |
1271 ResourceMark rm; |
1273 _predecessors = new BlockListList(BlockBegin::number_of_blocks(), NULL); |
1272 _predecessors = new BlockListList(BlockBegin::number_of_blocks(), BlockBegin::number_of_blocks(), NULL); |
1274 _blocks = new BlockList(); |
1273 _blocks = new BlockList(); |
1275 |
1274 |
1276 int i; |
1275 int i; |
1277 hir->start()->iterate_preorder(this); |
1276 hir->start()->iterate_preorder(this); |
1278 if (hir->code() != NULL) { |
1277 if (hir->code() != NULL) { |