[CVP] Replace incoming values from unreachable blocks with undef

[davide]

Summary

This is an attempt of fixing PR35807.
Due to the non-standard definition of dominance in LLVM, where uses in unreachable blocks are dominated by anything, you can have, in an unreachable block

%patatino = OP1 %patatino, CONSTANT

When SimplifyInstruction receives a PHI where an incoming value is of the aforementioned form, in some cases, loops indefinitely (see the stack trace in the PR). I, pretty honestly, tried to figure out what was wrong in ValueTracking and it seems cause a loop, but I wasn't really able to get to the bottom of it as SimplifyInstruction/ValueTracking recently became a big mess.

What I propose here instead is keeping track of the incoming values from unreachable blocks, and replacing them with undef. This fixes this case, and it seems to be good regardless (even if we can't prove that the value is constant, as it's coming from an unreachable block, we can ignore it).

OTOH, I don't want to paper over the issue, so if somebody feels brave enough to take a look, I'll abandon this (although it might go in for the reasons explained above).

I experimented using a domtree to query reachability rather than RPOT, but it doesn't seem to make a difference for compile time even for large test cases(where we spend a decent fraction of time in CVP).

[anna]

What I propose here instead is keeping track of the incoming values from unreachable blocks, and replacing them with undef. This fixes this case, and it seems to be good regardless (even if we can't prove that the value is constant, as it's coming from an unreachable block, we can ignore it).

LGTM - this was also the design I went with (change incoming values from unreachable blocks to undef) when we didn't want to break the structure of the loop in loop deletion.

[anna]

LGTM w/ comments.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

134 ↗

