Fix clang-format issue.

In D148420#4486924, @nikic wrote:

Fix the implementation by generating shl instruction instead of unset flags. Unsetting nuw/nsw flags was wrong when shl instruction has other use.

Generating a new shl isn't wrong, but I think your previous approach was better. The reason is that the shl with and without nowrap flags are going to be GVN/CSEd anyway, and the nowrap flags will be dropped in the process. So it makes more sense to me to directly go to the final form. Losing some nowrap flags is just the cost of this transform.

Try to fix builtbot fail on debian x64.

@kiranchandramohan BTW, please notice that ValueToValueMap in Loop Access Analysis is replaced by DenseMap<Value *, const SCEV *> in D147750 if you commandeer this patch and rebase it.

Thanks @nikic for the comments. Addressed them:

Update test cases.

In D127215#4481642, @NimishMishra wrote:

@kiranchandramohan @peixin If it is okay, I can rebase and merge this patch

Sorry for the continued ping. I hope to finish this patch by the end of next week due to work changes.

@kiranchandramohan Hi Kiran, could you please help commandeer this patch? I cannot continue working on it due to work changes.

@kiranchandramohan Hi Kiran, could you please help commandeer this patch? I cannot continue working on it due to work changes.

@kiranchandramohan Hi Kiran, could you please help commandeer this patch? I cannot continue working on it due to work changes.

Thanks @goldstein.w.n and @nikic for the comments. Addressed them.

@peixin your reproducer should be fixed by 7f5b15ad150e

gentle ping

In D153004#4469653, @fhahn wrote:

@peixin thanks for the additional test case! I precommitted a slightly reduced version of your test and should have a fix ready shortly

In D153004#4451053, @peixin wrote:

There may be one more case which this patch does not capture? Check the following input:

target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
target triple = "aarch64-unknown-linux-gnu"

@c = internal global i32 0, align 4
@g = dso_local local_unnamed_addr global ptr @c, align 8
@h = dso_local global i8 0, align 4
@j = dso_local local_unnamed_addr global ptr @h, align 8
@b = internal unnamed_addr global i32 0, align 4
@e = dso_local local_unnamed_addr global i16 0, align 4
@f = dso_local local_unnamed_addr global i64 0, align 8
@l = dso_local local_unnamed_addr global i64 0, align 8
@i = dso_local local_unnamed_addr global i64 0, align 8
@.str = private unnamed_addr constant [5 x i8] c"%lX\0A\00", align 1
@a = dso_local local_unnamed_addr global i8 0, align 1

; Function Attrs: mustprogress nofree norecurse nosync nounwind readnone willreturn uwtable
define dso_local void @n(ptr nocapture noundef %0) {
  ret void
}

; Function Attrs: nofree nounwind uwtable
define dso_local i32 @main() {
  %1 = load ptr, ptr @g, align 8
  %2 = load i64, ptr @f, align 8
  br label %3

3:                                                ; preds = %0, %18
  %4 = phi i32 [ 0, %0 ], [ %19, %18 ]
  %5 = phi i64 [ %2, %0 ], [ %15, %18 ]
  br label %6

6:                                                ; preds = %3, %6
  %7 = phi i32 [ 1, %3 ], [ %10, %6 ]
  %8 = phi i64 [ %5, %3 ], [ %9, %6 ]
  %9 = add nsw i64 %8, 1
  %10 = add nsw i32 %7, -1
  %11 = icmp sgt i32 %7, 0
  br i1 %11, label %6, label %12

12:                                               ; preds = %6, %12
  %13 = phi i32 [ %16, %12 ], [ 1, %6 ]
  %14 = phi i64 [ %15, %12 ], [ %9, %6 ]
  %15 = add nsw i64 %14, 1
  %16 = add nsw i32 %13, -1
  %17 = icmp sgt i32 %13, 0
  br i1 %17, label %12, label %18

18:                                               ; preds = %12
  %19 = add nuw nsw i32 %4, 1
  %20 = icmp eq i32 %19, 8
  br i1 %20, label %21, label %3

21:                                               ; preds = %18
  store i32 %16, ptr @b, align 4
  store i32 0, ptr %1, align 4
  %22 = zext i32 %13 to i64
  store i16 -1, ptr @e, align 4
  store i64 %15, ptr @f, align 8
  store i64 %14, ptr @l, align 8
  store i64 %22, ptr @i, align 8
  %23 = urem i32 %16, 53
  %24 = trunc i32 %23 to i8
  %25 = load ptr, ptr @j, align 8
  store i8 %24, ptr %25, align 1
  %26 = load i8, ptr @h, align 4
  %27 = xor i8 %26, 5
  %28 = zext i8 %27 to i64
  %29 = tail call i32 (ptr, ...) @printf(ptr noundef nonnull @.str, i64 noundef %28)
  ret i32 0
}

