diff options
| -rw-r--r-- | lib/Transforms/Scalar/CorrelatedValuePropagation.cpp | 28 | ||||
| -rw-r--r-- | test/Transforms/CorrelatedValuePropagation/pr35807.ll | 65 |
2 files changed, 89 insertions, 4 deletions
diff --git a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp index 8f468ebf894..7b898a3943d 100644 --- a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -14,6 +14,7 @@ #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" @@ -120,8 +121,8 @@ static bool processSelect(SelectInst *S, LazyValueInfo *LVI) { 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(); @@ -129,7 +130,18 @@ static bool processPHI(PHINode *P, LazyValueInfo *LVI, 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 @@ -561,6 +573,14 @@ static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) { 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 @@ -575,7 +595,7 @@ static bool runImpl(Function &F, LazyValueInfo *LVI, const SimplifyQuery &SQ) { 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: diff --git a/test/Transforms/CorrelatedValuePropagation/pr35807.ll b/test/Transforms/CorrelatedValuePropagation/pr35807.ll new file mode 100644 index 00000000000..8f72b596d28 --- /dev/null +++ b/test/Transforms/CorrelatedValuePropagation/pr35807.ll @@ -0,0 +1,65 @@ +; 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 +} |