1 /*
2 * Copyright (c) 1999, 2015, 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 *
513 DEBUG_ONLY(void verify();)
514
515 Compilation* compilation() const { return _compilation; }
516 public:
517 ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block);
518
519 // accessors for final result
520 BlockList* linear_scan_order() const { return _linear_scan_order; }
521 int num_loops() const { return _num_loops; }
522 };
523
524
525 ComputeLinearScanOrder::ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block) :
526 _max_block_id(BlockBegin::number_of_blocks()),
527 _num_blocks(0),
528 _num_loops(0),
529 _iterative_dominators(false),
530 _visited_blocks(_max_block_id),
531 _active_blocks(_max_block_id),
532 _dominator_blocks(_max_block_id),
533 _forward_branches(_max_block_id, 0),
534 _loop_end_blocks(8),
535 _work_list(8),
536 _linear_scan_order(NULL), // initialized later with correct size
537 _loop_map(0, 0), // initialized later with correct size
538 _compilation(c)
539 {
540 TRACE_LINEAR_SCAN(2, tty->print_cr("***** computing linear-scan block order"));
541
542 init_visited();
543 count_edges(start_block, NULL);
544
545 if (compilation()->is_profiling()) {
546 ciMethod *method = compilation()->method();
547 if (!method->is_accessor()) {
548 ciMethodData* md = method->method_data_or_null();
549 assert(md != NULL, "Sanity");
550 md->set_compilation_stats(_num_loops, _num_blocks);
551 }
552 }
553
831 // exceptions handlers are added as late as possible
832 INC_WEIGHT_IF(!cur->is_set(BlockBegin::exception_entry_flag));
833
834 // guarantee that weight is > 0
835 weight |= 1;
836
837 #undef INC_WEIGHT_IF
838 assert(cur_bit >= 0, "too many flags");
839 assert(weight > 0, "weight cannot become negative");
840
841 return weight;
842 }
843
844 bool ComputeLinearScanOrder::ready_for_processing(BlockBegin* cur) {
845 // Discount the edge just traveled.
846 // When the number drops to zero, all forward branches were processed
847 if (dec_forward_branches(cur) != 0) {
848 return false;
849 }
850
851 assert(_linear_scan_order->index_of(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)");
853 return true;
854 }
855
856 void ComputeLinearScanOrder::sort_into_work_list(BlockBegin* cur) {
857 assert(_work_list.index_of(cur) == -1, "block already in work list");
858
859 int cur_weight = compute_weight(cur);
860
861 // the linear_scan_number is used to cache the weight of a block
862 cur->set_linear_scan_number(cur_weight);
863
864 #ifndef PRODUCT
865 if (StressLinearScan) {
866 _work_list.insert_before(0, cur);
867 return;
868 }
869 #endif
870
871 _work_list.append(NULL); // provide space for new element
872
873 int insert_idx = _work_list.length() - 1;
874 while (insert_idx > 0 && _work_list.at(insert_idx - 1)->linear_scan_number() > cur_weight) {
875 _work_list.at_put(insert_idx, _work_list.at(insert_idx - 1));
876 insert_idx--;
877 }
878 _work_list.at_put(insert_idx, cur);
879
880 TRACE_LINEAR_SCAN(3, tty->print_cr("Sorted B%d into worklist. new worklist:", cur->block_id()));
881 TRACE_LINEAR_SCAN(3, for (int i = 0; i < _work_list.length(); i++) tty->print_cr("%8d B%2d weight:%6x", i, _work_list.at(i)->block_id(), _work_list.at(i)->linear_scan_number()));
882
883 #ifdef ASSERT
884 for (int i = 0; i < _work_list.length(); i++) {
885 assert(_work_list.at(i)->linear_scan_number() > 0, "weight not set");
886 assert(i == 0 || _work_list.at(i - 1)->linear_scan_number() <= _work_list.at(i)->linear_scan_number(), "incorrect order in worklist");
887 }
888 #endif
889 }
890
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()));
893 assert(_linear_scan_order->index_of(cur) == -1, "cannot add the same block twice");
894
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
897 // be equal.
898 cur->set_linear_scan_number(_linear_scan_order->length());
899 _linear_scan_order->append(cur);
900 }
901
902 void ComputeLinearScanOrder::compute_order(BlockBegin* start_block) {
903 TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing final block order"));
904
905 // the start block is always the first block in the linear scan order
906 _linear_scan_order = new BlockList(_num_blocks);
907 append_block(start_block);
908
909 assert(start_block->end()->as_Base() != NULL, "start block must end with Base-instruction");
910 BlockBegin* std_entry = ((Base*)start_block->end())->std_entry();
911 BlockBegin* osr_entry = ((Base*)start_block->end())->osr_entry();
912
913 BlockBegin* sux_of_osr_entry = NULL;
1098 }
1099 #endif
1100
1101 #ifdef ASSERT
1102 void ComputeLinearScanOrder::verify() {
1103 assert(_linear_scan_order->length() == _num_blocks, "wrong number of blocks in list");
1104
1105 if (StressLinearScan) {
1106 // blocks are scrambled when StressLinearScan is used
1107 return;
1108 }
1109
1110 // check that all successors of a block have a higher linear-scan-number
1111 // and that all predecessors of a block have a lower linear-scan-number
1112 // (only backward branches of loops are ignored)
1113 int i;
1114 for (i = 0; i < _linear_scan_order->length(); i++) {
1115 BlockBegin* cur = _linear_scan_order->at(i);
1116
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");
1119
1120 int j;
1121 for (j = cur->number_of_sux() - 1; j >= 0; j--) {
1122 BlockBegin* sux = cur->sux_at(j);
1123
1124 assert(sux->linear_scan_number() >= 0 && sux->linear_scan_number() == _linear_scan_order->index_of(sux), "incorrect linear_scan_number");
1125 if (!sux->is_set(BlockBegin::backward_branch_target_flag)) {
1126 assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order");
1127 }
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");
1130 }
1131 }
1132
1133 for (j = cur->number_of_preds() - 1; j >= 0; j--) {
1134 BlockBegin* pred = cur->pred_at(j);
1135
1136 assert(pred->linear_scan_number() >= 0 && pred->linear_scan_number() == _linear_scan_order->index_of(pred), "incorrect linear_scan_number");
1137 if (!cur->is_set(BlockBegin::backward_branch_target_flag)) {
1138 assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order");
1139 }
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");
1142 }
1143
1144 assert(cur->dominator()->linear_scan_number() <= cur->pred_at(j)->linear_scan_number(), "dominator must be before predecessors");
1145 }
1146
1147 // check dominator
1148 if (i == 0) {
1149 assert(cur->dominator() == NULL, "first block has no dominator");
1150 } else {
1151 assert(cur->dominator() != NULL, "all but first block must have dominator");
1152 }
1153 // Assertion does not hold for exception handlers
1154 assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0) || cur->is_set(BlockBegin::exception_entry_flag), "Single predecessor must also be dominator");
1155 }
1156
1238 };
1239
1240
1241 void IR::print(BlockBegin* start, bool cfg_only, bool live_only) {
1242 ttyLocker ttyl;
1243 InstructionPrinter ip(!cfg_only);
1244 BlockPrinter bp(&ip, cfg_only, live_only);
1245 start->iterate_preorder(&bp);
1246 tty->cr();
1247 }
1248
1249 void IR::print(bool cfg_only, bool live_only) {
1250 if (is_valid()) {
1251 print(start(), cfg_only, live_only);
1252 } else {
1253 tty->print_cr("invalid IR");
1254 }
1255 }
1256
1257
1258 define_array(BlockListArray, BlockList*)
1259 define_stack(BlockListList, BlockListArray)
1260
1261 class PredecessorValidator : public BlockClosure {
1262 private:
1263 BlockListList* _predecessors;
1264 BlockList* _blocks;
1265
1266 static int cmp(BlockBegin** a, BlockBegin** b) {
1267 return (*a)->block_id() - (*b)->block_id();
1268 }
1269
1270 public:
1271 PredecessorValidator(IR* hir) {
1272 ResourceMark rm;
1273 _predecessors = new BlockListList(BlockBegin::number_of_blocks(), NULL);
1274 _blocks = new BlockList();
1275
1276 int i;
1277 hir->start()->iterate_preorder(this);
1278 if (hir->code() != NULL) {
1279 assert(hir->code()->length() == _blocks->length(), "must match");
1280 for (i = 0; i < _blocks->length(); i++) {
1281 assert(hir->code()->contains(_blocks->at(i)), "should be in both lists");
1282 }
1283 }
1284
1285 for (i = 0; i < _blocks->length(); i++) {
1286 BlockBegin* block = _blocks->at(i);
1287 BlockList* preds = _predecessors->at(block->block_id());
1288 if (preds == NULL) {
1289 assert(block->number_of_preds() == 0, "should be the same");
1290 continue;
1291 }
1292
1293 // clone the pred list so we can mutate it
|
1 /*
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.
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 *
513 DEBUG_ONLY(void verify();)
514
515 Compilation* compilation() const { return _compilation; }
516 public:
517 ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block);
518
519 // accessors for final result
520 BlockList* linear_scan_order() const { return _linear_scan_order; }
521 int num_loops() const { return _num_loops; }
522 };
523
524
525 ComputeLinearScanOrder::ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block) :
526 _max_block_id(BlockBegin::number_of_blocks()),
527 _num_blocks(0),
528 _num_loops(0),
529 _iterative_dominators(false),
530 _visited_blocks(_max_block_id),
531 _active_blocks(_max_block_id),
532 _dominator_blocks(_max_block_id),
533 _forward_branches(_max_block_id, _max_block_id, 0),
534 _loop_end_blocks(8),
535 _work_list(8),
536 _linear_scan_order(NULL), // initialized later with correct size
537 _loop_map(0, 0), // initialized later with correct size
538 _compilation(c)
539 {
540 TRACE_LINEAR_SCAN(2, tty->print_cr("***** computing linear-scan block order"));
541
542 init_visited();
543 count_edges(start_block, NULL);
544
545 if (compilation()->is_profiling()) {
546 ciMethod *method = compilation()->method();
547 if (!method->is_accessor()) {
548 ciMethodData* md = method->method_data_or_null();
549 assert(md != NULL, "Sanity");
550 md->set_compilation_stats(_num_loops, _num_blocks);
551 }
552 }
553
831 // exceptions handlers are added as late as possible
832 INC_WEIGHT_IF(!cur->is_set(BlockBegin::exception_entry_flag));
833
834 // guarantee that weight is > 0
835 weight |= 1;
836
837 #undef INC_WEIGHT_IF
838 assert(cur_bit >= 0, "too many flags");
839 assert(weight > 0, "weight cannot become negative");
840
841 return weight;
842 }
843
844 bool ComputeLinearScanOrder::ready_for_processing(BlockBegin* cur) {
845 // Discount the edge just traveled.
846 // When the number drops to zero, all forward branches were processed
847 if (dec_forward_branches(cur) != 0) {
848 return false;
849 }
850
851 assert(_linear_scan_order->find(cur) == -1, "block already processed (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;
854 }
855
856 void ComputeLinearScanOrder::sort_into_work_list(BlockBegin* cur) {
857 assert(_work_list.find(cur) == -1, "block already in work list");
858
859 int cur_weight = compute_weight(cur);
860
861 // the linear_scan_number is used to cache the weight of a block
862 cur->set_linear_scan_number(cur_weight);
863
864 #ifndef PRODUCT
865 if (StressLinearScan) {
866 _work_list.insert_before(0, cur);
867 return;
868 }
869 #endif
870
871 _work_list.append(NULL); // provide space for new element
872
873 int insert_idx = _work_list.length() - 1;
874 while (insert_idx > 0 && _work_list.at(insert_idx - 1)->linear_scan_number() > cur_weight) {
875 _work_list.at_put(insert_idx, _work_list.at(insert_idx - 1));
876 insert_idx--;
877 }
878 _work_list.at_put(insert_idx, cur);
879
880 TRACE_LINEAR_SCAN(3, tty->print_cr("Sorted B%d into worklist. new worklist:", cur->block_id()));
881 TRACE_LINEAR_SCAN(3, for (int i = 0; i < _work_list.length(); i++) tty->print_cr("%8d B%2d weight:%6x", i, _work_list.at(i)->block_id(), _work_list.at(i)->linear_scan_number()));
882
883 #ifdef ASSERT
884 for (int i = 0; i < _work_list.length(); i++) {
885 assert(_work_list.at(i)->linear_scan_number() > 0, "weight not set");
886 assert(i == 0 || _work_list.at(i - 1)->linear_scan_number() <= _work_list.at(i)->linear_scan_number(), "incorrect order in worklist");
887 }
888 #endif
889 }
890
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()));
893 assert(_linear_scan_order->find(cur) == -1, "cannot add the same block twice");
894
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
897 // be equal.
898 cur->set_linear_scan_number(_linear_scan_order->length());
899 _linear_scan_order->append(cur);
900 }
901
902 void ComputeLinearScanOrder::compute_order(BlockBegin* start_block) {
903 TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing final block order"));
904
905 // the start block is always the first block in the linear scan order
906 _linear_scan_order = new BlockList(_num_blocks);
907 append_block(start_block);
908
909 assert(start_block->end()->as_Base() != NULL, "start block must end with Base-instruction");
910 BlockBegin* std_entry = ((Base*)start_block->end())->std_entry();
911 BlockBegin* osr_entry = ((Base*)start_block->end())->osr_entry();
912
913 BlockBegin* sux_of_osr_entry = NULL;
1098 }
1099 #endif
1100
1101 #ifdef ASSERT
1102 void ComputeLinearScanOrder::verify() {
1103 assert(_linear_scan_order->length() == _num_blocks, "wrong number of blocks in list");
1104
1105 if (StressLinearScan) {
1106 // blocks are scrambled when StressLinearScan is used
1107 return;
1108 }
1109
1110 // check that all successors of a block have a higher linear-scan-number
1111 // and that all predecessors of a block have a lower linear-scan-number
1112 // (only backward branches of loops are ignored)
1113 int i;
1114 for (i = 0; i < _linear_scan_order->length(); i++) {
1115 BlockBegin* cur = _linear_scan_order->at(i);
1116
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->find(cur), "incorrect linear_scan_number");
1119
1120 int j;
1121 for (j = cur->number_of_sux() - 1; j >= 0; j--) {
1122 BlockBegin* sux = cur->sux_at(j);
1123
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)) {
1126 assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order");
1127 }
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");
1130 }
1131 }
1132
1133 for (j = cur->number_of_preds() - 1; j >= 0; j--) {
1134 BlockBegin* pred = cur->pred_at(j);
1135
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)) {
1138 assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order");
1139 }
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");
1142 }
1143
1144 assert(cur->dominator()->linear_scan_number() <= cur->pred_at(j)->linear_scan_number(), "dominator must be before predecessors");
1145 }
1146
1147 // check dominator
1148 if (i == 0) {
1149 assert(cur->dominator() == NULL, "first block has no dominator");
1150 } else {
1151 assert(cur->dominator() != NULL, "all but first block must have dominator");
1152 }
1153 // Assertion does not hold for exception handlers
1154 assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0) || cur->is_set(BlockBegin::exception_entry_flag), "Single predecessor must also be dominator");
1155 }
1156
1238 };
1239
1240
1241 void IR::print(BlockBegin* start, bool cfg_only, bool live_only) {
1242 ttyLocker ttyl;
1243 InstructionPrinter ip(!cfg_only);
1244 BlockPrinter bp(&ip, cfg_only, live_only);
1245 start->iterate_preorder(&bp);
1246 tty->cr();
1247 }
1248
1249 void IR::print(bool cfg_only, bool live_only) {
1250 if (is_valid()) {
1251 print(start(), cfg_only, live_only);
1252 } else {
1253 tty->print_cr("invalid IR");
1254 }
1255 }
1256
1257
1258 typedef GrowableArray<BlockList*> BlockListList;
1259
1260 class PredecessorValidator : public BlockClosure {
1261 private:
1262 BlockListList* _predecessors;
1263 BlockList* _blocks;
1264
1265 static int cmp(BlockBegin** a, BlockBegin** b) {
1266 return (*a)->block_id() - (*b)->block_id();
1267 }
1268
1269 public:
1270 PredecessorValidator(IR* hir) {
1271 ResourceMark rm;
1272 _predecessors = new BlockListList(BlockBegin::number_of_blocks(), BlockBegin::number_of_blocks(), NULL);
1273 _blocks = new BlockList();
1274
1275 int i;
1276 hir->start()->iterate_preorder(this);
1277 if (hir->code() != NULL) {
1278 assert(hir->code()->length() == _blocks->length(), "must match");
1279 for (i = 0; i < _blocks->length(); i++) {
1280 assert(hir->code()->contains(_blocks->at(i)), "should be in both lists");
1281 }
1282 }
1283
1284 for (i = 0; i < _blocks->length(); i++) {
1285 BlockBegin* block = _blocks->at(i);
1286 BlockList* preds = _predecessors->at(block->block_id());
1287 if (preds == NULL) {
1288 assert(block->number_of_preds() == 0, "should be the same");
1289 continue;
1290 }
1291
1292 // clone the pred list so we can mutate it
|