declare noundef i32 @printf(ptr nocapture noundef readonly, ...)

$ opt -loop-reduce reduced.ll -S -o out.ll && clang out.ll -o a.out && ./a.out
B
$ clang reduced.ll -o a.out && ./a.out
2C

There may be one more case which this patch does not capture? Check the following input:

target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
target triple = "aarch64-unknown-linux-gnu"

In D129969#4420425, @kiranchandramohan wrote:

Adding Peixin and Val as Co-authors and commandeering this patch. Authorship will revert to Peixin on submission.

Thanks @vdonaldson. That sounds fine to me. Multiple OpenMP terminators are allowed. This will fix the two tests I had previously put up.

@peixin Could you share a testcase that shows the MLIR DCE issue

In D129969#4410385, @kiranchandramohan wrote:

In D129969#4183536, @vdonaldson wrote:

In D129969#4182999, @kiranchandramohan wrote:

Adding @vdonaldson also to check whether this is the right way to do this and also for the interaction with the block construct.

If the problem is that an existing required omp.terminator or omp.yield op is in danger of being deleted, would it suffice to check for that in genStopStatement code? If blockIsUnterminated from Bridge.cpp were available for use in Runtime.cpp that could be done like this:

@@ -106,6 +106,7 @@ void Fortran::lower::genStopStatement(
   }

   builder.create<fir::CallOp>(loc, callee, operands);
+  if (blockIsUnterminated())
     genUnreachable(builder, loc);
 }

If that is the right idea, then blockIsUnterminated or an alternative way of getting that information must be available in Runtime.cpp.

@peixin Can you implement what Val is suggesting here? This will not fix the two examples that I have provided but will fix a lot of usages of STOP. We can handle the other cases separately.

In D151394#4377695, @nikic wrote:

I think what I still don't really understand is why LSR thinks it is safe to replace the IV here when it isn't. It seems like marking the urem as interesting here may be non-profitable, but also shouldn't be incorrect. I think there has to be some bug on the LSR side to enable this replacement.

Note that urem is not the only non-add instruction that can end up producing an add SCEV node, so I'm not sure why we need to treat urem in particular specially.

In D151394#4372286, @nikic wrote:

Can you please explain in more detail what causes the miscompile in the first place?

ping for review @nikic

Upload the right patch.

It seems I uploaded the wrong patch.

Address the comments from @nikic .

In D148420#4315381, @nikic wrote:

Just took a closer look at this. This is one of those transforms where we need to be very careful about derefinement, because we're replacing a constant 0 with an instruction that (under the given condition) may refine to zero but is not necessarily equivalent to zero.

In particular, if the shl has nowrap flags, this transform is incorrect: https://alive2.llvm.org/ce/z/EjBRVW

This means we need to drop nowrap flags as part of the transform. I'm afraid this means that my original recommendation to move this to InstSimplify was wrong and this should be in InstCombine after all, as we can only drop nowrap flags there.

@awarzynski Hi Andrzej, sorry for the late reply. I am distracted by several internal projects and other things in my life recently (just came back from vacation). My boss has not decided to let me continue working on LLVM Flang this year, yet.

In D148420#4298441, @nikic wrote:

