1 /* |
1 /* |
2 * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved. |
2 * Copyright (c) 2012, 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. |
51 } |
51 } |
52 } |
52 } |
53 |
53 |
54 // Constructor |
54 // Constructor |
55 RangeCheckEliminator::RangeCheckEliminator(IR *ir) : |
55 RangeCheckEliminator::RangeCheckEliminator(IR *ir) : |
56 _bounds(Instruction::number_of_instructions(), NULL), |
56 _bounds(Instruction::number_of_instructions(), Instruction::number_of_instructions(), NULL), |
57 _access_indexed_info(Instruction::number_of_instructions(), NULL) |
57 _access_indexed_info(Instruction::number_of_instructions(), Instruction::number_of_instructions(), NULL) |
58 { |
58 { |
59 _visitor.set_range_check_eliminator(this); |
59 _visitor.set_range_check_eliminator(this); |
60 _ir = ir; |
60 _ir = ir; |
61 _number_of_instructions = Instruction::number_of_instructions(); |
61 _number_of_instructions = Instruction::number_of_instructions(); |
62 _optimistic = ir->compilation()->is_optimistic(); |
62 _optimistic = ir->compilation()->is_optimistic(); |
301 // Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack. |
301 // Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack. |
302 RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) { |
302 RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) { |
303 // Wrong type or NULL -> No bound |
303 // Wrong type or NULL -> No bound |
304 if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return NULL; |
304 if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return NULL; |
305 |
305 |
306 if (!_bounds[v->id()]) { |
306 if (!_bounds.at(v->id())) { |
307 // First (default) bound is calculated |
307 // First (default) bound is calculated |
308 // Create BoundStack |
308 // Create BoundStack |
309 _bounds[v->id()] = new BoundStack(); |
309 _bounds.at_put(v->id(), new BoundStack()); |
310 _visitor.clear_bound(); |
310 _visitor.clear_bound(); |
311 Value visit_value = v; |
311 Value visit_value = v; |
312 visit_value->visit(&_visitor); |
312 visit_value->visit(&_visitor); |
313 Bound *bound = _visitor.bound(); |
313 Bound *bound = _visitor.bound(); |
314 if (bound) { |
314 if (bound) { |
315 _bounds[v->id()]->push(bound); |
315 _bounds.at(v->id())->push(bound); |
316 } |
316 } |
317 if (_bounds[v->id()]->length() == 0) { |
317 if (_bounds.at(v->id())->length() == 0) { |
318 assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here"); |
318 assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here"); |
319 _bounds[v->id()]->push(new Bound()); |
319 _bounds.at(v->id())->push(new Bound()); |
320 } |
320 } |
321 } else if (_bounds[v->id()]->length() == 0) { |
321 } else if (_bounds.at(v->id())->length() == 0) { |
322 // To avoid endless loops, bound is currently in calculation -> nothing known about it |
322 // To avoid endless loops, bound is currently in calculation -> nothing known about it |
323 return new Bound(); |
323 return new Bound(); |
324 } |
324 } |
325 |
325 |
326 // Return bound |
326 // Return bound |
327 return _bounds[v->id()]->top(); |
327 return _bounds.at(v->id())->top(); |
328 } |
328 } |
329 |
329 |
330 // Update bound |
330 // Update bound |
331 void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) { |
331 void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) { |
332 if (cond == Instruction::gtr) { |
332 if (cond == Instruction::gtr) { |
351 void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) { |
351 void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) { |
352 if (v->as_Constant()) { |
352 if (v->as_Constant()) { |
353 // No bound update for constants |
353 // No bound update for constants |
354 return; |
354 return; |
355 } |
355 } |
356 if (!_bounds[v->id()]) { |
356 if (!_bounds.at(v->id())) { |
357 get_bound(v); |
357 get_bound(v); |
358 assert(_bounds[v->id()], "Now Stack must exist"); |
358 assert(_bounds.at(v->id()), "Now Stack must exist"); |
359 } |
359 } |
360 Bound *top = NULL; |
360 Bound *top = NULL; |
361 if (_bounds[v->id()]->length() > 0) { |
361 if (_bounds.at(v->id())->length() > 0) { |
362 top = _bounds[v->id()]->top(); |
362 top = _bounds.at(v->id())->top(); |
363 } |
363 } |
364 if (top) { |
364 if (top) { |
365 bound->and_op(top); |
365 bound->and_op(top); |
366 } |
366 } |
367 _bounds[v->id()]->push(bound); |
367 _bounds.at(v->id())->push(bound); |
368 pushed.append(v->id()); |
368 pushed.append(v->id()); |
369 } |
369 } |
370 |
370 |
371 // Add instruction + idx for in block motion |
371 // Add instruction + idx for in block motion |
372 void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) { |
372 void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) { |
373 int id = instruction->id(); |
373 int id = instruction->id(); |
374 AccessIndexedInfo *aii = _access_indexed_info[id]; |
374 AccessIndexedInfo *aii = _access_indexed_info.at(id); |
375 if (aii == NULL) { |
375 if (aii == NULL) { |
376 aii = new AccessIndexedInfo(); |
376 aii = new AccessIndexedInfo(); |
377 _access_indexed_info[id] = aii; |
377 _access_indexed_info.at_put(id, aii); |
378 indices.append(instruction); |
378 indices.append(instruction); |
379 aii->_min = idx; |
379 aii->_min = idx; |
380 aii->_max = idx; |
380 aii->_max = idx; |
381 aii->_list = new AccessIndexedList(); |
381 aii->_list = new AccessIndexedList(); |
382 } else if (idx >= aii->_min && idx <= aii->_max) { |
382 } else if (idx >= aii->_min && idx <= aii->_max) { |
459 |
459 |
460 // Iterate over all different indices |
460 // Iterate over all different indices |
461 if (_optimistic) { |
461 if (_optimistic) { |
462 for (int i = 0; i < indices.length(); i++) { |
462 for (int i = 0; i < indices.length(); i++) { |
463 Instruction *index_instruction = indices.at(i); |
463 Instruction *index_instruction = indices.at(i); |
464 AccessIndexedInfo *info = _access_indexed_info[index_instruction->id()]; |
464 AccessIndexedInfo *info = _access_indexed_info.at(index_instruction->id()); |
465 assert(info != NULL, "Info must not be null"); |
465 assert(info != NULL, "Info must not be null"); |
466 |
466 |
467 // if idx < 0, max > 0, max + idx may fall between 0 and |
467 // if idx < 0, max > 0, max + idx may fall between 0 and |
468 // length-1 and if min < 0, min + idx may overflow and be >= |
468 // length-1 and if min < 0, min + idx may overflow and be >= |
469 // 0. The predicate wouldn't trigger but some accesses could |
469 // 0. The predicate wouldn't trigger but some accesses could |
1144 // Try to reach Block end beginning in Block start and not using Block dont_use |
1144 // Try to reach Block end beginning in Block start and not using Block dont_use |
1145 bool RangeCheckEliminator::Verification::can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use /* = NULL */) { |
1145 bool RangeCheckEliminator::Verification::can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use /* = NULL */) { |
1146 if (start == end) return start != dont_use; |
1146 if (start == end) return start != dont_use; |
1147 // Simple BSF from start to end |
1147 // Simple BSF from start to end |
1148 // BlockBeginList _current; |
1148 // BlockBeginList _current; |
1149 for (int i=0; i<_used.length(); i++) { |
1149 for (int i=0; i < _used.length(); i++) { |
1150 _used[i] = false; |
1150 _used.at_put(i, false); |
1151 } |
1151 } |
1152 _current.truncate(0); |
1152 _current.trunc_to(0); |
1153 _successors.truncate(0); |
1153 _successors.trunc_to(0); |
1154 if (start != dont_use) { |
1154 if (start != dont_use) { |
1155 _current.push(start); |
1155 _current.push(start); |
1156 _used[start->block_id()] = true; |
1156 _used.at_put(start->block_id(), true); |
1157 } |
1157 } |
1158 |
1158 |
1159 // BlockBeginList _successors; |
1159 // BlockBeginList _successors; |
1160 while (_current.length() > 0) { |
1160 while (_current.length() > 0) { |
1161 BlockBegin *cur = _current.pop(); |
1161 BlockBegin *cur = _current.pop(); |
1178 BlockBegin *xhandler = sux->exception_handler_at(j); |
1178 BlockBegin *xhandler = sux->exception_handler_at(j); |
1179 _successors.push(xhandler); |
1179 _successors.push(xhandler); |
1180 } |
1180 } |
1181 } |
1181 } |
1182 for (int i=0; i<_successors.length(); i++) { |
1182 for (int i=0; i<_successors.length(); i++) { |
1183 BlockBegin *sux = _successors[i]; |
1183 BlockBegin *sux = _successors.at(i); |
1184 assert(sux != NULL, "Successor must not be NULL!"); |
1184 assert(sux != NULL, "Successor must not be NULL!"); |
1185 if (sux == end) { |
1185 if (sux == end) { |
1186 return true; |
1186 return true; |
1187 } |
1187 } |
1188 if (sux != dont_use && !_used[sux->block_id()]) { |
1188 if (sux != dont_use && !_used.at(sux->block_id())) { |
1189 _used[sux->block_id()] = true; |
1189 _used.at_put(sux->block_id(), true); |
1190 _current.push(sux); |
1190 _current.push(sux); |
1191 } |
1191 } |
1192 } |
1192 } |
1193 _successors.truncate(0); |
1193 _successors.trunc_to(0); |
1194 } |
1194 } |
1195 |
1195 |
1196 return false; |
1196 return false; |
1197 } |
1197 } |
1198 |
1198 |