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

annotate graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2652:6d19b4f476db

Removed more OSR handling stuff.

author	Thomas Wuerthinger <thomas@wuerthinger.net>
date	Wed, 11 May 2011 14:51:33 +0200
parents	4a36a0bd6d18
children	7c8ad40c1f88

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.*;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	30 import com.sun.c1x.util.*;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	31 import com.sun.cri.ci.*;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	32
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 * @author Thomas Wuerthinger
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 */
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	37 public final class ComputeLinearScanOrder {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	38
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	39 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	40 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	41 private int numLoops; // total number of loops
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	42 private boolean iterativeDominators; // method requires iterative computation of dominators
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	43
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	44 List<BlockBegin> linearScanOrder; // the resulting list of blocks in correct order
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	45
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	46 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	47 final CiBitMap activeBlocks; // used for recursive processing of blocks
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	48 final CiBitMap dominatorBlocks; // temporary BitMap used for computation of dominator
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	49 final int[] forwardBranches; // number of incoming forward branches for each block
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	50 final List<BlockBegin> loopEndBlocks; // list of all loop end blocks collected during countEdges
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	51 BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	52 final List<BlockBegin> workList; // temporary list (used in markLoops and computeOrder)
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	53
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	54 // accessors for visitedBlocks and activeBlocks
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	55 void initVisited() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	56 activeBlocks.clearAll();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	57 visitedBlocks.clearAll();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	58 }
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 boolean isVisited(BlockBegin b) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	61 return visitedBlocks.get(b.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	62 }
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 boolean isActive(BlockBegin b) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	65 return activeBlocks.get(b.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	66 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	67
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	68 void setVisited(BlockBegin b) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	69 assert !isVisited(b) : "already set";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	70 visitedBlocks.set(b.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	71 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	72
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	73 void setActive(BlockBegin b) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	74 assert !isActive(b) : "already set";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	75 activeBlocks.set(b.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	76 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	77
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	78 void clearActive(BlockBegin b) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	79 assert isActive(b) : "not already";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	80 activeBlocks.clear(b.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	81 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	82
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	83 // accessors for forwardBranches
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	84 void incForwardBranches(BlockBegin b) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	85 forwardBranches[b.blockID]++;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	86 }
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 int decForwardBranches(BlockBegin b) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	89 return --forwardBranches[b.blockID];
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	90 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	91
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	92 // accessors for loopMap
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	93 boolean isBlockInLoop(int loopIdx, BlockBegin b) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	94 return loopMap.at(loopIdx, b.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	95 }
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 void setBlockInLoop(int loopIdx, BlockBegin b) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	98 loopMap.setBit(loopIdx, b.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	99 }
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 void clearBlockInLoop(int loopIdx, int blockId) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	102 loopMap.clearBit(loopIdx, blockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	103 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	104
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	105 // accessors for final result
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	106 public List<BlockBegin> linearScanOrder() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	107 return linearScanOrder;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	108 }
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 public int numLoops() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	111 return numLoops;
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
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	114 public ComputeLinearScanOrder(int maxBlockId, BlockBegin startBlock) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	115
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	116 this.maxBlockId = maxBlockId;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	117 visitedBlocks = new CiBitMap(maxBlockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	118 activeBlocks = new CiBitMap(maxBlockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	119 dominatorBlocks = new CiBitMap(maxBlockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	120 forwardBranches = new int[maxBlockId];
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	121 loopEndBlocks = new ArrayList<BlockBegin>(8);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	122 workList = new ArrayList<BlockBegin>(8);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	123
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	124 splitCriticalEdges();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	125
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	126 countEdges(startBlock, null);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	127
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	128 if (numLoops > 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	129 markLoops();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	130 clearNonNaturalLoops(startBlock);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	131 assignLoopDepth(startBlock);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	132 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	133
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	134 computeOrder(startBlock);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	135 computeDominators();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	136
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	137 printBlocks();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	138 assert verify();
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 void splitCriticalEdges() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	142 // TODO: move critical edge splitting from IR to here
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
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	145 /**
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	146 * 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	147 *
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	148 * 1. Count of total number of blocks.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	149 * 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	150 * 3. Number loop header blocks.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	151 * 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	152 */
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	153 void countEdges(BlockBegin cur, BlockBegin parent) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	154 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	155 TTY.println("Counting edges for block B%d%s", cur.blockID, parent == null ? "" : " coming from B" + parent.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	156 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	157 assert cur.dominator() == null : "dominator already initialized";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	158
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	159 if (isActive(cur)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	160 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	161 TTY.println("backward branch");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	162 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	163 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	164 assert parent != null : "must have parent";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	165
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	166 cur.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	167 cur.setBlockFlag(BlockBegin.BlockFlag.BackwardBranchTarget);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	168
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	169 parent.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	170
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	171 // When a loop header is also the start of an exception handler, then the backward branch is
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	172 // an exception edge. Because such edges are usually critical edges which cannot be split, the
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	173 // loop must be excluded here from processing.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	174 if (cur.checkBlockFlag(BlockBegin.BlockFlag.ExceptionEntry)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	175 // Make sure that dominators are correct in this weird situation
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	176 iterativeDominators = true;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	177 return;
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 // assert parent.numberOfSux() == 1 && parent.suxAt(0) == cur : "loop end blocks must have one successor (critical edges are split)";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	180
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	181 loopEndBlocks.add(parent);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	182 return;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	183 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	184
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	185 // increment number of incoming forward branches
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	186 incForwardBranches(cur);
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 if (isVisited(cur)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	189 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	190 TTY.println("block already visited");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	191 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	192 return;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	193 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	194
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	195 numBlocks++;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	196 setVisited(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	197 setActive(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	198
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	199 // recursive call for all successors
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	200 int i;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	201 for (i = cur.numberOfSux() - 1; i >= 0; i--) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	202 countEdges(cur.suxAt(i), cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	203 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	204 for (i = cur.numberOfExceptionHandlers() - 1; i >= 0; i--) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	205 countEdges(cur.exceptionHandlerAt(i), cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	206 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	207
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	208 clearActive(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	209
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	210 // Each loop has a unique number.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	211 // When multiple loops are nested, assignLoopDepth assumes that the
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	212 // innermost loop has the lowest number. This is guaranteed by setting
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	213 // the loop number after the recursive calls for the successors above
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	214 // have returned.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	215 if (cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	216 assert cur.loopIndex() == -1 : "cannot set loop-index twice";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	217 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	218 TTY.println("Block B%d is loop header of loop %d", cur.blockID, numLoops);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	219 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	220
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	221 cur.setLoopIndex(numLoops);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	222 numLoops++;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	223 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	224
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	225 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	226 TTY.println("Finished counting edges for block B%d", cur.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	227 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	228 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	229
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	230 void markLoops() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	231 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	232 TTY.println("----- marking loops");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	233 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	234
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	235 loopMap = new BitMap2D(numLoops, maxBlockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	236
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	237 for (int i = loopEndBlocks.size() - 1; i >= 0; i--) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	238 BlockBegin loopEnd = loopEndBlocks.get(i);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	239 BlockBegin loopStart = loopEnd.suxAt(0);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	240 int loopIdx = loopStart.loopIndex();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	241
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	242 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	243 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID, loopEnd.blockID, loopIdx);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	244 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	245 assert loopEnd.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) : "loop end flag must be set";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	246 // assert loopEnd.numberOfSux() == 1 : "incorrect number of successors";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	247 assert loopStart.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "loop header flag must be set";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	248 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	249 assert workList.isEmpty() : "work list must be empty before processing";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	250
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	251 // add the end-block of the loop to the working list
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	252 workList.add(loopEnd);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	253 setBlockInLoop(loopIdx, loopEnd);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	254 do {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	255 BlockBegin cur = workList.remove(workList.size() - 1);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	256
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	257 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	258 TTY.println(" processing B%d", cur.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	259 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	260 assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	261
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	262 // recursive processing of all predecessors ends when start block of loop is reached
2516 a384fac3fd34 Removed anything OSR-related. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2509 diff changeset	263 if (cur != loopStart) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	264 for (int j = cur.numberOfPreds() - 1; j >= 0; j--) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	265 BlockBegin pred = cur.predAt(j);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	266
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	267 if (!isBlockInLoop(loopIdx, pred)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	268 // this predecessor has not been processed yet, so add it to work list
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	269 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	270 TTY.println(" pushing B%d", pred.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	271 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	272 workList.add(pred);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	273 setBlockInLoop(loopIdx, pred);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	274 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	275 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	276 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	277 } while (!workList.isEmpty());
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	278 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	279 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	280
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	281 // check for non-natural loops (loops where the loop header does not dominate
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	282 // all other loop blocks = loops with multiple entries).
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	283 // such loops are ignored
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	284 void clearNonNaturalLoops(BlockBegin startBlock) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	285 for (int i = numLoops - 1; i >= 0; i--) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	286 if (isBlockInLoop(i, startBlock)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	287 // loop i contains the entry block of the method.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	288 // this is not a natural loop, so ignore it
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	289 if (C1XOptions.TraceLinearScanLevel >= 2) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	290 TTY.println("Loop %d is non-natural, so it is ignored", i);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	291 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	292
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	293 for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	294 clearBlockInLoop(i, blockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	295 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	296 iterativeDominators = true;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	297 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	298 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	299 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	300
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	301 void assignLoopDepth(BlockBegin startBlock) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	302 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	303 TTY.println("----- computing loop-depth and weight");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	304 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	305 initVisited();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	306
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	307 assert workList.isEmpty() : "work list must be empty before processing";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	308 workList.add(startBlock);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	309
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	310 do {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	311 BlockBegin cur = workList.remove(workList.size() - 1);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	312
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	313 if (!isVisited(cur)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	314 setVisited(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	315 if (C1XOptions.TraceLinearScanLevel >= 4) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	316 TTY.println("Computing loop depth for block B%d", cur.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	317 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	318
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	319 // compute loop-depth and loop-index for the block
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	320 assert cur.loopDepth() == 0 : "cannot set loop-depth twice";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	321 int i;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	322 int loopDepth = 0;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	323 int minLoopIdx = -1;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	324 for (i = numLoops - 1; i >= 0; i--) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	325 if (isBlockInLoop(i, cur)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	326 loopDepth++;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	327 minLoopIdx = i;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	328 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	329 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	330 cur.setLoopDepth(loopDepth);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	331 cur.setLoopIndex(minLoopIdx);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	332
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	333 // append all unvisited successors to work list
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	334 for (i = cur.numberOfSux() - 1; i >= 0; i--) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	335 workList.add(cur.suxAt(i));
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	336 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	337 for (i = cur.numberOfExceptionHandlers() - 1; i >= 0; i--) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	338 workList.add(cur.exceptionHandlerAt(i));
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	339 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	340 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	341 } while (!workList.isEmpty());
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 BlockBegin commonDominator(BlockBegin a, BlockBegin b) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	345 assert a != null && b != null : "must have input blocks";
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 dominatorBlocks.clearAll();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	348 while (a != null) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	349 dominatorBlocks.set(a.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	350 assert a.dominator() != null \|\| a == linearScanOrder.get(0) : "dominator must be initialized";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	351 a = a.dominator();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	352 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	353 while (b != null && !dominatorBlocks.get(b.blockID)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	354 assert b.dominator() != null \|\| b == linearScanOrder.get(0) : "dominator must be initialized";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	355 b = b.dominator();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	356 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	357
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	358 assert b != null : "could not find dominator";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	359 return b;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	360 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	361
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	362 void computeDominator(BlockBegin cur, BlockBegin parent) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	363 if (cur.dominator() == null) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	364 if (C1XOptions.TraceLinearScanLevel >= 4) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	365 TTY.println("DOM: initializing dominator of B%d to B%d", cur.blockID, parent.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	366 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	367 if (cur.isExceptionEntry()) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	368 assert parent.dominator() != null;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	369 cur.setDominator(parent.dominator());
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	370 } else {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	371 cur.setDominator(parent);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	372 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	373
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	374 } else if (!(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) && parent.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd))) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	375 if (C1XOptions.TraceLinearScanLevel >= 4) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	376 TTY.println("DOM: computing dominator of B%d: common dominator of B%d and B%d is B%d", cur.blockID, parent.blockID, cur.dominator().blockID, commonDominator(cur.dominator(), parent).blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	377 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	378 assert cur.numberOfPreds() > 1 : "";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	379 cur.setDominator(commonDominator(cur.dominator(), parent));
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	380 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	381 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	382
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	383 int computeWeight(BlockBegin cur) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	384 BlockBegin singleSux = null;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	385 if (cur.numberOfSux() == 1) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	386 singleSux = cur.suxAt(0);
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
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	389 // limit loop-depth to 15 bit (only for security reason, it will never be so big)
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	390 int weight = (cur.loopDepth() & 0x7FFF) << 16;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	391
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	392 int curBit = 15;
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 // this is necessary for the (very rare) case that two successive blocks have
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	395 // the same loop depth, but a different loop index (can happen for endless loops
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	396 // with exception handlers)
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	397 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	398 weight \|= (1 << curBit);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	399 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	400 curBit--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	401
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	402 // loop end blocks (blocks that end with a backward branch) are added
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	403 // after all other blocks of the loop.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	404 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	405 weight \|= (1 << curBit);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	406 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	407 curBit--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	408
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	409 // critical edge split blocks are preferred because then they have a greater
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	410 // probability to be completely empty
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	411 if (cur.isCriticalEdgeSplit()) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	412 weight \|= (1 << curBit);
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 curBit--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	415
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	416 // 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	417 // are added as late as possible
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	418 if (!(cur.end() instanceof Throw) && (singleSux == null \|\| !(singleSux.end() instanceof Throw))) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	419 weight \|= (1 << curBit);
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 curBit--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	422 if (!(cur.end() instanceof Return) && (singleSux == null \|\| !(singleSux.end() instanceof Return))) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	423 weight \|= (1 << curBit);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	424 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	425 curBit--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	426
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	427 // exceptions handlers are added as late as possible
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	428 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.ExceptionEntry)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	429 weight \|= (1 << curBit);
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 curBit--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	432
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	433 // guarantee that weight is > 0
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	434 weight \|= 1;
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 assert curBit >= 0 : "too many flags";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	437 assert weight > 0 : "weight cannot become negative";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	438
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	439 return weight;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	440 }
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 boolean readyForProcessing(BlockBegin cur) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	443 // Discount the edge just traveled.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	444 // 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	445 if (decForwardBranches(cur) != 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	446 return false;
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
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	449 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	450 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	451 return true;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	452 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	453
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	454 void sortIntoWorkList(BlockBegin cur) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	455 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	456
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	457 int curWeight = computeWeight(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	458
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	459 // 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	460 cur.setLinearScanNumber(curWeight);
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 if (C1XOptions.StressLinearScan) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	463 workList.add(0, cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	464 return;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	465 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	466
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	467 workList.add(null); // provide space for new element
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	468
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	469 int insertIdx = workList.size() - 1;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	470 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	471 workList.set(insertIdx, workList.get(insertIdx - 1));
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	472 insertIdx--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	473 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	474 workList.set(insertIdx, cur);
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 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	477 TTY.println("Sorted B%d into worklist. new worklist:", cur.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	478 for (int i = 0; i < workList.size(); i++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	479 TTY.println(String.format("%8d B%02d weight:%6x", i, workList.get(i).blockID, workList.get(i).linearScanNumber()));
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	480 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	481 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	482
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	483 for (int i = 0; i < workList.size(); i++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	484 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	485 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	486 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	487 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	488
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	489 void appendBlock(BlockBegin cur) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	490 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	491 TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID, cur.linearScanNumber());
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	492 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	493 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	494
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	495 // 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	496 // 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	497 // be equal.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	498 cur.setLinearScanNumber(linearScanOrder.size());
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	499 linearScanOrder.add(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	500 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	501
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	502 void computeOrder(BlockBegin startBlock) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	503 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	504 TTY.println("----- computing final block order");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	505 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	506
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	507 // the start block is always the first block in the linear scan order
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	508 linearScanOrder = new ArrayList<BlockBegin>(numBlocks);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	509 appendBlock(startBlock);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	510
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	511 assert startBlock.end() instanceof Base : "start block must end with Base-instruction";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	512 BlockBegin stdEntry = ((Base) startBlock.end()).standardEntry();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	513
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	514 computeDominator(stdEntry, startBlock);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	515
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	516 // start processing with standard entry block
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	517 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	518
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	519 if (readyForProcessing(stdEntry)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	520 sortIntoWorkList(stdEntry);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	521 } else {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	522 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	523 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	524
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	525 do {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	526 BlockBegin cur = workList.remove(workList.size() - 1);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	527 appendBlock(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	528
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	529 int i;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	530 int numSux = cur.numberOfSux();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	531 // changed loop order to get "intuitive" order of if- and else-blocks
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	532 for (i = 0; i < numSux; i++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	533 BlockBegin sux = cur.suxAt(i);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	534 computeDominator(sux, cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	535 if (readyForProcessing(sux)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	536 sortIntoWorkList(sux);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	537 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	538 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	539 numSux = cur.numberOfExceptionHandlers();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	540 for (i = 0; i < numSux; i++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	541 BlockBegin sux = cur.exceptionHandlerAt(i);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	542 computeDominator(sux, cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	543 if (readyForProcessing(sux)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	544 sortIntoWorkList(sux);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	545 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	546 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	547 } while (workList.size() > 0);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	548 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	549
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	550 boolean computeDominatorsIter() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	551 boolean changed = false;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	552 int numBlocks = linearScanOrder.size();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	553
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	554 assert linearScanOrder.get(0).dominator() == null : "must not have dominator";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	555 assert linearScanOrder.get(0).numberOfPreds() == 0 : "must not have predecessors";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	556 for (int i = 1; i < numBlocks; i++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	557 BlockBegin block = linearScanOrder.get(i);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	558
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	559 assert block.numberOfPreds() > 0;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	560 BlockBegin dominator = block.predAt(0);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	561 if (block.isExceptionEntry()) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	562 dominator = dominator.dominator();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	563 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	564
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	565 int numPreds = block.numberOfPreds();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	566 for (int j = 1; j < numPreds; j++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	567 BlockBegin curPred = block.predAt(j);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	568 if (block.isExceptionEntry()) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	569 curPred = curPred.dominator();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	570 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	571 dominator = commonDominator(dominator, curPred);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	572 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	573
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	574 if (dominator != block.dominator()) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	575 if (C1XOptions.TraceLinearScanLevel >= 4) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	576 TTY.println("DOM: updating dominator of B%d from B%d to B%d", block.blockID, block.dominator().blockID, dominator.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	577 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	578 block.setDominator(dominator);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	579 changed = true;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	580 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	581 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	582 return changed;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	583 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	584
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	585 void computeDominators() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	586 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	587 TTY.println("----- computing dominators (iterative computation reqired: %b)", iterativeDominators);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	588 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	589
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	590 // iterative computation of dominators is only required for methods with non-natural loops
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	591 // and OSR-methods. For all other methods : the dominators computed when generating the
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	592 // linear scan block order are correct.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	593 if (iterativeDominators) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	594 do {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	595 if (C1XOptions.TraceLinearScanLevel >= 1) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	596 TTY.println("DOM: next iteration of fix-point calculation");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	597 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	598 } while (computeDominatorsIter());
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	599 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	600
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	601 // check that dominators are correct
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	602 assert !computeDominatorsIter() : "fix point not reached";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	603 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	604
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	605 public void printBlocks() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	606 if (C1XOptions.TraceLinearScanLevel >= 2) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	607 TTY.println("----- loop information:");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	608 for (BlockBegin cur : linearScanOrder) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	609 TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID));
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	610 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	611 TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur)));
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 TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", cur.loopIndex(), cur.loopDepth()));
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	614 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	615 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	616
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	617 if (C1XOptions.TraceLinearScanLevel >= 1) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	618 TTY.println("----- linear-scan block order:");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	619 for (BlockBegin cur : linearScanOrder) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	620 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID, cur.loopIndex(), cur.loopDepth()));
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	621
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	622 TTY.print(cur.isExceptionEntry() ? " ex" : " ");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	623 TTY.print(cur.isCriticalEdgeSplit() ? " ce" : " ");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	624 TTY.print(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) ? " lh" : " ");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	625 TTY.print(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) ? " le" : " ");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	626
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	627 if (cur.dominator() != null) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	628 TTY.print(" dom: B%d ", cur.dominator().blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	629 } else {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	630 TTY.print(" dom: null ");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	631 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	632
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	633 if (cur.numberOfPreds() > 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	634 TTY.print(" preds: ");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	635 for (int j = 0; j < cur.numberOfPreds(); j++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	636 BlockBegin pred = cur.predAt(j);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	637 TTY.print("B%d ", pred.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	638 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	639 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	640 if (cur.numberOfSux() > 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	641 TTY.print(" sux: ");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	642 for (int j = 0; j < cur.numberOfSux(); j++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	643 BlockBegin sux = cur.suxAt(j);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	644 TTY.print("B%d ", sux.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	645 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	646 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	647 if (cur.numberOfExceptionHandlers() > 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	648 TTY.print(" ex: ");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	649 for (int j = 0; j < cur.numberOfExceptionHandlers(); j++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	650 BlockBegin ex = cur.exceptionHandlerAt(j);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	651 TTY.print("B%d ", ex.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	652 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	653 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	654 TTY.println();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	655 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	656 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	657 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	658
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	659 boolean verify() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	660 assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	661
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	662 if (C1XOptions.StressLinearScan) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	663 // blocks are scrambled when StressLinearScan is used
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	664 return true;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	665 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	666
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	667 // check that all successors of a block have a higher linear-scan-number
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	668 // and that all predecessors of a block have a lower linear-scan-number
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	669 // (only backward branches of loops are ignored)
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	670 int i;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	671 for (i = 0; i < linearScanOrder.size(); i++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	672 BlockBegin cur = linearScanOrder.get(i);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	673
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	674 assert cur.linearScanNumber() == i : "incorrect linearScanNumber";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	675 assert cur.linearScanNumber() >= 0 && cur.linearScanNumber() == linearScanOrder.indexOf(cur) : "incorrect linearScanNumber";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	676
2581 4a36a0bd6d18 added GraalGraph to classpath, Node as superclass of Value Lukas Stadler <lukas.stadler@jku.at> parents: 2516 diff changeset	677 for (BlockBegin sux : cur.end().blockSuccessors()) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	678 assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	679 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	680 assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	681 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	682 if (cur.loopDepth() == sux.loopDepth()) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	683 assert cur.loopIndex() == sux.loopIndex() \|\| sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	684 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	685 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	686
2581 4a36a0bd6d18 added GraalGraph to classpath, Node as superclass of Value Lukas Stadler <lukas.stadler@jku.at> parents: 2516 diff changeset	687 for (BlockBegin pred : cur.blockPredecessors()) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	688 assert pred.linearScanNumber() >= 0 && pred.linearScanNumber() == linearScanOrder.indexOf(pred) : "incorrect linearScanNumber";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	689 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	690 assert cur.linearScanNumber() > pred.linearScanNumber() : "invalid order";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	691 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	692 if (cur.loopDepth() == pred.loopDepth()) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	693 assert cur.loopIndex() == pred.loopIndex() \|\| cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	694 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	695
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	696 assert cur.dominator().linearScanNumber() <= pred.linearScanNumber() : "dominator must be before predecessors";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	697 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	698
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	699 // check dominator
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	700 if (i == 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	701 assert cur.dominator() == null : "first block has no dominator";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	702 } else {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	703 assert cur.dominator() != null : "all but first block must have dominator";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	704 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	705 assert cur.numberOfPreds() != 1 \|\| cur.dominator() == cur.predAt(0) \|\| cur.isExceptionEntry() : "Single predecessor must also be dominator";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	706 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	707
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	708 // check that all loops are continuous
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	709 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	710 int blockIdx = 0;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	711 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	712
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	713 // skip blocks before the loop
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	714 while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	715 blockIdx++;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	716 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	717 // skip blocks of loop
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	718 while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	719 blockIdx++;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	720 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	721 // after the first non-loop block : there must not be another loop-block
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	722 while (blockIdx < numBlocks) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	723 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	724 blockIdx++;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	725 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	726 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	727
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	728 return true;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	729 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	730 }

Mercurial > hg > truffle

annotate graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2652:6d19b4f476db