[SCEVExp] Advance found insertion point until we find a non-dbg instruction.

[fhahn]

Summary

This avoids creating unnecessary casts if the IP used to be a dbg info
intrinsic. Fixes PR37727.

[vsk]

Thanks for doing this. Do you think we have the same bug here w.r.t lifetime markers, assume intrinsics, etc? If so, maybe this patch would be the right vehicle to add something like Instruction::isMetaInstruction, as suggested by Hideki in a previous thread.

As far as testing is concerned, I’ve started running a script to check for debug info IR generation differences in the LLVM test suite. It could be worthwhile to check in a specific regression test, but at the moment this is a bit cumbersome to write. See this commit for an example: https://github.com/llvm-mirror/llvm/commit/8c3bbfcc15b89aad062e9b6e9251ce5666a43427

(Edited because I hit send too early.)

[fhahn]

Yep, I think the other meta instructions will cause problems here (and other places) too. I can add a test case for this patch to the loop vectorizer tests, which exposed this problem.

[aprantl]

Didn't we recently add a more convenient mechanism to determine all meta-instructions? Or am I misremembering and that was MIR?

[efriedma]

Not sure this is the best fix. The function is named findInsertPointAfter; from the name, I would expect it to behave similarly to BasicBlock::getFirstInsertionPt (which does not try to move past debug info).

We added instructionsWithoutDebug recently to deal with this sort of issue, but it's not directly usable here.

lib/Analysis/ScalarEvolutionExpander.cpp

95 ↗

