1 /*
2 * Copyright (c) 1997, 2010, 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 *
167
168 // Node Sentinel
169 #define NodeSentinel (Node*)-1
170
171 // Unknown count frequency
172 #define COUNT_UNKNOWN (-1.0f)
173
174 //------------------------------Node-------------------------------------------
175 // Nodes define actions in the program. They create values, which have types.
176 // They are both vertices in a directed graph and program primitives. Nodes
177 // are labeled; the label is the "opcode", the primitive function in the lambda
178 // calculus sense that gives meaning to the Node. Node inputs are ordered (so
179 // that "a-b" is different from "b-a"). The inputs to a Node are the inputs to
180 // the Node's function. These inputs also define a Type equation for the Node.
181 // Solving these Type equations amounts to doing dataflow analysis.
182 // Control and data are uniformly represented in the graph. Finally, Nodes
183 // have a unique dense integer index which is used to index into side arrays
184 // whenever I have phase-specific information.
185
186 class Node {
187 // Lots of restrictions on cloning Nodes
188 Node(const Node&); // not defined; linker error to use these
189 Node &operator=(const Node &rhs);
190
191 public:
192 friend class Compile;
193 #if OPTO_DU_ITERATOR_ASSERT
194 friend class DUIterator_Common;
195 friend class DUIterator;
196 friend class DUIterator_Fast;
197 friend class DUIterator_Last;
198 #endif
199
200 // Because Nodes come and go, I define an Arena of Node structures to pull
201 // from. This should allow fast access to node creation & deletion. This
202 // field is a local cache of a value defined in some "program fragment" for
203 // which these Nodes are just a part of.
204
205 // New Operator that takes a Compile pointer, this will eventually
206 // be the "new" New operator.
1269 //
1270 class SimpleDUIterator : public StackObj {
1271 private:
1272 Node* node;
1273 DUIterator_Fast i;
1274 DUIterator_Fast imax;
1275 public:
1276 SimpleDUIterator(Node* n): node(n), i(n->fast_outs(imax)) {}
1277 bool has_next() { return i < imax; }
1278 void next() { i++; }
1279 Node* get() { return node->fast_out(i); }
1280 };
1281
1282
1283 //-----------------------------------------------------------------------------
1284 // Map dense integer indices to Nodes. Uses classic doubling-array trick.
1285 // Abstractly provides an infinite array of Node*'s, initialized to NULL.
1286 // Note that the constructor just zeros things, and since I use Arena
1287 // allocation I do not need a destructor to reclaim storage.
1288 class Node_Array : public ResourceObj {
1289 protected:
1290 Arena *_a; // Arena to allocate in
1291 uint _max;
1292 Node **_nodes;
1293 void grow( uint i ); // Grow array node to fit
1294 public:
1295 Node_Array(Arena *a) : _a(a), _max(OptoNodeListSize) {
1296 _nodes = NEW_ARENA_ARRAY( a, Node *, OptoNodeListSize );
1297 for( int i = 0; i < OptoNodeListSize; i++ ) {
1298 _nodes[i] = NULL;
1299 }
1300 }
1301
1302 Node_Array(Node_Array *na) : _a(na->_a), _max(na->_max), _nodes(na->_nodes) {}
1303 Node *operator[] ( uint i ) const // Lookup, or NULL for not mapped
1304 { return (i<_max) ? _nodes[i] : (Node*)NULL; }
1305 Node *at( uint i ) const { assert(i<_max,"oob"); return _nodes[i]; }
1306 Node **adr() { return _nodes; }
1307 // Extend the mapping: index i maps to Node *n.
1308 void map( uint i, Node *n ) { if( i>=_max ) grow(i); _nodes[i] = n; }
1309 void insert( uint i, Node *n );
1310 void remove( uint i ); // Remove, preserving order
1311 void sort( C_sort_func_t func);
1312 void reset( Arena *new_a ); // Zap mapping to empty; reclaim storage
1313 void clear(); // Set all entries to NULL, keep storage
1314 uint Size() const { return _max; }
1315 void dump() const;
1316 };
1317
1318 class Node_List : public Node_Array {
1319 uint _cnt;
1320 public:
1321 Node_List() : Node_Array(Thread::current()->resource_area()), _cnt(0) {}
1322 Node_List(Arena *a) : Node_Array(a), _cnt(0) {}
1323 bool contains(Node* n) {
1324 for (uint e = 0; e < size(); e++) {
1325 if (at(e) == n) return true;
1326 }
1327 return false;
1328 }
1329 void insert( uint i, Node *n ) { Node_Array::insert(i,n); _cnt++; }
1330 void remove( uint i ) { Node_Array::remove(i); _cnt--; }
1331 void push( Node *b ) { map(_cnt++,b); }
1332 void yank( Node *n ); // Find and remove
1333 Node *pop() { return _nodes[--_cnt]; }
1334 Node *rpop() { Node *b = _nodes[0]; _nodes[0]=_nodes[--_cnt]; return b;}
1335 void clear() { _cnt = 0; Node_Array::clear(); } // retain storage
1336 uint size() const { return _cnt; }
1337 void dump() const;
1338 };
1339
1340 //------------------------------Unique_Node_List-------------------------------
1341 class Unique_Node_List : public Node_List {
1342 VectorSet _in_worklist;
1343 uint _clock_index; // Index in list where to pop from next
1344 public:
1345 Unique_Node_List() : Node_List(), _in_worklist(Thread::current()->resource_area()), _clock_index(0) {}
1346 Unique_Node_List(Arena *a) : Node_List(a), _in_worklist(a), _clock_index(0) {}
1347
1348 void remove( Node *n );
1349 bool member( Node *n ) { return _in_worklist.test(n->_idx) != 0; }
1350 VectorSet &member_set(){ return _in_worklist; }
1351
1352 void push( Node *b ) {
1353 if( !_in_worklist.test_set(b->_idx) )
1354 Node_List::push(b);
1355 }
1356 Node *pop() {
1357 if( _clock_index >= size() ) _clock_index = 0;
1358 Node *b = at(_clock_index);
1359 map( _clock_index, Node_List::pop());
1360 if (size() != 0) _clock_index++; // Always start from 0
1361 _in_worklist >>= b->_idx;
1372 _in_worklist.Clear(); // Discards storage but grows automatically
1373 Node_List::clear();
1374 _clock_index = 0;
1375 }
1376
1377 // Used after parsing to remove useless nodes before Iterative GVN
1378 void remove_useless_nodes(VectorSet &useful);
1379
1380 #ifndef PRODUCT
1381 void print_set() const { _in_worklist.print(); }
1382 #endif
1383 };
1384
1385 // Inline definition of Compile::record_for_igvn must be deferred to this point.
1386 inline void Compile::record_for_igvn(Node* n) {
1387 _for_igvn->push(n);
1388 }
1389
1390 //------------------------------Node_Stack-------------------------------------
1391 class Node_Stack {
1392 protected:
1393 struct INode {
1394 Node *node; // Processed node
1395 uint indx; // Index of next node's child
1396 };
1397 INode *_inode_top; // tos, stack grows up
1398 INode *_inode_max; // End of _inodes == _inodes + _max
1399 INode *_inodes; // Array storage for the stack
1400 Arena *_a; // Arena to allocate in
1401 void grow();
1402 public:
1403 Node_Stack(int size) {
1404 size_t max = (size > OptoNodeListSize) ? size : OptoNodeListSize;
1405 _a = Thread::current()->resource_area();
1406 _inodes = NEW_ARENA_ARRAY( _a, INode, max );
1407 _inode_max = _inodes + max;
1408 _inode_top = _inodes - 1; // stack is empty
1409 }
1410
1411 Node_Stack(Arena *a, int size) : _a(a) {
1444 _inode_top->node = n;
1445 }
1446 void set_index(uint i) {
1447 _inode_top->indx = i;
1448 }
1449 uint size_max() const { return (uint)pointer_delta(_inode_max, _inodes, sizeof(INode)); } // Max size
1450 uint size() const { return (uint)pointer_delta((_inode_top+1), _inodes, sizeof(INode)); } // Current size
1451 bool is_nonempty() const { return (_inode_top >= _inodes); }
1452 bool is_empty() const { return (_inode_top < _inodes); }
1453 void clear() { _inode_top = _inodes - 1; } // retain storage
1454
1455 // Node_Stack is used to map nodes.
1456 Node* find(uint idx) const;
1457 };
1458
1459
1460 //-----------------------------Node_Notes--------------------------------------
1461 // Debugging or profiling annotations loosely and sparsely associated
1462 // with some nodes. See Compile::node_notes_at for the accessor.
1463 class Node_Notes VALUE_OBJ_CLASS_SPEC {
1464 JVMState* _jvms;
1465
1466 public:
1467 Node_Notes(JVMState* jvms = NULL) {
1468 _jvms = jvms;
1469 }
1470
1471 JVMState* jvms() { return _jvms; }
1472 void set_jvms(JVMState* x) { _jvms = x; }
1473
1474 // True if there is nothing here.
1475 bool is_clear() {
1476 return (_jvms == NULL);
1477 }
1478
1479 // Make there be nothing here.
1480 void clear() {
1481 _jvms = NULL;
1482 }
1483
|
1 /*
2 * Copyright (c) 1997, 2011, 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 *
167
168 // Node Sentinel
169 #define NodeSentinel (Node*)-1
170
171 // Unknown count frequency
172 #define COUNT_UNKNOWN (-1.0f)
173
174 //------------------------------Node-------------------------------------------
175 // Nodes define actions in the program. They create values, which have types.
176 // They are both vertices in a directed graph and program primitives. Nodes
177 // are labeled; the label is the "opcode", the primitive function in the lambda
178 // calculus sense that gives meaning to the Node. Node inputs are ordered (so
179 // that "a-b" is different from "b-a"). The inputs to a Node are the inputs to
180 // the Node's function. These inputs also define a Type equation for the Node.
181 // Solving these Type equations amounts to doing dataflow analysis.
182 // Control and data are uniformly represented in the graph. Finally, Nodes
183 // have a unique dense integer index which is used to index into side arrays
184 // whenever I have phase-specific information.
185
186 class Node {
187 friend class VMStructs;
188
189 // Lots of restrictions on cloning Nodes
190 Node(const Node&); // not defined; linker error to use these
191 Node &operator=(const Node &rhs);
192
193 public:
194 friend class Compile;
195 #if OPTO_DU_ITERATOR_ASSERT
196 friend class DUIterator_Common;
197 friend class DUIterator;
198 friend class DUIterator_Fast;
199 friend class DUIterator_Last;
200 #endif
201
202 // Because Nodes come and go, I define an Arena of Node structures to pull
203 // from. This should allow fast access to node creation & deletion. This
204 // field is a local cache of a value defined in some "program fragment" for
205 // which these Nodes are just a part of.
206
207 // New Operator that takes a Compile pointer, this will eventually
208 // be the "new" New operator.
1271 //
1272 class SimpleDUIterator : public StackObj {
1273 private:
1274 Node* node;
1275 DUIterator_Fast i;
1276 DUIterator_Fast imax;
1277 public:
1278 SimpleDUIterator(Node* n): node(n), i(n->fast_outs(imax)) {}
1279 bool has_next() { return i < imax; }
1280 void next() { i++; }
1281 Node* get() { return node->fast_out(i); }
1282 };
1283
1284
1285 //-----------------------------------------------------------------------------
1286 // Map dense integer indices to Nodes. Uses classic doubling-array trick.
1287 // Abstractly provides an infinite array of Node*'s, initialized to NULL.
1288 // Note that the constructor just zeros things, and since I use Arena
1289 // allocation I do not need a destructor to reclaim storage.
1290 class Node_Array : public ResourceObj {
1291 friend class VMStructs;
1292 protected:
1293 Arena *_a; // Arena to allocate in
1294 uint _max;
1295 Node **_nodes;
1296 void grow( uint i ); // Grow array node to fit
1297 public:
1298 Node_Array(Arena *a) : _a(a), _max(OptoNodeListSize) {
1299 _nodes = NEW_ARENA_ARRAY( a, Node *, OptoNodeListSize );
1300 for( int i = 0; i < OptoNodeListSize; i++ ) {
1301 _nodes[i] = NULL;
1302 }
1303 }
1304
1305 Node_Array(Node_Array *na) : _a(na->_a), _max(na->_max), _nodes(na->_nodes) {}
1306 Node *operator[] ( uint i ) const // Lookup, or NULL for not mapped
1307 { return (i<_max) ? _nodes[i] : (Node*)NULL; }
1308 Node *at( uint i ) const { assert(i<_max,"oob"); return _nodes[i]; }
1309 Node **adr() { return _nodes; }
1310 // Extend the mapping: index i maps to Node *n.
1311 void map( uint i, Node *n ) { if( i>=_max ) grow(i); _nodes[i] = n; }
1312 void insert( uint i, Node *n );
1313 void remove( uint i ); // Remove, preserving order
1314 void sort( C_sort_func_t func);
1315 void reset( Arena *new_a ); // Zap mapping to empty; reclaim storage
1316 void clear(); // Set all entries to NULL, keep storage
1317 uint Size() const { return _max; }
1318 void dump() const;
1319 };
1320
1321 class Node_List : public Node_Array {
1322 friend class VMStructs;
1323 uint _cnt;
1324 public:
1325 Node_List() : Node_Array(Thread::current()->resource_area()), _cnt(0) {}
1326 Node_List(Arena *a) : Node_Array(a), _cnt(0) {}
1327 bool contains(Node* n) {
1328 for (uint e = 0; e < size(); e++) {
1329 if (at(e) == n) return true;
1330 }
1331 return false;
1332 }
1333 void insert( uint i, Node *n ) { Node_Array::insert(i,n); _cnt++; }
1334 void remove( uint i ) { Node_Array::remove(i); _cnt--; }
1335 void push( Node *b ) { map(_cnt++,b); }
1336 void yank( Node *n ); // Find and remove
1337 Node *pop() { return _nodes[--_cnt]; }
1338 Node *rpop() { Node *b = _nodes[0]; _nodes[0]=_nodes[--_cnt]; return b;}
1339 void clear() { _cnt = 0; Node_Array::clear(); } // retain storage
1340 uint size() const { return _cnt; }
1341 void dump() const;
1342 };
1343
1344 //------------------------------Unique_Node_List-------------------------------
1345 class Unique_Node_List : public Node_List {
1346 friend class VMStructs;
1347 VectorSet _in_worklist;
1348 uint _clock_index; // Index in list where to pop from next
1349 public:
1350 Unique_Node_List() : Node_List(), _in_worklist(Thread::current()->resource_area()), _clock_index(0) {}
1351 Unique_Node_List(Arena *a) : Node_List(a), _in_worklist(a), _clock_index(0) {}
1352
1353 void remove( Node *n );
1354 bool member( Node *n ) { return _in_worklist.test(n->_idx) != 0; }
1355 VectorSet &member_set(){ return _in_worklist; }
1356
1357 void push( Node *b ) {
1358 if( !_in_worklist.test_set(b->_idx) )
1359 Node_List::push(b);
1360 }
1361 Node *pop() {
1362 if( _clock_index >= size() ) _clock_index = 0;
1363 Node *b = at(_clock_index);
1364 map( _clock_index, Node_List::pop());
1365 if (size() != 0) _clock_index++; // Always start from 0
1366 _in_worklist >>= b->_idx;
1377 _in_worklist.Clear(); // Discards storage but grows automatically
1378 Node_List::clear();
1379 _clock_index = 0;
1380 }
1381
1382 // Used after parsing to remove useless nodes before Iterative GVN
1383 void remove_useless_nodes(VectorSet &useful);
1384
1385 #ifndef PRODUCT
1386 void print_set() const { _in_worklist.print(); }
1387 #endif
1388 };
1389
1390 // Inline definition of Compile::record_for_igvn must be deferred to this point.
1391 inline void Compile::record_for_igvn(Node* n) {
1392 _for_igvn->push(n);
1393 }
1394
1395 //------------------------------Node_Stack-------------------------------------
1396 class Node_Stack {
1397 friend class VMStructs;
1398 protected:
1399 struct INode {
1400 Node *node; // Processed node
1401 uint indx; // Index of next node's child
1402 };
1403 INode *_inode_top; // tos, stack grows up
1404 INode *_inode_max; // End of _inodes == _inodes + _max
1405 INode *_inodes; // Array storage for the stack
1406 Arena *_a; // Arena to allocate in
1407 void grow();
1408 public:
1409 Node_Stack(int size) {
1410 size_t max = (size > OptoNodeListSize) ? size : OptoNodeListSize;
1411 _a = Thread::current()->resource_area();
1412 _inodes = NEW_ARENA_ARRAY( _a, INode, max );
1413 _inode_max = _inodes + max;
1414 _inode_top = _inodes - 1; // stack is empty
1415 }
1416
1417 Node_Stack(Arena *a, int size) : _a(a) {
1450 _inode_top->node = n;
1451 }
1452 void set_index(uint i) {
1453 _inode_top->indx = i;
1454 }
1455 uint size_max() const { return (uint)pointer_delta(_inode_max, _inodes, sizeof(INode)); } // Max size
1456 uint size() const { return (uint)pointer_delta((_inode_top+1), _inodes, sizeof(INode)); } // Current size
1457 bool is_nonempty() const { return (_inode_top >= _inodes); }
1458 bool is_empty() const { return (_inode_top < _inodes); }
1459 void clear() { _inode_top = _inodes - 1; } // retain storage
1460
1461 // Node_Stack is used to map nodes.
1462 Node* find(uint idx) const;
1463 };
1464
1465
1466 //-----------------------------Node_Notes--------------------------------------
1467 // Debugging or profiling annotations loosely and sparsely associated
1468 // with some nodes. See Compile::node_notes_at for the accessor.
1469 class Node_Notes VALUE_OBJ_CLASS_SPEC {
1470 friend class VMStructs;
1471 JVMState* _jvms;
1472
1473 public:
1474 Node_Notes(JVMState* jvms = NULL) {
1475 _jvms = jvms;
1476 }
1477
1478 JVMState* jvms() { return _jvms; }
1479 void set_jvms(JVMState* x) { _jvms = x; }
1480
1481 // True if there is nothing here.
1482 bool is_clear() {
1483 return (_jvms == NULL);
1484 }
1485
1486 // Make there be nothing here.
1487 void clear() {
1488 _jvms = NULL;
1489 }
1490
|