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 @@ -6002,15 +6002,15 @@ const SCEV *TrueExpr, const SCEV *FalseExpr) { assert(CondExpr->getType()->isIntegerTy(1) && TrueExpr->getType() == FalseExpr->getType() && - TrueExpr->getType()->isIntegerTy(1) && + TrueExpr->getType()->isIntegerTy() && "Unexpected operands of a select."); - // i1 cond ? i1 x : i1 C --> C + (i1 cond ? (i1 x - i1 C) : i1 0) - // --> C + (umin_seq cond, x - C) + // i1 cond ? iN x : iN C --> C + (i1 cond ? (iN x - iN C) : iN 0) + // --> C + (umin_seq (sext cond), x - C) // - // i1 cond ? i1 C : i1 x --> C + (i1 cond ? i1 0 : (i1 x - i1 C)) - // --> C + (i1 ~cond ? (i1 x - i1 C) : i1 0) - // --> C + (umin_seq ~cond, x - C) + // i1 cond ? iN C : iN x --> C + (i1 cond ? iN 0 : (iN x - iN C)) + // --> C + (i1 ~cond ? (iN x - iN C) : iN 0) + // --> C + (umin_seq (sext ~cond), x - C) // FIXME: while we can't legally model the case where both of the hands // are fully variable, we only require that the *difference* is constant. @@ -6018,6 +6018,9 @@ return None; const SCEV *X, *C; + if (SE->getTypeSizeInBits(TrueExpr->getType()) > + SE->getTypeSizeInBits(CondExpr->getType())) + CondExpr = SE->getSignExtendExpr(CondExpr, TrueExpr->getType()); if (isa(TrueExpr)) { CondExpr = SE->getNotSCEV(CondExpr); X = FalseExpr; @@ -6048,14 +6051,39 @@ V->getType() == TrueVal->getType() && "Types of select hands and of the result must match."); - // For now, only deal with i1-typed `select`s. - if (!V->getType()->isIntegerTy(1)) + // For now, only deal with i1-typed, or pointer-typed `select`s, + // but not arbitrary iN-typed `select`s. + if (!V->getType()->isIntegerTy(1) && !V->getType()->isPointerTy()) return getUnknown(V); if (Optional S = createNodeForSelectViaUMinSeq(this, Cond, TrueVal, FalseVal)) return *S; + if (V->getType()->isPointerTy()) { + // We can't model pointer selects in SCEV in their generality. + // + // But, *IFF* we are selecting between pointers with the same base object, + // we can instead decompose the pointers into pointer base + integer offset, + // try to model the select of said integer offsets, and add the result + // to the base pointer, thus modelling the original select. + + const SCEV *TrueExpr = getSCEV(TrueVal); + const SCEV *FalseExpr = getSCEV(FalseVal); + + const SCEV *TrueExprBasePtr = getPointerBase(TrueExpr); + const SCEV *FalseExprBasePtr = getPointerBase(FalseExpr); + if (TrueExprBasePtr == FalseExprBasePtr) { + const SCEV *BasePtrExpr = TrueExprBasePtr; + const SCEV *TrueOffsetExpr = removePointerBase(TrueExpr); + const SCEV *FalseOffsetExpr = removePointerBase(FalseExpr); + + if (Optional OffsetSelect = createNodeForSelectViaUMinSeq( + this, getSCEV(Cond), TrueOffsetExpr, FalseOffsetExpr)) + return getAddExpr(BasePtrExpr, *OffsetSelect); + } + } + return getUnknown(V); } diff --git a/llvm/test/Analysis/ScalarEvolution/pointer-rounding.ll b/llvm/test/Analysis/ScalarEvolution/pointer-rounding.ll --- a/llvm/test/Analysis/ScalarEvolution/pointer-rounding.ll +++ b/llvm/test/Analysis/ScalarEvolution/pointer-rounding.ll @@ -101,7 +101,7 @@ ; CHECK-NEXT: %i6 = getelementptr i8, ptr %i5, i64 16 ; CHECK-NEXT: --> (16 + (-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj to i64) to i4) to i64)) + %obj) U: full-set S: full-set ; CHECK-NEXT: %i7 = select i1 %i3, ptr %obj, ptr %i6 -; CHECK-NEXT: --> %i7 U: full-set S: full-set +; CHECK-NEXT: --> (((-1 + (-1 * (sext i1 %i3 to i64))) umin_seq (16 + (-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj to i64) to i4) to i64)))) + %obj) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @pointer_align_up_with_select ; %i = ptrtoint ptr %obj to i64 @@ -128,7 +128,7 @@ ; CHECK-NEXT: %i6 = getelementptr i8, ptr %i5, i64 16 ; CHECK-NEXT: --> (16 + (-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj_donor to i64) to i4) to i64)) + %obj_to_align) U: full-set S: full-set ; CHECK-NEXT: %i7 = select i1 %i3, ptr %obj_to_align, ptr %i6 -; CHECK-NEXT: --> %i7 U: full-set S: full-set +; CHECK-NEXT: --> (((-1 + (-1 * (sext i1 %i3 to i64))) umin_seq (16 + (-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj_donor to i64) to i4) to i64)))) + %obj_to_align) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @pointer_align_up_with_select_different_donor ; %i = ptrtoint ptr %obj_donor to i64 diff --git a/llvm/test/Analysis/ScalarEvolution/pointer-select.ll b/llvm/test/Analysis/ScalarEvolution/pointer-select.ll --- a/llvm/test/Analysis/ScalarEvolution/pointer-select.ll +++ b/llvm/test/Analysis/ScalarEvolution/pointer-select.ll @@ -22,7 +22,7 @@ ; CHECK-NEXT: %false_ptr = getelementptr i8, ptr %obj, i64 24 ; CHECK-NEXT: --> (24 + %obj) U: full-set S: full-set ; CHECK-NEXT: %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr -; CHECK-NEXT: --> %r U: full-set S: full-set +; CHECK-NEXT: --> (42 + (-18 umin (-1 + (-1 * (sext i1 %cond to i64)))) + %obj) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @pointer_select_same_object_constant_offsets ; %true_ptr = getelementptr i8, ptr %obj, i64 42 @@ -56,7 +56,7 @@ ; CHECK-NEXT: %false_ptr = getelementptr i8, ptr %obj, i64 %false_off ; CHECK-NEXT: --> (%false_off + %obj) U: full-set S: full-set ; CHECK-NEXT: %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr -; CHECK-NEXT: --> %r U: full-set S: full-set +; CHECK-NEXT: --> (42 + ((-1 + (-1 * (sext i1 %cond to i64))) umin_seq (-42 + %false_off)) + %obj) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @pointer_select_same_object_constant_offset_vs_variable_offset ; %true_ptr = getelementptr i8, ptr %obj, i64 42 @@ -73,7 +73,7 @@ ; CHECK-NEXT: %false_ptr = getelementptr i8, ptr %obj, i64 42 ; CHECK-NEXT: --> (42 + %obj) U: full-set S: full-set ; CHECK-NEXT: %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr -; CHECK-NEXT: --> %r U: full-set S: full-set +; CHECK-NEXT: --> (42 + ((sext i1 %cond to i64) umin_seq (-42 + %true_off)) + %obj) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @pointer_select_same_object_variable_offset_vs_constant_offset ; %true_ptr = getelementptr i8, ptr %obj, i64 %true_off @@ -94,7 +94,7 @@ ; CHECK-NEXT: %false_ptr = getelementptr i8, ptr %obj, i64 24 ; CHECK-NEXT: --> (36 + %obj.base) U: full-set S: full-set ; CHECK-NEXT: %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr -; CHECK-NEXT: --> %r U: full-set S: full-set +; CHECK-NEXT: --> (54 + (-18 umin (-1 + (-1 * (sext i1 %cond to i64)))) + %obj.base) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @pointer_select_same_object_with_constant_base_offset__constant_offsets ; %obj = getelementptr i8, ptr %obj.base, i64 12 @@ -134,7 +134,7 @@ ; CHECK-NEXT: %false_ptr = getelementptr i8, ptr %obj, i64 %false_off ; CHECK-NEXT: --> (12 + %false_off + %obj.base) U: full-set S: full-set ; CHECK-NEXT: %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr -; CHECK-NEXT: --> %r U: full-set S: full-set +; CHECK-NEXT: --> (54 + ((-1 + (-1 * (sext i1 %cond to i64))) umin_seq (-42 + %false_off)) + %obj.base) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @pointer_select_same_object_with_constant_base_offset__constant_offset_vs_variable_offset ; %obj = getelementptr i8, ptr %obj.base, i64 12 @@ -154,7 +154,7 @@ ; CHECK-NEXT: %false_ptr = getelementptr i8, ptr %obj, i64 42 ; CHECK-NEXT: --> (54 + %obj.base) U: full-set S: full-set ; CHECK-NEXT: %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr -; CHECK-NEXT: --> %r U: full-set S: full-set +; CHECK-NEXT: --> (54 + ((sext i1 %cond to i64) umin_seq (-42 + %true_off)) + %obj.base) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @pointer_select_same_object_with_constant_base_offset__variable_offset_vs_constant_offset ; %obj = getelementptr i8, ptr %obj.base, i64 12