(On Diff #128886)

The reasons for this code here is 2 fold right:

1. avoid querying LVI for unreachable block BB
2. transforming the incoming value so that transformation further below don't mess around with such IR in unreachable blocks.

It's really #2 that fixes this issue. #1 just avoids unnecessary work.

I agree that this change by itself is a good one to have (it also has the side effect of avoiding IR pattern in *this single* instance of SimplifyInstruction).

test/Transforms/CorrelatedValuePropagation/pr35807.ll

41 ↗

(On Diff #128886)

All of these are unreachable blocks, could you pls rename them or perhaps add a comment on bb14 stating its unreachable block.

[efriedma]

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

336

This call invalidates the set of reachable blocks.

[davide]

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

336

hmmm, this is annoying.
I can't think of an easy way of handling this case easily. Do you have something in your mind?
If not, I'll revert the patch for now until I come up with a better idea.
cc: @anna

[efriedma]

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

336

Maybe you could use an incrementally updated domtree to keep ReachableBlocks up-to-date? Not sure how expensive that would be, though.

Alternatively, you could record dead edges, and postpone actually modifying the CFG until the end of the pass. You lose a little optimization power that way, I guess, but it avoids any complicated incremental updates.

[davide]

thanks, I'll give this a shot when I have a minute to dedicate to llvm.

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

 //===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Correlated Value Propagation pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
   S->replaceAllUsesWith(ReplaceWith);
   S->eraseFromParent();
 
   ++NumSelects;
 
   return true;
 }
 
-static bool processPHI(PHINode *P, LazyValueInfo *LVI,
-                       const SimplifyQuery &SQ) {
+static bool processPHI(PHINode *P, LazyValueInfo *LVI, const SimplifyQuery &SQ,
+                       DenseSet<BasicBlock *> &ReachableBlocks) {
   bool Changed = false;
 
   BasicBlock *BB = P->getParent();
   for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
     Value *Incoming = P->getIncomingValue(i);
     if (isa<Constant>(Incoming)) continue;
 
-    Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
+    // If the incoming value is coming from an unreachable block, replace
+    // it with undef and go on. This is good for two reasons:
+    // 1) We skip an LVI query for an unreachable block
+    // 2) We transform the incoming value so that the code below doesn't
+    //    mess around with IR in unreachable blocks.
+    BasicBlock *IncomingBB = P->getIncomingBlock(i);
+    if (!ReachableBlocks.count(IncomingBB)) {
+      P->setIncomingValue(i, UndefValue::get(P->getType()));
+      continue;
+    }
+
+    Value *V = LVI->getConstantOnEdge(Incoming, IncomingBB, BB, P);
 
     // Look if the incoming value is a select with a scalar condition for which
     // LVI can tells us the value. In that case replace the incoming value with
     // the appropriate value of the select. This often allows us to remove the
     // select later.
     if (!V) {
       SelectInst *SI = dyn_cast<SelectInst>(Incoming);
       if (!SI) continue;
for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
 
     // Increment the case iterator since we didn't delete it.
     ++CI;
   }
 
   if (Changed)
     // If the switch has been simplified to the point where it can be replaced
     // by a branch then do so now.
     ConstantFoldTerminator(BB);
 
   return Changed;
 }
 
 // See if we can prove that the given overflow intrinsic will not overflow.
 static bool willNotOverflow(IntrinsicInst *II, LazyValueInfo *LVI) {
   using OBO = OverflowingBinaryOperator;
   auto NoWrap = [&] (Instruction::BinaryOps BinOp, unsigned NoWrapKind) {
static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) {
   
   return (Result == LazyValueInfo::True) ?
     ConstantInt::getTrue(C->getContext()) :
     ConstantInt::getFalse(C->getContext());
 }
 
 static bool runImpl(Function &F, LazyValueInfo *LVI, const SimplifyQuery &SQ) {
   bool FnChanged = false;
+
+  // Compute reachability from the entry block of this function via an RPO
+  // walk. We use this information when processing PHIs.
+  DenseSet<BasicBlock *> ReachableBlocks;
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+  for (BasicBlock *BB : RPOT)
+    ReachableBlocks.insert(BB);
+
   // Visiting in a pre-order depth-first traversal causes us to simplify early
   // blocks before querying later blocks (which require us to analyze early
   // blocks).  Eagerly simplifying shallow blocks means there is strictly less
   // work to do for deep blocks.  This also means we don't visit unreachable
   // blocks.
   for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
     bool BBChanged = false;
     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
       Instruction *II = &*BI++;
       switch (II->getOpcode()) {
       case Instruction::Select:
         BBChanged |= processSelect(cast<SelectInst>(II), LVI);
         break;
       case Instruction::PHI:
-        BBChanged |= processPHI(cast<PHINode>(II), LVI, SQ);
+        BBChanged |= processPHI(cast<PHINode>(II), LVI, SQ, ReachableBlocks);
         break;
       case Instruction::ICmp:
       case Instruction::FCmp:
         BBChanged |= processCmp(cast<CmpInst>(II), LVI);
         break;
       case Instruction::Load:
       case Instruction::Store:
         BBChanged |= processMemAccess(II, LVI);

llvm/trunk/test/Transforms/CorrelatedValuePropagation/pr35807.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -correlated-propagation -S %s | FileCheck %s
+
+target triple = "x86_64-apple-darwin17.4.0"
+
+define void @patatino() {
+; CHECK-LABEL: @patatino(
+; CHECK-NEXT:    br i1 undef, label [[BB3:%.*]], label [[BB4:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br i1 undef, label [[BB40:%.*]], label [[BB22:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB14:%.*]]
+; CHECK:       bb12:
+; CHECK-NEXT:    br label [[BB14]]
+; CHECK:       bb14:
+; CHECK-NEXT:    [[TMP19:%.*]] = icmp sgt i32 undef, undef
+; CHECK-NEXT:    [[TMP20:%.*]] = select i1 [[TMP19]], i64 [[TMP20]], i64 0
+; CHECK-NEXT:    br i1 undef, label [[BB40]], label [[BB7:%.*]]
+; CHECK:       bb22:
+; CHECK-NEXT:    br label [[BB24:%.*]]
+; CHECK:       bb24:
+; CHECK-NEXT:    br label [[BB32:%.*]]
+; CHECK:       bb32:
+; CHECK-NEXT:    br i1 undef, label [[BB40]], label [[BB24]]
+; CHECK:       bb40:
+; CHECK-NEXT:    ret void
+;
+  br i1 undef, label %bb3, label %bb4
+
+bb3:
+  br label %bb3
+
+bb4:
+  br i1 undef, label %bb40, label %bb22
+
+bb7:
+  br label %bb14
+
+bb12:
+  br label %bb14
+
+; This block is unreachable. Due to the non-standard definition of
+; dominance in LLVM where uses in unreachable blocks are dominated
+; by anything, it contains an instruction of the form
+; %def = OP %def, %something
+bb14:
+  %tmp19 = icmp sgt i32 undef, undef
+  %tmp20 = select i1 %tmp19, i64 %tmp20, i64 0
+  br i1 undef, label %bb40, label %bb7
+
+bb22:
+  br label %bb24
+
+bb24:
+  br label %bb32
+
+bb32:
+  br i1 undef, label %bb40, label %bb24
+
+bb40:
+  %tmp41 = phi i64 [ 4, %bb4 ], [ %tmp20, %bb14 ], [ undef, %bb32 ]
+  ret void
+}