Remove unnecessary IDom check

[trentxintong]

Summary

This Idom check seems unnecessary. The immediate children of a node on the Dominator Tree should always be the IDom of its immediate children in this case.

[trentxintong]

Gentle ping ? I will close this patch if no one is interested in Sink.cpp anymore.

[davide]

Sink.cpp

172 ↗

(On Diff #78822)

Add a comment here to explain why you don't need to check.

[trentxintong]

Address davide's comment

[• dberlin]

lib/Transforms/Scalar/Sink.cpp

174 ↗

(On Diff #92295)

I wouldn't even bother with this assert.
Just remove it and commit.

Honestly, this whole code is silly.

If you want to take a whack at it, the proper (IMHO) way to do this is:

ncdblock = find nearestcommondominator(blocks that contain uses)

If ncdblock == Inst->getParent(), stop, can't sink.
Otherwise,
while (!AcceptableTarget(Inst, ncdblock) && ncdblock != Inst->getParent())
, NCDBlock = getIDom(NCDBlock);

This will sink as low as possible.
You can then remove the allusesdominatedbyblock check from IsAcceptableTarget. Any idom of the ncd must, by definition, still dominate the uses.
Note that when computing NearestCommonDominator(uses), phi uses have to be considered to live at the end of the incoming block they come from to get optimal results.

[• dberlin]

(Though note, it's probably the case that few people care about Sink.cpp anymore)

[trentxintong]

lib/Transforms/Scalar/Sink.cpp

174 ↗

(On Diff #92295)

Thats what I have in mind as well. However, this would work well for sinking SSA values, but not memory reading/writing instructions.

Sink.cpp has some simple abilities to sink loads and stores.

[trentxintong]

lib/Transforms/Scalar/Sink.cpp

174 ↗

(On Diff #92295)

By SSA values I meant instructions without reading/writing to memory.

[• dberlin]

lib/Transforms/Scalar/Sink.cpp

174 ↗

(On Diff #92295)

If we cared, we'd just run MemorySSA, and for loads/stores, and then you have the SSA form you need to sink stores

[trentxintong]

Address comments.

[trentxintong]

Ok, I have not had the time to look at the MemorySSA work (I have plan to get to it in the near future). I will land this for now. This pass probably needs to be significantly changed (essentially rewritten) later if we need it.

llvm/trunk/lib/Transforms/Scalar/Sink.cpp

static bool SinkInstruction(Instruction *Inst,
   // and z and only shrink the live range of x.
 
   // SuccToSinkTo - This is the successor to sink this instruction to, once we
   // decide.
   BasicBlock *SuccToSinkTo = nullptr;
 
   // Instructions can only be sunk if all their uses are in blocks
   // dominated by one of the successors.
-  // Look at all the postdominators and see if we can sink it in one.
+  // Look at all the dominated blocks and see if we can sink it in one.
   DomTreeNode *DTN = DT.getNode(Inst->getParent());
   for (DomTreeNode::iterator I = DTN->begin(), E = DTN->end();
       I != E && SuccToSinkTo == nullptr; ++I) {
     BasicBlock *Candidate = (*I)->getBlock();
-    if ((*I)->getIDom()->getBlock() == Inst->getParent() &&
-        IsAcceptableTarget(Inst, Candidate, DT, LI))
+    // A node always immediate-dominates its children on the dominator
+    // tree.
+    if (IsAcceptableTarget(Inst, Candidate, DT, LI))
       SuccToSinkTo = Candidate;
   }
 
   // If no suitable postdominator was found, look at all the successors and
   // decide which one we should sink to, if any.
   for (succ_iterator I = succ_begin(Inst->getParent()),
       E = succ_end(Inst->getParent()); I != E && !SuccToSinkTo; ++I) {
     if (IsAcceptableTarget(Inst, *I, DT, LI))