[VectorCombine] Run load/extract scalarization after scalarizing store.

[fhahn]

Summary

Remove the insertelement instruction (via D98240) can enable further
load/extract scalarization opportunities. Try it again.

[fhahn]

Rebase and update to actually pass the first user.

[fhahn]

rebase and ping :) All pending patches should be committed now.

[spatel]

Some questions were raised about D98240, so we should deal with those before adding this.

[fhahn]

Rebase and ping :)

In D100302#2782012, @spatel wrote:

Some questions were raised about D98240, so we should deal with those before adding this.

I think those questions should be addressed by now and the issues raised by Alive2 should also be ironed out now.

[lebedev.ri]

I do not like the general direction VectorCombine seems to be going in.
Doing only a single pass and hoping that the second pass wouldn't do anything clearly leads to problems if (!Load->user_empty()) { is solving.
I would think we'd really want an instcombine-lite approach here, with a worklist..

[fhahn]

In D100302#2941173, @lebedev.ri wrote:

I do not like the general direction VectorCombine seems to be going in.
Doing only a single pass and hoping that the second pass wouldn't do anything clearly leads to problems if (!Load->user_empty()) { is solving.
I would think we'd really want an instcombine-lite approach here, with a worklist..

That's a fair point. But I think the same probably holds true fo somer other combines in VectorCombine. So should the whole pass just use a worklist?

[lebedev.ri]

In D100302#2949997, @fhahn wrote:

In D100302#2941173, @lebedev.ri wrote:

I do not like the general direction VectorCombine seems to be going in.
Doing only a single pass and hoping that the second pass wouldn't do anything clearly leads to problems if (!Load->user_empty()) { is solving.
I would think we'd really want an instcombine-lite approach here, with a worklist..

That's a fair point. But I think the same probably holds true fo somer other combines in VectorCombine. So should the whole pass just use a worklist?

That was my comment precisely.

[fhahn]

In D100302#2950029, @lebedev.ri wrote:

In D100302#2949997, @fhahn wrote:

In D100302#2941173, @lebedev.ri wrote:

I do not like the general direction VectorCombine seems to be going in.
Doing only a single pass and hoping that the second pass wouldn't do anything clearly leads to problems if (!Load->user_empty()) { is solving.
I would think we'd really want an instcombine-lite approach here, with a worklist..

That's a fair point. But I think the same probably holds true fo somer other combines in VectorCombine. So should the whole pass just use a worklist?

That was my comment precisely.

@spatel did you by any chance already think/consider this for VectorCombine? Or do you have any concerns?

[spatel]

In D100302#2950411, @fhahn wrote:

@spatel did you by any chance already think/consider this for VectorCombine? Or do you have any concerns?

No concerns. This has come up before (we were walking the instruction bottom-up at some point instead of top-down), but we just didn't have enough motivation with the existing transforms to justify implementing a worklist. If you want to try it, that would be great!

[fhahn]

In D100302#2950426, @spatel wrote:

In D100302#2950411, @fhahn wrote:

@spatel did you by any chance already think/consider this for VectorCombine? Or do you have any concerns?

No concerns. This has come up before (we were walking the instruction bottom-up at some point instead of top-down), but we just didn't have enough motivation with the existing transforms to justify implementing a worklist. If you want to try it, that would be great!

I put up a patch: D110171

I'll abandon the patch here for now.

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

if (auto *Load = dyn_cast<LoadInst>(Source)) {
     Value *GEP = GetElementPtrInst::CreateInBounds(
         SI->getPointerOperand(), {ConstantInt::get(Idx->getType(), 0), Idx});
     Builder.Insert(GEP);
     StoreInst *NSI = Builder.CreateStore(NewElement, GEP);
     NSI->copyMetadata(*SI);
     if (SI->getAlign() < NSI->getAlign())
       NSI->setAlignment(SI->getAlign());
     replaceValue(I, *NSI);
+    auto *IEI = cast<Instruction>(SI->getOperand(0));
     // Need erasing the store manually.
     I.eraseFromParent();
+    // Removing the insertelement instruction may unlock further load/extract
+    // scalarization opportunities.
+    if (IEI->use_empty())
+      IEI->eraseFromParent();
+    if (!Load->user_empty()) {
+      Instruction *UI = cast<Instruction>(*Load->user_begin());
+      scalarizeLoadExtract(*UI);
+    }
     return true;
   }
 
   return false;
 }
 
 /// Try to scalarize vector loads feeding extractelement instructions.
 bool VectorCombine::scalarizeLoadExtract(Instruction &I) {

llvm/test/Transforms/PhaseOrdering/AArch64/matrix-extract-insert.ll

 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast [225 x double]* [[A:%.*]] to <225 x double>*
 ; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[TMP3]], i64 0, i64 [[TMP1]]
 ; CHECK-NEXT:    [[MATRIXEXT:%.*]] = load double, double* [[TMP4]], align 8
 ; CHECK-NEXT:    [[CONV2:%.*]] = zext i32 [[I:%.*]] to i64
 ; CHECK-NEXT:    [[TMP5:%.*]] = add nuw nsw i64 [[TMP0]], [[CONV2]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp ult i64 [[TMP5]], 225
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[TMP6]])
 ; CHECK-NEXT:    [[TMP7:%.*]] = bitcast [225 x double]* [[B:%.*]] to <225 x double>*
