From e77d2b86b478872128ab31d8296840161068fd26 Mon Sep 17 00:00:00 2001 From: Eli Friedman Date: Wed, 19 Apr 2017 20:19:58 +0000 Subject: [PATCH] [SCEV] Make SCEV or modeling more aggressive. Use haveNoCommonBitsSet to figure out whether an "or" instruction is equivalent to addition. This handles more cases than just checking for a constant on the RHS. Differential Revision: https://reviews.llvm.org/D32239 llvm-svn: 300746 --- llvm/lib/Analysis/ScalarEvolution.cpp | 28 ++++-------------- llvm/test/Analysis/ScalarEvolution/or-as-add.ll | 38 +++++++++++++++++++++++++ 2 files changed, 44 insertions(+), 22 deletions(-) create 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 278b65c..b573374b 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -5328,28 +5328,12 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { break; case Instruction::Or: - // 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; - } + // 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); } break; diff --git a/llvm/test/Analysis/ScalarEvolution/or-as-add.ll b/llvm/test/Analysis/ScalarEvolution/or-as-add.ll new file mode 100644 index 0000000..ac4e65a --- /dev/null +++ b/llvm/test/Analysis/ScalarEvolution/or-as-add.ll @@ -0,0 +1,38 @@ +; 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