[llvm-dev] RFC: faster simplifyInstructionsInBlock/SimplifyInstructions pass

[Philip Reames via llvm-dev]

This seems like a useful change to me. Why don't you post it for review 
on llvm-commits?

This seems rather similar to both 
RecursivelyDeleteTriviallyDeadInstructions and 
replaceAndRecursivelySimplifyImpl.  I think at least your single user 
trick should be applied to those as well.  Given how similar all three 
are, I'm be tempted to common them into a common implementation.

Philip



On 09/13/2015 09:03 AM, escha via llvm-dev wrote:
> LLVM has two similar bits of infrastructure: a 
> simplifyInstructionsInBlock function and a SimplifyInstructions pass, 
> both intended to be lightweight “fix up this code without doing 
> serious optimizations” functions, as far as I can tell. I don’t think 
> either is used in a performance-sensitive place in-tree; the former is 
> mostly called in minor places when doing CFG twiddling, and the latter 
> seems to be for testing purposes.
>
> However, in our out-of-tree code, I found we were calling 
> simplifyInstructionsInBlock on the entire function to clean things up 
> before another pass. This turns out to be quite costly: the function 
> is not very efficient, tends to revisit instructions more than is 
> necessary, and spends a lot of time constructing weak handles and 
> handling its worklists. I wrote a new version of it that is about ~3x 
> faster and reduced our total compilation time by about 2%. The new 
> version is very very fast: it’s a full-function simplify-and-DCE that 
> looks to be about twice as fast as comparatively “fast” passes like 
> ADCE — fast enough that I can imagine plopping it down in a pipeline 
> pretty much wherever is relevant.
>
> Would anyone be interested in having this in LLVM? It could be a 
> replacement for simplifyInstructionsInBlock, a replacement for 
> SimplifyInstructionsPass, or whatever else is reasonable; I’m mostly 
> just not sure where to put it, and want to be sure it’d be useful to 
> someone (given the current comparative lack of use of this code 
> in-tree). It -should- be NFC compared to simplifyInstructionsInBlock 
> other than running per-function instead of per-block (which can be 
> easily changed, I just made it per-function since that’s what was most 
> useful to us).
>
> —escha
>
> P.S. Here’s the code. The main optimizations here are:
> 1. Use a worklist, not a recursive approach, to avoid needless 
> revisitation and being repeatedly forced to jump back to the start of 
> the BB if a handle is invalidated.
> 2. Only insert operands to the worklist if they become unused after a 
> dead instruction is removed, so we don’t have to visit them again in 
> most cases.
> 3. Use a SmallSetVector to track the worklist.
> 4. Instead of pre-initting the SmallSetVector like in 
> DeadCodeEliminationPass, only put things into the worklist if they 
> have to be revisited after the first run-through. This minimizes how 
> much the actual SmallSetVector gets used, which saves a lot of time.
>
> static bool simplifyAndDCEInstruction(Instruction *I,
> SmallSetVector<Instruction *, 16> &WorkList,
> const DataLayout &DL) {
> if(isInstructionTriviallyDead(I, nullptr)) {
> // Loop over all of the values that the instruction uses. If there are
> // instructions being used, add them to the worklist, because they might
> // go dead after this one is removed.
> SmallVector<Instruction *, 8> Operands;
> for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI)
> if (Instruction *Used = dyn_cast<Instruction>(*OI))
>         Operands.push_back(Used);
>
> // Remove the instruction.
>     I->eraseFromParent();
>
> // Only add the operands to the worklist if their uses are now empty,
> // to avoid needlessly revisiting instructions.
> for (auto U : Operands)
> if (U->use_empty())
>         WorkList.insert(U);
>
> returntrue;
>   }
>
> if (Value *SimpleV = SimplifyInstruction(I, DL)) {
> // Add the users to the worklist.
> for (User *U : I->users())
>       WorkList.insert(cast<Instruction>(U));
>
> // Replace the instruction with its simplified value.
>     I->replaceAllUsesWith(SimpleV);
>
> // Gracefully handle edge cases where the instruction is not wired 
> into any
> // parent block.
> if (I->getParent())
>       I->eraseFromParent();
> returntrue;
>   }
> returnfalse;
> }
>
> // A faster version of SimplifyInstructionsInBlock, designed for a whole
> // function. Modelled after DeadCodeEliminationPass.
> static bool simplifyAndDCEFunction(Function &F) {
> bool MadeChange = false;
> constDataLayout&DL = F.getParent()->getDataLayout();
>
> SmallSetVector<Instruction *, 16> WorkList;
> // Iterate over the original function, only adding insts to the worklist
> // if they actually need to be revisited. This avoids having to pre-init
> // the worklist with the entire function's worth of instructions.
> for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
> Instruction *I = &*FI;
>     ++FI;
>
> // We're visiting this instruction now, so make sure it's not in the
> // worklist from an earlier visit.
>     WorkList.remove(I);
>     MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL);
>   }
>
> while (!WorkList.empty()) {
> Instruction *I = WorkList.pop_back_val();
>     MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL);
>   }
> return MadeChange;
> }
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150914/42599ba5/attachment-0001.html>