-; CHECK-NEXT:    [[TMP8:%.*]] = load <225 x double>, <225 x double>* [[TMP7]], align 8
-; CHECK-NEXT:    [[MATRIXEXT4:%.*]] = extractelement <225 x double> [[TMP8]], i64 [[TMP5]]
+; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[TMP7]], i64 0, i64 [[TMP5]]
+; CHECK-NEXT:    [[MATRIXEXT4:%.*]] = load double, double* [[TMP8]], align 8
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul double [[MATRIXEXT]], [[MATRIXEXT4]]
-; CHECK-NEXT:    [[MATRIXEXT7:%.*]] = extractelement <225 x double> [[TMP8]], i64 [[TMP1]]
-; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[MATRIXEXT7]], [[MUL]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[TMP7]], i64 0, i64 [[TMP1]]
-; CHECK-NEXT:    store double [[SUB]], double* [[TMP9]], align 8
+; CHECK-NEXT:    [[MATRIXEXT7:%.*]] = load double, double* [[TMP9]], align 8
+; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[MATRIXEXT7]], [[MUL]]
+; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[TMP7]], i64 0, i64 [[TMP1]]
+; CHECK-NEXT:    store double [[SUB]], double* [[TMP10]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %i.addr = alloca i32, align 4
   %k.addr = alloca i32, align 4
   %j.addr = alloca i32, align 4
   %A.addr = alloca [225 x double]*, align 8
   %B.addr = alloca [225 x double]*, align 8

llvm/test/Transforms/VectorCombine/AArch64/load-extract-insert-store-scalarization.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -vector-combine -S %s | FileCheck %s
 
 target triple = "arm64-apple-darwin"
 
 define void @load_extract_insert_store_const_idx(<225 x double>* %A) {
 ; CHECK-LABEL: @load_extract_insert_store_const_idx(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[LV:%.*]] = load <225 x double>, <225 x double>* [[A:%.*]], align 8
-; CHECK-NEXT:    [[EXT_0:%.*]] = extractelement <225 x double> [[LV]], i64 0
+; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[A:%.*]], i32 0, i64 1
+; CHECK-NEXT:    [[EXT_0:%.*]] = load double, double* [[TMP0]], align 8
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul double 2.000000e+01, [[EXT_0]]
-; CHECK-NEXT:    [[EXT_1:%.*]] = extractelement <225 x double> [[LV]], i64 1
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[A]], i32 0, i64 1
+; CHECK-NEXT:    [[EXT_1:%.*]] = load double, double* [[TMP1]], align 8
 ; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[EXT_1]], [[MUL]]
-; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[A]], i64 0, i64 1
-; CHECK-NEXT:    store double [[SUB]], double* [[TMP0]], align 8
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[A]], i64 0, i64 1
+; CHECK-NEXT:    store double [[SUB]], double* [[TMP2]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %lv = load <225 x double>, <225 x double>* %A, align 8
-  %ext.0 = extractelement <225 x double> %lv, i64 0
+  %ext.0 = extractelement <225 x double> %lv, i64 1
   %mul = fmul double 20.0, %ext.0
   %ext.1 = extractelement <225 x double> %lv, i64 1
   %sub = fsub double %ext.1, %mul
   %ins = insertelement <225 x double> %lv, double %sub, i64 1
   store <225 x double> %ins, <225 x double>* %A, align 8
   ret void
 }
 
 define void @load_extract_insert_store_var_idx_assume_valid(i64 %idx.1, i64 %idx.2, <225 x double>* %A) {
 ; CHECK-LABEL: @load_extract_insert_store_var_idx_assume_valid(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i64 [[IDX_1:%.*]], 225
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP_1]])
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i64 [[IDX_2:%.*]], 225
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP_2]])
-; CHECK-NEXT:    [[LV:%.*]] = load <225 x double>, <225 x double>* [[A:%.*]], align 8
-; CHECK-NEXT:    [[EXT_0:%.*]] = extractelement <225 x double> [[LV]], i64 [[IDX_1]]
+; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[A:%.*]], i32 0, i64 [[IDX_1]]
+; CHECK-NEXT:    [[EXT_0:%.*]] = load double, double* [[TMP0]], align 8
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul double 2.000000e+01, [[EXT_0]]
-; CHECK-NEXT:    [[EXT_1:%.*]] = extractelement <225 x double> [[LV]], i64 [[IDX_2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[A]], i32 0, i64 [[IDX_2]]
+; CHECK-NEXT:    [[EXT_1:%.*]] = load double, double* [[TMP1]], align 8
 ; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[EXT_1]], [[MUL]]
-; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[A]], i64 0, i64 [[IDX_1]]
-; CHECK-NEXT:    store double [[SUB]], double* [[TMP0]], align 8
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds <225 x double>, <225 x double>* [[A]], i64 0, i64 [[IDX_1]]
+; CHECK-NEXT:    store double [[SUB]], double* [[TMP2]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp.1 = icmp ult i64 %idx.1, 225
   call void @llvm.assume(i1 %cmp.1)
   %cmp.2 = icmp ult i64 %idx.2, 225
   call void @llvm.assume(i1 %cmp.2)