Page MenuHomePhabricator

Faster SimplifyInstructionsInBlock

Authored by escha on Sep 22 2015, 11:52 AM.



From the original RFC:

  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.

One small change since the original is fix a bug where we were adding the users to the list even if they were the current instruction, which is possible with phi nodes (and causes a crash).

Diff Detail


Event Timeline

escha updated this revision to Diff 35400.Sep 22 2015, 11:52 AM
escha retitled this revision from to Faster SimplifyInstructionsInBlock.
escha updated this object.
escha set the repository for this revision to rL LLVM.
escha added a subscriber: llvm-commits.
reames added inline comments.Sep 22 2015, 2:09 PM

You need to pass in TLI here or you have a regression over the previous code when handling target library routines.


Use a foreach operands loop here.

Actually, the style used in RecursivelyDeleteTriviallyDeadInstructions is probably preferable here. It doesn't need the extra Operands array.


I think this should just be an assert at the top of the function. Or at least, if you're going to handle this in one case, handle it in the dead instruction case as well.


This remove seems problematic. Isn't this potentially O(n^2) in the instructions in the BB? Or is the argument that we're walking through the BB in an order where they shouldn't generally be in the Worklist?

Would it be cleaner/safer to use a SmallSetVector of Weak Value Handles and then just skip the deleted nodes?

Or alternatively, just not visit the instruction here if it's already in the worklist?

escha added inline comments.Sep 22 2015, 4:23 PM

Ah, right, I missed that. Will fix.


Ah, I see, that should work.


Okay, I was just matching the original code; I didn't quite understand what it's there for?


Removal from a SmallSetVector should be fast, shouldn't it?

Also, one of the main problems I encountered earlier is specifically that WeakVHs are *incredibly slow* and constructing them took a large portion of this function's time.

escha updated this revision to Diff 35437.Sep 22 2015, 4:26 PM

Updated per comments.

reames added inline comments.Sep 22 2015, 4:39 PM

I don't know. If the assert doesn't fail, it clearly wasn't tested or used.


Why would removing from a SmallSetVector be fast? It appears to be doing an erase on the underlying vector which is needed to preserve order.

Does simply skipping the instruction if it's already in the worklist work? That should be pretty fast.

escha updated this revision to Diff 35442.Sep 22 2015, 4:45 PM

Avoiding using remove() on the setvector.

reames accepted this revision.Sep 22 2015, 4:52 PM
reames edited edge metadata.

LGTM w/one minor comment, but please give it a day or so in case anyone else spots something I've missed.


please use std::prev instead of -- here. Makes it more clear what's going on.

This revision is now accepted and ready to land.Sep 22 2015, 4:52 PM
escha closed this revision.Sep 28 2015, 11:57 AM