(On Diff #150297)

This handling isn't consistent with the handling for landing pads/etc.

[fhahn]

In D47874#1125474, @efriedma wrote:

Not sure this is the best fix. The function is named findInsertPointAfter; from the name, I would expect it to behave similarly to BasicBlock::getFirstInsertionPt (which does not try to move past debug info).

We added instructionsWithoutDebug recently to deal with this sort of issue, but it's not directly usable here.

Yeah, maybe we should have a function that takes an iterator and advances the iterator to the first non debug/meta instruction?

[vsk]

In D47874#1125517, @fhahn wrote:

In D47874#1125474, @efriedma wrote:

Not sure this is the best fix. The function is named findInsertPointAfter; from the name, I would expect it to behave similarly to BasicBlock::getFirstInsertionPt (which does not try to move past debug info).

We added instructionsWithoutDebug recently to deal with this sort of issue, but it's not directly usable here.

Yeah, maybe we should have a function that takes an iterator and advances the iterator to the first non debug/meta instruction?

Yes, I think it makes sense to introduce this. It might also be convenient to add an analogous method to Instruction to replace some uses of getNextNode().

lib/Analysis/ScalarEvolutionExpander.cpp

95 ↗

(On Diff #150297)

Would it be correct to write "IP = advancePastNonAffectingInsts(IP)", everywhere we see "++IP" here?

[davide]

In D47874#1125517, @fhahn wrote:

In D47874#1125474, @efriedma wrote:

Not sure this is the best fix. The function is named findInsertPointAfter; from the name, I would expect it to behave similarly to BasicBlock::getFirstInsertionPt (which does not try to move past debug info).

We added instructionsWithoutDebug recently to deal with this sort of issue, but it's not directly usable here.

Yeah, maybe we should have a function that takes an iterator and advances the iterator to the first non debug/meta instruction?

I think so, we could also refactor rL334317 to be less cumbersome.
Are you going to work on this or you want me to? [I suspect we're going to find more places where we need the utility so the sooner we get this done, the better].

[fhahn]

In D47874#1126869, @davide wrote:

In D47874#1125517, @fhahn wrote:

In D47874#1125474, @efriedma wrote:

Not sure this is the best fix. The function is named findInsertPointAfter; from the name, I would expect it to behave similarly to BasicBlock::getFirstInsertionPt (which does not try to move past debug info).

We added instructionsWithoutDebug recently to deal with this sort of issue, but it's not directly usable here.

Yeah, maybe we should have a function that takes an iterator and advances the iterator to the first non debug/meta instruction?

I think so, we could also refactor rL334317 to be less cumbersome.
Are you going to work on this or you want me to? [I suspect we're going to find more places where we need the utility so the sooner we get this done, the better].

Something straight forward would be to just add something like the skipDebug below as a static function to BasicBlock, similar to instructionsWithoutDebug

+BasicBlock::iterator BasicBlock::skipDebug(iterator Iter) {
+  while (isa<DbgInfoIntrinsic>(*Iter))
+    Iter++;
+  return Iter;
+}

I am happy to add something like that, but I will only get around to that early next week I guess. Maybe it would be even better to have this helper skip all 'meta' instructions that are not supposed to have an impact on codegen and also adopt instructionsWithoutDebug. Otherwise those issues will just keep popping up for various kinds of such instructions.

[fhahn]

Or maybe it would be even more convenient to just have a new iterator type, which skips such meta instructions.

[vsk]

In D47874#1126902, @fhahn wrote:

Or maybe it would be even more convenient to just have a new iterator type, which skips such meta instructions.

Presumably there's a lot of pre-existing code which traffics in BasicBlock::iterator. It might be hard to refactor that code to use a different iterator kind.

Something straight forward would be to just add something like the skipDebug below as a static function to BasicBlock

My preference is to have a function in the llvm namespace which advances a BasicBlock::iterator, because I don't think of a BasicBlock as something that can advance an iterator.

Yeah, maybe we should have a function that takes an iterator and advances the iterator to the first non debug/meta instruction?

I think so, we could also refactor rL334317 to be less cumbersome.
Are you going to work on this or you want me to? [I suspect we're going to find more places where we need the utility so the sooner we get this done, the better].

I'm going on a week-long vacation starting tomorrow, so I'm happy to have someone else push this forward :).

Skimming through the LangRef, here are the intrinsics which should be non-affecting: llvm.donothing, llvm.dbg.*, and llvm.{var, ptr, }.annotation.*. I'm skeptical of adding lifetime markers and llvm.assume to this list, because these intrinsics have behaviors that optimizations may want to consider.

[davide]

In D47874#1126902, @fhahn wrote:

Or maybe it would be even more convenient to just have a new iterator type, which skips such meta instructions.

The reason I don't necessarily want to go that route is that people now have to think about which iterator they should use when walking instructions in a BB.
I think it creates more confusion than it helps. Your other idea is fine to me, but I'd love to hear from others (Eli/Vedant/Adrian etc.)

[fhahn]

I've updated the patch to add a skipDebugInstructionsForward utility. We have a very similar function defined in MachineBasicBlock.h, maybe we should consolidate those functions?

With this approach, there is one scenario where we could still get different codegen depending on debug info if there are debug intrinsics before a funclet/landingpad instruction.

[aprantl]

In D47874#1132374, @fhahn wrote:

I've updated the patch to add a skipDebugInstructionsForward utility. We have a very similar function defined in MachineBasicBlock.h, maybe we should consolidate those functions?

The MachineBasicBlock.h function operates on MachineInstrs the one in BasicBlock operates on Instructions. I'm not sure how to unify these: perhaps by adding a skipForwardWhile(std::function(bool() shouldSkip) primitive to ilist?

[dblaikie]

Probably overkill, but I'd imagine the way to do this would be a trait
class that implements the two different tests depending on the type of the
node. (I guess a generic "isDebugInstruction" function that uses that trait
could be a handy general purpose tool to have, maybe? (so you don't have to
think so hard about different way s of testing whether something is a debug
instruction in MC versus IR))

[fhahn]

I like the trait suggestion! There potentially are a few useful helper functions we provide, and using a trait we could provide them in a generic way for both IR and machine instructions & co. As it is now, I am just slightly worried that we will end up with 2 different but quite similar APIs for dealing with debug info in IR/machine instructions.

[vsk]

include/llvm/IR/BasicBlock.h

440 ↗

(On Diff #151344)

I think this should skip llvm.ptr.annotation, llvm.var.annotation, etc. as well.

Stepping back a bit, I shouldn't have suggested adding a 'skip meta instruction' API as a part of your SCEVExpander bug fix. IMO it would be cleaner to split the new API out, add a unit test, and incorporate some light refactoring along with it.

Would you mind if I started a separate review to add this API? I had a patch for this prepped before I went out-of-office, but didn't have the time to start a review then. I'd be happy to take a stab at this.

[mattd]

In D47874#1125451, @aprantl wrote:

Didn't we recently add a more convenient mechanism to determine all meta-instructions? Or am I misremembering and that was MIR?

Perhaps you are thinking about MachineInstr::isMetaInstruction?
https://llvm.org/doxygen/MachineInstr_8h_source.html#l00918

[fhahn]

include/llvm/IR/BasicBlock.h

440 ↗

(On Diff #151344)

Would you mind if I started a separate review to add this API? I had a patch for this prepped before I went out-of-office, but didn't have the time to start a review then. I'd be happy to take a stab at this.

Not at all, that would be great. I will probably only be able to pick this patch up again in a couple of days.

[vsk]

include/llvm/IR/BasicBlock.h

440 ↗

(On Diff #151344)

Great, 'rL335083: [IR] Introduce helpers to skip debug instructions (NFC)' has landed, hope that helps.

[fhahn]

Update to use skipDebugInfo introduced in rL335083

[efriedma]

LGTM assuming you're planning to regression-test this somehow.

[vsk]

In D47874#1139746, @efriedma wrote:

LGTM assuming you're planning to regression-test this somehow.

I'm planning on verifying the change. The testing process is roughly:
$ find test/Transforms -name \*.ll | parallel opt-check-dbg-invar.sh $OPT {} -loop-vectorize

lib/Analysis/ScalarEvolutionExpander.cpp

105 ↗

(On Diff #152287)

Why not skip debug instructions here, instead? It should make less work for callers of findInsertPointAfter, right?

95 ↗

(On Diff #150297)

I suppose this wouldn't be useful, because dbg.values aren't allowed to occur before phis / eh instructions.

[fhahn]

Added test case.

[fhahn]

lib/Analysis/ScalarEvolutionExpander.cpp

105 ↗

(On Diff #152287)

IIRC Eli suggested to not do it in this function, as it should behave similar to BasicBlock::getFirstInsertionPt , which also does not skip debug info.

[vsk]

LGTM, thanks!

[fhahn]

I had to revert this, as there is crash in relwithdebug builds, presumably because insertion points get out of sync. I'll do some digging.

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

while ((isa<BitCastInst>(IP) &&
             cast<BitCastInst>(IP)->getOperand(0) != A) ||
            isa<DbgInfoIntrinsic>(IP))
       ++IP;
     return ReuseOrCreateCast(A, Ty, Op, IP);
   }
 
   // Cast the instruction immediately after the instruction.
   Instruction *I = cast<Instruction>(V);
-  BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock());
+  BasicBlock::iterator IP = skipDebugInfo(
+      findInsertPointAfter(I, Builder.GetInsertBlock()));
   return ReuseOrCreateCast(I, Ty, Op, IP);
 }
 
 /// InsertBinop - Insert the specified binary operator, doing a small amount
 /// of work to avoid inserting an obviously redundant operation.
 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
                                  Value *LHS, Value *RHS) {
   // Fold a binop with constant operands.
Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
   if (CanonicalIV &&
       SE.getTypeSizeInBits(CanonicalIV->getType()) >
       SE.getTypeSizeInBits(Ty)) {
     SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
     for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
       NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
     Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
                                        S->getNoWrapFlags(SCEV::FlagNW)));
-    BasicBlock::iterator NewInsertPt =
-        findInsertPointAfter(cast<Instruction>(V), Builder.GetInsertBlock());
+    BasicBlock::iterator NewInsertPt = skipDebugInfo(
+        findInsertPointAfter(cast<Instruction>(V), Builder.GetInsertBlock()));
     V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
                       &*NewInsertPt);
     return V;
   }
 
   // {X,+,F} --> X + {0,+,F}
   if (!S->getStart()->isZero()) {
     SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end());

llvm/trunk/test/Transforms/LoopVectorize/scev-expander-debug.ll

+; RUN: opt -loop-vectorize %s -S | FileCheck %s
+; Tests that the debug intrinsic does not cause additional instructions to be
+; created by SCEVExpander.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.s = type { double* }
+
+; CHECK-LABEL: entry:
+; CHECK: %[[LV:.+]] = load double*, double** %a
+; CHECK-NEXT: call void @llvm.dbg.value(metadata double* %[[LV]]
+; CHECK-NEXT: %[[PTI:.+]] = ptrtoint double* %[[LV]] to i64
+; CHECK-NEXT: %[[MPTR:.+]] = and i64 %[[PTI]], 31
+; CHECK-NEXT: %[[MCOND:.+]] = icmp eq i64 %[[MPTR]], 0
+; CHECK-NEXT: br i1 false, label %scalar.ph, label %vector.scevcheck
+
+
+define void @test(%struct.s* %x) !dbg !6 {
+entry:
+  %a = getelementptr inbounds %struct.s, %struct.s* %x, i64 0, i32 0
+  %0 = load double*, double** %a, align 8
+  call void @llvm.dbg.value(metadata double* %0, metadata !9, metadata !DIExpression()), !dbg !11
+  %ptrint = ptrtoint double* %0 to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next.1, %for.body ]
+  %arrayidx = getelementptr inbounds double, double* %0, i64 %indvars.iv
+  %1 = load double, double* %arrayidx, align 16
+  %add = fadd double %1, 1.000000e+00
+  store double %add, double* %arrayidx, align 16
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %arrayidx.1 = getelementptr inbounds double, double* %0, i64 %indvars.iv.next
+  %2 = load double, double* %arrayidx.1, align 8
+  %add.1 = fadd double %2, 1.000000e+00
+  store double %add.1, double* %arrayidx.1, align 8
+  %indvars.iv.next.1 = add nuw nsw i64 %indvars.iv.next, 1
+  %exitcond.1 = icmp eq i64 %indvars.iv.next, 1599
+  br i1 %exitcond.1, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "debugify", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "file.ll", directory: "/")
+!2 = !{}
+!5 = !{i32 2, !"Debug Info Version", i32 3}
+!6 = distinct !DISubprogram(name: "test", linkageName: "test", scope: null, file: !1, line: 1, type: !7, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !0)
+!7 = !DISubroutineType(types: !2)
+!9 = !DILocalVariable(name: "1", scope: !6, file: !1, line: 1, type: !10)
+!10 = !DIBasicType(name: "ty64", size: 64, encoding: DW_ATE_unsigned)
+!11 = !DILocation(line: 1, column: 1, scope: !6)