[InlineCost] Tracking Values through PHI Nodes

[haicheng]

Summary

This patch fix this FIXME in visitPHI()

// FIXME: We should potentially be tracking values through phi nodes,
// especially when they collapse to a single value due to deleted CFG edges
// during inlining.

To do this, I maintain two lists: dead blocks during inlining and a mapping of the blocks to their known successors. For example,

define i1 @outer9(i1 %cond) {             
  %C = call i1 @inner9(i32 0, i1 %cond)
  ret i1 %C
}
  
define i1 @inner9(i32 %cond1, i1 %cond2) {
entry:                         
  switch i32 %cond1, label %exit [ i32 0, label %zero
                                   i32 1, label %one
                                   i32 2, label %two ]
  
zero:
  br label %exit

one:   
  br label %exit    

two:
  br i1 %cond2, label %two_true, label %two_false
  
two_true: 
  br label %exit
              
two_false: 
  br label %exit
  
exit:
  %phi = phi i32 [0, %zero], [1, %one], [2, %two_true], [2, %two_false], [-1, %entry] ; Simplified to 0
  %cmp = icmp eq i32 %phi, 0
  call void @pad()
  store i32 0, i32* @glbl
  ret i1 %cmp
}

Blocks one, two, two_true, two_false are unreachable because of the deleted CFG edges. The successor of block entry has to be block zero so block entry must not be the predecessor of block exit during inlining. Thus, the phi node in block exit can be collapsed to a constant 0.

The algorithm used to find dead blocks is a simplified version from GVN::addDeadBlock(). Basically, if all the predecessors of a block are dead, this block is dead too.

This patch can reduce the inlinecost of the problematic callee of PR34173 from 235 to 65. The impact to spec is as follows

Benchmark	Code Size (%)	Perf (%)
	(+ is bigger)	(+ is faster)
spec2000/gcc	0.05	-0.39
spec2006/gcc	-0.04	-0.03
spec2006/h264ref	-0.05	0.15
spec2006/xalancbmk	0.05	-0.64
spec2017/blender	0.02	0.54
spec2017/gcc	0.04	0.03
spec2017/imagick	0.01	1.03
spec2017/perlbench	0.01	-0.04
spec2017/xalancbmk	0.04	0.29

[haicheng]

Kindly Ping.

[eraman]

Thanks for working on this!

lib/Analysis/InlineCost.cpp

167

nit: Kepp -> Keep

170

known successors -> known unique successors may be helpful here .

496

If you have a phi with null as one incoming value and a non-null pointer with a constant offset as the other incoming argument, this code would incorrectly treat the result of the phi as null. Inside the loop, both FirstC and FirstV will be non-null and after exiting the loop , SimplifiedValues[&I] will be set to FirstC.

1624

This doesn't consider the case where a dead block's successor S has a predecessor P that is not dead, but that predecessor P has a known successor that is not S. Why not extend 1630 below to

return DeadBlocks.count(P) || (KnownSuccessors[P] && KnownSuccessors[P] != S)

[haicheng]

Addressed Easwaran's comments and added two test cases. Thank you very much.

[haicheng]

Kindly Ping

[haicheng]

