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

annotate graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2718:c1ce2a53d6c3

Attempt to remove dependency between backend and BlockBegin.

author	Thomas Wuerthinger <thomas@wuerthinger.net>
date	Thu, 19 May 2011 16:05:42 +0200
parents	bd85cf08720a
children	3fbe58ac818d

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 public final class ComputeLinearScanOrder {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	34
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	35 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	36 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	37 private int numLoops; // total number of loops
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	38 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	39
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	40 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	41
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	42 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	43 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	44 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	45 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	46 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	47 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	48
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	49 // accessors for visitedBlocks and activeBlocks
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	50 private void initVisited() {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	51 activeBlocks.clearAll();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	52 visitedBlocks.clearAll();
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
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	55 private boolean isVisited(BlockBegin b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	56 return visitedBlocks.get(b.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	57 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	58
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	59 private boolean isActive(BlockBegin b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	60 return activeBlocks.get(b.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	61 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	62
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	63 private void setVisited(BlockBegin b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	64 assert !isVisited(b) : "already set";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	65 visitedBlocks.set(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
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	68 private void setActive(BlockBegin b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	69 assert !isActive(b) : "already set";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	70 activeBlocks.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
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	73 private void clearActive(BlockBegin b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	74 assert isActive(b) : "not already";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	75 activeBlocks.clear(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 // accessors for forwardBranches
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	79 private void incForwardBranches(BlockBegin b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	80 forwardBranches[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
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	83 private int decForwardBranches(BlockBegin b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	84 return --forwardBranches[b.blockID];
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	85 }
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 // accessors for loopMap
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	88 private boolean isBlockInLoop(int loopIdx, BlockBegin b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	89 return loopMap.at(loopIdx, 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
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	92 private void setBlockInLoop(int loopIdx, BlockBegin b) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	93 loopMap.setBit(loopIdx, b.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	94 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	95
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	96 private void clearBlockInLoop(int loopIdx, int blockId) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	97 loopMap.clearBit(loopIdx, blockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	98 }
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 // accessors for final result
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	101 public List<BlockBegin> linearScanOrder() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	102 return linearScanOrder;
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 public int numLoops() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	106 return numLoops;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	107 }
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 public ComputeLinearScanOrder(int maxBlockId, BlockBegin startBlock) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	110
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	111 this.maxBlockId = maxBlockId;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	112 visitedBlocks = new CiBitMap(maxBlockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	113 activeBlocks = new CiBitMap(maxBlockId);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	114 forwardBranches = new int[maxBlockId];
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	115 loopEndBlocks = new ArrayList<BlockBegin>(8);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	116 workList = new ArrayList<BlockBegin>(8);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	117
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	118 countEdges(startBlock, null);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	119
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	120 if (numLoops > 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	121 markLoops();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	122 clearNonNaturalLoops(startBlock);
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
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	125 computeOrder(startBlock);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	126
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	127 printBlocks();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	128 assert verify();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	129 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	130
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	131 /**
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	132 * 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	133 *
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	134 * 1. Count of total number of blocks.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	135 * 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	136 * 3. Number loop header blocks.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	137 * 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	138 */
2707 7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	139 private void countEdges(final BlockBegin cur, BlockBegin parent) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	140 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	141 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	142 }
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 if (isActive(cur)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	145 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	146 TTY.println("backward branch");
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 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	149 assert parent != null : "must have parent";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	150
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	151 cur.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	152 cur.setBlockFlag(BlockBegin.BlockFlag.BackwardBranchTarget);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	153
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	154 parent.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	155
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	156 loopEndBlocks.add(parent);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	157 return;
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
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	160 // increment number of incoming forward branches
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	161 incForwardBranches(cur);
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 if (isVisited(cur)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	164 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	165 TTY.println("block already visited");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	166 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	167 return;
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
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	170 numBlocks++;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	171 setVisited(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	172 setActive(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	173
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	174 // recursive call for all successors
2707 7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	175 cur.allSuccessorsDo(true, new BlockClosure() {
7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	176 public void apply(BlockBegin block) {
7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	177 countEdges(block, cur);
7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	178 }
7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	179 });
2507 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 clearActive(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	182
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	183 // Each loop has a unique number.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	184 // 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	185 // 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	186 // 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	187 // have returned.
2718 c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	188 // if (cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	189 // // assert cur.loopIndex() == -1 : "cannot set loop-index twice";
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	190 // if (C1XOptions.TraceLinearScanLevel >= 3) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	191 // TTY.println("Block B%d is loop header of loop %d", cur.blockID, numLoops);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	192 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	193 //
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	194 // cur.setLoopIndex(numLoops);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	195 // numLoops++;
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	196 // }
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	197
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	198 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	199 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	200 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	201 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	202
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	203 private void markLoops() {
2718 c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	204 // if (C1XOptions.TraceLinearScanLevel >= 3) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	205 // TTY.println("----- marking loops");
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	206 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	207 //
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	208 // loopMap = new BitMap2D(numLoops, maxBlockId);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	209 //
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	210 // for (int i = loopEndBlocks.size() - 1; i >= 0; i--) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	211 // BlockBegin loopEnd = loopEndBlocks.get(i);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	212 // BlockBegin loopStart = loopEnd.suxAt(0);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	213 // int loopIdx = loopStart.loopIndex();
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	214 //
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	215 // if (C1XOptions.TraceLinearScanLevel >= 3) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	216 // TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID, loopEnd.blockID, loopIdx);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	217 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	218 // assert loopEnd.isLinearScanLoopEnd() : "loop end flag must be set";
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	219 // assert loopStart.isLinearScanLoopHeader() : "loop header flag must be set";
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	220 // assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set";
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	221 // assert workList.isEmpty() : "work list must be empty before processing";
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	222 //
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	223 // // add the end-block of the loop to the working list
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	224 // workList.add(loopEnd);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	225 // setBlockInLoop(loopIdx, loopEnd);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	226 // do {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	227 // BlockBegin cur = workList.remove(workList.size() - 1);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	228 //
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	229 // if (C1XOptions.TraceLinearScanLevel >= 3) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	230 // TTY.println(" processing B%d", cur.blockID);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	231 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	232 // //assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list";
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	233 //
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	234 // // recursive processing of all predecessors ends when start block of loop is reached
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	235 // if (cur != loopStart) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	236 // for (int j = cur.numberOfPreds() - 1; j >= 0; j--) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	237 // BlockBegin pred = cur.predAt(j).block();
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	238 //
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	239 // if (!isBlockInLoop(loopIdx, pred)) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	240 // // this predecessor has not been processed yet, so add it to work list
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	241 // if (C1XOptions.TraceLinearScanLevel >= 3) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	242 // TTY.println(" pushing B%d", pred.blockID);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	243 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	244 // workList.add(pred);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	245 // setBlockInLoop(loopIdx, pred);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	246 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	247 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	248 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	249 // } while (!workList.isEmpty());
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	250 // }
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	251 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	252
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	253 // 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	254 // all other loop blocks = loops with multiple entries).
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	255 // such loops are ignored
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	256 private void clearNonNaturalLoops(BlockBegin startBlock) {
2718 c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	257 // for (int i = numLoops - 1; i >= 0; i--) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	258 // if (isBlockInLoop(i, startBlock)) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	259 // // loop i contains the entry block of the method.
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	260 // // this is not a natural loop, so ignore it
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	261 // if (C1XOptions.TraceLinearScanLevel >= 2) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	262 // TTY.println("Loop %d is non-natural, so it is ignored", i);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	263 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	264 //
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	265 // for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	266 // clearBlockInLoop(i, blockId);
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	267 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	268 // iterativeDominators = true;
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	269 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	270 // }
2507 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
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	273 private int computeWeight(BlockBegin cur) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	274 BlockBegin singleSux = null;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	275 if (cur.numberOfSux() == 1) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	276 singleSux = cur.suxAt(0);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	277 }
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 // limit loop-depth to 15 bit (only for security reason, it will never be so big)
2718 c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	280 int loopDepth = 0; // TODO(tw): Assign loop depth
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	281 int weight = (loopDepth & 0x7FFF) << 16;
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	282
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	283 int curBit = 15;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	284
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	285 // 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	286 // 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	287 // with exception handlers)
2703 42450f536d24 More cleanup towards separation of graphbuilding<>graph<>lirgeneration Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2694 diff changeset	288 if (!cur.isLinearScanLoopHeader()) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	289 weight \|= (1 << curBit);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	290 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	291 curBit--;
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 // 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	294 // after all other blocks of the loop.
2703 42450f536d24 More cleanup towards separation of graphbuilding<>graph<>lirgeneration Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2694 diff changeset	295 if (!cur.isLinearScanLoopEnd()) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	296 weight \|= (1 << curBit);
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 curBit--;
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 // 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	301 // are added as late as possible
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	302 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	303 weight \|= (1 << curBit);
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 curBit--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	306 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	307 weight \|= (1 << curBit);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	308 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	309 curBit--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	310
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	311 // guarantee that weight is > 0
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	312 weight \|= 1;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	313
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	314 assert curBit >= 0 : "too many flags";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	315 assert weight > 0 : "weight cannot become negative";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	316
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	317 return weight;
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
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	320 private boolean readyForProcessing(BlockBegin cur) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	321 // Discount the edge just traveled.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	322 // 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	323 if (decForwardBranches(cur) != 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	324 return false;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	325 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	326
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	327 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	328 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	329 return true;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	330 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	331
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	332 private void sortIntoWorkList(BlockBegin cur) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	333 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	334
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	335 int curWeight = computeWeight(cur);
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 // 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	338 cur.setLinearScanNumber(curWeight);
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 if (C1XOptions.StressLinearScan) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	341 workList.add(0, cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	342 return;
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
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	345 workList.add(null); // provide space for new element
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	346
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	347 int insertIdx = workList.size() - 1;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	348 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	349 workList.set(insertIdx, workList.get(insertIdx - 1));
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	350 insertIdx--;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	351 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	352 workList.set(insertIdx, cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	353
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	354 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	355 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	356 for (int i = 0; i < workList.size(); i++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	357 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	358 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	359 }
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 for (int i = 0; i < workList.size(); i++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	362 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	363 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	364 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	365 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	366
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	367 private void appendBlock(BlockBegin cur) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	368 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	369 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	370 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	371 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	372
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	373 // 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	374 // 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	375 // be equal.
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	376 cur.setLinearScanNumber(linearScanOrder.size());
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	377 linearScanOrder.add(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	378 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	379
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	380 private void computeOrder(BlockBegin startBlock) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	381 if (C1XOptions.TraceLinearScanLevel >= 3) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	382 TTY.println("----- computing final block order");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	383 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	384
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	385 // 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	386 linearScanOrder = new ArrayList<BlockBegin>(numBlocks);
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 // start processing with standard entry block
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	389 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	390
2657 4a6518c4d17d Removed need for base instruction. Cleanup. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2653 diff changeset	391 if (readyForProcessing(startBlock)) {
4a6518c4d17d Removed need for base instruction. Cleanup. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2653 diff changeset	392 sortIntoWorkList(startBlock);
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	393 } else {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	394 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	395 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	396
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	397 do {
2707 7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	398 final BlockBegin cur = workList.remove(workList.size() - 1);
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	399 appendBlock(cur);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	400
2707 7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	401 cur.allSuccessorsDo(false, new BlockClosure() {
7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	402 public void apply(BlockBegin block) {
7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	403 if (readyForProcessing(block)) {
7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	404 sortIntoWorkList(block);
7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	405 }
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	406 }
2707 7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	407 });
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	408 } while (workList.size() > 0);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	409 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	410
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	411 public void printBlocks() {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	412 if (C1XOptions.TraceLinearScanLevel >= 2) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	413 TTY.println("----- loop information:");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	414 for (BlockBegin cur : linearScanOrder) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	415 TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID));
2718 c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	416 // for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	417 // TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur)));
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	418 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	419 TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", -1, -1));
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	420 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	421 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	422
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	423 if (C1XOptions.TraceLinearScanLevel >= 1) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	424 TTY.println("----- linear-scan block order:");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	425 for (BlockBegin cur : linearScanOrder) {
2718 c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	426 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID, -1, -1));
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	427
2703 42450f536d24 More cleanup towards separation of graphbuilding<>graph<>lirgeneration Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2694 diff changeset	428 TTY.print(cur.isLinearScanLoopHeader() ? " lh" : " ");
42450f536d24 More cleanup towards separation of graphbuilding<>graph<>lirgeneration Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2694 diff changeset	429 TTY.print(cur.isLinearScanLoopEnd() ? " le" : " ");
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	430
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	431 if (cur.numberOfPreds() > 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	432 TTY.print(" preds: ");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	433 for (int j = 0; j < cur.numberOfPreds(); j++) {
2707 7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	434 BlockBegin pred = cur.predAt(j).block();
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	435 TTY.print("B%d ", pred.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	436 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	437 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	438 if (cur.numberOfSux() > 0) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	439 TTY.print(" sux: ");
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	440 for (int j = 0; j < cur.numberOfSux(); j++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	441 BlockBegin sux = cur.suxAt(j);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	442 TTY.print("B%d ", sux.blockID);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	443 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	444 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	445 TTY.println();
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	446 }
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
2653 7c8ad40c1f88 No need for stateAfter on volatile field loads. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2652 diff changeset	450 private boolean verify() {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	451 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	452
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	453 if (C1XOptions.StressLinearScan) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	454 // blocks are scrambled when StressLinearScan is used
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	455 return true;
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
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	458 // 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	459 // 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	460 // (only backward branches of loops are ignored)
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	461 int i;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	462 for (i = 0; i < linearScanOrder.size(); i++) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	463 BlockBegin cur = linearScanOrder.get(i);
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	464
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	465 assert cur.linearScanNumber() == i : "incorrect linearScanNumber";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	466 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	467
2581 4a36a0bd6d18 added GraalGraph to classpath, Node as superclass of Value Lukas Stadler <lukas.stadler@jku.at> parents: 2516 diff changeset	468 for (BlockBegin sux : cur.end().blockSuccessors()) {
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	469 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	470 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) {
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	471 assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order";
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	472 }
2718 c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	473 //if (cur.loopDepth() == sux.loopDepth()) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	474 // assert cur.loopIndex() == sux.loopIndex() \|\| sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	475 //}
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	476 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	477
2707 7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	478 for (Instruction pred : cur.blockPredecessors()) {
7ed72769d51a exception handling related changes: Lukas Stadler <lukas.stadler@jku.at> parents: 2674 diff changeset	479 BlockBegin begin = pred.block();
2674 6ab73784566a * BlockBegin.predecessors changed to List<BlockEnd> Lukas Stadler <lukas.stadler@jku.at> parents: 2657 diff changeset	480 assert begin.linearScanNumber() >= 0 && begin.linearScanNumber() == linearScanOrder.indexOf(begin) : "incorrect linearScanNumber";
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	481 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
2674 6ab73784566a * BlockBegin.predecessors changed to List<BlockEnd> Lukas Stadler <lukas.stadler@jku.at> parents: 2657 diff changeset	482 assert cur.linearScanNumber() > begin.linearScanNumber() : "invalid order";
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	483 }
2718 c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	484 //if (cur.loopDepth() == begin.loopDepth()) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	485 // assert cur.loopIndex() == begin.loopIndex() \|\| cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	486 //}
2507 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
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	490 // check that all loops are continuous
2718 c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	491 // for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	492 // int blockIdx = 0;
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	493 // assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop";
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	494 //
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	495 // // skip blocks before the loop
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	496 // while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	497 // blockIdx++;
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	498 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	499 // // skip blocks of loop
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	500 // while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	501 // blockIdx++;
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	502 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	503 // // after the first non-loop block : there must not be another loop-block
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	504 // while (blockIdx < numBlocks) {
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	505 // assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order";
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	506 // blockIdx++;
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	507 // }
c1ce2a53d6c3 Attempt to remove dependency between backend and BlockBegin. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2717 diff changeset	508 // }
2507 9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	509
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	510 return true;
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	511 }
9ec15d6914ca Pull over of compiler from maxine repository. Thomas Wuerthinger <thomas@wuerthinger.net> parents: diff changeset	512 }

Mercurial > hg > truffle

annotate graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2718:c1ce2a53d6c3