[CGP] Make optimizeMemoryInst able to combine more kinds of ExtAddrMode fields

[john.brawn]

Summary

This patch extends the recent work in optimizeMemoryInst to make it able to combine more ExtAddrMode fields than just the BaseReg.

This fixes some benchmark regressions introduced by r309397, where GVN PRE is hoisting a getelementptr such that it can no longer be combined into the addressing mode of the load or store that uses it.

[davidxl]

test/Transforms/CodeGenPrepare/ARM/sink-addrmode.ll

161

The old select may have profile meta data, so you need to make sure the new select inherits it.

[skatkov]

Do I understand correctly that you consider only very simple cases?
Specifically if Addr is represented as Select or Phi and no one from its input might be other Select/Phi.

Also it seems you create Phi unconditionally even if the Phi you need already exists.

Please take a look into the patch I come up to cover more cases https://reviews.llvm.org/D36073 but for Phi nodes only and for base registers only.

Does it makes sense for you to review it and extend with select support and other than base parts?

lib/CodeGen/CodeGenPrepare.cpp

4648

What if this Phi already exists?

4715–4718

For select you set PhiSeen to true so you will skip this check but for select all intructions might be in the same basic block. Is it what you expect?
If yes, you need to update a comment.

4754

bail out earlier?

[reames]

In D38133#878598, @skatkov wrote:

Does it makes sense for you to review it and extend with select support and other than base parts?

I will insist on collaboration here. It doesn't have to be the case that we land either patch as currently structured; we could instead extract common functionality they can both build on. We don't want to waste the time either of you have put into this, and as currently structured the two patches are conflicting. That needs to change.

[reames]

lib/CodeGen/CodeGenPrepare.cpp

4648

I think this case where a single PHI or Select needs inserted (or reused) is a enough to require the appropriate structure in the caller. I'd suggest that we factor out a common patch which does this which can implement both your patch and Serguei's analysis behind the same API. Once we have that, the code structure is in place for either patch and we can focus on reviewing the two analyses.

4688

I think the select handling can be separate from the rest of the patch and reviewed separately. This should kick in even if the underlying addresses share the same addr mode.

Please do this to simply the review and increase the common code which can be shared between the two related patches in this area.

4701

Having an unbounded number of AddrModes here is likely problematic. How much power do you loose if you cap this to say 2 or 3?

[reames]

Marking as changes needs to reflect split requested. Note that I really haven't even looked at the guts of the transform and don't plan to until the common pieces have been extracted.

[john.brawn]

OK, so looking at the comments here and looking at D36073 what looks like it would be the easiest way to progress things forwards is:

• I split out the select handling into a separate patch.
• I split out a patch which gathers the AddrModes and figures out how they differ, but then bails out when we get to sinking if we have more than one.
• @skatkov modifies D36073 to build on top of this - from a brief look at FindCommonBase and the functions they call it looks like they could be modified to handle taking the AddrModes vector, so then we can handle the DifferentBase case similar to as in this patch but with AddrMode.BaseReg = FindCommonBase() instead of AddrMode.BaseReg = CreateSelectOrPhi().
• I then write a patch on top of that which modifies FindCommonBase to handle the fields other than the base register.

Does this seem reasonable?

[john.brawn]

lib/CodeGen/CodeGenPrepare.cpp

4688

I've split this out into D38242.

[skatkov]

In D38133#880243, @john.brawn wrote:

OK, so looking at the comments here and looking at D36073 what looks like it would be the easiest way to progress things forwards is:

• I split out the select handling into a separate patch.
• I split out a patch which gathers the AddrModes and figures out how they differ, but then bails out when we get to sinking if we have more than one.
• @skatkov modifies D36073 to build on top of this - from a brief look at FindCommonBase and the functions they call it looks like they could be modified to handle taking the AddrModes vector, so then we can handle the DifferentBase case similar to as in this patch but with AddrMode.BaseReg = FindCommonBase() instead of AddrMode.BaseReg = CreateSelectOrPhi().
• I then write a patch on top of that which modifies FindCommonBase to handle the fields other than the base register.

Does this seem reasonable?

Yes, it seems reasonable to me.

[skatkov]

In D38133#880911, @skatkov wrote:

In D38133#880243, @john.brawn wrote:

OK, so looking at the comments here and looking at D36073 what looks like it would be the easiest way to progress things forwards is:

