graal-compiler: graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java annotate

annotate graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2788:df4c5254c5cc

Towards goto removal.

author	Thomas Wuerthinger <thomas@wuerthinger.net>
date	Wed, 25 May 2011 14:33:44 +0200
parents	2ac7b30b7290
children	775c31be565c

rev	line source
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	1 /*
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	4 *
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	5 * This code is free software; you can redistribute it and/or modify it
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	6 * under the terms of the GNU General Public License version 2 only, as
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	7 * published by the Free Software Foundation.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	8 *
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	9 * This code is distributed in the hope that it will be useful, but WITHOUT
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	12 * version 2 for more details (a copy is included in the LICENSE file that
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	13 * accompanied this code).
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	14 *
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	15 * You should have received a copy of the GNU General Public License version
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	16 * 2 along with this work; if not, write to the Free Software Foundation,
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	18 *
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	20 * or visit www.oracle.com if you need additional information or have any
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	21 * questions.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	22 */
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	23
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	24 package com.sun.c1x.ir;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	25
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	26 import java.util.*;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	27
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	28 import com.sun.c1x.*;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	29 import com.sun.c1x.debug.*;
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	30 import com.sun.c1x.lir.*;
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	31 import com.sun.c1x.util.*;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	32 import com.sun.cri.ci.*;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	33
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	34 public final class ComputeLinearScanOrder {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	35
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	36 private final int maxBlockId; // the highest blockId of a block
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	37 private int numBlocks; // total number of blocks (smaller than maxBlockId)
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	38 private int numLoops; // total number of loops
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	39 private boolean iterativeDominators; // method requires iterative computation of dominators
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	40
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	41 List<LIRBlock> linearScanOrder; // the resulting list of blocks in correct order
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	42
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	43 final CiBitMap visitedBlocks; // used for recursive processing of blocks
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	44 final CiBitMap activeBlocks; // used for recursive processing of blocks
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	45 final CiBitMap dominatorBlocks; // temporary BitMap used for computation of dominator
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	46 final int[] forwardBranches; // number of incoming forward branches for each block
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	47 final List<LIRBlock> loopEndBlocks; // list of all loop end blocks collected during countEdges
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	48 BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	49 final List<LIRBlock> workList; // temporary list (used in markLoops and computeOrder)
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	50
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	51 // accessors for visitedBlocks and activeBlocks
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	52 void initVisited() {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	53 activeBlocks.clearAll();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	54 visitedBlocks.clearAll();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	55 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	56
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	57 boolean isVisited(LIRBlock b) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	58 return visitedBlocks.get(b.blockID());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	59 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	60
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	61 boolean isActive(LIRBlock b) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	62 return activeBlocks.get(b.blockID());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	63 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	64
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	65 void setVisited(LIRBlock b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	66 assert !isVisited(b) : "already set";
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	67 visitedBlocks.set(b.blockID());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	68 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	69
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	70 void setActive(LIRBlock b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	71 assert !isActive(b) : "already set";
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	72 activeBlocks.set(b.blockID());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	73 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	74
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	75 void clearActive(LIRBlock b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	76 assert isActive(b) : "not already";
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	77 activeBlocks.clear(b.blockID());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	78 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	79
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	80 // accessors for forwardBranches
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	81 void incForwardBranches(LIRBlock b) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	82 forwardBranches[b.blockID()]++;
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	83 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	84
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	85 int decForwardBranches(LIRBlock b) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	86 return --forwardBranches[b.blockID()];
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	87 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	88
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	89 // accessors for loopMap
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	90 boolean isBlockInLoop(int loopIdx, LIRBlock b) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	91 return loopMap.at(loopIdx, b.blockID());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	92 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	93
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	94 void setBlockInLoop(int loopIdx, LIRBlock b) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	95 loopMap.setBit(loopIdx, b.blockID());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	96 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	97
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	98 void clearBlockInLoop(int loopIdx, int blockId) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	99 loopMap.clearBit(loopIdx, blockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	100 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	101
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	102 // accessors for final result
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	103 public List<LIRBlock> linearScanOrder() {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	104 return linearScanOrder;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	105 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	106
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	107 public int numLoops() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	108 return numLoops;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	109 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	110
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	111 public ComputeLinearScanOrder(int maxBlockId, LIRBlock startBlock) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	112
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	113 this.maxBlockId = maxBlockId;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	114 visitedBlocks = new CiBitMap(maxBlockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	115 activeBlocks = new CiBitMap(maxBlockId);
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	116 dominatorBlocks = new CiBitMap(maxBlockId);
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	117 forwardBranches = new int[maxBlockId];
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	118 loopEndBlocks = new ArrayList<LIRBlock>(8);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	119 workList = new ArrayList<LIRBlock>(8);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	120
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	121 splitCriticalEdges();
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	122
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	123 countEdges(startBlock, null);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	124
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	125 if (numLoops > 0) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	126 markLoops();
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	127 clearNonNaturalLoops(startBlock);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	128 assignLoopDepth(startBlock);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	129 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	130
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	131 computeOrder(startBlock);
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	132
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	133 printBlocks();
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	134 assert verify();
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	135 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	136
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	137 void splitCriticalEdges() {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	138 // TODO: move critical edge splitting from IR to here
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	139 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	140
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	141 /**
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	142 * Traverses the CFG to analyze block and edge info. The analysis performed is:
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	143 *
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	144 * 1. Count of total number of blocks.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	145 * 2. Count of all incoming edges and backward incoming edges.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	146 * 3. Number loop header blocks.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	147 * 4. Create a list with all loop end blocks.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	148 */
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	149 void countEdges(LIRBlock cur, LIRBlock parent) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	150 if (C1XOptions.TraceLinearScanLevel >= 3) {
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	151 TTY.println("Counting edges for block B%d%s", cur.blockID(), parent == null ? "" : " coming from B" + parent.blockID());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	152 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	153
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	154 if (isActive(cur)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	155 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	156 TTY.println("backward branch");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	157 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	158 assert isVisited(cur) : "block must be visited when block is active";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	159 assert parent != null : "must have parent";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	160
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	161 cur.setLinearScanLoopHeader();
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	162 cur.setBackwardBranchTarget(true);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	163 parent.setLinearScanLoopEnd();
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	164
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	165 // When a loop header is also the start of an exception handler, then the backward branch is
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	166 // an exception edge. Because such edges are usually critical edges which cannot be split, the
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	167 // loop must be excluded here from processing.
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	168 if (cur.isExceptionEntry()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	169 // Make sure that dominators are correct in this weird situation
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	170 iterativeDominators = true;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	171 return;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	172 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	173 // assert parent.numberOfSux() == 1 && parent.suxAt(0) == cur : "loop end blocks must have one successor (critical edges are split)";
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	174
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	175 loopEndBlocks.add(parent);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	176 return;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	177 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	178
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	179 // increment number of incoming forward branches
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	180 incForwardBranches(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	181
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	182 if (isVisited(cur)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	183 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	184 TTY.println("block already visited");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	185 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	186 return;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	187 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	188
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	189 numBlocks++;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	190 setVisited(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	191 setActive(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	192
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	193 // recursive call for all successors
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	194 int i;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	195 for (i = cur.numberOfSux() - 1; i >= 0; i--) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	196 countEdges(cur.suxAt(i), cur);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	197 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	198 for (LIRBlock ex : cur.getExceptionHandlerSuccessors()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	199 countEdges(ex, cur);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	200 }
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	201
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	202 clearActive(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	203
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	204 // Each loop has a unique number.
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	205 // When multiple loops are nested, assignLoopDepth assumes that the
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	206 // innermost loop has the lowest number. This is guaranteed by setting
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	207 // the loop number after the recursive calls for the successors above
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	208 // have returned.
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	209 if (cur.isLinearScanLoopHeader()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	210 assert cur.loopIndex() == -1 : "cannot set loop-index twice";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	211 if (C1XOptions.TraceLinearScanLevel >= 3) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	212 TTY.println("Block B%d is loop header of loop %d", cur.blockID(), numLoops);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	213 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	214
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	215 cur.setLoopIndex(numLoops);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	216 numLoops++;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	217 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	218
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	219 if (C1XOptions.TraceLinearScanLevel >= 3) {
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	220 TTY.println("Finished counting edges for block B%d", cur.blockID());
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	221 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	222 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	223
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	224 void markLoops() {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	225 if (C1XOptions.TraceLinearScanLevel >= 3) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	226 TTY.println("----- marking loops");
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	227 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	228
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	229 loopMap = new BitMap2D(numLoops, maxBlockId);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	230
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	231 for (int i = loopEndBlocks.size() - 1; i >= 0; i--) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	232 LIRBlock loopEnd = loopEndBlocks.get(i);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	233 LIRBlock loopStart = loopEnd.suxAt(0);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	234 int loopIdx = loopStart.loopIndex();
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	235
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	236 if (C1XOptions.TraceLinearScanLevel >= 3) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	237 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID(), loopEnd.blockID(), loopIdx);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	238 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	239 assert loopEnd.isLinearScanLoopEnd() : "loop end flag must be set";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	240 // assert loopEnd.numberOfSux() == 1 : "incorrect number of successors";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	241 assert loopStart.isLinearScanLoopHeader() : "loop header flag must be set";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	242 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	243 assert workList.isEmpty() : "work list must be empty before processing";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	244
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	245 // add the end-block of the loop to the working list
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	246 workList.add(loopEnd);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	247 setBlockInLoop(loopIdx, loopEnd);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	248 do {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	249 LIRBlock cur = workList.remove(workList.size() - 1);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	250
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	251 if (C1XOptions.TraceLinearScanLevel >= 3) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	252 TTY.println(" processing B%d", cur.blockID());
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	253 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	254 assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	255
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	256 // recursive processing of all predecessors ends when start block of loop is reached
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	257 if (cur != loopStart) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	258 for (int j = cur.numberOfPreds() - 1; j >= 0; j--) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	259 LIRBlock pred = cur.predAt(j);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	260
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	261 if (!isBlockInLoop(loopIdx, pred)) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	262 // this predecessor has not been processed yet, so add it to work list
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	263 if (C1XOptions.TraceLinearScanLevel >= 3) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	264 TTY.println(" pushing B%d", pred.blockID());
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	265 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	266 workList.add(pred);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	267 setBlockInLoop(loopIdx, pred);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	268 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	269 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	270 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	271 } while (!workList.isEmpty());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	272 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	273 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	274
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	275 // check for non-natural loops (loops where the loop header does not dominate
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	276 // all other loop blocks = loops with multiple entries).
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	277 // such loops are ignored
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	278 void clearNonNaturalLoops(LIRBlock startBlock) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	279 for (int i = numLoops - 1; i >= 0; i--) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	280 if (isBlockInLoop(i, startBlock)) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	281 // loop i contains the entry block of the method.
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	282 // this is not a natural loop, so ignore it
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	283 if (C1XOptions.TraceLinearScanLevel >= 2) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	284 TTY.println("Loop %d is non-natural, so it is ignored", i);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	285 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	286
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	287 for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	288 clearBlockInLoop(i, blockId);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	289 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	290 iterativeDominators = true;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	291 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	292 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	293 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	294
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	295 void assignLoopDepth(LIRBlock startBlock) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	296 if (C1XOptions.TraceLinearScanLevel >= 3) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	297 TTY.println("----- computing loop-depth and weight");
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	298 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	299 initVisited();
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	300
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	301 assert workList.isEmpty() : "work list must be empty before processing";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	302 workList.add(startBlock);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	303
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	304 do {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	305 LIRBlock cur = workList.remove(workList.size() - 1);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	306
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	307 if (!isVisited(cur)) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	308 setVisited(cur);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	309 if (C1XOptions.TraceLinearScanLevel >= 4) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	310 TTY.println("Computing loop depth for block B%d", cur.blockID());
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	311 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	312
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	313 // compute loop-depth and loop-index for the block
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	314 assert cur.loopDepth() == 0 : "cannot set loop-depth twice";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	315 int i;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	316 int loopDepth = 0;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	317 int minLoopIdx = -1;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	318 for (i = numLoops - 1; i >= 0; i--) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	319 if (isBlockInLoop(i, cur)) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	320 loopDepth++;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	321 minLoopIdx = i;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	322 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	323 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	324 cur.setLoopDepth(loopDepth);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	325 cur.setLoopIndex(minLoopIdx);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	326
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	327 // append all unvisited successors to work list
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	328 for (i = cur.numberOfSux() - 1; i >= 0; i--) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	329 workList.add(cur.suxAt(i));
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	330 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	331 for (LIRBlock ex : cur.getExceptionHandlerSuccessors()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	332 workList.add(ex);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	333 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	334 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	335 } while (!workList.isEmpty());
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	336 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	337
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	338 int computeWeight(LIRBlock cur) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	339 LIRBlock singleSux = null;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	340 if (cur.numberOfSux() == 1) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	341 singleSux = cur.suxAt(0);
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	342 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	343
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	344 // limit loop-depth to 15 bit (only for security reason, it will never be so big)
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	345 int weight = (cur.loopDepth() & 0x7FFF) << 16;
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	346
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	347 int curBit = 15;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	348
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	349 // this is necessary for the (very rare) case that two successive blocks have
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	350 // the same loop depth, but a different loop index (can happen for endless loops
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	351 // with exception handlers)
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	352 if (!cur.isLinearScanLoopHeader()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	353 weight \|= 1 << curBit;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	354 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	355 curBit--;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	356
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	357 // loop end blocks (blocks that end with a backward branch) are added
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	358 // after all other blocks of the loop.
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	359 if (!cur.isLinearScanLoopEnd()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	360 weight \|= 1 << curBit;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	361 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	362 curBit--;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	363
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	364 // critical edge split blocks are preferred because then they have a greater
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	365 // probability to be completely empty
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	366 //if (cur.isCriticalEdgeSplit()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	367 // weight \|= 1 << curBit;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	368 //}
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	369 //curBit--;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	370
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	371 // exceptions should not be thrown in normal control flow, so these blocks
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	372 // are added as late as possible
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	373 // if (!(cur.end() instanceof Throw) && (singleSux == null \|\| !(singleSux.end() instanceof Throw))) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	374 // weight \|= 1 << curBit;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	375 // }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	376 // curBit--;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	377 // if (!(cur.end() instanceof Return) && (singleSux == null \|\| !(singleSux.end() instanceof Return))) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	378 // weight \|= 1 << curBit;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	379 // }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	380 // curBit--;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	381
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	382 // exceptions handlers are added as late as possible
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	383 if (!cur.isExceptionEntry()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	384 weight \|= 1 << curBit;
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	385 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	386 curBit--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	387
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	388 // guarantee that weight is > 0
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	389 weight \|= 1;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	390
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	391 assert curBit >= 0 : "too many flags";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	392 assert weight > 0 : "weight cannot become negative";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	393
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	394 return weight;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	395 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	396
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	397 boolean readyForProcessing(LIRBlock cur) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	398 // Discount the edge just traveled.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	399 // When the number drops to zero, all forward branches were processed
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	400 if (decForwardBranches(cur) != 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	401 return false;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	402 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	403
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	404 assert !linearScanOrder.contains(cur) : "block already processed (block can be ready only once)";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	405 assert !workList.contains(cur) : "block already in work-list (block can be ready only once)";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	406 return true;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	407 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	408
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	409 void sortIntoWorkList(LIRBlock cur) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	410 assert !workList.contains(cur) : "block already in work list";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	411
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	412 int curWeight = computeWeight(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	413
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	414 // the linearScanNumber is used to cache the weight of a block
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	415 cur.setLinearScanNumber(curWeight);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	416
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	417 if (C1XOptions.StressLinearScan) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	418 workList.add(0, cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	419 return;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	420 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	421
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	422 workList.add(null); // provide space for new element
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	423
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	424 int insertIdx = workList.size() - 1;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	425 while (insertIdx > 0 && workList.get(insertIdx - 1).linearScanNumber() > curWeight) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	426 workList.set(insertIdx, workList.get(insertIdx - 1));
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	427 insertIdx--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	428 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	429 workList.set(insertIdx, cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	430
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	431 if (C1XOptions.TraceLinearScanLevel >= 3) {
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	432 TTY.println("Sorted B%d into worklist. new worklist:", cur.blockID());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	433 for (int i = 0; i < workList.size(); i++) {
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	434 TTY.println(String.format("%8d B%02d weight:%6x", i, workList.get(i).blockID(), workList.get(i).linearScanNumber()));
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	435 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	436 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	437
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	438 for (int i = 0; i < workList.size(); i++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	439 assert workList.get(i).linearScanNumber() > 0 : "weight not set";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	440 assert i == 0 \|\| workList.get(i - 1).linearScanNumber() <= workList.get(i).linearScanNumber() : "incorrect order in worklist";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	441 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	442 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	443
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	444 void appendBlock(LIRBlock cur) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	445 if (C1XOptions.TraceLinearScanLevel >= 3) {
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	446 TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID(), cur.linearScanNumber());
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	447 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	448 assert !linearScanOrder.contains(cur) : "cannot add the same block twice";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	449
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	450 // currently, the linear scan order and code emit order are equal.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	451 // therefore the linearScanNumber and the weight of a block must also
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	452 // be equal.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	453 cur.setLinearScanNumber(linearScanOrder.size());
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	454 linearScanOrder.add(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	455 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	456
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	457 void computeOrder(LIRBlock startBlock) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	458 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	459 TTY.println("----- computing final block order");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	460 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	461
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	462 // the start block is always the first block in the linear scan order
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	463 linearScanOrder = new ArrayList<LIRBlock>(numBlocks);
2788 df4c5254c5cc Towards goto removal. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2778 diff changeset	464 // appendBlock(startBlock);
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	465
2788 df4c5254c5cc Towards goto removal. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2778 diff changeset	466 LIRBlock stdEntry = startBlock; //.suxAt(0);
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	467
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	468 // start processing with standard entry block
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	469 assert workList.isEmpty() : "list must be empty before processing";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	470
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	471 if (readyForProcessing(stdEntry)) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	472 sortIntoWorkList(stdEntry);
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	473 } else {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	474 throw new CiBailout("the stdEntry must be ready for processing (otherwise, the method has no start block)");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	475 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	476
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	477 do {
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	478 LIRBlock cur = workList.remove(workList.size() - 1);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	479
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	480 appendBlock(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	481
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	482 int i;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	483 int numSux = cur.numberOfSux();
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	484 // changed loop order to get "intuitive" order of if- and else-blocks
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	485 for (i = 0; i < numSux; i++) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	486 LIRBlock sux = cur.suxAt(i);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	487 if (readyForProcessing(sux)) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	488 sortIntoWorkList(sux);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	489 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	490 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	491 for (LIRBlock ex : cur.getExceptionHandlerSuccessors()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	492 if (readyForProcessing(ex)) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	493 sortIntoWorkList(ex);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	494 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	495 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	496 } while (workList.size() > 0);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	497 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	498
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	499 public void printBlocks() {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	500 if (C1XOptions.TraceLinearScanLevel >= 2) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	501 TTY.println("----- loop information:");
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	502 for (LIRBlock cur : linearScanOrder) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	503 TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID()));
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	504 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	505 TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur)));
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	506 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	507 TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", cur.loopIndex(), cur.loopDepth()));
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	508 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	509 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	510
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	511 if (C1XOptions.TraceLinearScanLevel >= 1) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	512 TTY.println("----- linear-scan block order:");
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	513 for (LIRBlock cur : linearScanOrder) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	514 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID(), cur.loopIndex(), cur.loopDepth()));
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	515
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	516 TTY.print(cur.isExceptionEntry() ? " ex" : " ");
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	517 TTY.print(cur.isLinearScanLoopHeader() ? " lh" : " ");
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	518 TTY.print(cur.isLinearScanLoopEnd() ? " le" : " ");
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	519
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	520 TTY.print(" dom: null ");
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	521
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	522
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	523 if (cur.numberOfPreds() > 0) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	524 TTY.print(" preds: ");
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	525 for (int j = 0; j < cur.numberOfPreds(); j++) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	526 LIRBlock pred = cur.predAt(j);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	527 TTY.print("B%d ", pred.blockID());
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	528 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	529 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	530 if (cur.numberOfSux() > 0) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	531 TTY.print(" sux: ");
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	532 for (int j = 0; j < cur.numberOfSux(); j++) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	533 LIRBlock sux = cur.suxAt(j);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	534 TTY.print("B%d ", sux.blockID());
2707 7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	535 }
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	536 }
2778 2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	537 TTY.println();
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	538 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	539 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	540 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	541
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	542 boolean verify() {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	543 /* assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	544
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	545 if (C1XOptions.StressLinearScan) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	546 // blocks are scrambled when StressLinearScan is used
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	547 return true;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	548 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	549
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	550 // check that all successors of a block have a higher linear-scan-number
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	551 // and that all predecessors of a block have a lower linear-scan-number
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	552 // (only backward branches of loops are ignored)
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	553 int i;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	554 for (i = 0; i < linearScanOrder.size(); i++) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	555 BlockBegin cur = linearScanOrder.get(i);
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	556
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	557 assert cur.linearScanNumber() == i : "incorrect linearScanNumber";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	558 assert cur.linearScanNumber() >= 0 && cur.linearScanNumber() == linearScanOrder.indexOf(cur) : "incorrect linearScanNumber";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	559
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	560 for (BlockBegin sux : cur.end().successors()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	561 assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	562 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	563 assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	564 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	565 if (cur.loopDepth() == sux.loopDepth()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	566 assert cur.loopIndex() == sux.loopIndex() \|\| sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	567 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	568 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	569
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	570 for (BlockBegin pred : cur.predecessors()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	571 assert pred.linearScanNumber() >= 0 && pred.linearScanNumber() == linearScanOrder.indexOf(pred) : "incorrect linearScanNumber";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	572 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	573 assert cur.linearScanNumber() > pred.linearScanNumber() : "invalid order";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	574 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	575 if (cur.loopDepth() == pred.loopDepth()) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	576 assert cur.loopIndex() == pred.loopIndex() \|\| cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	577 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	578
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	579 assert cur.dominator().linearScanNumber() <= pred.linearScanNumber() : "dominator must be before predecessors";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	580 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	581
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	582 // check dominator
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	583 if (i == 0) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	584 assert cur.dominator() == null : "first block has no dominator";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	585 } else {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	586 assert cur.dominator() != null : "all but first block must have dominator";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	587 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	588 assert cur.numberOfPreds() != 1 \|\| cur.dominator() == cur.predAt(0) \|\| cur.isExceptionEntry() : "Single predecessor must also be dominator";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	589 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	590
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	591 // check that all loops are continuous
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	592 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	593 int blockIdx = 0;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	594 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	595
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	596 // skip blocks before the loop
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	597 while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	598 blockIdx++;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	599 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	600 // skip blocks of loop
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	601 while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	602 blockIdx++;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	603 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	604 // after the first non-loop block : there must not be another loop-block
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	605 while (blockIdx < numBlocks) {
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	606 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order";
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	607 blockIdx++;
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	608 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	609 }
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	610 */
2ac7b30b7290 Enabled new block finding algorithm. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2773 diff changeset	611 return true;
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	612 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	613 }

Mercurial > hg > graal-compiler

annotate graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2788:df4c5254c5cc