In D148420#4295784, @peixin wrote:

In D148420#4291703, @nikic wrote:

It looks like this should be part of simplifySelectBitTest(), which covers other "select of icmp and" patterns.

It seems not, the CondVal in simplifySelectWithICmpCond is ICmp of value and zero. For cases in simplifySelectBitTest, the CondVal is ICmp of value and value.

Not sure I follow. Isn't it matching the (X & C) == 0 pattern here? https://github.com/llvm/llvm-project/blob/f6ec56ac5be26ad862e22d0eebb2645d1ad78218/llvm/lib/Analysis/InstructionSimplify.cpp#L4494-L4500

In D148420#4291703, @nikic wrote:

It looks like this should be part of simplifySelectBitTest(), which covers other "select of icmp and" patterns.

gentle ping

Addressed the comments.

Address the comments.

1. Move to instsimplify.
2. Add support for vector type.

1. Address the comments.
2. Reverse to the previous implementation since it is more robust. The use of gep instruction may not be load or store instruction.

Address the comments.

ping for review

Rebase and refine the implementation so that it is more readable.

Simplify the implementation.

Found one more problem, the symbolic strides in vector.ph are not replaced, either, although it's negligible.

D147378 made changes for 12 lines for strided-accesses.ll.

Thanks for the update. The whole design looks good to me now. Thanks for the work.

In D141820#4243777, @vzakhari wrote:

In D141820#4226126, @peixin wrote:

In D141820#4224901, @vzakhari wrote:

In D141820#4221238, @peixin wrote:

Hi @vzakhari , are you still working on box/type descriptor such as type_desc_4/5/6? Or do you plan to work on that later? I am studying some optimizations which may benefit from the complete tbaa.

Hi @peixin, I am not working on this. Can you please share the cases where you think it might be profitable to distinguish boxes with different number of dimensions? Is it from real applications? We can discuss it in email - it seems more convenient.

Yes, it's from one real application, and the hot loop is from one specific input. The loop is like the following where a is assumed shape array, and b is explicit-shape array. To perform the loop interchange optimization, one problem is that it is hard to understand the loop structure from the SCEV of a(i, k) access. I am thinking if the tbaa lower bound, upper bound and stride would help.

DO j=Jstart, Jend
  DO i=Istart, Iend
    DO k=1, N
      a(i,k)=0.5_8*(b(i-1,j,k) + b(i  ,j,k))
    END DO
  END DO
END DO

Hi @peixin, sorry, I do not understand how more specific tbaa for the members of the descriptor can help here. This loop has a single "data" store for a(i,k). The loads of the descriptor members are also inside the loop, but the current tbaa should allow disambiguating the data store with the member loads. So LLVM should be able to hoist the member loads from the loop nest with the current tbaa, since they are invariants.

I suppose the load from N might be a problem for the loop interchange, since the current tbaa does not help disambiguating load from N with the store to a(i,k) inside the outer loop. But having more precise tbaa for the descriptor members won't help here as well.

Why do you remove the StrideSet? It can be used to check the const stride in cost model very fast. Now, you check if it is constant one in PSE. The question is if all the const one in PSE are the strides?

In D147539#4245938, @reames wrote:

JFYI, I find the description on this patch confusing. I think I've managed to understand it, but let me confirm.

Given an induction variable with a loop invariant (but not constant) stride, LAA currently speculates the stride is 1. In the case where the access type and the index type differ, this results in a meaningless speculation. Instead of unconditionally speculating 1, we can speculate that the stride is the constant required to stride sizeof(element-type) on each iteration.

Is that a correct understanding?

Strange. One of my inlined comment is lost.

So, I will have a closer look at this, but IF the call was made with a contiguous array, it would benefit a fair amount, since it vectorizes the loop - I will try to do a compare "with and without" benchmark thing.

Fix failed tests with ARM and RISCV backends. Replace the strides with const values in vector region, which is expected with this patch.