• I split out the select handling into a separate patch.
• I split out a patch which gathers the AddrModes and figures out how they differ, but then bails out when we get to sinking if we have more than one.
• @skatkov modifies D36073 to build on top of this - from a brief look at FindCommonBase and the functions they call it looks like they could be modified to handle taking the AddrModes vector, so then we can handle the DifferentBase case similar to as in this patch but with AddrMode.BaseReg = FindCommonBase() instead of AddrMode.BaseReg = CreateSelectOrPhi().
• I then write a patch on top of that which modifies FindCommonBase to handle the fields other than the base register.

Does this seem reasonable?

Yes, it seems reasonable to me.

To be clear, I'm waiting you for implementation of diff between AddrModes and then I update D36073 on top of your change.

[john.brawn]

I've updated the patch to something that builds on top of D38133, to give more context to that. I'm not intending to commit this patch, as instead I'll be rewriting it to apply on top of D36073 (once that's been updated to apply on top of D38133).

[john.brawn]

Reworked this so that it applies on top of D36073.

[skatkov]

Hi John, in general looks good to me. I wonder whether we can add some options to enable/disable different fields and enable them step-by-step?
The patch has a significant impact and in this case people can use these options to quickly detect where the problem is. Does it make sense?

Please postpone the landing of this patch until I finish enabling the optimization itself.

[john.brawn]

Rebase, and allow combining of the different parts of the addressing mode to be individually disabled.

[skatkov]

Hi John, LGTM.

Unfortunately I still have problems enabling the optimization by default. It causes build bot hangs-up, I'm evaluating the failures.
If you can also look into it, would be great.

Anyway, I think you can land this patch with all options off be default. Then I will switch them on one by one resolving different issues.

[john.brawn]

Unfortunately I still have problems enabling the optimization by default. It causes build bot hangs-up, I'm evaluating the failures.
If you can also look into it, would be great.

I've done some testing and there appears to be a problem with how isTrivial handles null pointers, I'll post a patch for that shortly.

Anyway, I think you can land this patch with all options off be default. Then I will switch them on one by one resolving different issues.

DisableComplexAddrModes already disables everything, so I don't think there's a need to disable the various AddrSinkCombine options for now. We can disable individual ones when DisableComplexAddrModes is turned on, if we need to.