Kindly Ping (#2)

[eraman]

lib/Analysis/InlineCost.cpp

496

This version also suffers from the same issue if the order of the phi is reversed (you first see a non-null pointer with constant offset and then see the null). I think it will be easier to first check if you have seen a reachable incoming value and then check if it is constant or constant offset and then make sure the phi you see now is the same. Add a test case as well after fixing this.

[haicheng]

Address Easwaran's comments. Thank you very much.

[haicheng]

Kindly Ping.

[haicheng]

Kindly Ping (#2)

[haicheng]

Kindly Ping (#3)

[eraman]

LGTM

lib/Analysis/InlineCost.cpp

1632

You could move this above condition !DeadBlocks.count(S) && llvm::all_of(predecessors(S)...) to a lambda IsNewlyDead(BasicBlock *B) and then use that in line 1619 above (if (Succ == NextBB) || !IsNewlyDead(Succ)) continue; I prefer that but will leave it to you.

[haicheng]

Thank you very much, Easwaran. The new code looks much simpler. I will commit soon.

lib/Analysis/InlineCost.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   /// The mapping of caller Alloca values to their accumulated cost savings. If
   /// we have to disable SROA for one of the allocas, this tells us how much
   /// cost must be added.
   DenseMap<Value *, int> SROAArgCosts;
 
   /// Keep track of values which map to a pointer base and constant offset.
   DenseMap<Value *, std::pair<Value *, APInt>> ConstantOffsetPtrs;
 
+  /// Keep track of dead blocks due to the constant arguments.
+  SetVector<BasicBlock *> DeadBlocks;
+
+  /// The mapping of the blocks to their known unique successors due to the
+  /// constant arguments.
+  DenseMap<BasicBlock *, BasicBlock *> KnownSuccessors;
+
   // Custom simplification helper routines.
   bool isAllocaDerivedArg(Value *V);
   bool lookupSROAArgAndCost(Value *V, Value *&Arg,
                             DenseMap<Value *, int>::iterator &CostIt);
   void disableSROA(DenseMap<Value *, int>::iterator CostIt);
   void disableSROA(Value *V);
+  void findDeadBlocks(BasicBlock *CurrBB, BasicBlock *NextBB);
   void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
                           int InstructionCost);
   bool isGEPFree(GetElementPtrInst &GEP);
   bool canFoldInboundsGEP(GetElementPtrInst &I);
   bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
   bool simplifyCallSite(Function *F, CallSite CS);
   template <typename Callable>
   bool simplifyInstruction(Instruction &I, Callable Evaluate);
bool CallAnalyzer::visitAlloca(AllocaInst &I) {
   // a variety of reasons, and so we would like to not inline them into
   // functions which don't currently have a dynamic alloca. This simply
   // disables inlining altogether in the presence of a dynamic alloca.
   HasDynamicAlloca = true;
   return false;
 }
 
 bool CallAnalyzer::visitPHI(PHINode &I) {
-  // FIXME: We should potentially be tracking values through phi nodes,
-  // especially when they collapse to a single value due to deleted CFG edges
-  // during inlining.
-
   // FIXME: We need to propagate SROA *disabling* through phi nodes, even
   // though we don't want to propagate it's bonuses. The idea is to disable
   // SROA if it *might* be used in an inappropriate manner.
 
   // Phi nodes are always zero-cost.
+
+  APInt ZeroOffset = APInt::getNullValue(DL.getPointerSizeInBits());
+  bool CheckSROA = I.getType()->isPointerTy();
+
+  // Track the constant or pointer with constant offset we've seen so far.
+  Constant *FirstC = nullptr;
+  std::pair<Value *, APInt> FirstBaseAndOffset = {nullptr, ZeroOffset};
+  Value *FirstV = nullptr;
+
+  for (unsigned i = 0, e = I.getNumIncomingValues(); i != e; ++i) {
+    BasicBlock *Pred = I.getIncomingBlock(i);
+    // If the incoming block is dead, skip the incoming block.
+    if (DeadBlocks.count(Pred))
+      continue;
+    // If the parent block of phi is not the known successor of the incoming
+    // block, skip the incoming block.
+    BasicBlock *KnownSuccessor = KnownSuccessors[Pred];
+    if (KnownSuccessor && KnownSuccessor != I.getParent())
+      continue;
+
+    Value *V = I.getIncomingValue(i);
+    // If the incoming value is this phi itself, skip the incoming value.
+    if (&I == V)
+      continue;
+
+    Constant *C = dyn_cast<Constant>(V);
+    if (!C)
+      C = SimplifiedValues.lookup(V);
+
+    std::pair<Value *, APInt> BaseAndOffset = {nullptr, ZeroOffset};
+    if (!C && CheckSROA)
+      BaseAndOffset = ConstantOffsetPtrs.lookup(V);
+
+    if (!C && !BaseAndOffset.first)
+      // The incoming value is neither a constant nor a pointer with constant
+      // offset, exit early.
+      return true;
+
+    if (FirstC) {
+      if (FirstC == C)
+        // If we've seen a constant incoming value before and it is the same
+        // constant we see this time, continue checking the next incoming value.
+        continue;
+      // Otherwise early exit because we either see a different constant or saw
+      // a constant before but we have a pointer with constant offset this time.
+      return true;
+    }
+
+    if (FirstV) {
+      // The same logic as above, but check pointer with constant offset here.
+      if (FirstBaseAndOffset == BaseAndOffset)
+        continue;
+      return true;
+    }
+
+    if (C) {
+      // This is the 1st time we've seen a constant, record it.
+      FirstC = C;
+      continue;
+    }
+
+    // The remaining case is that this is the 1st time we've seen a pointer with
+    // constant offset, record it.
+    FirstV = V;
+    FirstBaseAndOffset = BaseAndOffset;
+  }
+
+  // Check if we can map phi to a constant.
+  if (FirstC) {
+    SimplifiedValues[&I] = FirstC;
+    return true;
+  }
+
+  // Check if we can map phi to a pointer with constant offset.
+  if (FirstBaseAndOffset.first) {
+    ConstantOffsetPtrs[&I] = FirstBaseAndOffset;
+
+    Value *SROAArg;
+    DenseMap<Value *, int>::iterator CostIt;
+    if (lookupSROAArgAndCost(FirstV, SROAArg, CostIt))
+      SROAArgValues[&I] = SROAArg;
+  }
+
   return true;
 }
 
 /// \brief Check we can fold GEPs of constant-offset call site argument pointers.
 /// This requires target data and inbounds GEPs.
 ///
 /// \return true if the specified GEP can be folded.
 bool CallAnalyzer::canFoldInboundsGEP(GetElementPtrInst &I) {
do {
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V).second);
 
   Type *IntPtrTy = DL.getIntPtrType(V->getContext());
   return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset));
 }
 
