[LLVMdev] Question regarding basic-block placement optimization

[Evan Cheng]

On Oct 19, 2011, at 7:56 AM, Jakob Stoklund Olesen wrote:

> 
> On Oct 19, 2011, at 5:50 AM, Chandler Carruth wrote:
> 
>> Ok, wow that wasn't hard at all.
> 
> Awesome ;-)
> 
>> This is still *very* much a rough draft, but it's probably better to review that the previous patch. One big caveat, I know I have an iteration bug in here somewhere that is inf-looping. Just ran out of steam debugging it, will pick it back up again later today to shake it out.
> 
> Maybe splicing a block into it current position will create a loop?
> 
> Some random notes:
> 
> - Please add a description of the algorithm.
> - Please add a comment to the BlockChain class.
> - Use a separate anonymous namespace per class, and don't indent for the namespace.
> 
> +BlockChain *BlockPlacement2::CreateChain(MachineBasicBlock *BB) {
> +  Chains.push_back(BlockChain(BlockToChain, BB));
> +  BlockToChain[BB] = &Chains.back();
> +  assert(ActiveChains.insert(&Chains.back()));
> +  return &Chains.back();
> +}
> 
> Whoa, you are storing pointers into a growing vector. You should at least assert(Chains.size() != Chains.capacity()) before pushing.
> 
> +      RequiredChain->BBEnd = ++MachineFunction::iterator(From);
> 
> Does C++ allow this these days? I would prefer llvm::next(MachineFunction::iterator(From))
> 
> Note that MachineFunction::iterator decays into an MBB pointer, so you can say FI->canFallThrough() and AnalyzeBranch(*FI...)
> 
> +      WeightedEdge WE = { BaseFrequency * MBPI->getEdgeProbability(From, To),
> 
> Did we add API for this computation? We intended to add a function that computes this and saturates on overflow etc.
> 
>> Still, for the test cases that don't tickle the iteration bug, it generates beautiful, well laid out code. =]
> 
> I am sure others have strong opinions about the algorithm ;-)
> 
> I would like to see a more explicit handling of loop layout. There is a tradeoff between entering the loop with a branch, and having the exit block last. It is not clear to me that this algorithm handles that properly.

I agree. The current CodePlacementOpt pass handles blocks layout within a loop. The new BB placement optimization should be integrated with it. 

Evan

> 
> Be careful about placing too much trust in the behavior of branch probabilities. They go out of whack when they saturate.
> 
> Second, you should handle blocks that can never fall through (indirect branches from jump tables). There is no need to try to place their successors.
> 
> /jakob
> 
> 
> 
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev