It would go something like like the code below. The goal would be to
turn the basic blocks which the graph looks like
"...->x->y->..."
where the instructions of x and y could live in the same basic block
without a jump or fall through in between.
bool runOnMachineFunction(MachineFunction &mf) {
BitVector seen( mf.size() );
for( unsigned i = 0, e = mf.size(); i != e; ++i ) {
if( seen[i] )
continue;
seen[i] = true;
MachineBasicBlock * start, *block;
start = block = mf.getBlockNumbered(i);
std::vector< MachineBasicBlock* > blocks;
while( block->succ_size() == 1 &&
(*block->succ_begin())->pred_size() == 1 ) {
block = *block->succ_begin();
seen[block->getNumber()] = true;
blocks.push_back( block );
}
// TODO:
// For each basic block bb in blocks in order of insersion:
// 1. Remove basic blocks in the block vector from the machine function.
// 2. Remove the jump from the start block if it exists.
// 3. Add the instruction from bb into the start block.
}
Thanks,
Jeff Kunkel
On Wed, Oct 6, 2010 at 7:49 PM, Bob Wilson <bob.wilson at apple.com>
wrote:>
> On Oct 6, 2010, at 4:31 PM, Jeff Kunkel wrote:
>
>> Has anyone written a pass at the MachineFunction level which combines
>> machine basic blocks which is guaranteed to be the single predecessor
>> to another block? Or is there a reason not to combine them?
>
> I'm not sure exactly what transformation you're referring to, but
BranchFolder::OptimizeBranches does a lot of things like that.
I thought that the BranchFolder pass already handled that. Did you check? On Oct 6, 2010, at 5:03 PM, Jeff Kunkel wrote:> It would go something like like the code below. The goal would be to > turn the basic blocks which the graph looks like "...->x->y->..." > where the instructions of x and y could live in the same basic block > without a jump or fall through in between. > > bool runOnMachineFunction(MachineFunction &mf) { > BitVector seen( mf.size() ); > for( unsigned i = 0, e = mf.size(); i != e; ++i ) { > if( seen[i] ) > continue; > seen[i] = true; > MachineBasicBlock * start, *block; > start = block = mf.getBlockNumbered(i); > std::vector< MachineBasicBlock* > blocks; > while( block->succ_size() == 1 && > (*block->succ_begin())->pred_size() == 1 ) { > block = *block->succ_begin(); > seen[block->getNumber()] = true; > blocks.push_back( block ); > } > // TODO: > // For each basic block bb in blocks in order of insersion: > // 1. Remove basic blocks in the block vector from the machine function. > // 2. Remove the jump from the start block if it exists. > // 3. Add the instruction from bb into the start block. > } > > Thanks, > Jeff Kunkel > > On Wed, Oct 6, 2010 at 7:49 PM, Bob Wilson <bob.wilson at apple.com> wrote: >> >> On Oct 6, 2010, at 4:31 PM, Jeff Kunkel wrote: >> >>> Has anyone written a pass at the MachineFunction level which combines >>> machine basic blocks which is guaranteed to be the single predecessor >>> to another block? Or is there a reason not to combine them? >> >> I'm not sure exactly what transformation you're referring to, but BranchFolder::OptimizeBranches does a lot of things like that.
I forgot to CC the forum. I found what was happening. The BranchFolder documentation says: // Note that this pass must be run after register allocation, it cannot handle // SSA form.> On Wed, Oct 6, 2010 at 8:05 PM, Jeff Kunkel <jdkunk3 at gmail.com> wrote: >> No, I just noticed that blocks were separated. >> >> >> On Wed, Oct 6, 2010 at 8:04 PM, Bob Wilson <bob.wilson at apple.com> wrote: >>> I thought that the BranchFolder pass already handled that. Did you check? >>> >>> On Oct 6, 2010, at 5:03 PM, Jeff Kunkel wrote: >>> >>>> It would go something like like the code below. The goal would be to >>>> turn the basic blocks which the graph looks like "...->x->y->..." >>>> where the instructions of x and y could live in the same basic block >>>> without a jump or fall through in between. >>>> >>>> bool runOnMachineFunction(MachineFunction &mf) { >>>> BitVector seen( mf.size() ); >>>> for( unsigned i = 0, e = mf.size(); i != e; ++i ) { >>>> if( seen[i] ) >>>> continue; >>>> seen[i] = true; >>>> MachineBasicBlock * start, *block; >>>> start = block = mf.getBlockNumbered(i); >>>> std::vector< MachineBasicBlock* > blocks; >>>> while( block->succ_size() == 1 && >>>> (*block->succ_begin())->pred_size() == 1 ) { >>>> block = *block->succ_begin(); >>>> seen[block->getNumber()] = true; >>>> blocks.push_back( block ); >>>> } >>>> // TODO: >>>> // For each basic block bb in blocks in order of insersion: >>>> // 1. Remove basic blocks in the block vector from the machine function. >>>> // 2. Remove the jump from the start block if it exists. >>>> // 3. Add the instruction from bb into the start block. >>>> } >>>> >>>> Thanks, >>>> Jeff Kunkel >>>> >>>> On Wed, Oct 6, 2010 at 7:49 PM, Bob Wilson <bob.wilson at apple.com> wrote: >>>>> >>>>> On Oct 6, 2010, at 4:31 PM, Jeff Kunkel wrote: >>>>> >>>>>> Has anyone written a pass at the MachineFunction level which combines >>>>>> machine basic blocks which is guaranteed to be the single predecessor >>>>>> to another block? Or is there a reason not to combine them? >>>>> >>>>> I'm not sure exactly what transformation you're referring to, but BranchFolder::OptimizeBranches does a lot of things like that. >>> >>> >> >