hotspot/src/share/vm/c1/c1_RangeCheckElimination.cpp
changeset 38051 d092550d625d
parent 38031 e0b822facc03
equal deleted inserted replaced
37993:e446184da25e 38051:d092550d625d
     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
   560     }
   560     }
   561 
   561 
   562     // Clear data structures for next array
   562     // Clear data structures for next array
   563     for (int i = 0; i < indices.length(); i++) {
   563     for (int i = 0; i < indices.length(); i++) {
   564       Instruction *index_instruction = indices.at(i);
   564       Instruction *index_instruction = indices.at(i);
   565       _access_indexed_info[index_instruction->id()] = NULL;
   565       _access_indexed_info.at_put(index_instruction->id(), NULL);
   566     }
   566     }
   567     indices.clear();
   567     indices.clear();
   568   }
   568   }
   569 }
   569 }
   570 
   570 
  1003     }
  1003     }
  1004   }
  1004   }
  1005 
  1005 
  1006   // Reset stack
  1006   // Reset stack
  1007   for (int i=0; i<pushed.length(); i++) {
  1007   for (int i=0; i<pushed.length(); i++) {
  1008     _bounds[pushed[i]]->pop();
  1008     _bounds.at(pushed.at(i))->pop();
  1009   }
  1009   }
  1010 }
  1010 }
  1011 
  1011 
  1012 #ifndef PRODUCT
  1012 #ifndef PRODUCT
  1013 // Dump condition stack
  1013 // Dump condition stack
  1049   }
  1049   }
  1050 }
  1050 }
  1051 #endif
  1051 #endif
  1052 
  1052 
  1053 // Verification or the IR
  1053 // Verification or the IR
  1054 RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), false) {
  1054 RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), BlockBegin::number_of_blocks(), false) {
  1055   this->_ir = ir;
  1055   this->_ir = ir;
  1056   ir->iterate_linear_scan_order(this);
  1056   ir->iterate_linear_scan_order(this);
  1057 }
  1057 }
  1058 
  1058 
  1059 // Verify this block
  1059 // Verify this block
  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