1 /*
2 * Copyright (c) 2013, 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 #include "precompiled.hpp"
26 #include "memory/allocation.inline.hpp"
27 #include "opto/addnode.hpp"
28 #include "opto/cfgnode.hpp"
29 #include "opto/machnode.hpp"
30 #include "opto/matcher.hpp"
31 #include "opto/mathexactnode.hpp"
32 #include "opto/subnode.hpp"
33
34 OverflowNode::OverflowNode(Node* in1, Node* in2) : CmpNode(in1, in2) {
35 }
36
37 template <typename OverflowOp>
38 class AddHelper {
39 public:
40 typedef typename OverflowOp::TypeClass TypeClass;
41 typedef typename TypeClass::NativeType NativeType;
42
43 static bool will_overflow(NativeType value1, NativeType value2) {
44 NativeType result = value1 + value2;
45 // Hacker's Delight 2-12 Overflow if both arguments have the opposite sign of the result
46 if ( (((value1 ^ result) & (value2 ^ result)) >= 0)) {
47 return false;
48 }
49 return true;
50 }
51
52 static bool can_overflow(const Type* type1, const Type* type2) {
53 if (type1 == TypeClass::ZERO || type2 == TypeClass::ZERO) {
54 return false;
55 }
56 return true;
57 }
58 };
59
60 template <typename OverflowOp>
61 class SubHelper {
62 public:
63 typedef typename OverflowOp::TypeClass TypeClass;
64 typedef typename TypeClass::NativeType NativeType;
65
66 static bool will_overflow(NativeType value1, NativeType value2) {
67 NativeType result = value1 - value2;
68 // hacker's delight 2-12 overflow iff the arguments have different signs and
69 // the sign of the result is different than the sign of arg1
70 if (((value1 ^ value2) & (value1 ^ result)) >= 0) {
71 return false;
72 }
73 return true;
74 }
75
76 static bool can_overflow(const Type* type1, const Type* type2) {
77 if (type2 == TypeClass::ZERO) {
78 return false;
79 }
80 return true;
81 }
82 };
83
84 template <typename OverflowOp>
85 class MulHelper {
86 public:
87 typedef typename OverflowOp::TypeClass TypeClass;
88
89 static bool can_overflow(const Type* type1, const Type* type2) {
90 if (type1 == TypeClass::ZERO || type2 == TypeClass::ZERO) {
91 return false;
92 } else if (type1 == TypeClass::ONE || type2 == TypeClass::ONE) {
93 return false;
94 }
95 return true;
96 }
97 };
98
99 bool OverflowAddINode::will_overflow(jint v1, jint v2) const {
100 return AddHelper<OverflowAddINode>::will_overflow(v1, v2);
101 }
102
103 bool OverflowSubINode::will_overflow(jint v1, jint v2) const {
104 return SubHelper<OverflowSubINode>::will_overflow(v1, v2);
105 }
106
107 bool OverflowMulINode::will_overflow(jint v1, jint v2) const {
108 jlong result = (jlong) v1 * (jlong) v2;
109 if ((jint) result == result) {
110 return false;
111 }
112 return true;
113 }
114
115 bool OverflowAddLNode::will_overflow(jlong v1, jlong v2) const {
116 return AddHelper<OverflowAddLNode>::will_overflow(v1, v2);
117 }
118
119 bool OverflowSubLNode::will_overflow(jlong v1, jlong v2) const {
120 return SubHelper<OverflowSubLNode>::will_overflow(v1, v2);
121 }
122
123 bool OverflowMulLNode::will_overflow(jlong val1, jlong val2) const {
124 jlong result = val1 * val2;
125 jlong ax = (val1 < 0 ? -val1 : val1);
126 jlong ay = (val2 < 0 ? -val2 : val2);
127
128 bool overflow = false;
129 if ((ax | ay) & CONST64(0xFFFFFFFF00000000)) {
130 // potential overflow if any bit in upper 32 bits are set
131 if ((val1 == min_jlong && val2 == -1) || (val2 == min_jlong && val1 == -1)) {
132 // -1 * Long.MIN_VALUE will overflow
133 overflow = true;
134 } else if (val2 != 0 && (result / val2 != val1)) {
135 overflow = true;
136 }
137 }
138
139 return overflow;
140 }
141
142 template <typename OverflowOp>
143 struct IdealHelper {
144 typedef typename OverflowOp::TypeClass TypeClass; // TypeInt, TypeLong
145 typedef typename TypeClass::NativeType NativeType;
146
147 static Node* Ideal(const OverflowOp* node, PhaseGVN* phase, bool can_reshape) {
148 Node* arg1 = node->in(1);
149 Node* arg2 = node->in(2);
150 const Type* type1 = phase->type(arg1);
151 const Type* type2 = phase->type(arg2);
152
153 if (type1 != Type::TOP && type1->singleton() &&
154 type2 != Type::TOP && type2->singleton()) {
155 NativeType val1 = TypeClass::as_self(type1)->get_con();
156 NativeType val2 = TypeClass::as_self(type2)->get_con();
157 if (node->will_overflow(val1, val2) == false) {
158 Node* con_result = ConINode::make(phase->C, 0);
159 return con_result;
160 }
161 return NULL;
162 }
163 return NULL;
164 }
165
166 static const Type* Value(const OverflowOp* node, PhaseTransform* phase) {
167 const Type *t1 = phase->type( node->in(1) );
168 const Type *t2 = phase->type( node->in(2) );
169 if( t1 == Type::TOP ) return Type::TOP;
170 if( t2 == Type::TOP ) return Type::TOP;
171
172 const TypeClass* i1 = TypeClass::as_self(t1);
173 const TypeClass* i2 = TypeClass::as_self(t2);
174
175 if (t1->singleton() && t2->singleton()) {
176 if (i1 == NULL || i2 == NULL) {
177 return TypeInt::CC;
178 }
179
180 NativeType val1 = i1->get_con();
181 NativeType val2 = i2->get_con();
182 if (node->will_overflow(val1, val2)) {
183 return TypeInt::CC;
184 }
185 return TypeInt::ZERO;
186 } else if (i1 != TypeClass::bottom() && i2 != TypeClass::bottom()) {
187 if (node->will_overflow(i1->_lo, i2->_lo)) {
188 return TypeInt::CC;
189 } else if (node->will_overflow(i1->_lo, i2->_hi)) {
190 return TypeInt::CC;
191 } else if (node->will_overflow(i1->_hi, i2->_lo)) {
192 return TypeInt::CC;
193 } else if (node->will_overflow(i1->_hi, i2->_hi)) {
194 return TypeInt::CC;
195 }
196 return TypeInt::ZERO;
197 }
198
199 if (!node->can_overflow(t1, t2)) {
200 return TypeInt::ZERO;
201 }
202 return TypeInt::CC;
203 }
204 };
205
206 Node* OverflowINode::Ideal(PhaseGVN* phase, bool can_reshape) {
207 return IdealHelper<OverflowINode>::Ideal(this, phase, can_reshape);
208 }
209
210 Node* OverflowLNode::Ideal(PhaseGVN* phase, bool can_reshape) {
211 return IdealHelper<OverflowLNode>::Ideal(this, phase, can_reshape);
212 }
213
214 const Type* OverflowINode::Value(PhaseTransform* phase) const {
215 return IdealHelper<OverflowINode>::Value(this, phase);
216 }
217
218 const Type* OverflowLNode::Value(PhaseTransform* phase) const {
219 return IdealHelper<OverflowLNode>::Value(this, phase);
220 }
221
222 bool OverflowAddINode::can_overflow(const Type* t1, const Type* t2) const {
223 return AddHelper<OverflowAddINode>::can_overflow(t1, t2);
224 }
225
226 bool OverflowSubINode::can_overflow(const Type* t1, const Type* t2) const {
227 if (in(1) == in(2)) {
228 return false;
229 }
230 return SubHelper<OverflowSubINode>::can_overflow(t1, t2);
231 }
232
233 bool OverflowMulINode::can_overflow(const Type* t1, const Type* t2) const {
234 return MulHelper<OverflowMulINode>::can_overflow(t1, t2);
235 }
236
237 bool OverflowAddLNode::can_overflow(const Type* t1, const Type* t2) const {
238 return AddHelper<OverflowAddLNode>::can_overflow(t1, t2);
239 }
240
241 bool OverflowSubLNode::can_overflow(const Type* t1, const Type* t2) const {
242 return SubHelper<OverflowSubLNode>::can_overflow(t1, t2);
243 }
244
245 bool OverflowMulLNode::can_overflow(const Type* t1, const Type* t2) const {
246 return MulHelper<OverflowMulLNode>::can_overflow(t1, t2);
247 }
248
249 const Type* OverflowNode::sub(const Type* t1, const Type* t2) const {
250 ShouldNotReachHere();
251 return TypeInt::CC;
252 }