[GVN] Disallow phi translation for expressions with calls.

[asbirlea]

Summary

Phi translation for expressions with calls may lead to miscompiles in the absence of additional checks for memory interfering instructions.
See PR42605, for additional details.
Resolves PR42605.

[wmi]

Thanks Alina to analyze the problem and write the fix.

I agree with your analysis and I believe the patch could fix the problem. But I am little worried the blunt hammer fix could pontentially hurt performance. Maybe we can use MD to do a finegrain check? I draft a fix attached. Please take a look whether it is correct and free to change it. {F9879631}

[wmi]

In D66909#1651640, @wmi wrote:

Thanks Alina to analyze the problem and write the fix.

I agree with your analysis and I believe the patch could fix the problem. But I am little worried the blunt hammer fix could pontentially hurt performance. Maybe we can use MD to do a finegrain check? I draft a fix attached. Please take a look whether it is correct and free to change it. {F9879631}

The previous patch uploaded is somehow not intact. Upload it another time:

patch.txt2 KBDownload

[asbirlea]

Thanks Wei, I think the patch you sent looks like a good path forward. I'd have a few comments on it.
Do you want to send it for review and pick up the test from this patch? I'll be happy to review it.

[wmi]

In D66909#1651731, @asbirlea wrote:

Thanks Wei, I think the patch you sent looks like a good path forward. I'd have a few comments on it.
Do you want to send it for review and pick up the test from this patch? I'll be happy to review it.

Thanks Alina. Send https://reviews.llvm.org/D67013 for review. I found MemDepResult with 'Def' DefType won't give us the collection of calls we want. It will give us the collection of identical calls without clobber between them and the current call, however, the identical criteria is too strict to accommodate phi-translate case.

So currently D67013 only does phitranslate for the call instruction with NonFuncLocal type MemDepResult, i.e., no clobber instruction in current function, and it is still conservative.

lib/Transforms/Scalar/GVN.cpp

uint32_t GVN::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
   // a backedge. We can do an early exit in that case to save compile time.
   if (!areAllValsInBB(Num, PhiBlock, Gvn))
     return Num;
 
   if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
     return Num;
   Expression Exp = Expressions[ExprIdx[Num]];
 
+  // Number assignment to expressions assumes that a new number for an
+  // expression makes two Calls distinct, hence there are no further checks for
+  // interfering/aliasing instructions. Do not do Phi translation for
+  // expressions with calls, as this breaks this assumption. Phi translation
+  // could be allowed if MemDep checks similar to the ones in lookupOrAddCall
+  // are added before updating Exp.varargs below.
+  if (Exp.opcode == Instruction::Call)
+    return Num;
+
   for (unsigned i = 0; i < Exp.varargs.size(); i++) {
     // For InsertValue and ExtractValue, some varargs are index numbers
     // instead of value numbers. Those index numbers should not be
     // translated.
     if ((i > 1 && Exp.opcode == Instruction::InsertValue) ||
         (i > 0 && Exp.opcode == Instruction::ExtractValue))
       continue;
     Exp.varargs[i] = phiTranslate(Pred, PhiBlock, Exp.varargs[i], Gvn);

test/Transforms/GVN/pr42605.ll

+; RUN: opt -gvn %s -S | FileCheck %s
+; CHECK: %tmp4 = extractvalue { i8*, i8* } %call6, 0
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@.str = private unnamed_addr constant [7 x i8] c"%p %p\0A\00", align 1
+@a = global i32 0, align 4
+
+; Function Attrs: nounwind readonly
+define { i8*, i8* } @entry(i32 %index) #0 {
+entry:
+  %entry0 = load i32, i32* @a, align 4
+  %cmp = icmp eq i32 %entry0, 0
+  %first = select i1 %cmp, i8* null, i8* inttoptr (i64 291 to i8*)
+  %second = select i1 %cmp, i8* null, i8* inttoptr (i64 1110 to i8*)
+  %.fca.0.insert = insertvalue { i8*, i8* } undef, i8* %first, 0
+  %.fca.1.insert = insertvalue { i8*, i8* } %.fca.0.insert, i8* %second, 1
+  ret { i8*, i8* } %.fca.1.insert
+}
+
+; Function Attrs: nounwind
+define i32 @main() #1 {
+entry:
+  %call129 = tail call { i8*, i8* } @entry(i32 0)
+  %tmp1 = extractvalue { i8*, i8* } %call129, 0
+  %cmp30 = icmp eq i8* %tmp1, null
+  br i1 %cmp30, label %cleanup.lr.ph, label %while.end
+
+cleanup.lr.ph:                                    ; preds = %entry
+  br label %cleanup
+
+cleanup:                                          ; preds = %cleanup, %cleanup.lr.ph
+  %index.031 = phi i32 [ 0, %cleanup.lr.ph ], [ %inc, %cleanup ]
+  %inc = add nsw i32 %index.031, 1
+  %call1 = tail call { i8*, i8* } @entry(i32 %inc)
+  %tmp3 = extractvalue { i8*, i8* } %call1, 0
+  %cmp = icmp eq i8* %tmp3, null
+  br i1 %cmp, label %while.end, label %cleanup
+
+while.end:                                        ; preds = %cleanup, %entry
+  %index.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %cleanup ]
+  store i32 1, i32* @a, align 4
+  %call6 = tail call { i8*, i8* } @entry(i32 %index.0.lcssa)
+  %tmp4 = extractvalue { i8*, i8* } %call6, 0
+  %tmp5 = extractvalue { i8*, i8* } %call6, 1
+  %call8 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @.str, i64 0, i64 0), i8* %tmp4, i8* %tmp5)
+  ret i32 0
+}
+
+; Function Attrs: nounwind
+declare i32 @printf(i8* nocapture readonly %0, ...) #1
+
+attributes #0 = { nounwind readonly }
+attributes #1 = { nounwind }