+/// \brief Find dead blocks due to deleted CFG edges during inlining.
+///
+/// If we know the successor of the current block, \p CurrBB, has to be \p
+/// NextBB, the other successors of \p CurrBB are dead if these successors have
+/// no live incoming CFG edges.  If one block is found to be dead, we can
+/// continue growing the dead block list by checking the successors of the dead
+/// blocks to see if all their incoming edges are dead or not.
+void CallAnalyzer::findDeadBlocks(BasicBlock *CurrBB, BasicBlock *NextBB) {
+  auto IsEdgeDead = [&](BasicBlock *Pred, BasicBlock *Succ) {
+    // A CFG edge is dead if the predecessor is dead or the predessor has a
+    // known successor which is not the one under exam.
+    return (DeadBlocks.count(Pred) ||
+            (KnownSuccessors[Pred] && KnownSuccessors[Pred] != Succ));
+  };
+
+  auto IsNewlyDead = [&](BasicBlock *BB) {
+    // If all the edges to a block are dead, the block is also dead.
+    return (!DeadBlocks.count(BB) &&
+            llvm::all_of(predecessors(BB),
+                         [&](BasicBlock *P) { return IsEdgeDead(P, BB); }));
+  };
+
+  for (BasicBlock *Succ : successors(CurrBB)) {
+    if (Succ == NextBB || !IsNewlyDead(Succ))
+      continue;
+    SmallVector<BasicBlock *, 4> NewDead;
+    NewDead.push_back(Succ);
+    while (!NewDead.empty()) {
+      BasicBlock *Dead = NewDead.pop_back_val();
+      if (DeadBlocks.insert(Dead))
+        // Continue growing the dead block lists.
+        for (BasicBlock *S : successors(Dead))
+          if (IsNewlyDead(S))
+            NewDead.push_back(S);
+    }
+  }
+}
+
 /// \brief Analyze a call site for potential inlining.
 ///
 /// Returns true if inlining this call is viable, and false if it is not
 /// viable. It computes the cost and adjusts the threshold based on numerous
 /// factors and heuristics. If this method returns false but the computed cost
 /// is below the computed threshold, then inlining was forcibly disabled by
 /// some artifact of the routine.
 bool CallAnalyzer::analyzeCall(CallSite CS) {
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
 
     // Add in the live successors by first checking whether we have terminator
     // that may be simplified based on the values simplified by this call.
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       if (BI->isConditional()) {
         Value *Cond = BI->getCondition();
         if (ConstantInt *SimpleCond =
                 dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
-          BBWorklist.insert(BI->getSuccessor(SimpleCond->isZero() ? 1 : 0));
+          BasicBlock *NextBB = BI->getSuccessor(SimpleCond->isZero() ? 1 : 0);
+          BBWorklist.insert(NextBB);
+          KnownSuccessors[BB] = NextBB;
+          findDeadBlocks(BB, NextBB);
           continue;
         }
       }
     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
       Value *Cond = SI->getCondition();
       if (ConstantInt *SimpleCond =
               dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
-        BBWorklist.insert(SI->findCaseValue(SimpleCond)->getCaseSuccessor());
+        BasicBlock *NextBB = SI->findCaseValue(SimpleCond)->getCaseSuccessor();
+        BBWorklist.insert(NextBB);
+        KnownSuccessors[BB] = NextBB;
+        findDeadBlocks(BB, NextBB);
         continue;
       }
     }
 
     // If we're unable to select a particular successor, just count all of
     // them.
     for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize;
          ++TIdx)

