[InstCombine] Support load(gep(A, select(idx1, idx2)))) to select(load(gep(A, idx1)), load(gep(A, idx2))) transformation

[wmi]

Summary

It is to fix PR30950. After SimplifyCfg sinking, it will create IR as load(gep(A, select(idx1, idx2)))). Only equipped with the transformation, InstCombine can make the redundent loads hidden by select exposed to GVN.

[majnemer]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

886

auto *SI

907–908

Do not create IR if you don't think you will use it.

test/Transforms/InstCombine/load-gep-select.ll

1

I'm not sure how I feel about two different passes showing up here.

[wmi]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

886

Ok, will fix it.

907–908

But I only need to insert the nodes into IR after isSafeToLoadUnconditionally return true for them. Any suggestion for this case?

[majnemer]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

907–908

Something like:

if (isSafeToLoadUnconditionally(NewGEP1, Align, DL, GEPI) &&
    isSafeToLoadUnconditionally(NewGEP2, Align, DL, GEPI)) {
  GetElementPtrInst *NewGEP1 = cast<GetElementPtrInst>(GEPI->clone());
  GetElementPtrInst *NewGEP2 = cast<GetElementPtrInst>(GEPI->clone());
  NewGEP1->setOperand(LastIdx, SI->getOperand(1));
  NewGEP2->setOperand(LastIdx, SI->getOperand(2));
  ...

[wmi]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

907–908

But then NewGEP1 will be used in the if condition before it is created.

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

if (isa<ConstantPointerNull>(GEPI0) && GEPI->getPointerAddressSpace() == 0){
       // Insert a new store to null instruction before the load to indicate
       // that this code is not reachable.  We do this instead of inserting
       // an unreachable instruction directly because we cannot modify the
       // CFG.
       new StoreInst(UndefValue::get(LI.getType()),
                     Constant::getNullValue(Op->getType()), &LI);
       return replaceInstUsesWith(LI, UndefValue::get(LI.getType()));
     }
+
+    // load(gep(A, select(Cond, I1, I2)))  -->
+    // select(Cond, load(gep(A, I1)), load(gep(A, I2)).
+    // It helps alias analysis and load elimination. But we need to make sure
+    // load(gep(A, I1)) and load(gep(A, I2)) will never trap.
+    unsigned LastIdx = GEPI->getNumIndices();
+    Value *LastOp = GEPI->getOperand(LastIdx);
+    if (SelectInst *SI = dyn_cast<SelectInst>(LastOp)) {
+      GetElementPtrInst *NewGEP1 = cast<GetElementPtrInst>(GEPI->clone());
+      GetElementPtrInst *NewGEP2 = cast<GetElementPtrInst>(GEPI->clone());
+      NewGEP1->setOperand(LastIdx, SI->getOperand(1));
+      NewGEP2->setOperand(LastIdx, SI->getOperand(2));
+      unsigned Align = LI.getAlignment();
+      if (isSafeToLoadUnconditionally(NewGEP1, Align, DL, GEPI) &&
+          isSafeToLoadUnconditionally(NewGEP2, Align, DL, GEPI)) {
+        Builder->Insert(NewGEP1, "newgep1");
+        Builder->Insert(NewGEP2, "newgep2");
+        LoadInst *V1 =
+            Builder->CreateLoad(NewGEP1, NewGEP1->getName() + ".val");
+        LoadInst *V2 =
+            Builder->CreateLoad(NewGEP2, NewGEP2->getName() + ".val");
+        assert(LI.isUnordered() && "implied by above");
+        V1->setAlignment(Align);
+        V1->setAtomic(LI.getOrdering(), LI.getSynchScope());
+        V2->setAlignment(Align);
+        V2->setAtomic(LI.getOrdering(), LI.getSynchScope());
+        return SelectInst::Create(SI->getCondition(), V1, V2);
+      } else {
+        delete NewGEP1;
+        delete NewGEP2;
+      }
+    }
   }
 
   // load null/undef -> unreachable
   // TODO: Consider a target hook for valid address spaces for this xform.
   if (isa<UndefValue>(Op) ||
       (isa<ConstantPointerNull>(Op) && LI.getPointerAddressSpace() == 0)) {
     // Insert a new store to null instruction before the load to indicate that
     // this code is not reachable.  We do this instead of inserting an

test/Transforms/InstCombine/load-gep-select.ll

+; RUN: opt -instcombine -gvn -S < %s | FileCheck %s
+; PR30950. Check instcombine supports the transformation of load(gep(A, select(I1, I2))) ==> select(load(gep(A, I1)), load(gep(A, I2))), so that global value numbering can remove the redundent loads.
+
+; CHECK-LABEL: @foo
+; CHECK: [[AIDX0:%[^ ]+]] = getelementptr inbounds i64, i64* %maxarray, i64 %k
+; CHECK: [[TMP0:%[^ ]+]] = load i64, i64* [[AIDX0]], align 8
+; CHECK: [[AIDX1:%[^ ]+]] = getelementptr inbounds i64, i64* %maxarray, i64 {{.*}}
+; CHECK: [[TMP1:%[^ ]+]] = load i64, i64* [[AIDX1]], align 8
+; CHECK: [[CMP:%[^ ]+]] = icmp sgt i64 [[TMP0]], [[TMP1]]
+; CHECK: [[SEL:%[^ ]+]] = select i1 [[CMP]], i64 [[TMP0]], i64 [[TMP1]]
+; CHECK: ret i64 [[SEL]]
+
+define i64 @foo(i64* nocapture readonly %maxarray, i64 %k, i64 %size) {
+entry:
+  %arrayidx = getelementptr inbounds i64, i64* %maxarray, i64 %k
+  %t0 = load i64, i64* %arrayidx, align 8
+  %add = add nsw i64 %k, %size
+  %add1 = add nsw i64 %add, 1
+  %arrayidx2 = getelementptr inbounds i64, i64* %maxarray, i64 %add1
+  %t1 = load i64, i64* %arrayidx2, align 8
+  %cmp = icmp sgt i64 %t0, %t1
+  %k.add1 = select i1 %cmp, i64 %k, i64 %add1
+  %arrayidx6 = getelementptr inbounds i64, i64* %maxarray, i64 %k.add1
+  %t2 = load i64, i64* %arrayidx6, align 8
+  ret i64 %t2
+}