diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -7879,6 +7879,32 @@ Type *TruncTy = IntegerType::get(getContext(), BitWidth - AShrAmt); Operator *L = dyn_cast(BO->LHS); + if (L && L->getOpcode() == Instruction::Add) { + Operator *LShift = dyn_cast(L->getOperand(0)); + if (LShift && LShift->getOpcode() == Instruction::Shl) { + // X = Shl A, n + // Y = Add X, c + // Z = AShr Y, m + + const SCEV *ShlOp0SCEV = getSCEV(LShift->getOperand(0)); + ConstantInt *AddOperandCI = dyn_cast(L->getOperand(1)); + // since we truncate to TruncTy, the AddConstant should be of the same + // type, so create a new Constant with type same as TruncTy + int64_t AddOperand = AddOperandCI->getSExtValue(); + const SCEV *AddConstant = getConstant(TruncTy, AddOperand >> AShrAmt); + + // As of now only handle cases where n = m, and n should be a value + // corresponding to a 8, 16, 32 integer. + if (LShift->getOperand(1) == BO->RHS && + (AShrAmt == 32 || AShrAmt == 48 || AShrAmt == 56)) { + // use sext(add(trunc(A), c)) as the SCEV expression. + return getSignExtendExpr( + getAddExpr(getTruncateExpr(ShlOp0SCEV, TruncTy), AddConstant), + LShift->getType()); + } + } + } + if (L && L->getOpcode() == Instruction::Shl) { // X = Shl A, n // Y = AShr X, m diff --git a/llvm/test/Analysis/ScalarEvolution/sext-add-inreg.ll b/llvm/test/Analysis/ScalarEvolution/sext-add-inreg.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/ScalarEvolution/sext-add-inreg.ll @@ -0,0 +1,98 @@ +; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2 +; RUN: opt < %s -disable-output "-passes=print" 2>&1 | FileCheck %s + +@.str = private unnamed_addr constant [3 x i8] c"%x\00", align 1 + +define dso_local i32 @test(ptr nocapture noundef readonly %x) { +; CHECK-LABEL: 'test' +; CHECK-NEXT: Classifying expressions for: @test +; CHECK-NEXT: %i.03 = phi i64 [ 1, %entry ], [ %inc, %for.body ] +; CHECK-NEXT: --> {1,+,1}<%for.body> U: [1,10) S: [1,10) Exits: 9 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %conv = shl nuw nsw i64 %i.03, 32 +; CHECK-NEXT: --> {4294967296,+,4294967296}<%for.body> U: [4294967296,38654705665) S: [4294967296,38654705665) Exits: 38654705664 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %sext = add nsw i64 %conv, -4294967296 +; CHECK-NEXT: --> {0,+,4294967296}<%for.body> U: [0,34359738369) S: [0,34359738369) Exits: 34359738368 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %idxprom = ashr exact i64 %sext, 32 +; CHECK-NEXT: --> {0,+,1}<%for.body> U: [0,9) S: [0,9) Exits: 8 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %arrayidx = getelementptr inbounds i32, ptr %x, i64 %idxprom +; CHECK-NEXT: --> {%x,+,4}<%for.body> U: full-set S: full-set Exits: (32 + %x) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %0 = load i32, ptr %arrayidx, align 4 +; CHECK-NEXT: --> %0 U: full-set S: full-set Exits: <> LoopDispositions: { %for.body: Variant } +; CHECK-NEXT: %call = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, i32 noundef %0) +; CHECK-NEXT: --> %call U: full-set S: full-set Exits: <> LoopDispositions: { %for.body: Variant } +; CHECK-NEXT: %inc = add nuw nsw i64 %i.03, 1 +; CHECK-NEXT: --> {2,+,1}<%for.body> U: [2,11) S: [2,11) Exits: 10 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: Determining loop execution counts for: @test +; CHECK-NEXT: Loop %for.body: backedge-taken count is 8 +; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is 8 +; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is 8 +; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is 8 +; CHECK-NEXT: Predicates: +; CHECK: Loop %for.body: Trip multiple is 9 +; +entry: + br label %for.body + +for.cond.cleanup: ; preds = %for.body + ret i32 0 + +for.body: ; preds = %entry, %for.body + %i.03 = phi i64 [ 1, %entry ], [ %inc, %for.body ] + %conv = shl nuw nsw i64 %i.03, 32 + %sext = add nsw i64 %conv, -4294967296 + %idxprom = ashr exact i64 %sext, 32 + %arrayidx = getelementptr inbounds i32, ptr %x, i64 %idxprom + %0 = load i32, ptr %arrayidx, align 4 + %call = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, i32 noundef %0) + %inc = add nuw nsw i64 %i.03, 1 + %exitcond.not = icmp eq i64 %inc, 10 + br i1 %exitcond.not, label %for.cond.cleanup, label %for.body +} + +define dso_local i32 @test_fail(ptr nocapture noundef readonly %x) { +; CHECK-LABEL: 'test_fail' +; CHECK-NEXT: Classifying expressions for: @test_fail +; CHECK-NEXT: %i.03 = phi i64 [ 1, %entry ], [ %inc, %for.body ] +; CHECK-NEXT: --> {1,+,1}<%for.body> U: [1,10) S: [1,10) Exits: 9 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %conv = shl nuw nsw i64 %i.03, 34 +; CHECK-NEXT: --> {17179869184,+,17179869184}<%for.body> U: [17179869184,154618822657) S: [17179869184,154618822657) Exits: 154618822656 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %sext = add nsw i64 %conv, -4294967296 +; CHECK-NEXT: --> {12884901888,+,17179869184}<%for.body> U: [12884901888,150323855361) S: [12884901888,150323855361) Exits: 150323855360 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %idxprom = ashr exact i64 %sext, 34 +; CHECK-NEXT: --> %idxprom U: [-536870912,536870912) S: [-536870912,536870912) Exits: 8 LoopDispositions: { %for.body: Variant } +; CHECK-NEXT: %arrayidx = getelementptr inbounds i32, ptr %x, i64 %idxprom +; CHECK-NEXT: --> ((4 * %idxprom) + %x) U: full-set S: full-set Exits: (32 + %x) LoopDispositions: { %for.body: Variant } +; CHECK-NEXT: %0 = load i32, ptr %arrayidx, align 4 +; CHECK-NEXT: --> %0 U: full-set S: full-set Exits: <> LoopDispositions: { %for.body: Variant } +; CHECK-NEXT: %call = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, i32 noundef %0) +; CHECK-NEXT: --> %call U: full-set S: full-set Exits: <> LoopDispositions: { %for.body: Variant } +; CHECK-NEXT: %inc = add nuw nsw i64 %i.03, 1 +; CHECK-NEXT: --> {2,+,1}<%for.body> U: [2,11) S: [2,11) Exits: 10 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: Determining loop execution counts for: @test_fail +; CHECK-NEXT: Loop %for.body: backedge-taken count is 8 +; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is 8 +; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is 8 +; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is 8 +; CHECK-NEXT: Predicates: +; CHECK: Loop %for.body: Trip multiple is 9 +; +entry: + br label %for.body + +for.cond.cleanup: ; preds = %for.body + ret i32 0 + +for.body: ; preds = %entry, %for.body + %i.03 = phi i64 [ 1, %entry ], [ %inc, %for.body ] + %conv = shl nuw nsw i64 %i.03, 34 + %sext = add nsw i64 %conv, -4294967296 + %idxprom = ashr exact i64 %sext, 34 + %arrayidx = getelementptr inbounds i32, ptr %x, i64 %idxprom + %0 = load i32, ptr %arrayidx, align 4 + %call = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, i32 noundef %0) + %inc = add nuw nsw i64 %i.03, 1 + %exitcond.not = icmp eq i64 %inc, 10 + br i1 %exitcond.not, label %for.cond.cleanup, label %for.body +} + +declare noundef i32 @printf(ptr nocapture noundef readonly, ...)