Page MenuHomePhabricator

[SCEV] CreateNodeForPhi should return SCEVUnknown for incomplete PHIs
Needs ReviewPublic

Authored by w2yehia on Apr 6 2020, 8:40 AM.

Details

Summary

The problem

SCEVExpander::getAddRecExprPHILiterally might call itself recursively (when calling expandIVInc), and in the process attempts to create a SCEV for the PHINode it is constructing. The resulting SCEV would never be correct.
ScalaraEvolution caches SCEVs in ValueExprMap, and ScalarEvolution::getSCEV(Value*) uses that cache.

The issue is that two different PHIs, might look the same when they are in an incomplete state, for example:

%incomplete_1 = phi i32 [0, %entry]   ;; missing incoming value from the latch block
%incomplete_2 = phi i32 [0, %entry]   ;; missing incoming value from the latch block

and so createSCEV would return the same, incorrect, SCEV value for both.

Users of ScalarEvolution, such as Loop Strength Reduction, assume that two Values that have the same SCEV are "equivalent".

Solution 1 (this patch):

ScalarEvolution::createSCEV returns SCEVUnknown for incomplete SCEVs.
According to the discussion here: http://lists.llvm.org/pipermail/llvm-dev/2017-May/112541.html and doing a quick scan of llvm source, we assume that for every predecessor block there is a corresponding incoming value in the PHI, even for duplicate predecessors.

Solution 2 (not implemented):

Have SCEVExpander::getAddRecExprPHILiterally delete the old entry in ValueExprMap when a new incoming value is added to the PHI that is under construction.
Actually, any other data structure that stores the "incorrect" SCEV should prune it. Which leads to thinking that some sort of call back mechanism has to be used when an incoming value is added to the PHI. I couldn't find such a call back. CallBackVH only deals with deleting and replacing a Value

Testcase:

I have the following reduced testcase from bugpoint, but I don't see how useful it is or to how make it useful:

source_filename = "t.cpp"
target datalayout = "e-m:e-i64:64-n32:64"
target triple = "powerpc64le-unknown-linux-gnu"

define dso_local void @foo(i32* %.n) local_unnamed_addr {
foo_entry:
  %n = load i32, i32* %.n, align 4
  %_conv19 = sext i32 %n to i64
  br label %_loop_4_do_

_loop_4_do_:                                      ; preds = %_loop_7_endl_, %foo_entry
  %lda.0304 = phi i64 [ undef, %foo_entry ], [ %_add_tmp68, %_loop_7_endl_ ]
  %ib.0302 = phi i64 [ 0, %foo_entry ], [ %_add_tmp84, %_loop_7_endl_ ]
  %_add_tmp66 = add nsw i64 %lda.0304, %_conv19
  %_add_tmp68 = add nsw i64 %_add_tmp66, %_conv19
  %_mult_tmp70.neg = add i64 %ib.0302, 2
  %_sub_tmp71 = sub i64 %_mult_tmp70.neg, undef
  %_add_tmp74 = add i64 %_add_tmp66, undef
  %_mult_tmp75 = shl i64 %_add_tmp74, 1
  %_add_tmp76 = add nsw i64 %_sub_tmp71, %_mult_tmp75
  %_add_tmp84 = add nsw i64 %_add_tmp76, 32
  br i1 undef, label %_loop_7_endl_, label %_loop_7_do_

_loop_7_do_:                                      ; preds = %_loop_7_do_, %_loop_4_do_
  %i.0289 = phi i64 [ %_add_tmp678.3, %_loop_7_do_ ], [ undef, %_loop_4_do_ ]
  %_add_tmp678.2 = add nuw nsw i64 %i.0289, 3
  %_mult_tmp619.3 = shl nuw i64 %_add_tmp678.2, 1
  %_add_tmp622.3199 = add i64 %_mult_tmp619.3, %_add_tmp76
  %0 = shl i64 %_add_tmp622.3199, 2
  %uglygep200 = getelementptr i8, i8* undef, i64 %0
  %uglygep201 = getelementptr i8, i8* %uglygep200, i64 -4
  %1 = bitcast i8* %uglygep201 to float*
  %_add_tmp678.3 = add nuw nsw i64 %i.0289, 4
  %_add_tmp724.3215 = add i64 %_mult_tmp619.3, %_sub_tmp71
  %2 = shl i64 %_add_tmp724.3215, 2
  %uglygep216 = getelementptr i8, i8* undef, i64 %2
  %uglygep217 = getelementptr i8, i8* %uglygep216, i64 -4
  %3 = bitcast i8* %uglygep217 to float*
  store float undef, float* %3, align 4
  %4 = call i64 @bar(i64 undef, float* nonnull %1, i64 4, i64 4)
  br label %_loop_7_do_

_loop_7_endl_:                                    ; preds = %_loop_4_do_
  br label %_loop_4_do_
}
declare i64 @bar(i64, float*, i64, i64) local_unnamed_addr

Diff Detail

Event Timeline

w2yehia created this revision.Apr 6 2020, 8:40 AM
w2yehia edited the summary of this revision. (Show Details)Apr 6 2020, 8:41 AM
w2yehia edited the summary of this revision. (Show Details)
w2yehia edited the summary of this revision. (Show Details)Apr 6 2020, 9:01 AM