lib/CodeGen/CodeGenPrepare.cpp

 namespace {
 
 /// This is an extended version of TargetLowering::AddrMode
 /// which holds actual Value*'s for register values.
 struct ExtAddrMode : public TargetLowering::AddrMode {
   Value *BaseReg = nullptr;
   Value *ScaledReg = nullptr;
   Value *OriginalValue = nullptr;
+  User *AddrModeUser = nullptr;
 
   enum FieldName {
     NoField        = 0x00,
     BaseRegField   = 0x01,
     BaseGVField    = 0x02,
     BaseOffsField  = 0x04,
     ScaledRegField = 0x08,
     ScaleField     = 0x10,
private:
   SmallVector<ExtAddrMode, 16> AddrModes;
 
   /// The field in which the AddrModes differ, when we have more than one.
   ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
 
   /// Are the AddrModes that we have all just equal to their original values?
   bool AllAddrModesTrivial = true;
 
+  const DataLayout &DL;
+
 public:
+  AddressingModeCombiner(const DataLayout &DL) : DL(DL) { }
+
   /// \brief Get the combined AddrMode
   const ExtAddrMode &getAddrMode() const {
     return AddrModes[0];
   }
 
   /// \brief Add a new AddrMode if it's compatible with the AddrModes we already
   /// have.
   /// \return True iff we succeeded in doing so.
bool combineAddrModes() {
     if (AddrModes.size() == 1)
       return true;
 
     // If the AddrModes we collected are all just equal to the value they are
     // derived from then combining them wouldn't do anything useful.
     if (AllAddrModesTrivial)
       return false;
 
-    // TODO: Combine multiple AddrModes by inserting a select or phi for the
+    // If we have more than one AddrMode then insert a select or phi for the
     // field in which the AddrModes differ.
+    switch (DifferentField) {
+    default:
+      llvm_unreachable("Expected a single field to be different");
+      return false;
+
+    case ExtAddrMode::ScaleField:
+      // We can't cope with scale being different.
+      return false;
+
+    case ExtAddrMode::BaseRegField:
+      AddrModes[0].BaseReg =
+        CreateSelectOrPHI([&](ExtAddrMode &AM) { return AM.BaseReg; });
+      if (!AddrModes[0].BaseReg)
+        return false;
+      break;
+
+    case ExtAddrMode::BaseGVField:
+      // Set BaseReg to be the select/phi of the BaseGV.
+      assert(!AddrModes[0].BaseReg);
+      AddrModes[0].BaseReg =
+        CreateSelectOrPHI([&](ExtAddrMode &AM) { return AM.BaseGV; });
+      if (!AddrModes[0].BaseReg)
+        return false;
+      AddrModes[0].BaseGV = nullptr;
+      break;
+
+    case ExtAddrMode::BaseOffsField:
+    {
+      // Handle differing offsets by setting ScaledReg to be the select/phi of
+      // the offset values, with a scale of 1.
+      Type *IntPtrTy = DL.getIntPtrType(AddrModes[0].OriginalValue->getType());
+      assert(AddrModes[0].Scale == 0);
+      assert(!AddrModes[0].ScaledReg);
+      AddrModes[0].Scale = 1;
+      AddrModes[0].ScaledReg = CreateSelectOrPHI([&](ExtAddrMode &AM) {
+          return ConstantInt::get(IntPtrTy, AM.BaseOffs);
+        });
+      if (!AddrModes[0].ScaledReg)
         return false;
+      AddrModes[0].BaseOffs = 0;
+      break;
+    }
+
+    case ExtAddrMode::ScaledRegField:
+      AddrModes[0].ScaledReg =
+        CreateSelectOrPHI([&](ExtAddrMode &AM) { return AM.ScaledReg; });
+      if (!AddrModes[0].ScaledReg)
+        return false;
+      // If we have a mix of scaled and unscaled addrmodes then we want scale
+      // to be the scale and not zero.
+      if (!AddrModes[0].Scale)
+        for (ExtAddrMode &AM : AddrModes)
+          if (AM.Scale) {
+            AddrModes[0].Scale = AM.Scale;
+            break;
+          }
+      break;
+    }
+
+    return true;
+  }
+
+  // Convert a null Value to a null value constant
+  static Value *NullValueToNullConstant(Value *V, Type *T) {
+    if (V)
+      return V;
+    else
+      return Constant::getNullValue(T);
+  }
+
+  Value *CreateSelectOrPHI(std::function<Value *(ExtAddrMode &)> GetVal) {
+    Value *Addr = AddrModes[0].AddrModeUser;
+    // The select/phi has to be used only in the memory instruction the addrmode
+    // will be folded into.
+    if (!Addr->hasOneUse())
+      return nullptr;
+    // Start off by figuring out the type
+    Type *T = nullptr;
+    for (ExtAddrMode &AM : AddrModes) {
+      Value *V = GetVal(AM);
+      if (V) {
+        Type *NewT = V->getType();
+        if (!T)
+          T = NewT;
+        else if (T != NewT)
+          return nullptr; // We can't handle mismatched types
+      }
+    }
+    Value *Result = nullptr;
+    if (PHINode *OrigPHI = dyn_cast<PHINode>(Addr)) {
+      // We can't do anything if addrmodes doesn't match the number of incoming
+      // values
+      if (AddrModes.size() != OrigPHI->getNumIncomingValues())
+        return nullptr;
+      PHINode *NewPHI = PHINode::Create(T, OrigPHI->getNumIncomingValues(),
+                                        OrigPHI->getName(),
+                                        OrigPHI->getParent()->getFirstNonPHI());
+      for (BasicBlock *BB : OrigPHI->blocks()) {
+        Value *IV = OrigPHI->getIncomingValueForBlock(BB);
+        // Find the AddrMode this corresponds to
+        for (ExtAddrMode &AM : AddrModes) {
+          if (AM.OriginalValue == IV) {
+            Value *V = NullValueToNullConstant(GetVal(AM), T);
+            NewPHI->addIncoming(V, BB);
+            break;
+          }
+        }
+      }
+      // If we failed to add an incoming value for each in the original then we
+      // can't proceed
+      if (NewPHI->getNumIncomingValues() != OrigPHI->getNumIncomingValues()) {
+        NewPHI->eraseFromParent();
+        return nullptr;
+      }
+      Result = NewPHI;
+    } else if (SelectInst *OrigSelect = dyn_cast<SelectInst>(Addr)) {
+      // Can't do anything if we don't have exactly two addrmodes
+      if (AddrModes.size() != 2)
+        return nullptr;
+      // The two addrmodes we have must correspond to the operands of the select
+      if (AddrModes[0].OriginalValue != OrigSelect->getTrueValue())
+        return nullptr;
+      if (AddrModes[1].OriginalValue != OrigSelect->getFalseValue())
+        return nullptr;
+      Value *X = NullValueToNullConstant(GetVal(AddrModes[0]), T);
+      Value *Y = NullValueToNullConstant(GetVal(AddrModes[1]), T);
+      Result = SelectInst::Create(OrigSelect->getCondition(), X, Y,
+                                  OrigSelect->getName(), OrigSelect, OrigSelect);
+    } else {
+      llvm_unreachable("Addr should be PHI or Select");
+    }
+    return Result;
   }
 };
 
 } // end anonymous namespace
 
 /// Try adding ScaleReg*Scale to the current addressing mode.
 /// Return true and update AddrMode if this addr mode is legal for the target,
 /// false if not.

 /// constraint above), and reduce register pressure globally (by removing the
 /// addressing mode computation from the fast path entirely.).
 bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
                                         Type *AccessTy, unsigned AddrSpace) {
   Value *Repl = Addr;
 
   // Try to collapse single-value PHI nodes.  This is necessary to undo
   // unprofitable PRE transformations.
-  SmallVector<Value*, 8> worklist;
+  SmallVector<std::pair<Value*, User*>, 8> worklist;
   SmallPtrSet<Value*, 16> Visited;
-  worklist.push_back(Addr);
+  worklist.push_back({Addr,MemoryInst});
 
   // Use a worklist to iteratively look through PHI and select nodes, and
   // ensure that the addressing mode obtained from the non-PHI/select roots of
   // the graph are compatible.
   bool PhiOrSelectSeen = false;
   SmallVector<Instruction*, 16> AddrModeInsts;
-  AddressingModeCombiner AddrModes;
+  AddressingModeCombiner AddrModes(*DL);
   TypePromotionTransaction TPT(RemovedInsts);
   TypePromotionTransaction::ConstRestorationPt LastKnownGood =
       TPT.getRestorationPoint();
   while (!worklist.empty()) {
-    Value *V = worklist.back();
+    Value *V = worklist.back().first;
+    User *U = worklist.back().second;
     worklist.pop_back();
 
     // We allow traversing cyclic Phi nodes.
     // In case of success after this loop we ensure that traversing through
     // Phi nodes ends up with all cases to compute address of the form
     //    BaseGV + Base + Scale * Index + Offset
     // where Scale and Offset are constans and BaseGV, Base and Index
     // are exactly the same Values in all cases.
     // It means that BaseGV, Scale and Offset dominate our memory instruction
     // and have the same value as they had in address computation represented
     // as Phi. So we can safely sink address computation to memory instruction.
     if (!Visited.insert(V).second)
       continue;
 
     // For a PHI node, push all of its incoming values.
     if (PHINode *P = dyn_cast<PHINode>(V)) {
       for (Value *IncValue : P->incoming_values())
-        worklist.push_back(IncValue);
+        worklist.push_back({IncValue,P});
       PhiOrSelectSeen = true;
       continue;
     }
     // Similar for select.
     if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
-      worklist.push_back(SI->getFalseValue());
-      worklist.push_back(SI->getTrueValue());
+      worklist.push_back({SI->getFalseValue(),SI});
+      worklist.push_back({SI->getTrueValue(),SI});
       PhiOrSelectSeen = true;
       continue;
     }
 
     // For non-PHIs, determine the addressing mode being computed.  Note that
     // the result may differ depending on what other uses our candidate
     // addressing instructions might have.
     AddrModeInsts.clear();
     ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
         V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *TRI,
         InsertedInsts, PromotedInsts, TPT);
     NewAddrMode.OriginalValue = V;
