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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
24
25 // Portions of code courtesy of Clifford Click
26
27 // Optimization - Graph Style
28
29 #include "incls/_precompiled.incl"
30 #include "incls/_gcm.cpp.incl"
31
32 //----------------------------schedule_node_into_block-------------------------
33 // Insert node n into block b. Look for projections of n and make sure they
34 // are in b also.
35 void PhaseCFG::schedule_node_into_block( Node *n, Block *b ) {
36 // Set basic block of n, Add n to b,
37 _bbs.map(n->_idx, b);
38 b->add_inst(n);
39
40 // After Matching, nearly any old Node may have projections trailing it.
41 // These are usually machine-dependent flags. In any case, they might
42 // float to another block below this one. Move them up.
43 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
44 Node* use = n->fast_out(i);
45 if (use->is_Proj()) {
46 Block* buse = _bbs[use->_idx];
47 if (buse != b) { // In wrong block?
48 if (buse != NULL)
49 buse->find_remove(use); // Remove from wrong block
50 _bbs.map(use->_idx, b); // Re-insert in this block
51 b->add_inst(use);
1363 Block_List worklist;
1364 Block* root_blk = _blocks[0];
1365 for (uint i = 1; i < root_blk->num_preds(); i++) {
1366 Block *pb = _bbs[root_blk->pred(i)->_idx];
1367 if (pb->has_uncommon_code()) {
1368 worklist.push(pb);
1369 }
1370 }
1371 while (worklist.size() > 0) {
1372 Block* uct = worklist.pop();
1373 uct->_freq = PROB_MIN;
1374 for (uint i = 1; i < uct->num_preds(); i++) {
1375 Block *pb = _bbs[uct->pred(i)->_idx];
1376 if (pb->_num_succs == 1 && pb->_freq > PROB_MIN) {
1377 worklist.push(pb);
1378 }
1379 }
1380 }
1381 }
1382
1383 #ifndef PRODUCT
1384 if (PrintCFGBlockFreq) {
1385 tty->print_cr("CFG Block Frequencies");
1386 _root_loop->dump_tree();
1387 if (Verbose) {
1388 tty->print_cr("PhaseCFG dump");
1389 dump();
1390 tty->print_cr("Node dump");
1391 _root->dump(99999);
1392 }
1393 }
1394 #endif
1395 }
1396
1397 //----------------------------create_loop_tree--------------------------------
1398 // Create a loop tree from the CFG
1399 CFGLoop* PhaseCFG::create_loop_tree() {
1400
1401 #ifdef ASSERT
1402 assert( _blocks[0] == _broot, "" );
1860 int depth = _depth;
1861 CFGLoop* b_loop = b->_loop;
1862 int b_depth = b_loop->_depth;
1863 if (depth == b_depth) {
1864 return true;
1865 }
1866 while (b_depth > depth) {
1867 b_loop = b_loop->_parent;
1868 b_depth = b_loop->_depth;
1869 }
1870 return b_loop == this;
1871 }
1872
1873 //------------------------------scale_freq-------------------------------------
1874 // Scale frequency of loops and blocks by trip counts from outer loops
1875 // Do a top down traversal of loop tree (visit outer loops first.)
1876 void CFGLoop::scale_freq() {
1877 float loop_freq = _freq * trip_count();
1878 for (int i = 0; i < _members.length(); i++) {
1879 CFGElement* s = _members.at(i);
1880 s->_freq *= loop_freq;
1881 }
1882 CFGLoop* ch = _child;
1883 while (ch != NULL) {
1884 ch->scale_freq();
1885 ch = ch->_sibling;
1886 }
1887 }
1888
1889 #ifndef PRODUCT
1890 //------------------------------dump_tree--------------------------------------
1891 void CFGLoop::dump_tree() const {
1892 dump();
1893 if (_child != NULL) _child->dump_tree();
1894 if (_sibling != NULL) _sibling->dump_tree();
1895 }
1896
1897 //------------------------------dump-------------------------------------------
1898 void CFGLoop::dump() const {
1899 for (int i = 0; i < _depth; i++) tty->print(" ");
1900 tty->print("%s: %d trip_count: %6.0f freq: %6.0f\n",
|
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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
24
25 // Portions of code courtesy of Clifford Click
26
27 // Optimization - Graph Style
28
29 #include "incls/_precompiled.incl"
30 #include "incls/_gcm.cpp.incl"
31
32 // To avoid float value underflow
33 #define MIN_BLOCK_FREQUENCY 1.e-35f
34
35 //----------------------------schedule_node_into_block-------------------------
36 // Insert node n into block b. Look for projections of n and make sure they
37 // are in b also.
38 void PhaseCFG::schedule_node_into_block( Node *n, Block *b ) {
39 // Set basic block of n, Add n to b,
40 _bbs.map(n->_idx, b);
41 b->add_inst(n);
42
43 // After Matching, nearly any old Node may have projections trailing it.
44 // These are usually machine-dependent flags. In any case, they might
45 // float to another block below this one. Move them up.
46 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
47 Node* use = n->fast_out(i);
48 if (use->is_Proj()) {
49 Block* buse = _bbs[use->_idx];
50 if (buse != b) { // In wrong block?
51 if (buse != NULL)
52 buse->find_remove(use); // Remove from wrong block
53 _bbs.map(use->_idx, b); // Re-insert in this block
54 b->add_inst(use);
1366 Block_List worklist;
1367 Block* root_blk = _blocks[0];
1368 for (uint i = 1; i < root_blk->num_preds(); i++) {
1369 Block *pb = _bbs[root_blk->pred(i)->_idx];
1370 if (pb->has_uncommon_code()) {
1371 worklist.push(pb);
1372 }
1373 }
1374 while (worklist.size() > 0) {
1375 Block* uct = worklist.pop();
1376 uct->_freq = PROB_MIN;
1377 for (uint i = 1; i < uct->num_preds(); i++) {
1378 Block *pb = _bbs[uct->pred(i)->_idx];
1379 if (pb->_num_succs == 1 && pb->_freq > PROB_MIN) {
1380 worklist.push(pb);
1381 }
1382 }
1383 }
1384 }
1385
1386 #ifdef ASSERT
1387 for (uint i = 0; i < _num_blocks; i++ ) {
1388 Block *b = _blocks[i];
1389 assert(b->_freq >= MIN_BLOCK_FREQUENCY, "Register Allocator requiers meaningful block frequency");
1390 }
1391 #endif
1392
1393 #ifndef PRODUCT
1394 if (PrintCFGBlockFreq) {
1395 tty->print_cr("CFG Block Frequencies");
1396 _root_loop->dump_tree();
1397 if (Verbose) {
1398 tty->print_cr("PhaseCFG dump");
1399 dump();
1400 tty->print_cr("Node dump");
1401 _root->dump(99999);
1402 }
1403 }
1404 #endif
1405 }
1406
1407 //----------------------------create_loop_tree--------------------------------
1408 // Create a loop tree from the CFG
1409 CFGLoop* PhaseCFG::create_loop_tree() {
1410
1411 #ifdef ASSERT
1412 assert( _blocks[0] == _broot, "" );
1870 int depth = _depth;
1871 CFGLoop* b_loop = b->_loop;
1872 int b_depth = b_loop->_depth;
1873 if (depth == b_depth) {
1874 return true;
1875 }
1876 while (b_depth > depth) {
1877 b_loop = b_loop->_parent;
1878 b_depth = b_loop->_depth;
1879 }
1880 return b_loop == this;
1881 }
1882
1883 //------------------------------scale_freq-------------------------------------
1884 // Scale frequency of loops and blocks by trip counts from outer loops
1885 // Do a top down traversal of loop tree (visit outer loops first.)
1886 void CFGLoop::scale_freq() {
1887 float loop_freq = _freq * trip_count();
1888 for (int i = 0; i < _members.length(); i++) {
1889 CFGElement* s = _members.at(i);
1890 float block_freq = s->_freq * loop_freq;
1891 if (block_freq < MIN_BLOCK_FREQUENCY) block_freq = MIN_BLOCK_FREQUENCY;
1892 s->_freq = block_freq;
1893 }
1894 CFGLoop* ch = _child;
1895 while (ch != NULL) {
1896 ch->scale_freq();
1897 ch = ch->_sibling;
1898 }
1899 }
1900
1901 #ifndef PRODUCT
1902 //------------------------------dump_tree--------------------------------------
1903 void CFGLoop::dump_tree() const {
1904 dump();
1905 if (_child != NULL) _child->dump_tree();
1906 if (_sibling != NULL) _sibling->dump_tree();
1907 }
1908
1909 //------------------------------dump-------------------------------------------
1910 void CFGLoop::dump() const {
1911 for (int i = 0; i < _depth; i++) tty->print(" ");
1912 tty->print("%s: %d trip_count: %6.0f freq: %6.0f\n",
|