Thanks @peixin. We were looking at some kernels from lapack. Some of the complex type kernels give an order-of-magnitude slowdown compared to classic-flang. We see plenty of memchecks generated by the llvm vectorizer for an inner loop. But these were not present for the real type kernels. We are not yet sure whether these are caused by a lack of alias info or something specific to the Complex vectorisation in llvm.

@SBallantyne also ran into some cases where additional tbaa information is useful. It is not clear yet whether this involves tbaa for dummy arguments as well. If we can discuss this in discourse that would be great since we can also participate or stay informed.

In D141820#4224901, @vzakhari wrote:

In D141820#4221238, @peixin wrote:

Hi @vzakhari , are you still working on box/type descriptor such as type_desc_4/5/6? Or do you plan to work on that later? I am studying some optimizations which may benefit from the complete tbaa.

Hi @peixin, I am not working on this. Can you please share the cases where you think it might be profitable to distinguish boxes with different number of dimensions? Is it from real applications? We can discuss it in email - it seems more convenient.

In D145684#4223733, @kiranchandramohan wrote:

Thanks @peixin for the patch.

I was wondering where is the right place to fix this issue. I see that this works correctly when a block construct is present with handling in Lowering. A modified version of one of your tests would be,

module tpmod
  real :: val = 2.0
end module

subroutine tptest
  use tpmod
  call tps()
contains
  subroutine tps()
    !$omp parallel
    block
      val = 1.0
    end block
    !$omp end parallel
  end subroutine
end subroutine

Would calling instantiateVar for the scope variables as is done for block (https://github.com/llvm/llvm-project/blob/2d68a42f084a460007b368eab191cf0ff1b976d7/flang/lib/Lower/Bridge.cpp#L2282) help fix the issue? Or did you try this and face any issues?

Hi @vzakhari , are you still working on box/type descriptor such as type_desc_4/5/6? Or do you plan to work on that later? I am studying some optimizations which may benefit from the complete tbaa.

Thanks @peixin for the comment. Mats is away and is only back in April.

The loop versioning is inefficient for the following scenario, in which not all arrays are contiguous in a loop. Maybe there should be one cost model to perform the loop versioning, and be refined driven by the cases in real workloads?

subroutine vadd(c, a, b, n)
  implicit none
  real :: c(:), a(:), b(:)
  integer :: i, n

LGTM except one small problem

I failed to apply this patch locally.

FYI, another related scenario is https://github.com/llvm/llvm-project/issues/59388.

Yes, I've only spent SOME time trying to understand why vectorizer doesn't - it basically comes down to "can't figure out how the stride is calculated, and whether it may change over time". The loop versioning here is helping to solve that for the lower layers in the compiler - and in my experience (I've written quite a few different style loops and such), either some MLIR pass(es) manages to vectorize the codr, or LLVM loop vectorizer can't do it either. [Why is there two layers of vectorizers? I don't know - presumably people like to write code that does similar things on multiple levels].

I have not noticed any measurable increase in compile time - Spec 2017 wrf_r takes within 1-2 seconds, and that's the one that takes about 15 minutes to build in total. I'm not saying it's impossible to come up with something that compiles slowly with this code, but I've made as good an attempt as I can to "exit early" if there's nothing that needs doing, and only duplicate the innermost loop [which potentially is not the most optimal case].

I am thinking if we should do the loop versioning in MLIR since this may increase compilation time in optimization passes.

Thanks @kiranchandramohan for the provided test cases. It looks like this method is not good one.

Thanks @kiranchandramohan for the notice. Rebase to fix patch application fail.

In D129969#4181090, @clementval wrote:

In D129969#4181034, @peixin wrote:

In D129969#4181028, @clementval wrote:

We have such condition enforce in flang/lib/Semantics/check-directive-structure.h by the NoBranchingEnforce. I think STOP should follow this. Sorry I didn't think about this restriction before.

I removed the semantic checks in https://reviews.llvm.org/D126471. At that time, I have tested using gfortran to confirm it should be removed. Not your fault :)

Ok fine. nvfortran also accept this.