scale.backend.trips2
Class BlockSplitter

java.lang.Object
  scale.backend.trips2.BlockSplitter

public class BlockSplitter
extends java.lang.Object

This class can determine if a block is a legal TRIPS block and can cut a block so that it meets the TRIPS block constraints.

$Id: BlockSplitter.java,v 1.36 2007-10-04 19:57:58 burrill Exp $

Copyright 2008 by the Scale Compiler Group,
Department of Computer Science
University of Massachusetts,
Amherst MA. 01003, USA
All Rights Reserved.

BLOCK CUTTING HEURISTIC

The following heuristic is used to cut blocks:

Blocks are cut so that the number of instructions in the block does not exceed the maximum TRIPS block size. Block size is determined by,

total block size = # instructions + estimated fanout

The block is cut into N parts with,

N = total block size / maximum TRIPS block size + 1

Blocks are also cut based on the number of loads and stores. The first instruction in the new block, is the load/store that exceeded the maximum number of loads and stores in the original block or the instruction which would make the block exceed 128 instructions. The original block will be cut as many times as necessary to enforce these limits.

FAN OUT

We base our estimate of fanout on the number of targets an instruction can have. If an instruction uses a register and the defining instruction (the instruction which defines the register) has no more available targets, we need to insert fanout. Note, we don't actually insert anything into the codestream. We just track the number of instructions that we would insert.

For example,

   addi $t1, $t2, 7     // $t1 defined
   sub  $t4, $t1, $t5   // $t1 used
   sub  $t6, $t1, $t7   // $t1 used
 

Here $t1 is defined by the "addi" instruction, which can only target one other instruction. There are two uses of $t1, so a "mov" must be inserted to forward the value of $t1 to the second "sub". The "mov" is inserted by the TRIPS scheduler.

Our algorithm (derived from the scheduler's) computes fanout as,

fanout = total # targets - # targets for instruction

The difference between the algorithm here and the one in the scheduler is that this algorithm does not use mov3 or mov4 instructions in the approximation.

REVERSE IF-CONVERSION

TODO

SPILL CODE

During register allocation, spill code may be inserted. The spills can cause the number of instructions in a block to exceed the maximum block size. They may also cause the number of load/store queue ids to exceed their limit. To handle this we re-run the block splitter after register allocation on the set of hyperblocks that contain spills.

The block cutting algorithm for spills is different than the normal algorithm. The main differences are that we do not go into SSA form and that the block cutter removes all spill code from the hyperblocks. The reason we remove the spill code is that the register allocator is going to re-run and it will re-insert any required spill code at that time.

READ AND WRITE INSTRUCTIONS

The block cutter does not handle read and write instructions at this time. We use liveness information during the analysis phase to determine what the read and write instructions would be.

Constructor Summary

BlockSplitter(Trips2Generator gen)
The constructor.

Method Summary

static int	blocksReverseIfConverted() Return the number of blocks reverse if-converted.
static HashMap<Instruction,Hyperblock>	computeEntries(Hyperblock hbStart, Vector<Hyperblock> hbs) Compute the entry points for a list of hyperblocks to be inserted into the HFG.
void	split(Hyperblock hbStart) The main routine for block splitting.
boolean	splitBlocksWithSpills(Hyperblock hbStart, Vector<Hyperblock> blocks) This routine is called to split blocks during register allocation.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BlockSplitter

public BlockSplitter(Trips2Generator gen)

The constructor.

Method Detail

blocksReverseIfConverted

public static int blocksReverseIfConverted()

Return the number of blocks reverse if-converted.

split

public final void split(Hyperblock hbStart)

The main routine for block splitting.

splitBlocksWithSpills

public final boolean splitBlocksWithSpills(Hyperblock hbStart,
                                           Vector<Hyperblock> blocks)

This routine is called to split blocks during register allocation. At this point we know that the block was legal before the spill stores and loads were inserted. For every hyperblock with spills that is no longer legal, we pick its largest predicate block and split that in half. One half is then placed into a new hyperblock.

The case that was causing trouble results from the classic diamond-shaped predicate flow graph:

     a
    / \
   b   c
    \ /
     d
 

where predicate block a contains most of the instructions, blocks b and c each contain a predicated branch, and block d is empty. Because of spilling, the hyperblock was too big but all of the predicate blocks were legal. As a result we attempted to split block d which did no good.

Parameters:

blocks - is a list of hyperblocks that have had spills inserted

Returns:

true if a block was split

computeEntries

public static HashMap<Instruction,Hyperblock> computeEntries(Hyperblock hbStart,
                                                             Vector<Hyperblock> hbs)

Compute the entry points for a list of hyperblocks to be inserted into the HFG. This method also removes the link between hbStart and all its successors.