I've looked at the patch one more time more carefully, it looks good to me!

Thanks for working on this! From the description the approach looks correct and promising. I glanced through the patch, and it looked good, but if you don't mind I'd like to have another look.

Thanks, Brian!

do you happen to know why?

The difference compared to the old SSAUpdater is in how we handled uses and defs located in the same block - it did not lead to a problem with the old SSAUpdater, but was unnecessary anyway, since such uses don't need to be rewritten (not in general, but in this particular case when the use is still dominated by its existing def).

Could anyone review this fix please?

Is there some way to figure out what exactly got slower (it could be SCEV or some user of SCEV)?

Not really at the moment.

Hi Justin,

What are benchmarks results with this pass (compile-time/performance)? Do we really need it at all optlevels, or can we only include it at -O3?

Looks correct to me.

Looks good to me! (+ a couple of nitpicks inline)

I thought about this transformation more, and I no longer think that we even need to move it to aggressive-instcombine (or another FunctionPass). What we need is to just change it from top-down to bottom-up: i.e. to start looking not from phi-nodes, but rather from inttoptr instructions. That is, the algorithm would look like:

visitIntToPtr(Instruction &I) {
  Value *Def = I.getOperand()
  if (!Def.hasSingleUse())
     return;
  if (isa<PtrToInt>(Def)) {   // Simple case without phi - it's probably already handled somewhere else, but I'm putting it here for completeness
     I.replaceAllUsesWith(Def.getOperand());
  }
  if (isa<PHINode>(Def)) {    // Interesting case where we have a phi-node
     if (all operands are PtrToInt with a single use) {
       NewPHI = RewritePHI();
       I.replaceAllUsesWith(NewPHI);
    }
  }
}

What do you think? Would it work?

Hi David,

Do you mind adding a TODO note describing the problem and another way to fix it? Otherwise, LGTM.

Thanks!

Thanks!

Thanks, Daniel! A fix for IDF was posted for review in D46646. If that fix is accepted, we should no longer need the current patch. Also, we should be able to remove blocks sorting from MemorySSA.

The solution in IDF should just be changing domtreenodepair to a tuple, with the last item being domtreenode->getDFSNumIn()

Just to make sure I understand you correctly: we need to change pair<DomTreeNode *, unsigned> to tuple<DomTreeNode *, unsigned, unsigned> and use the second and third elements as keys for the priority queue (i.e. we will need to implement a compare function for it, which will look at RootLevel first and at DfsNumber second if RootLevels are the same). Is it what you meant?

This patch includes two pieces: fixing non-determinism in SSAUpdaterBulk and enabling it in JumpThreading. When approved, I'll commit them separately, but I included them both here for convenience. The fix for SSAUpdaterBulk requires basic-block enumeration, which should be passed from the SSAUpdaterBulk user, and thus it incurs the corresponding changes in JumpThreading. I'm not a big fan of an extra parameter in RewriteAllUses function and will be happy to discuss alternative, but for now I followed an example from MemorySSA. What do you think?

I meant to LGTM it provided @dberlin didn't have objections.

Looks good to me now, thanks!

I looked deeper into this, and I think you exposed several issues here:

Ok, I will make an attempt to reduce it further, but if there was an easy way to trigger the problem, then I guess we would have seen it a long time ago (and bugpoint would have been able to remove some more basic blocks).
If it is preferred, then I can remove all the checks and keep it as a "just check that this no longer asserts" kind of test.

Yes, it is much preferred, thank you! If we have more than one problem here, then we need more small tests, but not one huge test.

First of all, please clean-up the testcase. The bugpoint-output tests are impossible to understand and maintain (it is impossible to say if such a test checks anything at all after some time). I'm pretty sure you can expose the same issue with much a smaller test.