From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x536.google.com (mail-ed1-x536.google.com [IPv6:2a00:1450:4864:20::536]) by sourceware.org (Postfix) with ESMTPS id 198AD3857815 for ; Fri, 2 Jul 2021 01:37:29 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 198AD3857815 Received: by mail-ed1-x536.google.com with SMTP id w17so11031464edd.10 for ; Thu, 01 Jul 2021 18:37:29 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=56cZl/GvoPtBktQMJmwG4Jzzq9rmWy3L/DM8tSivnwM=; b=fDQXglWmccTjfi+JQtYphJMK0G8PecVNfVXkuorQTsz2ShIwfXSdxNZgKIZJtDP093 z+C8GyTW8YUwQZMoynmCpBGa8w0THl3o2VmVgjUrGwUz2Ra5h4C5ram8ndt1oxijAdCN xp740hWiivkrbgHIbDVfRHa4OdfTNdlPim6cZe3cPhmO5k99Y+9Id4LX5ontX/AjZo8z MGdK3fvCei7CfkxCIGvcbGLBBi/iqsiz/WW3+akG0joGD+A4JSNHdFgR3yyfoB2OFfUJ pMXEzQ62S7ytbkGKWzQjff5j373Vtap3PRyV3D/a1JMyLUm1M0PKM3v8AvkT1eJKVYs9 gkdw== X-Gm-Message-State: AOAM532OYZHz4iQjjL0JbDly0JcDIEM1Pm8dbiSDJr0yl4YoecCX6sw0 6IdVKiJiS5CMWvkRKrdTMdCFAA/DHQbgc4aqWUU= X-Google-Smtp-Source: ABdhPJy9rYdn+TSmKO+x4EpfAhDKoKjfZ50SfyhzMTiZ9N0mfgXnzSKhE+lu1j48MSNl23SeslHfwvAzYevHD8egC/E= X-Received: by 2002:a05:6402:1581:: with SMTP id c1mr3457739edv.213.1625189848032; Thu, 01 Jul 2021 18:37:28 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: "Bin.Cheng" Date: Fri, 2 Jul 2021 09:37:17 +0800 Message-ID: Subject: Re: [PATCH PR100740]Fix overflow check in simplifying exit cond comparing two IVs. To: Richard Biener Cc: "bin.cheng" , GCC Patches Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-3.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 02 Jul 2021 01:37:30 -0000 On Thu, Jul 1, 2021 at 8:19 PM Richard Biener wrote: > > On Mon, Jun 7, 2021 at 4:35 PM Richard Biener > wrote: > > > > On Sun, Jun 6, 2021 at 12:01 PM Bin.Cheng wrote: > > > > > > On Wed, Jun 2, 2021 at 3:28 PM Richard Biener via Gcc-patches > > > wrote: > > > > > > > > On Tue, Jun 1, 2021 at 4:00 PM bin.cheng via Gcc-patches > > > > wrote: > > > > > > > > > > Hi, > > > > > As described in patch summary, this fixes the wrong code issue by adding overflow-ness > > > > > check for iv1.step - iv2.step. > > > > > > > > > > Bootstrap and test on x86_64. Any comments? > > > > > > > > + bool wrap_p = TYPE_OVERFLOW_WRAPS (step_type); > > > > + if (wrap_p) > > > > + { > > > > + tree t = fold_binary_to_constant (GE_EXPR, step_type, > > > > + iv0->step, iv1->step); > > > > + wrap_p = integer_zerop (t); > > > > + } > > > > > > > > I think we can't use TYPE_OVERFLOW_WRAPS/TYPE_OVERFLOW_UNDEFINED since > > > > that's only relevant for expressions written by the user - we're > > > > computing iv0.step - iv1.step > > > > which can even overflow when TYPE_OVERFLOW_UNDEFINED (in fact we may not > > > > even generate this expression then!). So I think we have to do sth like > > > > > > > > /* If the iv0->step - iv1->step wraps, fail. */ > > > > if (!operand_equal_p (iv0->step, iv1->step) > > > > && (TREE_CODE (iv0->step) != INTEGER_CST || TREE_CODE > > > > (iv1->step) != INTEGER_CST) > > > > && !wi::gt (wi::to_widest (iv0->step), wi::to_widest (iv1->step)) > > > > return false; > > > > > > > > which only handles equality and all integer constant steps. You could > > > Thanks for the suggestion. I realized that we have LE/LT/NE > > > conditions here, and for LE/LT what we need to check is iv0/iv1 > > > converge to each other, rather than diverge. Also steps here can only > > > be constants, so there is no need to use range information. > > > > Ah, that simplifies things. > > > > + if (tree_int_cst_lt (iv0->step, iv1->step)) > > + return false; > > > > so it looks to me that iv?->step can be negative which means we should > > verify that abs(iv0->step - iv1->step) <= abs (iv0->step), correct? > > > > tree step = fold_binary_to_constant (MINUS_EXPR, step_type, > > iv0->step, iv1->step); > > ... > > + if (TREE_CODE (step) != INTEGER_CST) > > + return false; > > > > note fold_binary_to_constant will return NULL if the result is not > > TREE_CONSTANT (which would also include symbolic constants > > like &a - &b). It wasn't checked before, of course but since we're > > touching the code we might very well be checking for NULL step ... > > (or assert it is not for documentation purposes). > > > > That said, if iv0->step and iv1->step are known INTEGER_CSTs > > (I think they indeed are given the constraints we impose on > > simple_iv_with_niters). > > > > That said, with just a quick look again it looks to me the > > IV1 {<=,<} IV2 transform to IV1 - IV2step {<=,<} IV2base > > is OK whenever the effective step magnitude on the IV1' > > decreases, thus abs(IV1.step - IV2.step) <= abs(IV1.step) > > since then IV1 is still guaranteed to not overflow. But > > for example {0, +, 1} and {10, -, 1} also converge if the > > number of iterations is less than 10 but they would not pass > > this criteria. So I'm not sure "convergence" is a good wording > > here - but maybe I'm missing some critical piece of understanding > > here. > > > > But in any case it looks like we're on the right track ;) > > Just to pick up things where we left them (and seeing the patch to > unti-wrap which reminded me), I've digged in myself a bit and > came to the following conclusion. > > The b0 + s0 < b1 + s1 -> b0 + s0 - s1 < b1 transform is only > valid if b0 + s0 - s1 does not wrap which we can only ensure > by ensuring that b0 + s0 and b1 + s1 do not wrap (which we > already check) but also - what we're missing - that (s0 - s1) > makes b0 still evolve in the same direction (thus s0-s1 has the > same sign as s0) and that its magnitude is less that that of s0. > > Extra cases could be handled if we have an upper bound for > the number of iterations from other sources, not sure if that's > worth checking. > > Thus I am testing the attached now. > > Hope you don't mind - and I of course welcome any comments. Oh, not at all. Your help on these issues are greatly appreciated. As for the change: > + if (tree_int_cst_sign_bit (iv0->step) != tree_int_cst_sign_bit (step) > + || wi::geu_p (wi::abs (wi::to_wide (step)), > + wi::abs (wi::to_wide (iv0->step)))) It returns false on condition "{base, 5}_iv0 < {base, -1}_iv1", but this is like the "convergence" case I mentioned and could be analyzed? Thanks, bin > + return false; > + } Thanks, bin > > Thanks, > Richard. > > > Thanks, > > Richard. > > > > > > also use ranges > > > > like > > > > > > > > wide_int min0, max0, min1, max1; > > > > if (!operand_equal_p (iv->step, iv1->step) > > > > && (determine_value_range (iv0->step, &min0, &max0) != VR_RANGE > > > > || determine_value_range (iv1->step, &min1, &max1) != VR_RANGE > > > > || !wi::ge (min0, max1))) > > > > return false; > > > > > > > > Note I'm not sure why > > > > > > > > iv0->step = step; > > > > if (!POINTER_TYPE_P (type)) > > > > iv0->no_overflow = false; > > > I don't exactly remember, this was added sometime when no_overflow was > > > introduced. Note we only do various checks for non NE_EXPR so the > > > step isn't always less in absolute value? I will check if we should > > > reset it in all cases. > > > > > > Patch updated. test ongoing. > > > > > > Thanks, > > > bin > > > > > > > > here the no_overflow reset does not happen for pointer types? Or > > > > rather why does > > > > it happen at all? Don't we strictly make the step less in absolute value? > > > > > > > > > Thanks, > > > > > bin