[MemCpyOpt] Skip optimizing basic blocks not reachable from entry

[bjope]

Summary

Skip basic blocks not reachable from the entry node
in MemCpyOptPass::iterateOnFunction.

Code that is unreachable may have properties that do not exist
for reachable code (an instruction in a basic block can for
example be dominated by a later instruction in the same basic
block, for example if there is a single block loop).
MemCpyOptPass::processStore is only safe to use for reachable
basic blocks, since it may iterate past the basic block
beginning when used for unreachable blocks. By simply skipping
to optimize unreachable basic blocks we can avoid asserts such
as "Assertion `!NodePtr->isKnownSentinel()' failed."
in MemCpyOptPass::processStore.

The problem was detected by fuzz tests.

[bjope]

Not sure who wants to review this patch (but Eli seems to have touched nearby code in the past, and Daniel made recent changes in the same method).

[efriedma]

This sort of thing gets very confusing; it would be better to explicitly reject unreachable blocks in MemCpyOptPass::iterateOnFunction.

[bjope]

In D45889#1073834, @efriedma wrote:

This sort of thing gets very confusing; it would be better to explicitly reject unreachable blocks in MemCpyOptPass::iterateOnFunction.

Ok. I'm not so familiar with this code and is not 100% sure that this only happens for unreachable blocks.
The processStore method can be invoked for store instructions that is first in reachable blocks as well, right? It was not obvious to me that we never could end up doing the --SI->getIterator() also for reachable code.
Maybe the check for that LI->getParent() == SI->getParent() and LoadInst *LI = dyn_cast<LoadInst>(SI->getOperand(0)) somehow will guarantee that.
But how is it guaranteed that C always is before SI when entering the loop?

I can try to add something in MemCpyOptPass::iterateOnFunction to avoid optimizing in non-reachable blocks instead. And then maybe I can add some asserts in processStore to show that SI can't be first in the BB somewhere before doing --SI->getIterator().

[efriedma]

C dominates LI because it's the result of getDependency. LI dominates SI because LI is an operand of SI. Therefore C dominates SI. LI and SI are in the same block because of the getParent() check. C is in the same block as LI because getDependency always returns an instruction in the same block. Therefore C and SI are in the same block. Given C and SI are in the same block, and C dominates SI, and the block is reachable, C must come before SI in the block (so SI can't be the first instruction in the block, and the loop will eventually terminate).

[bjope]

Update after comments from Eli. We now skip processing unreachable blocks.

[efriedma]

LGTM

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

bool MemCpyOptPass::processByValArgument(CallSite CS, unsigned ArgNo) {
   ++NumMemCpyInstr;
   return true;
 }
 
 /// Executes one iteration of MemCpyOptPass.
 bool MemCpyOptPass::iterateOnFunction(Function &F) {
   bool MadeChange = false;
 
+  DominatorTree &DT = LookupDomTree();
+
   // Walk all instruction in the function.
   for (BasicBlock &BB : F) {
+    // Skip unreachable blocks. For example processStore assumes that an
+    // instruction in a BB can't be dominated by a later instruction in the
+    // same BB (which is a scenario that can happen for an unreachable BB that
+    // has itself as a predecessor).
+    if (!DT.isReachableFromEntry(&BB))
+      continue;
+
     for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
         // Avoid invalidating the iterator.
       Instruction *I = &*BI++;
 
       bool RepeatInstruction = false;
 
       if (StoreInst *SI = dyn_cast<StoreInst>(I))
         MadeChange |= processStore(SI, BI);
       else if (MemSetInst *M = dyn_cast<MemSetInst>(I))
         RepeatInstruction = processMemSet(M, BI);

llvm/trunk/test/Transforms/MemCpyOpt/process_store.ll

+; RUN: opt < %s -memcpyopt -disable-output
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@b = common dso_local local_unnamed_addr global i32 0, align 4
+@a = common dso_local local_unnamed_addr global i32 0, align 4
+
+declare dso_local i32 @f1()
+
+; Do not crash due to store first in BB.
+define dso_local void @f2() {
+for.end:
+  %0 = load i32, i32* @b, align 4
+  ret void
+
+for.body:
+  store i32 %1, i32* @a, align 4
+  %call = call i32 @f1()
+  %cmp = icmp sge i32 %call, 0
+  %1 = load i32, i32* @b, align 4
+  br label %for.body
+}
+
+; Do not crash due to call not before store in BB.
+define dso_local void @f3() {
+for.end:
+  %0 = load i32, i32* @b, align 4
+  ret void
+
+for.body:
+  %t = add i32 %t2, 1
+  store i32 %1, i32* @a, align 4
+  %call = call i32 @f1()
+  %cmp = icmp sge i32 %call, 0
+  %1 = load i32, i32* @b, align 4
+  %t2 = xor i32 %t, 5
+  br label %for.body
+}