Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -860,15 +860,28 @@ // Except in the trivial case described above, we do not know how to divide // Expr by Denominator for the following functions with empty implementation. - void visitTruncateExpr(const SCEVTruncateExpr *Numerator) {} void visitZeroExtendExpr(const SCEVZeroExtendExpr *Numerator) {} - void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {} void visitUDivExpr(const SCEVUDivExpr *Numerator) {} void visitSMaxExpr(const SCEVSMaxExpr *Numerator) {} void visitUMaxExpr(const SCEVUMaxExpr *Numerator) {} void visitUnknown(const SCEVUnknown *Numerator) {} void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {} + void visitTruncateExpr(const SCEVTruncateExpr *Numerator) { + const SCEV *Q, *R; + divide(SE, Numerator->getOperand(), Denominator, &Q, &R); + Quotient = SE.getTruncateExpr(Q, Numerator->getType()); + Remainder = SE.getTruncateExpr(R, Numerator->getType()); + } + + void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) { + const SCEV *Q, *R; + divide(SE, Numerator->getOperand(), Denominator, &Q, &R); + Quotient = SE.getSignExtendExpr(Q, Numerator->getType()); + Remainder = SE.getSignExtendExpr(R, Numerator->getType()); + } + + void visitConstant(const SCEVConstant *Numerator) { if (const SCEVConstant *D = dyn_cast(Denominator)) { APInt NumeratorVal = Numerator->getAPInt(); @@ -886,6 +899,8 @@ APInt::sdivrem(NumeratorVal, DenominatorVal, QuotientVal, RemainderVal); Quotient = SE.getConstant(QuotientVal); Remainder = SE.getConstant(RemainderVal); + Quotient = SE.getTruncateOrNoop(Quotient, Numerator->getType()); + Remainder = SE.getTruncateOrNoop(Remainder, Numerator->getType()); return; } } @@ -896,20 +911,23 @@ return cannotDivide(Numerator); divide(SE, Numerator->getStart(), Denominator, &StartQ, &StartR); divide(SE, Numerator->getStepRecurrence(SE), Denominator, &StepQ, &StepR); - // Bail out if the types do not match. - Type *Ty = Denominator->getType(); - if (Ty != StartQ->getType() || Ty != StartR->getType() || - Ty != StepQ->getType() || Ty != StepR->getType()) - return cannotDivide(Numerator); - Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(), - Numerator->getNoWrapFlags()); - Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(), - Numerator->getNoWrapFlags()); + assert( + Numerator->getStart()->getType() == StartQ->getType() + && StartQ->getType() == StartR->getType() + && "Expected matching types"); + assert( + Numerator->getStepRecurrence(SE)->getType() == StepQ->getType() + && StepQ->getType() == StepR->getType() + && "Expected matching types"); + Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(), + Numerator->getNoWrapFlags()); + Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(), + Numerator->getNoWrapFlags()); } void visitAddExpr(const SCEVAddExpr *Numerator) { SmallVector Qs, Rs; - Type *Ty = Denominator->getType(); + Type *Ty = Numerator->getType(); for (const SCEV *Op : Numerator->operands()) { const SCEV *Q, *R; @@ -918,6 +936,8 @@ // Bail out if types do not match. if (Ty != Q->getType() || Ty != R->getType()) return cannotDivide(Numerator); + assert(Ty == Q->getType() && Ty == R->getType() && + "Expected matching types"); Qs.push_back(Q); Rs.push_back(R); @@ -979,13 +999,13 @@ // The Remainder is obtained by replacing Denominator by 0 in Numerator. ValueToValueMap RewriteMap; RewriteMap[cast(Denominator)->getValue()] = - cast(Zero)->getValue(); + cast(SE.getZero(Denominator->getType()))->getValue(); Remainder = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true); if (Remainder->isZero()) { // The Quotient is obtained by replacing Denominator by 1 in Numerator. RewriteMap[cast(Denominator)->getValue()] = - cast(One)->getValue(); + cast(SE.getOne(Denominator->getType()))->getValue(); Quotient = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true); return; @@ -1007,8 +1027,8 @@ SCEVDivision(ScalarEvolution &S, const SCEV *Numerator, const SCEV *Denominator) : SE(S), Denominator(Denominator) { - Zero = SE.getZero(Denominator->getType()); - One = SE.getOne(Denominator->getType()); + Zero = SE.getZero(Numerator->getType()); + One = SE.getOne(Numerator->getType()); // We generally do not know how to divide Expr by Denominator. We // initialize the division to a "cannot divide" state to simplify the rest Index: test/Analysis/Delinearization/constant_sext_trunc.ll =================================================================== --- test/Analysis/Delinearization/constant_sext_trunc.ll +++ test/Analysis/Delinearization/constant_sext_trunc.ll @@ -0,0 +1,83 @@ +; RUN: opt -delinearize -analyze < %s | FileCheck %s + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +; CHECK: Inst: store i64 -281474976710602, i64* %19 +; CHECK-NEXT: In Loop with Header: Block #6 +; CHECK-NEXT: AccessFunction: (8 * (sext i32 {{[{][{]}}0,+,(trunc i64 %4 to i32)}<%"Block #3">,+,1}<%"Block #6"> to i64)) +; CHECK-NEXT: Base offset: %18 +; CHECK-NEXT: ArrayDecl[UnknownSize][%4] with elements of 8 bytes. +; CHECK-NEXT: ArrayRef[(sext i32 {0,+,1}<%"Block #3"> to i64)][{0,+,1}<%"Block #6">] + +; CHECK: Inst: store i64 -281474976710602, i64* %19 +; CHECK-NEXT: In Loop with Header: Block #3 +; CHECK-NEXT: AccessFunction: (8 * (sext i32 {(-1 + (trunc i64 %4 to i32)),+,(trunc i64 %4 to i32)}<%"Block #3"> to i64)) +; CHECK-NEXT: Base offset: %18 +; CHECK-NEXT: ArrayDecl[UnknownSize][%4] with elements of 8 bytes. +; CHECK-NEXT: ArrayRef[(sext i32 {1,+,1}<%"Block #3"> to i64)][-1] + +define i64 @jsBody_test() #0 { +Prologue: + %0 = call i8* @llvm.frameaddress(i32 0) + %1 = ptrtoint i8* %0 to i64 + %2 = add i64 %1, 56 + %3 = inttoptr i64 %2 to i64* + %4 = load i64, i64* %3 + %5 = add i64 %1, 48 + %6 = inttoptr i64 %5 to i64* + %7 = load i64, i64* %6 + %8 = trunc i64 %4 to i32 + %9 = icmp slt i32 0, %8 + %10 = add i64 %7, 8 + %11 = inttoptr i64 %10 to i64* + %12 = load i64, i64* %11 + %13 = add i64 %12, 0 + br label %"Block #3" + +"Block #1": ; preds = %"Block #9" + br label %"Block #3" + +"Block #3": ; preds = %"Block #1", %Prologue + %.01 = phi i32 [ 0, %Prologue ], [ %22, %"Block #1" ] + br i1 %9, label %"Block #4", label %"Block #9" + +"Block #4": ; preds = %"Block #3" + %14 = call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %8, i32 %.01) + %15 = extractvalue { i32, i1 } %14, 0 + br label %"Block #6" + +"Block #5": ; preds = %"Block #6" + br label %"Block #6" + +"Block #6": ; preds = %"Block #5", %"Block #4" + %.0 = phi i32 [ 0, %"Block #4" ], [ %20, %"Block #5" ] + %16 = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %15, i32 %.0) + %17 = extractvalue { i32, i1 } %16, 0 + %18 = inttoptr i64 %13 to [10000000 x i64]* + %19 = getelementptr [10000000 x i64], [10000000 x i64]* %18, i32 0, i32 %17 + store i64 -281474976710602, i64* %19 + %20 = add i32 %.0, 1 + %21 = icmp slt i32 %20, %8 + br i1 %21, label %"Block #5", label %"Block #9" + +"Block #9": ; preds = %"Block #6", %"Block #3" + %22 = add i32 %.01, 1 + %23 = icmp slt i32 %22, 1000 + br i1 %23, label %"Block #1", label %"Block #10" + +"Block #10": ; preds = %"Block #9" + ret i64 10 +} + +; Function Attrs: nounwind readnone +declare i8* @llvm.frameaddress(i32) #1 + +; Function Attrs: nounwind readnone speculatable +declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) #2 + +; Function Attrs: nounwind readnone speculatable +declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32) #2 + +attributes #0 = { "target-features"="-avx" } +attributes #1 = { nounwind readnone } +attributes #2 = { nounwind readnone speculatable }