+    NewAddrMode.AddrModeUser = U;
 
     if (!AddrModes.addNewAddrMode(NewAddrMode))
       break;
   }
 
   // Try to combine the AddrModes we've collected. If we couldn't collect any,
   // or we have multiple but either couldn't combine them or combining them
   // wouldn't do anything useful, bail out now.
   if (!AddrModes.combineAddrModes()) {
     TPT.rollback(LastKnownGood);
     return false;
   }
   TPT.commit();
 
   // Get the combined AddrMode (or the only AddrMode, if we only had one).
   ExtAddrMode AddrMode = AddrModes.getAddrMode();
 
   // If all the instructions matched are already in this BB, don't do anything.
   // If we saw a Phi node then it is not local definitely, and if we saw a select
   // then we want to push the address calculation past it even if it's already
   // in this BB.
   if (!PhiOrSelectSeen && none_of(AddrModeInsts, [&](Value *V) {
         return IsNonLocalValue(V, MemoryInst->getParent());
                   })) {
     DEBUG(dbgs() << "CGP: Found      local addrmode: " << AddrMode << "\n");
     return false;
   }
 
   // Insert this computation right after this user.  Since our caller is
   // scanning from the top of the BB to the bottom, reuse of the expr are
DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
                  << *MemoryInst << "\n");
     Type *IntPtrTy = DL->getIntPtrType(Addr->getType());
     Value *ResultPtr = nullptr, *ResultIndex = nullptr;
 
     // First, find the pointer.
     if (AddrMode.BaseReg && AddrMode.BaseReg->getType()->isPointerTy()) {
       ResultPtr = AddrMode.BaseReg;
       AddrMode.BaseReg = nullptr;
     }
 
     if (AddrMode.Scale && AddrMode.ScaledReg->getType()->isPointerTy()) {
       // We can't add more than one pointer together, nor can we scale a
       // pointer (both of which seem meaningless).
       if (ResultPtr || AddrMode.Scale != 1)
         return false;
 
       ResultPtr = AddrMode.ScaledReg;

test/CodeGen/X86/tail-merge-identical.ll

 ; RUN: llc -o - -verify-machineinstrs %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @data = external global [3 x i32], align 4
 @store = external global i32, align 4
 
 ; %else1 and %then2 end up lowering to identical blocks. These blocks should be
 ; merged during tail-merging.
 ; CHECK-LABEL: merge_identical_blocks
-; CHECK: movl $data+4
-; CHECK-NOT: movl $data+4
+; CHECK: movl $4
+; CHECK-NOT: movl $4
 ; CHECK: retq
 define void @merge_identical_blocks(i1 %a, i1 %b) {
 entry:
   br label %if1
 
 if1:                                              ; predfs = %entry
   br i1 %a, label %else1, label %if2
 

test/CodeGen/X86/x86-cmov-converter.ll

for.body:                                         ; preds = %for.body.preheader, %for.body
   %cmp2 = icmp sgt i32 %1, %t.014
   %.t.0 = select i1 %cmp2, i32 %1, i32 %t.014
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 }
 
 ; CHECK-LABEL: BinarySearch
-; CHECK: cmov
+; CHECK-NOT: cmov
+; CHECK: setae %[[REG:[a-z]]]l
+; CHECK-NEXT: movq 8(%rdx,%r[[REG]]x,8)
 
 define i32 @BinarySearch(i32 %Mask, %struct.Node* nocapture readonly %Curr, %struct.Node* nocapture readonly %Next) #0 {
 entry:
   %Val8 = getelementptr inbounds %struct.Node, %struct.Node* %Curr, i64 0, i32 0
   %0 = load i32, i32* %Val8, align 8
   %Val19 = getelementptr inbounds %struct.Node, %struct.Node* %Next, i64 0, i32 0
   %1 = load i32, i32* %Val19, align 8
   %cmp10 = icmp ugt i32 %0, %1

test/Transforms/CodeGenPrepare/ARM/sink-addrmode.ll

+; RUN: opt -S -codegenprepare -mtriple=thumbv7m < %s | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+
+@gv1 = common global i32 0, align 4
+@gv2 = common global i32 0, align 4
+
+; Phi selects between ptr and gep with ptr as base and constant offset
+define void @test_phi_onegep_offset(i32* %ptr, i32 %value) {
+; CHECK-LABEL: @test_phi_onegep_offset
+; CHECK-NOT: phi i32* [ %ptr, %entry ], [ %gep, %if.then ]
+; CHECK: phi i32 [ 0, %entry ], [ 4, %if.then ]
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  %gep = getelementptr inbounds i32, i32* %ptr, i32 1
+  br label %if.end
+
+if.end:
+  %phi = phi i32* [ %ptr, %entry ], [ %gep, %if.then ]
+  store i32 %value, i32* %phi, align 4
+  ret void
+}
+
+; Phi selects between two geps with same base, different constant offsets
+define void @test_phi_twogep_offset(i32* %ptr, i32 %value) {
+; CHECK-LABEL: @test_phi_twogep_offset
+; CHECK-NOT: phi i32* [ %gep1, %if.then ], [ %gep2, %if.else ]
+; CHECK: phi i32 [ 4, %if.then ], [ 8, %if.else ]
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i32 1
+  br label %if.end
+
+if.else:
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i32 2
+  br label %if.end
+
+if.end:
+  %phi = phi i32* [ %gep1, %if.then ], [ %gep2, %if.else ]
+  store i32 %value, i32* %phi, align 4
+  ret void
+}
+
+; Phi selects between ptr and gep with ptr as base and nonconstant offset
+define void @test_phi_onegep_nonconst_offset(i32* %ptr, i32 %value, i32 %off) {
+; CHECK-LABEL: @test_phi_onegep_nonconst_offset
+; CHECK-NOT: phi i32* [ %ptr, %entry ], [ %gep, %if.then ]
+; CHECK: phi i32 [ 0, %entry ], [ %off, %if.then ]
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  %gep = getelementptr inbounds i32, i32* %ptr, i32 %off
+  br label %if.end
+
+if.end:
+  %phi = phi i32* [ %ptr, %entry ], [ %gep, %if.then ]
+  store i32 %value, i32* %phi, align 4
+  ret void
+}
+
+; Phi selects between two geps with same base, different nonconstant offsets
+define void @test_phi_twogep_nonconst_offset(i32* %ptr, i32 %value, i32 %off1, i32 %off2) {
+; CHECK-LABEL: @test_phi_twogep_nonconst_offset
+; CHECK-NOT: phi i32* [ %gep1, %if.then ], [ %gep2, %if.else ]
+; CHECK: phi i32 [ %off1, %if.then ], [ %off2, %if.else ]
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i32 %off1
+  br label %if.end
+
+if.else:
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i32 %off2
+  br label %if.end
+
+if.end:
+  %phi = phi i32* [ %gep1, %if.then ], [ %gep2, %if.else ]
+  store i32 %value, i32* %phi, align 4
+  ret void
+}
+
+; Phi selects between two geps with different base, same constant offset
+define void @test_phi_twogep_base(i32* %ptr1, i32* %ptr2, i32 %value) {
+; CHECK-LABEL: @test_phi_twogep_base
+; CHECK-NOT: phi i32* [ %gep1, %if.then ], [ %gep2, %if.else ]
+; CHECK: phi i32* [ %ptr1, %if.then ], [ %ptr2, %if.else ]
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %gep1 = getelementptr inbounds i32, i32* %ptr1, i32 1
+  br label %if.end
+
+if.else:
+  %gep2 = getelementptr inbounds i32, i32* %ptr2, i32 1
+  br label %if.end
+
+if.end:
+  %phi = phi i32* [ %gep1, %if.then ], [ %gep2, %if.else ]
+  store i32 %value, i32* %phi, align 4
+  ret void
+}
+
+; Phi selects between two geps with different base global variables, same constant offset
+define void @test_phi_twogep_base_gv(i32 %value) {
+; CHECK-LABEL: @test_phi_twogep_base_gv
+; CHECK-NOT: phi i32* [ %gep1, %if.then ], [ %gep2, %if.else ]
+; CHECK: phi i32* [ @gv1, %if.then ], [ @gv2, %if.else ]
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %gep1 = getelementptr inbounds i32, i32* @gv1, i32 1
+  br label %if.end
+
+if.else:
+  %gep2 = getelementptr inbounds i32, i32* @gv2, i32 1
+  br label %if.end
+
+if.end:
+  %phi = phi i32* [ %gep1, %if.then ], [ %gep2, %if.else ]
+  store i32 %value, i32* %phi, align 4
+  ret void
+}
+
+; Phi selects between ptr and gep with ptr as base and constant offset
+define void @test_select_onegep_offset(i32* %ptr, i32 %value) {
+; CHECK-LABEL: @test_select_onegep_offset
+; CHECK-NOT: select i1 %cmp, i32* %ptr, i32* %gep
+; CHECK: select i1 %cmp, i32 0, i32 4
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  %gep = getelementptr inbounds i32, i32* %ptr, i32 1
+  %select = select i1 %cmp, i32* %ptr, i32* %gep
+  store i32 %value, i32* %select, align 4
+  ret void
+}
+
+; Select between two geps with same base, different constant offsets
+define void @test_select_twogep_offset(i32* %ptr, i32 %value) {
+; CHECK-LABEL: @test_select_twogep_offset
+; CHECK-NOT: select i1 %cmp, i32* %gep1, i32* %gep2
+; CHECK: select i1 %cmp, i32 4, i32 8
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i32 1
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i32 2
+  %select = select i1 %cmp, i32* %gep1, i32* %gep2
+  store i32 %value, i32* %select, align 4
+  ret void
+}
+
+; Select between ptr and gep with ptr as base and nonconstant offset
+define void @test_select_onegep_nonconst_offset(i32* %ptr, i32 %value, i32 %off) {
+; CHECK-LABEL: @test_select_onegep_nonconst_offset
+; CHECK-NOT: select i1 %cmp, i32* %ptr, i32* %gep
+; CHECK: select i1 %cmp, i32 0, i32 %off
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  %gep = getelementptr inbounds i32, i32* %ptr, i32 %off
+  %select = select i1 %cmp, i32* %ptr, i32* %gep
+  store i32 %value, i32* %select, align 4
+  ret void
+}
+
+; Select between two geps with same base, different nonconstant offsets
+define void @test_select_twogep_nonconst_offset(i32* %ptr, i32 %value, i32 %off1, i32 %off2) {
+; CHECK-LABEL: @test_select_twogep_nonconst_offset
+; CHECK-NOT: select i1 %cmp, i32* %gep1, i32* %gep2
+; CHECK: select i1 %cmp, i32 %off1, i32 %off2
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i32 %off1
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i32 %off2
+  %select = select i1 %cmp, i32* %gep1, i32* %gep2
+  store i32 %value, i32* %select, align 4
+  ret void
+}
+
+; Select between two geps with different base, same constant offset
+define void @test_select_twogep_base(i32* %ptr1, i32* %ptr2, i32 %value) {
+; CHECK-LABEL: @test_select_twogep_base
+; CHECK-NOT: select i1 %cmp, i32* %gep1, i32* %gep2
+; CHECK: select i1 %cmp, i32* %ptr1, i32* %ptr2
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  %gep1 = getelementptr inbounds i32, i32* %ptr1, i32 1
+  %gep2 = getelementptr inbounds i32, i32* %ptr2, i32 1
+  %select = select i1 %cmp, i32* %gep1, i32* %gep2
+  store i32 %value, i32* %select, align 4
+  ret void
+}
+
+; Select between two geps with different base global variables, same constant offset
+define void @test_select_twogep_base_gv(i32 %value) {
+; CHECK-LABEL: @test_select_twogep_base_gv
+; CHECK-NOT: select i1 %cmp, i32* %gep1, i32* %gep2
+; CHECK: select i1 %cmp, i32* @gv1, i32* @gv2
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  %gep1 = getelementptr inbounds i32, i32* @gv1, i32 1
+  %gep2 = getelementptr inbounds i32, i32* @gv2, i32 1
+  %select = select i1 %cmp, i32* %gep1, i32* %gep2
+  store i32 %value, i32* %select, align 4
+  ret void
+}
+
+; If the phi is in a different block to where the gep will be, the phi goes where
+; the original phi was bit where the gep is.
+; CHECK-LABEL: @test_phi_different_block
+; CHECK-LABEL: if1.end
+; CHECK-NOT: phi i32* [ %ptr, %entry ], [ %gep, %if1.then ]
+; CHECK: phi i32 [ 0, %entry ], [ 4, %if1.then ]
+define void @test_phi_different_block(i32* %ptr, i32 %value1, i32 %value2) {
+entry:
+  %cmp1 = icmp sgt i32 %value1, 0
+  br i1 %cmp1, label %if1.then, label %if1.end
+
+if1.then:
+  %gep = getelementptr inbounds i32, i32* %ptr, i32 1
+  br label %if1.end
+
+if1.end:
+  %phi = phi i32* [ %ptr, %entry ], [ %gep, %if1.then ]
+  %cmp2 = icmp sgt i32 %value2, 0
+  br i1 %cmp2, label %if2.then, label %if2.end
+
+if2.then:
+  store i32 %value1, i32* %ptr, align 4
+  br label %if2.end
+
+if2.end:
+  store i32 %value2, i32* %phi, align 4
+  ret void
+}
+
+; A phi with three incoming values should be optimised
+; CHECK-LABEL: @test_phi_threegep
+; CHECK-NOT: phi i32* [ %gep1, %if.then ], [ %gep2, %if.else.then ], [ %gep3, %if.else.else ]
+; CHECK: phi i32 [ 4, %if.then ], [ 8, %if.else.then ], [ 12, %if.else.else ]
+define void @test_phi_threegep(i32* %ptr, i32 %value1, i32 %value2) {
+entry:
+  %cmp1 = icmp sgt i32 %value1, 0
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i32 1
+  br label %if.end
+
+if.else:
+  %cmp2 = icmp sgt i32 %value2, 0
+  br i1 %cmp2, label %if.else.then, label %if.else.else
+
+if.else.then:
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i32 2
+  br label %if.end
+
+if.else.else:
+  %gep3 = getelementptr inbounds i32, i32* %ptr, i32 3
+  br label %if.end
+
+if.end:
+  %phi = phi i32* [ %gep1, %if.then ], [ %gep2, %if.else.then ], [ %gep3, %if.else.else ]
+  store i32 %value1, i32* %phi, align 4
+  ret void
+}
+
+; A phi with two incoming values but three geps due to nesting shouldn't be
+; optimised
+; CHECK-LABEL: @test_phi_threegep_nested
+; CHECK: phi i32* [ %gep2, %if.else.then ], [ %gep3, %if.else.else ]
+define void @test_phi_threegep_nested(i32* %ptr, i32 %value1, i32 %value2) {
+entry:
+  %cmp1 = icmp sgt i32 %value1, 0
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i32 1
+  br label %if.end
+
+if.else:
+  %cmp2 = icmp sgt i32 %value2, 0
+  br i1 %cmp2, label %if.else.then, label %if.else.else
+
+if.else.then:
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i32 2
+  br label %if.else.end
+
+if.else.else:
+  %gep3 = getelementptr inbounds i32, i32* %ptr, i32 3
+  br label %if.else.end
+
+if.else.end:
+  %gep4 = phi i32* [ %gep2, %if.else.then ], [ %gep3, %if.else.else ]
+  store i32 %value2, i32* %ptr, align 4
+  br label %if.end
+
+if.end:
+  %phi = phi i32* [ %gep1, %if.then ], [ %gep4, %if.else.end ]
+  store i32 %value1, i32* %phi, align 4
+  ret void
+}
+
+; A nested select is expected to not be optimised
+; CHECK-LABEL: @test_nested_select
+; CHECK: select i1 %cmp2, i32* %gep1, i32* %gep2
+; CHECK: select i1 %cmp1, i32* %gep1, i32* %select1
+define void @test_nested_select(i32* %ptr, i32 %value1, i32 %value2) {
+entry:
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i32 1
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i32 2
+  %cmp1 = icmp sgt i32 %value1, 0
+  %cmp2 = icmp sgt i32 %value2, 0
+  %select1 = select i1 %cmp2, i32* %gep1, i32* %gep2
+  %select2 = select i1 %cmp1, i32* %gep1, i32* %select1
+  store i32 %value1, i32* %select2, align 4
+  ret void
+}
+
+; Scaling the offset by a different amount is expected not to be optimised
+; CHECK-LABEL: @test_select_different_scale
+; CHECK: select i1 %cmp, i32* %gep1, i32* %castgep
+define void @test_select_different_scale(i32* %ptr, i32 %value, i32 %off) {
+entry:
+  %cmp = icmp sgt i32 %value, 0
+  %castptr = bitcast i32* %ptr to i16*
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i32 %off
+  %gep2 = getelementptr inbounds i16, i16* %castptr, i32 %off
+  %castgep = bitcast i16* %gep2 to i32*
+  %select = select i1 %cmp, i32* %gep1, i32* %castgep
+  store i32 %value, i32* %select, align 4
+  ret void
+}
+
+; A select between two values is already the best we can do
+; CHECK-LABEL: @test_select_trivial
+; CHECK: select i1 %cmp, i32* %ptr1, i32* %ptr2
+define void @test_select_trivial(i32* %ptr1, i32* %ptr2, i32 %value) {
+entey:
+  %cmp = icmp sgt i32 %value, 0
+  %select = select i1 %cmp, i32* %ptr1, i32* %ptr2
+  store i32 %value, i32* %select, align 4
+  ret void
+}
+
+; A select between two global variables is already the best we can do
+; CHECK-LABEL: @test_select_trivial_gv
+; CHECK: select i1 %cmp, i32* @gv1, i32* @gv2
+define void @test_select_trivial_gv(i32 %value) {
+entey:
+  %cmp = icmp sgt i32 %value, 0
+  %select = select i1 %cmp, i32* @gv1, i32* @gv2
+  store i32 %value, i32* %select, align 4
+  ret void
+}