From d0e6ae56785b7ebf2688f71a146c81962efe9ece Mon Sep 17 00:00:00 2001 From: Eli Friedman Date: Thu, 20 Apr 2017 23:59:05 +0000 Subject: [PATCH] Revert r300746 (SCEV analysis for or instructions). There have been multiple reports of this causing problems: a compile-time explosion on the LLVM testsuite, and a stack overflow for an opencl kernel. llvm-svn: 300928 --- llvm/lib/Analysis/ScalarEvolution.cpp | 28 ++++++++++++++---- llvm/test/Analysis/ScalarEvolution/or-as-add.ll | 38 ------------------------- 2 files changed, 22 insertions(+), 44 deletions(-) delete mode 100644 llvm/test/Analysis/ScalarEvolution/or-as-add.ll diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 700c383..593f78b 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -5328,12 +5328,28 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { break; case Instruction::Or: - // Use ValueTracking to check whether this is actually an add. - if (haveNoCommonBitsSet(BO->LHS, BO->RHS, getDataLayout(), &AC, - nullptr, &DT)) { - // There aren't any common bits set, so the add can't wrap. - auto Flags = SCEV::NoWrapFlags(SCEV::FlagNUW | SCEV::FlagNSW); - return getAddExpr(getSCEV(BO->LHS), getSCEV(BO->RHS), Flags); + // If the RHS of the Or is a constant, we may have something like: + // X*4+1 which got turned into X*4|1. Handle this as an Add so loop + // optimizations will transparently handle this case. + // + // In order for this transformation to be safe, the LHS must be of the + // form X*(2^n) and the Or constant must be less than 2^n. + if (ConstantInt *CI = dyn_cast(BO->RHS)) { + const SCEV *LHS = getSCEV(BO->LHS); + const APInt &CIVal = CI->getValue(); + if (GetMinTrailingZeros(LHS) >= + (CIVal.getBitWidth() - CIVal.countLeadingZeros())) { + // Build a plain add SCEV. + const SCEV *S = getAddExpr(LHS, getSCEV(CI)); + // If the LHS of the add was an addrec and it has no-wrap flags, + // transfer the no-wrap flags, since an or won't introduce a wrap. + if (const SCEVAddRecExpr *NewAR = dyn_cast(S)) { + const SCEVAddRecExpr *OldAR = cast(LHS); + const_cast(NewAR)->setNoWrapFlags( + OldAR->getNoWrapFlags()); + } + return S; + } } break; diff --git a/llvm/test/Analysis/ScalarEvolution/or-as-add.ll b/llvm/test/Analysis/ScalarEvolution/or-as-add.ll deleted file mode 100644 index ac4e65a..0000000 --- a/llvm/test/Analysis/ScalarEvolution/or-as-add.ll +++ /dev/null @@ -1,38 +0,0 @@ -; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s - -declare void @z(i32) -declare void @z2(i64) - -define void @fun(i1 %bool, i32 %x) { -entry: - br label %body -body: - %i = phi i32 [ 0, %entry ], [ %i.next, %body ] - %bottom_zero = mul i32 %i, 2 - %a = or i32 %bottom_zero, 1 - call void @z(i32 %a) - %bool_ext = zext i1 %bool to i32 - %b = or i32 %bool_ext, %bottom_zero - call void @z(i32 %b) - %shifted = lshr i32 %x, 31 - %c = or i32 %shifted, %bottom_zero - call void @z(i32 %c) - %i_ext = zext i32 %i to i64 - %d = or i64 %i_ext, 4294967296 - call void @z2(i64 %d) - %i.next = add i32 %i, 1 - %cond = icmp eq i32 %i.next, 10 - br i1 %cond, label %exit, label %body -exit: - ret void -} - -; CHECK: %a = or i32 %bottom_zero, 1 -; CHECK-NEXT: --> {1,+,2}<%body> -; CHECK: %b = or i32 %bool_ext, %bottom_zero -; CHECK-NEXT: --> {(zext i1 %bool to i32),+,2} -; CHECK: %c = or i32 %shifted, %bottom_zero -; CHECK-NEXT: --> {(%x /u -2147483648),+,2}<%body> -; CHECK: %d = or i64 %i_ext, 4294967296 -; CHECK-NEXT: --> {4294967296,+,1}<%body> - -- 2.7.4