16611
|
1 |
/*
|
|
2 |
* Copyright (c) 2012, 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 |
*
|
|
23 |
*/
|
|
24 |
|
|
25 |
#ifndef SHARE_VM_C1_C1_RANGECHECKELIMINATION_HPP
|
|
26 |
#define SHARE_VM_C1_C1_RANGECHECKELIMINATION_HPP
|
|
27 |
|
|
28 |
#include "c1/c1_Instruction.hpp"
|
|
29 |
|
|
30 |
// Base class for range check elimination
|
|
31 |
class RangeCheckElimination : AllStatic {
|
|
32 |
public:
|
|
33 |
static void eliminate(IR *ir);
|
|
34 |
};
|
|
35 |
|
|
36 |
// Implementation
|
|
37 |
class RangeCheckEliminator VALUE_OBJ_CLASS_SPEC {
|
|
38 |
private:
|
|
39 |
int _number_of_instructions;
|
|
40 |
bool _optimistic; // Insert predicates and deoptimize when they fail
|
|
41 |
IR *_ir;
|
|
42 |
|
|
43 |
define_array(BlockBeginArray, BlockBegin*)
|
|
44 |
define_stack(BlockBeginList, BlockBeginArray)
|
|
45 |
define_stack(IntegerStack, intArray)
|
|
46 |
define_array(IntegerMap, IntegerStack*)
|
|
47 |
|
|
48 |
class Verification : public _ValueObj /*VALUE_OBJ_CLASS_SPEC*/, public BlockClosure {
|
|
49 |
private:
|
|
50 |
IR *_ir;
|
|
51 |
boolArray _used;
|
|
52 |
BlockBeginList _current;
|
|
53 |
BlockBeginList _successors;
|
|
54 |
|
|
55 |
public:
|
|
56 |
Verification(IR *ir);
|
|
57 |
virtual void block_do(BlockBegin *block);
|
|
58 |
bool can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use = NULL);
|
|
59 |
bool dominates(BlockBegin *dominator, BlockBegin *block);
|
|
60 |
};
|
|
61 |
|
|
62 |
public:
|
|
63 |
// Bounds for an instruction in the form x + c which c integer
|
|
64 |
// constant and x another instruction
|
|
65 |
class Bound : public CompilationResourceObj {
|
|
66 |
private:
|
|
67 |
int _upper;
|
|
68 |
Value _upper_instr;
|
|
69 |
int _lower;
|
|
70 |
Value _lower_instr;
|
|
71 |
|
|
72 |
public:
|
|
73 |
Bound();
|
|
74 |
Bound(Value v);
|
|
75 |
Bound(Instruction::Condition cond, Value v, int constant = 0);
|
|
76 |
Bound(int lower, Value lower_instr, int upper, Value upper_instr);
|
|
77 |
~Bound();
|
|
78 |
|
|
79 |
#ifdef ASSERT
|
|
80 |
void add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond);
|
|
81 |
#endif
|
|
82 |
int upper();
|
|
83 |
Value upper_instr();
|
|
84 |
int lower();
|
|
85 |
Value lower_instr();
|
|
86 |
void print();
|
|
87 |
bool check_no_overflow(int const_value);
|
|
88 |
void or_op(Bound *b);
|
|
89 |
void and_op(Bound *b);
|
|
90 |
bool has_upper();
|
|
91 |
bool has_lower();
|
|
92 |
void set_upper(int upper, Value upper_instr);
|
|
93 |
void set_lower(int lower, Value lower_instr);
|
|
94 |
bool is_smaller(Bound *b);
|
|
95 |
void remove_upper();
|
|
96 |
void remove_lower();
|
|
97 |
void add_constant(int value);
|
|
98 |
Bound *copy();
|
|
99 |
|
|
100 |
private:
|
|
101 |
void init();
|
|
102 |
};
|
|
103 |
|
|
104 |
|
|
105 |
class Visitor : public InstructionVisitor {
|
|
106 |
private:
|
|
107 |
Bound *_bound;
|
|
108 |
RangeCheckEliminator *_rce;
|
|
109 |
|
|
110 |
public:
|
|
111 |
void set_range_check_eliminator(RangeCheckEliminator *rce) { _rce = rce; }
|
|
112 |
Bound *bound() const { return _bound; }
|
|
113 |
void clear_bound() { _bound = NULL; }
|
|
114 |
|
|
115 |
protected:
|
|
116 |
// visitor functions
|
|
117 |
void do_Constant (Constant* x);
|
|
118 |
void do_IfOp (IfOp* x);
|
|
119 |
void do_LogicOp (LogicOp* x);
|
|
120 |
void do_ArithmeticOp (ArithmeticOp* x);
|
|
121 |
void do_Phi (Phi* x);
|
|
122 |
|
|
123 |
void do_StoreField (StoreField* x) { /* nothing to do */ };
|
|
124 |
void do_StoreIndexed (StoreIndexed* x) { /* nothing to do */ };
|
|
125 |
void do_MonitorEnter (MonitorEnter* x) { /* nothing to do */ };
|
|
126 |
void do_MonitorExit (MonitorExit* x) { /* nothing to do */ };
|
|
127 |
void do_Invoke (Invoke* x) { /* nothing to do */ };
|
|
128 |
void do_UnsafePutRaw (UnsafePutRaw* x) { /* nothing to do */ };
|
|
129 |
void do_UnsafePutObject(UnsafePutObject* x) { /* nothing to do */ };
|
|
130 |
void do_Intrinsic (Intrinsic* x) { /* nothing to do */ };
|
|
131 |
void do_Local (Local* x) { /* nothing to do */ };
|
|
132 |
void do_LoadField (LoadField* x) { /* nothing to do */ };
|
|
133 |
void do_ArrayLength (ArrayLength* x) { /* nothing to do */ };
|
|
134 |
void do_LoadIndexed (LoadIndexed* x) { /* nothing to do */ };
|
|
135 |
void do_NegateOp (NegateOp* x) { /* nothing to do */ };
|
|
136 |
void do_ShiftOp (ShiftOp* x) { /* nothing to do */ };
|
|
137 |
void do_CompareOp (CompareOp* x) { /* nothing to do */ };
|
|
138 |
void do_Convert (Convert* x) { /* nothing to do */ };
|
|
139 |
void do_NullCheck (NullCheck* x) { /* nothing to do */ };
|
|
140 |
void do_TypeCast (TypeCast* x) { /* nothing to do */ };
|
|
141 |
void do_NewInstance (NewInstance* x) { /* nothing to do */ };
|
|
142 |
void do_NewTypeArray (NewTypeArray* x) { /* nothing to do */ };
|
|
143 |
void do_NewObjectArray (NewObjectArray* x) { /* nothing to do */ };
|
|
144 |
void do_NewMultiArray (NewMultiArray* x) { /* nothing to do */ };
|
|
145 |
void do_CheckCast (CheckCast* x) { /* nothing to do */ };
|
|
146 |
void do_InstanceOf (InstanceOf* x) { /* nothing to do */ };
|
|
147 |
void do_BlockBegin (BlockBegin* x) { /* nothing to do */ };
|
|
148 |
void do_Goto (Goto* x) { /* nothing to do */ };
|
|
149 |
void do_If (If* x) { /* nothing to do */ };
|
|
150 |
void do_IfInstanceOf (IfInstanceOf* x) { /* nothing to do */ };
|
|
151 |
void do_TableSwitch (TableSwitch* x) { /* nothing to do */ };
|
|
152 |
void do_LookupSwitch (LookupSwitch* x) { /* nothing to do */ };
|
|
153 |
void do_Return (Return* x) { /* nothing to do */ };
|
|
154 |
void do_Throw (Throw* x) { /* nothing to do */ };
|
|
155 |
void do_Base (Base* x) { /* nothing to do */ };
|
|
156 |
void do_OsrEntry (OsrEntry* x) { /* nothing to do */ };
|
|
157 |
void do_ExceptionObject(ExceptionObject* x) { /* nothing to do */ };
|
|
158 |
void do_RoundFP (RoundFP* x) { /* nothing to do */ };
|
|
159 |
void do_UnsafeGetRaw (UnsafeGetRaw* x) { /* nothing to do */ };
|
|
160 |
void do_UnsafeGetObject(UnsafeGetObject* x) { /* nothing to do */ };
|
|
161 |
void do_UnsafeGetAndSetObject(UnsafeGetAndSetObject* x) { /* nothing to do */ };
|
|
162 |
void do_UnsafePrefetchRead (UnsafePrefetchRead* x) { /* nothing to do */ };
|
|
163 |
void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x) { /* nothing to do */ };
|
|
164 |
void do_ProfileCall (ProfileCall* x) { /* nothing to do */ };
|
|
165 |
void do_ProfileInvoke (ProfileInvoke* x) { /* nothing to do */ };
|
|
166 |
void do_RuntimeCall (RuntimeCall* x) { /* nothing to do */ };
|
|
167 |
void do_MemBar (MemBar* x) { /* nothing to do */ };
|
|
168 |
void do_RangeCheckPredicate(RangeCheckPredicate* x) { /* nothing to do */ };
|
|
169 |
void do_Assert (Assert* x) { /* nothing to do */ };
|
|
170 |
};
|
|
171 |
|
|
172 |
#ifdef ASSERT
|
|
173 |
void add_assertions(Bound *bound, Instruction *instruction, Instruction *position);
|
|
174 |
#endif
|
|
175 |
|
|
176 |
define_array(BoundArray, Bound *)
|
|
177 |
define_stack(BoundStack, BoundArray)
|
|
178 |
define_array(BoundMap, BoundStack *)
|
|
179 |
define_array(AccessIndexedArray, AccessIndexed *)
|
|
180 |
define_stack(AccessIndexedList, AccessIndexedArray)
|
|
181 |
define_array(InstructionArray, Instruction *)
|
|
182 |
define_stack(InstructionList, InstructionArray)
|
|
183 |
|
|
184 |
class AccessIndexedInfo : public CompilationResourceObj {
|
|
185 |
public:
|
|
186 |
AccessIndexedList *_list;
|
|
187 |
int _min;
|
|
188 |
int _max;
|
|
189 |
};
|
|
190 |
|
|
191 |
define_array(AccessIndexedInfoArray, AccessIndexedInfo *)
|
|
192 |
BoundMap _bounds; // Mapping from Instruction's id to current bound
|
|
193 |
AccessIndexedInfoArray _access_indexed_info; // Mapping from Instruction's id to AccessIndexedInfo for in block motion
|
|
194 |
Visitor _visitor;
|
|
195 |
|
|
196 |
public:
|
|
197 |
RangeCheckEliminator(IR *ir);
|
|
198 |
|
|
199 |
IR *ir() const { return _ir; }
|
|
200 |
|
|
201 |
// Pass over the dominator tree to identify blocks where there's an oppportunity for optimization
|
|
202 |
bool set_process_block_flags(BlockBegin *block);
|
|
203 |
// The core of the optimization work: pass over the dominator tree
|
|
204 |
// to propagate bound information, insert predicate out of loops,
|
|
205 |
// eliminate bound checks when possible and perform in block motion
|
|
206 |
void calc_bounds(BlockBegin *block, BlockBegin *loop_header);
|
|
207 |
// reorder bound checks within a block in order to eliminate some of them
|
|
208 |
void in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays);
|
|
209 |
|
|
210 |
// update/access current bound
|
|
211 |
void update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant);
|
|
212 |
void update_bound(IntegerStack &pushed, Value v, Bound *bound);
|
|
213 |
Bound *get_bound(Value v);
|
|
214 |
|
|
215 |
bool loop_invariant(BlockBegin *loop_header, Instruction *instruction); // check for loop invariance
|
|
216 |
void add_access_indexed_info(InstructionList &indices, int i, Value instruction, AccessIndexed *ai); // record indexed access for in block motion
|
|
217 |
void remove_range_check(AccessIndexed *ai); // Mark this instructions as not needing a range check
|
|
218 |
void add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition); // Update bound for an If
|
|
219 |
bool in_array_bound(Bound *bound, Value array); // Check whether bound is known to fall within array
|
|
220 |
|
|
221 |
// helper functions to work with predicates
|
|
222 |
Instruction* insert_after(Instruction* insert_position, Instruction* instr, int bci);
|
|
223 |
Instruction* predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci=-1);
|
|
224 |
Instruction* predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci=1);
|
|
225 |
Instruction* predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci=-1);
|
|
226 |
Instruction* predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci=-1);
|
|
227 |
|
|
228 |
void insert_deoptimization(ValueStack *state, Instruction *insert_position, Instruction *array_instr, // Add predicate
|
|
229 |
Instruction *length_instruction, Instruction *lower_instr, int lower,
|
|
230 |
Instruction *upper_instr, int upper, AccessIndexed *ai);
|
|
231 |
bool is_ok_for_deoptimization(Instruction *insert_position, Instruction *array_instr, // Can we safely add a predicate?
|
|
232 |
Instruction *length_instr, Instruction *lower_instr,
|
|
233 |
int lower, Instruction *upper_instr, int upper);
|
|
234 |
void process_if(IntegerStack &pushed, BlockBegin *block, If *cond); // process If Instruction
|
|
235 |
void process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai); // process indexed access
|
|
236 |
|
|
237 |
void dump_condition_stack(BlockBegin *cur_block);
|
|
238 |
static void print_statistics();
|
|
239 |
};
|
|
240 |
|
|
241 |
#endif // SHARE_VM_C1_C1_RANGECHECKELIMINATION_HPP
|