I prefer solution 1 if SCEV for an incomplete PHI is meaningless.

%incomplete_1 = phi i32 [0, %entry] will be simplified to undef in createNodeForPHI()->SimplifyInstruction(), and for every incomplete PHI like above will be mapped to same SCEVUnknown object in ValueExprMap and will not be updated even after the PHI is populated with all its incoming values. So SCEV returns the wrong cached SCEVUnknown value to the populated PHI values.

This is missing tests.

w2yehia updated this revision to Diff 256165.Apr 8 2020, 8:11 PM

unit test added

Any chance this can get reviewed today. Thanks.

The change in ScalarEvolution looks good to me.

Some comments:
1: You might need to modify the summary a little bit especially for the testcases part.
2: I am a little concern about the unitcase in unittests/Analysis/ScalarEvolutionTest.cpp, It hides too many details in scalar evolution and not shows the bug well. I cooked a case for your reference. Better to commit one nfc patch first with current behavior, then rebase this one, and we can get a better show about what the bug is.

+TEST_F(ScalarEvolutionsTest, SCEVIncompletePHI) {
+  Module NIM("nonintegral", Context);
+  std::string DataLayout = M.getDataLayoutStr();
+  if (!DataLayout.empty())
+    DataLayout += "-";
+  DataLayout += "ni:10";
+  NIM.setDataLayout(DataLayout);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+  Type *T_int1 = Type::getInt1Ty(Context);
+  Type *T_pint64 = T_int64->getPointerTo(10);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
+  Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM);
+
+  BasicBlock *Top = BasicBlock::Create(Context, "top", F);
+  BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
+  BasicBlock *L = BasicBlock::Create(Context, "L", F);
+  BasicBlock *Post = BasicBlock::Create(Context, "post", F);
+
+  IRBuilder<> Builder(Top);
+  Builder.CreateBr(LPh);
+
+  Builder.SetInsertPoint(LPh);
+  Builder.CreateBr(L);
+
+  Builder.SetInsertPoint(L);
+  // Create empty PHIs
+  PHINode *Phi = Builder.CreatePHI(T_int64, 2);
+  PHINode *Phi2 = Builder.CreatePHI(T_int64, 2);
+
+  ScalarEvolution SE = buildSE(*F);
+
+  const SCEV *OldS = SE.getSCEV(Phi);
+  const SCEV *OldS2 = SE.getSCEV(Phi2);
+
+  // No simplify here, so different SCEVUnknown for unpopulated PHIs.
+  EXPECT_NE(OldS, OldS2);
+
+  auto *Add = cast<Instruction>(
+      Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
+  Builder.CreateCondBr(UndefValue::get(T_int1), L, Post);
+
+  // Populate PHIs with different start values.
+  Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
+  Phi->addIncoming(Add, L);
+
+  Phi2->addIncoming(ConstantInt::get(T_int64, 100), LPh);
+  Phi2->addIncoming(Add, L);
+  Builder.SetInsertPoint(Post);
+  Builder.CreateRetVoid();
+
+  // Get SCEVUnknown for populated PHIs through getUnknown()
+  const SCEV *getUnknownNewS = SE.getUnknown(Phi);
+  const SCEV *getUnknownNewS2 = SE.getUnknown(Phi2);
+
+  EXPECT_NE(getUnknownNewS, getUnknownNewS2);
+  // Get the SCEVUnknown object in cache UniqueSCEVs.
+  EXPECT_EQ(getUnknownNewS, OldS);
+  EXPECT_EQ(getUnknownNewS2, OldS2);
+
+  // Get SCEVUnknown for populated PHIs through getSCEV()
+  const SCEV *getSCEVNewS = SE.getSCEV(Phi);
+  const SCEV *getSCEVNewS2 = SE.getSCEV(Phi2);
+  EXPECT_EQ(getSCEVNewS, getUnknownNewS);
+  EXPECT_EQ(getSCEVNewS2, getUnknownNewS2);
+}
+

Thanks Zheng !! Your testcase is indeed more focused on the exact issue in getSCEV.
I will wait to get more feedback on the correctness of the fix. Once it's decided that it's the correct fix, I will post an NFC review that adds your testcase with the "old behavior" expectations, and then this patch will amend the testcase.

gentle ping. Thanks

gentle ping. Thanks

gentle ping. Thanks

gentle ping.
Just to summarize. The testcase demonstrating the issue is added to llvm/unittests/Analysis/ScalarEvolutionTest.cpp.
The description of what the issue is, is in the "The problem" section in the description of this review.
The solution implemented in this review is to detect when an "incomplete" PHI is being createSCEV'ed and return a SCEVUnknown.
Feedback is greatly appreciated.

shchenz added a subscriber: sanjoy.Wed, May 13, 7:17 PM

I think we should fix this SCEV bug as it leads to runtime functionality issue. Could @sanjoy or any experts familar with the SCEV have a look at this issue?

I think we should just never query SCEVs for incomplete Phis as this operation makes no sense. It should be a bug in SCEV expander. Do you know why it makes this query to this Phi?

Let's frame it this way: please add an XFAIL test which runs some passes and fails an assertion with the situation you are describing. I think hiding the bug by returning SCEVUnknown is just wrong. We should investigate why we are making this query instead.