Strip metadata when speculatively hoisting instructions

[igor-laevsky]

Summary

This is fix for PR24059.

When we are hoisting instruction above some condition it may turn out that metadata on this instruction was control dependant on the condition. So metadata on the hoisted instruction becomes invalid and we need to drop it. See the bug and test cases for the llvm-ir examples.

This patch should cover most obvious places of speculative execution (which I have found by greping isSafeToSpeculativelyExecute). I think there is more cases but at least it covers the severe ones.

[sanjoy]

With the nits addressed, this LGTM.

lib/Analysis/LoopInfo.cpp

125 ↗

(On Diff #39410)

Nit: "dependent"

126 ↗

(On Diff #39410)

Nit: Conservatively strip

Fix these spelling errors elsewhere too.

lib/Transforms/Scalar/LICM.cpp

675 ↗

(On Diff #39410)

This is clearly a step in the right direction.

However, I think we can be more precise than this: (unless I'm missing something) if we justified hoisting the operation using isGuaranteedToExecute and not via isSafeToSpeculativelyExecute, I think we can keep the metadata. Perhaps something like that could be done in a separate patch?

[igor-laevsky]

lib/Transforms/Scalar/LICM.cpp

675 ↗

(On Diff #39410)

I think you are right. I'll probably try to come up with something about this.

llvm/trunk/lib/Analysis/LoopInfo.cpp

bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
   }
   // Don't hoist instructions with loop-variant operands.
   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
     if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt))
       return false;
 
   // Hoist.
   I->moveBefore(InsertPt);
+
+  // There is possibility of hoisting this instruction above some arbitrary
+  // condition. Any metadata defined on it can be control dependent on this
+  // condition. Conservatively strip it here so that we don't give any wrong
+  // information to the optimizer.
+  I->dropUnknownNonDebugMetadata();
+
   Changed = true;
   return true;
 }
 
 /// getCanonicalInductionVariable - Check to see if the loop has a canonical
 /// induction variable: an integer recurrence that starts at 0 and increments
 /// by one each time through the loop.  If so, return the phi node that
 /// corresponds to it.

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

 /// is safe to hoist, this instruction is called to do the dirty work.
 ///
 static bool hoist(Instruction &I, BasicBlock *Preheader) {
   DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": "
         << I << "\n");
   // Move the new node to the Preheader, before its terminator.
   I.moveBefore(Preheader->getTerminator());
 
+  // Metadata can be dependent on the condition we are hoisting above.
+  // Conservatively strip all metadata on the instruction.
+  I.dropUnknownNonDebugMetadata();
+
   if (isa<LoadInst>(I)) ++NumMovedLoads;
   else if (isa<CallInst>(I)) ++NumMovedCalls;
   ++NumHoisted;
   return true;
 }
 
 /// Only sink or hoist an instruction if it is not a trapping instruction,
 /// or if the instruction is known not to trap when moved to the preheader.

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

if (SpeculatedStoreValue) {
     Value *FalseV = SpeculatedStoreValue;
     if (Invert)
       std::swap(TrueV, FalseV);
     Value *S = Builder.CreateSelect(BrCond, TrueV, FalseV, TrueV->getName() +
                                     "." + FalseV->getName());
     SpeculatedStore->setOperand(0, S);
   }
 
+  // Metadata can be dependent on the condition we are hoisting above.
+  // Conservatively strip all metadata on the instruction.
+  for (auto &I: *ThenBB)
+    I.dropUnknownNonDebugMetadata();
+
   // Hoist the instructions.
   BB->getInstList().splice(BI->getIterator(), ThenBB->getInstList(),
                            ThenBB->begin(), std::prev(ThenBB->end()));
 
   // Insert selects and rewrite the PHI operands.
   IRBuilder<true, NoFolder> Builder(BI);
   for (BasicBlock::iterator I = EndBB->begin();
        PHINode *PN = dyn_cast<PHINode>(I); ++I) {

llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/licm.ll

 ; RUN: opt -tbaa -licm -S < %s | FileCheck %s
 
 ; LICM should be able to hoist the address load out of the loop
 ; by using TBAA information.
 
 ; CHECK: @foo
 ; CHECK:      entry:
-; CHECK-NEXT:   %tmp3 = load double*, double** @P, !tbaa !0
+; CHECK-NEXT:   %tmp3 = load double*, double** @P
 ; CHECK-NEXT:   br label %for.body
 
 @P = common global double* null
 
 define void @foo(i64 %n) nounwind {
 entry:
   br label %for.body
 

llvm/trunk/test/Transforms/LICM/hoist-deref-load.ll

for.inc:                                          ; preds = %for.body, %if.then
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, %n
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.inc, %entry
   ret void
 }
 
+; In this test we should be able to only hoist load from %cptr. We can't hoist
+; load from %c because it's dereferenceability can depend on %cmp1 condition.
+; By moving it out of the loop we break this dependency and can not rely
+; on the dereferenceability anymore.
+; In other words this test checks that we strip dereferenceability  metadata
+; after hoisting an instruction.
+
+; CHECK-LABEL: @test10
+; CHECK: %c = load i32*, i32** %cptr
+; CHECK-NOT: dereferenceable
+; CHECK: if.then:
+; CHECK: load i32, i32* %c, align 4
+
+define void @test10(i32* noalias %a, i32* %b, i32** dereferenceable(8) %cptr, i32 %n) #0 {
+entry:
+  %cmp11 = icmp sgt i32 %n, 0
+  br i1 %cmp11, label %for.body, label %for.end
+
+for.body:                                         ; preds = %entry, %for.inc
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %0, 0
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %c = load i32*, i32** %cptr, !dereferenceable !0
+  %1 = load i32, i32* %c, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %2 = load i32, i32* %arrayidx3, align 4
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc, %entry
+  ret void
+}
+
 attributes #0 = { nounwind uwtable }
 !0 = !{i64 4}

llvm/trunk/test/Transforms/SimplifyCFG/SpeculativeExec.ll

 ; CHECK: phi i8*
 ; CHECK: phi i8*
 ; CHECK: phi i8*
 ; CHECK: phi i8*
 ; CHECK: phi i8*
 
   ret i8* %x10
 }
+
+define i32* @test5(i32 %a, i32 %b, i32 %c, i32* dereferenceable(10) %ptr1,
+                  i32* dereferenceable(10) %ptr2, i32** dereferenceable(10) %ptr3) nounwind {
+; CHECK-LABEL: @test5(
+entry:
+        %tmp1 = icmp eq i32 %b, 0
+        br i1 %tmp1, label %bb1, label %bb3
+
+bb1:            ; preds = %entry
+  %tmp2 = icmp sgt i32 %c, 1
+  br i1 %tmp2, label %bb2, label %bb3
+; CHECK: bb1:
+; CHECK-NEXT: icmp sgt i32 %c, 1
+; CHECK-NEXT: load i32*, i32** %ptr3
+; CHECK-NOT: dereferenceable
+; CHECK-NEXT: select i1 %tmp2, i32* %tmp3, i32* %ptr2
+; CHECK-NEXT: ret i32* %tmp3.ptr2
+
+bb2:    ; preds = bb1
+        %tmp3 = load i32*, i32** %ptr3, !dereferenceable !{i64 10}
+  br label %bb3
+
+bb3:    ; preds = %bb2, %entry
+  %tmp4 = phi i32* [ %ptr1, %entry ], [ %ptr2, %bb1 ], [ %tmp3, %bb2 ]
+  ret i32* %tmp4
+}