test/Transforms/Inline/AArch64/phi.ll

+; RUN: opt -inline -mtriple=aarch64--linux-gnu -S -o - < %s -inline-threshold=0 | FileCheck %s
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnu"
+
+declare void @pad()
+@glbl = external global i32
+
+define i1 @outer1() {
+; CHECK-LABEL: @outer1(
+; CHECK-NOT: call i1 @inner1
+  %C = call i1 @inner1()
+  ret i1 %C
+}
+
+define i1 @inner1() {
+entry:
+  br label %if_true
+
+if_true:
+  %phi = phi i1 [0, %entry], [%phi, %if_true] ; Simplified to 0
+  br i1 %phi, label %if_true, label %exit
+
+exit:
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  store i32 2, i32* @glbl
+  store i32 3, i32* @glbl
+  store i32 4, i32* @glbl
+  ret i1 %phi
+}
+
+
+define i1 @outer2(i1 %val) {
+; CHECK-LABEL: @outer2(
+; CHECK: call i1 @inner2
+  %C = call i1 @inner2(i1 %val)
+  ret i1 %C
+}
+
+define i1 @inner2(i1 %val) {
+entry:
+  br label %if_true
+
+if_true:
+  %phi = phi i1 [%val, %entry], [%phi, %if_true] ; Cannot be simplified to a constant
+  br i1 %phi, label %if_true, label %exit
+
+exit:
+  call void @pad()
+  ret i1 %phi
+}
+
+
+define i1 @outer3(i1 %cond) {
+; CHECK-LABEL: @outer3(
+; CHECK-NOT: call i1 @inner3
+  %C = call i1 @inner3(i1 %cond)
+  ret i1 %C
+}
+
+define i1 @inner3(i1 %cond) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32 [0, %entry], [0, %if_true] ; Simplified to 0
+  %cmp = icmp eq i32 %phi, 0
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  store i32 2, i32* @glbl
+  store i32 3, i32* @glbl
+  store i32 4, i32* @glbl
+  ret i1 %cmp
+}
+
+
+define i1 @outer4(i1 %cond) {
+; CHECK-LABEL: @outer4(
+; CHECK-NOT: call i1 @inner4
+  %C = call i1 @inner4(i1 %cond, i32 0)
+  ret i1 %C
+}
+
+define i1 @inner4(i1 %cond, i32 %val) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32 [0, %entry], [%val, %if_true] ; Simplified to 0
+  %cmp = icmp eq i32 %phi, 0
+  call void @pad()
+  ret i1 %cmp
+}
+
+
+define i1 @outer5_1(i1 %cond) {
+; CHECK-LABEL: @outer5_1(
+; CHECK-NOT: call i1 @inner5
+  %C = call i1 @inner5(i1 %cond, i32 0, i32 0)
+  ret i1 %C
+}
+
+
+define i1 @outer5_2(i1 %cond) {
+; CHECK-LABEL: @outer5_2(
+; CHECK: call i1 @inner5
+  %C = call i1 @inner5(i1 %cond, i32 0, i32 1)
+  ret i1 %C
+}
+
+define i1 @inner5(i1 %cond, i32 %val1, i32 %val2) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32 [%val1, %entry], [%val2, %if_true] ; Can be simplified to a constant if %val1 and %val2 are the same constants
+  %cmp = icmp eq i32 %phi, 0
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret i1 %cmp
+}
+
+
+define i1 @outer6(i1 %cond, i32 %val) {
+; CHECK-LABEL: @outer6(
+; CHECK-NOT: call i1 @inner6
+  %C = call i1 @inner6(i1 true, i32 %val, i32 0)
+  ret i1 %C
+}
+
+define i1 @inner6(i1 %cond, i32 %val1, i32 %val2) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32 [%val1, %entry], [%val2, %if_true] ; Simplified to 0
+  %cmp = icmp eq i32 %phi, 0
+  call void @pad()
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  ret i1 %cmp
+}
+
+
+define i1 @outer7(i1 %cond, i32 %val) {
+; CHECK-LABEL: @outer7(
+; CHECK-NOT: call i1 @inner7
+  %C = call i1 @inner7(i1 false, i32 0, i32 %val)
+  ret i1 %C
+}
+
+define i1 @inner7(i1 %cond, i32 %val1, i32 %val2) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32 [%val1, %entry], [%val2, %if_true] ; Simplified to 0
+  %cmp = icmp eq i32 %phi, 0
+  call void @pad()
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  ret i1 %cmp
+}
+
+
+define i1 @outer8_1() {
+; CHECK-LABEL: @outer8_1(
+; CHECK-NOT: call i1 @inner8
+  %C = call i1 @inner8(i32 0)
+  ret i1 %C
+}
+
+
+
+define i1 @outer8_2() {
+; CHECK-LABEL: @outer8_2(
+; CHECK-NOT: call i1 @inner8
+  %C = call i1 @inner8(i32 3)
+  ret i1 %C
+}
+
+define i1 @inner8(i32 %cond) {
+entry:
+  switch i32 %cond, label %default [ i32 0, label %zero
+                                     i32 1, label %one
+                                     i32 2, label %two ]
+
+zero:
+  br label %exit
+
+one:
+  br label %exit
+
+two:
+  br label %exit
+
+default:
+  br label %exit
+
+exit:
+  %phi = phi i32 [0, %zero], [1, %one], [2, %two], [-1, %default] ; Can be simplified to a constant if the switch condition is known
+  %cmp = icmp eq i32 %phi, 0
+  call void @pad()
+  ret i1 %cmp
+}
+
+
+define i1 @outer9(i1 %cond) {
+; CHECK-LABEL: @outer9(
+; CHECK-NOT: call i1 @inner9
+  %C = call i1 @inner9(i32 0, i1 %cond)
+  ret i1 %C
+}
+
+define i1 @inner9(i32 %cond1, i1 %cond2) {
+entry:
+  switch i32 %cond1, label %exit [ i32 0, label %zero
+                                   i32 1, label %one
+                                   i32 2, label %two ]
+
+zero:
+  br label %exit
+
+one:
+  br label %exit
+
+two:
+  br i1 %cond2, label %two_true, label %two_false
+
+two_true:
+  br label %exit
+
+two_false:
+  br label %exit
+
+exit:
+  %phi = phi i32 [0, %zero], [1, %one], [2, %two_true], [2, %two_false], [-1, %entry] ; Simplified to 0
+  %cmp = icmp eq i32 %phi, 0
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret i1 %cmp
+}
+
+
+define i32 @outer10(i1 %cond) {
+; CHECK-LABEL: @outer10(
+; CHECK-NOT: call i32 @inner10
+  %A = alloca i32
+  %C = call i32 @inner10(i1 %cond, i32* %A)
+  ret i32 %C
+}
+
+define i32 @inner10(i1 %cond, i32* %A) {
+entry:
+  br label %if_true
+
+if_true:
+  %phi = phi i32* [%A, %entry], [%phi, %if_true] ; Simplified to %A
+  %load = load i32, i32* %phi
+  br i1 %cond, label %if_true, label %exit
+
+exit:
+  call void @pad()
+  ret i32 %load
+}
+
+
+define i32 @outer11(i1 %cond, i32* %ptr) {
+; CHECK-LABEL: @outer11(
+; CHECK: call i32 @inner11
+  %C = call i32 @inner11(i1 %cond, i32* %ptr)
+  ret i32 %C
+}
+
+define i32 @inner11(i1 %cond, i32* %ptr) {
+entry:
+  br label %if_true
+
+if_true:
+  %phi = phi i32* [%ptr, %entry], [%phi, %if_true] ; Cannot be simplified
+  %load = load i32, i32* %phi
+  br i1 %cond, label %if_true, label %exit
+
+exit:
+  call void @pad()
+  ret i32 %load
+}
+
+
+define i32 @outer12(i1 %cond) {
+; CHECK-LABEL: @outer12(
+; CHECK-NOT: call i32 @inner12
+  %A = alloca i32
+  %C = call i32 @inner12(i1 %cond, i32* %A)
+  ret i32 %C
+}
+
+define i32 @inner12(i1 %cond, i32* %ptr) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32* [%ptr, %entry], [%ptr, %if_true] ; Simplified to %A
+  %load = load i32, i32* %phi
+  call void @pad()
+  ret i32 %load
+}
+
+
+define i32 @outer13(i1 %cond) {
+; CHECK-LABEL: @outer13(
+; CHECK-NOT: call i32 @inner13
+  %A = alloca i32
+  %C = call i32 @inner13(i1 %cond, i32* %A)
+  ret i32 %C
+}
+
+define i32 @inner13(i1 %cond, i32* %ptr) {
+entry:
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i32 2
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i32 1
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  %gep3 = getelementptr inbounds i32, i32* %gep2, i32 1
+  br label %exit
+
+exit:
+  %phi = phi i32* [%gep1, %entry], [%gep3, %if_true] ; Simplifeid to %gep1
+  %load = load i32, i32* %phi
+  call void @pad()
+  ret i32 %load
+}
+
+
+define i32 @outer14(i1 %cond) {
+; CHECK-LABEL: @outer14(
+; CHECK: call i32 @inner14
+  %A1 = alloca i32
+  %A2 = alloca i32
+  %C = call i32 @inner14(i1 %cond, i32* %A1, i32* %A2)
+  ret i32 %C
+}
+
+define i32 @inner14(i1 %cond, i32* %ptr1, i32* %ptr2) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32* [%ptr1, %entry], [%ptr2, %if_true] ; Cannot be simplified
+  %load = load i32, i32* %phi
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret i32 %load
+}
+
+
+define i32 @outer15(i1 %cond, i32* %ptr) {
+; CHECK-LABEL: @outer15(
+; CHECK-NOT: call i32 @inner15
+  %A = alloca i32
+  %C = call i32 @inner15(i1 true, i32* %ptr, i32* %A)
+  ret i32 %C
+}
+
+define i32 @inner15(i1 %cond, i32* %ptr1, i32* %ptr2) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32* [%ptr1, %entry], [%ptr2, %if_true] ; Simplified to %A
+  %load = load i32, i32* %phi
+  call void @pad()
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  ret i32 %load
+}
+
+
+define i32 @outer16(i1 %cond, i32* %ptr) {
+; CHECK-LABEL: @outer16(
+; CHECK-NOT: call i32 @inner16
+  %A = alloca i32
+  %C = call i32 @inner16(i1 false, i32* %A, i32* %ptr)
+  ret i32 %C
+}
+
+define i32 @inner16(i1 %cond, i32* %ptr1, i32* %ptr2) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32* [%ptr1, %entry], [%ptr2, %if_true] ; Simplified to %A
+  %load = load i32, i32* %phi
+  call void @pad()
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  ret i32 %load
+}
+
+
+define i1 @outer17(i1 %cond) {
+; CHECK-LABEL: @outer17(
+; CHECK: call i1 @inner17
+  %A = alloca i32
+  %C = call i1 @inner17(i1 %cond, i32* %A)
+  ret i1 %C
+}
+
+define i1 @inner17(i1 %cond, i32* %ptr) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32* [null, %entry], [%ptr, %if_true] ; Cannot be mapped to a constant
+  %cmp = icmp eq i32* %phi, null
+  call void @pad()
+  ret i1 %cmp
+}
+
+
+define i1 @outer18(i1 %cond) {
+; CHECK-LABEL: @outer18(
+; CHECK-NOT: call i1 @inner18
+  %C = call i1 @inner18(i1 %cond, i1 true)
+  ret i1 %C
+}
+
+define i1 @inner18(i1 %cond1, i1 %cond2) {
+entry:
+  br i1 %cond1, label %block1, label %block2
+
+block1:
+  br i1 %cond2, label %block3, label %block4
+
+block2:
+  br i1 %cond2, label %block5, label %block4
+
+block3:
+  %phi = phi i32 [0, %block1], [1, %block4], [0, %block5] ; Simplified to 0
+  %cmp = icmp eq i32 %phi, 0
+  call void @pad()
+  ret i1 %cmp
+
+block4:                                                   ; Unreachable block
+  br label %block3
+
+block5:
+  br label %block3
+}
+
+
+define i1 @outer19(i1 %cond) {
+; CHECK-LABEL: @outer19(
+; CHECK: call i1 @inner19
+  %A = alloca i32
+  %C = call i1 @inner19(i1 %cond, i32* %A)
+  ret i1 %C
+}
+
+define i1 @inner19(i1 %cond, i32* %ptr) {
+entry:
+  br i1 %cond, label %if_true, label %exit
+
+if_true:
+  br label %exit
+
+exit:
+  %phi = phi i32* [%ptr, %entry], [null, %if_true] ; Cannot be mapped to a constant
+  %cmp = icmp eq i32* %phi, null
+  call void @pad()
+  ret i1 %cmp
+}