{"id":2231302,"url":"http://patchwork.ozlabs.org/api/patches/2231302/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/DI6KI7UV67P0.34JJS8EFC64T9@gmail.com/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/projects/17/?format=json","name":"GNU Compiler Collection","link_name":"gcc","list_id":"gcc-patches.gcc.gnu.org","list_email":"gcc-patches@gcc.gnu.org","web_url":null,"scm_url":null,"webscm_url":null,"list_archive_url":"","list_archive_url_format":"","commit_url_format":""},"msgid":"","list_archive_url":null,"date":"2026-04-30T14:43:31","name":"backprop: Add demand-bit handling. [PR113487]","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"ab9de38cbec30094c69a9a630a0c01ac7578c36a","submitter":{"id":86205,"url":"http://patchwork.ozlabs.org/api/people/86205/?format=json","name":"Robin Dapp","email":"rdapp.gcc@gmail.com"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/DI6KI7UV67P0.34JJS8EFC64T9@gmail.com/mbox/","series":[{"id":502318,"url":"http://patchwork.ozlabs.org/api/series/502318/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=502318","date":"2026-04-30T14:43:31","name":"backprop: Add demand-bit handling. [PR113487]","version":1,"mbox":"http://patchwork.ozlabs.org/series/502318/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/2231302/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2231302/checks/","tags":{},"related":[],"headers":{"Return-Path":"","X-Original-To":["incoming@patchwork.ozlabs.org","gcc-patches@gcc.gnu.org"],"Delivered-To":["patchwork-incoming@legolas.ozlabs.org","gcc-patches@gcc.gnu.org"],"Authentication-Results":["legolas.ozlabs.org;\n\tdkim=pass (2048-bit key;\n unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256\n header.s=20251104 header.b=lhtLzTzo;\n\tdkim-atps=neutral","legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=2620:52:6:3111::32; helo=vm01.sourceware.org;\n envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org;\n receiver=patchwork.ozlabs.org)","sourceware.org;\n\tdkim=pass (2048-bit key,\n unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256\n header.s=20251104 header.b=lhtLzTzo","sourceware.org;\n dmarc=pass (p=none dis=none) header.from=gmail.com","sourceware.org; spf=pass smtp.mailfrom=gmail.com","server2.sourceware.org;\n arc=none smtp.remote-ip=209.85.128.46"],"Received":["from vm01.sourceware.org (vm01.sourceware.org\n [IPv6:2620:52:6:3111::32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4g5xkx4rd9z1yJr\n\tfor ; Fri, 01 May 2026 00:44:09 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 976D143B5522\n\tfor ; Thu, 30 Apr 2026 14:44:07 +0000 (GMT)","from mail-wm1-f46.google.com (mail-wm1-f46.google.com\n [209.85.128.46])\n by sourceware.org (Postfix) with ESMTPS id EEB844BB3BE3\n for ; Thu, 30 Apr 2026 14:43:34 +0000 (GMT)","by mail-wm1-f46.google.com with SMTP id\n 5b1f17b1804b1-483487335c2so11527105e9.2\n for ; Thu, 30 Apr 2026 07:43:34 -0700 (PDT)","from localhost (ip-085-216-098-084.um25.pools.vodafone-ip.de.\n [85.216.98.84]) by smtp.gmail.com with ESMTPSA id\n 5b1f17b1804b1-48a7b900af7sm45025615e9.1.2026.04.30.07.43.32\n (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);\n Thu, 30 Apr 2026 07:43:32 -0700 (PDT)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org 976D143B5522","OpenDKIM Filter v2.11.0 sourceware.org EEB844BB3BE3"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org EEB844BB3BE3","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org EEB844BB3BE3","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1777560215; cv=none;\n b=mzqbmzs2LxzuLAwXRYU15XMaUua/QPc4ZNN2GgmeAL8zOBUL0SuhMZK97C/d2lw4FAzlk1fH9A9QumwKap3hv1e6FyFK1GM0q6B0V+T2YuYGVD7Mu/UhAl8UXGCKxi8T5oe8qsLmZ9IE68imOEt3OptsjGZwqVZCMQej8I44nvE=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1777560215; c=relaxed/simple;\n bh=h/d0bZeK+6QJMIwTdNV8OtPB56nGCQBcnL7yJ+0LB/U=;\n h=DKIM-Signature:Mime-Version:Date:Message-Id:To:From:Subject;\n b=Egbh404SG6XKNgccTxJptEqXPTxHvgMm36ioybhJxT5XliC1ZAyzMW/kf4TlE3MqEySmipdSLzX2kL5I3QoZfvOryQEPRHXEya8DxqC1zUzJdKgUBk7jp/mZXrGJ93EgwDzntTzKnpdeoTPzCIdc9Z+w4ir4ZdROt9OgGo8aExk=","ARC-Authentication-Results":"i=1; server2.sourceware.org","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n d=gmail.com; s=20251104; t=1777560213; x=1778165013; darn=gcc.gnu.org;\n h=subject:from:to:cc:message-id:date:content-transfer-encoding\n :mime-version:from:to:cc:subject:date:message-id:reply-to;\n bh=+dLOsJbnxI4Hr9Dfv1tMi7/0qPaTFpWiEVJvX+XoceY=;\n b=lhtLzTzo4EXuZGTfG/1sqAoawQ2hzB9/jcv9g2WRSHule9EHyO/BQZCxMqZvLoCjnH\n kitTgWh6gvY4a5seB2smB5/vgmciHzMSz0JIrKfklLw6W+SEDFFb+WLHmNmVkXjJ9APs\n TuL+EWGXoPCJPOTBV1NXHRNB1j7jVXkngfX9YwggaquUAc9KH7o+AASsDLmgVjt4doFi\n NqVq1Gfuo+L529TuBvuZkjZbWSZuCpQtvQLNMiNIjs8XicOpm5gl826Ak0B7rbKPkKG9\n rw732pGhe0jIiGnMpWaE6S+tC9XTbtCrjV7O5lnVNRsFbXsAxOaTSEFsKf8j8zzshCFP\n 2xKA==","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n d=1e100.net; s=20251104; t=1777560213; x=1778165013;\n h=subject:from:to:cc:message-id:date:content-transfer-encoding\n :mime-version:x-gm-gg:x-gm-message-state:from:to:cc:subject:date\n :message-id:reply-to;\n bh=+dLOsJbnxI4Hr9Dfv1tMi7/0qPaTFpWiEVJvX+XoceY=;\n b=cMMRSCbv0tnokC6tY3JWsok33dOPUpRX3/cldXljXBisXWUNecgGviE6uT8mFMw9La\n z9byUulPEHWdak3FE0MQKjAJ+5DFYrwoDz5jLwFa5YO9tFqWaWUb9FM+Rb/emIL/sjNY\n kNElIM0QgyYtcXTJHqhA0FKNuAh/UHtz/tt3FL6uSJjMjPXtuKOcWdytnPF0vY5Vnb/l\n 44oa7tgx704QXudvvcm0PmgUHw2nZN8VMKXSuFEMRMSBC7nYIBpNBiEKBy6LeMwwleJO\n aPBDcXmMzc91rI1G4ekI2vqXEffoopblessUJoLTsyojFuUiPueC0RWJl0vq2JjQ7a3K\n lqYw==","X-Gm-Message-State":"AOJu0Yz3yPC2q3z3k1qaCNUq3BvCUSZElfR0ZiYJY0iA4mTsUjMra4fC\n L0pryKqH63b4DIh4j2BniBVdoMsOHt/LAQJG9oa//SOz07YU5mOacQ3Y+ZjThw==","X-Gm-Gg":"AeBDieuUw2wEyAB5+aJzZZAG4l403Icv5vDmrQcBtDGUHPCUhP8XydxjtlzMq1QPaGC\n chtHHh63cgeNNg+dfLTNQymZfuSRm0iaqiUEwY+61Kgfuv4nP6D5a7paxuoFaCDI2tjujmoFlNT\n dCk6l8eeKsowflwOAzfA+iYSciy7USJnb/HuMHx+EESB9nQq/FZpG9ZJ45HHamJumF18SwaaLT8\n 0/qu+8Z34c7/JDPMvBjbXJXs5+5ZxZoO6v9aFxvG83wgmSOImLCpoFuqUX0yUQRM4AKr8BGuP5t\n a5J5qvaKGMtqIf4Uvjy8x8dDqk22WfPAhYrNMCN5noMAURA0JlZOqqU9PmLyd+P2X6z78rNVBfZ\n KPlQpxdiiDGz8iwpndht9bHOFBo/V7W449sKgXsVFi3t/DIQ2FI9zPWiuVOM6nDcNLmxA8TzWC7\n 474DCwRxsLC1zXXhfwMM3/Wq+nQlge43Ck/hL9PTxrtujYpzuz63nuq7Q6Tt5WESuM4YfTShcI5\n FZDXkM=","X-Received":"by 2002:a05:600c:a119:b0:48a:75b9:5e07 with SMTP id\n 5b1f17b1804b1-48a844f4de3mr41437385e9.11.1777560212921;\n Thu, 30 Apr 2026 07:43:32 -0700 (PDT)","Mime-Version":"1.0","Content-Transfer-Encoding":"quoted-printable","Content-Type":"text/plain; charset=UTF-8","Date":"Thu, 30 Apr 2026 16:43:31 +0200","Message-Id":"","Cc":"\"Robin Dapp\" ","To":"\"gcc-patches\" , \"Richard Sandiford\"\n ","From":"\"Robin Dapp\" ","Subject":"[PATCH] backprop: Add demand-bit handling. [PR113487]","X-BeenThere":"gcc-patches@gcc.gnu.org","X-Mailman-Version":"2.1.30","Precedence":"list","List-Id":"Gcc-patches mailing list ","List-Unsubscribe":",\n ","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n ","Errors-To":"gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org"},"content":"Hi,\n\nThis patch adds backpropagation of demand-bit information to the\nbackprop pass. It is intended to catch cases like this\n\n int\n foo (int in)\n {\n int a = in & 0xff;\n int b = a << 1;\n int c = b & 0xf;\n return c;\n }\n\nwhere we can propagate B's demand of 0xf back to IN and elide the\n& 0xff masking. This works in situations where forward-looking\noptimizations like in match.pd fail, for example due to non-single\nuse.\n\nI tried to keep the implementation simple at first, but it grew\nover time and now handles BIT_AND_EXPR, BIT_IOR_EXPR, BIT_XOR_EXPR,\nMULT_EXPR, LSHIFT_EXPR, RSHIFT_EXPR, and PLUS_EXPR, MINUS_EXPR.\n\nThe most important case is surely eliding masks: Once the demand has reached\na BIT_AND_EXPR and we see that it does not exceed what we mask off anyway, we\nelide it. In SPECint 2017 this hits a couple hundred times, predominantly gcc \nand perlbench, albeit not in very hot code paths.\n\nBootstrapped and regtested on x86, power10, and aarch64.\nRegtested on riscv64.\n\nRegards\n Robin\n\n\tPR tree-optimization/113487\n\tPR tree-optimization/122209\n\ngcc/ChangeLog:\n\n\t* gimple-ssa-backprop.cc (usage_info::intersection_identity):\n\tAdd demand-bit handling.\n\t(usage_info::is_useful): Ditto.\n\t(dump_usage_info): Log demand bits.\n\t(backprop::process_assign_use): Handle demand bits.\n\t(backprop::process_phi_use): Ditto.\n\t(backprop::intersect_uses): Ditto.\n\t(backprop::process_var): Ditto.\n\t(backprop::optimize_assign): Elide mask if possible.\n\ngcc/testsuite/ChangeLog:\n\n\t* gcc.dg/tree-ssa/backprop-bits-1.c: New test.\n\t* gcc.dg/tree-ssa/backprop-bits-2.c: New test.\n\t* gcc.dg/tree-ssa/backprop-bits-3.c: New test.\n\t* gcc.dg/tree-ssa/backprop-bits-4.c: New test.\n\t* gcc.dg/tree-ssa/backprop-bits-5.c: New test.\n\t* gcc.dg/tree-ssa/backprop-bits-6.c: New test.\n\t* gcc.dg/tree-ssa/backprop-bits-7.c: New test.\n\t* gcc.dg/tree-ssa/backprop-bits-8.c: New test.\n---\n gcc/gimple-ssa-backprop.cc | 435 ++++++++++++++++--\n .../gcc.dg/tree-ssa/backprop-bits-1.c | 16 +\n .../gcc.dg/tree-ssa/backprop-bits-2.c | 29 ++\n .../gcc.dg/tree-ssa/backprop-bits-3.c | 29 ++\n .../gcc.dg/tree-ssa/backprop-bits-4.c | 34 ++\n .../gcc.dg/tree-ssa/backprop-bits-5.c | 39 ++\n .../gcc.dg/tree-ssa/backprop-bits-6.c | 18 +\n .../gcc.dg/tree-ssa/backprop-bits-7.c | 41 ++\n .../gcc.dg/tree-ssa/backprop-bits-8.c | 31 ++\n 9 files changed, 643 insertions(+), 29 deletions(-)\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-1.c\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-2.c\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-3.c\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-4.c\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-5.c\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-6.c\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-7.c\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-8.c","diff":"diff --git a/gcc/gimple-ssa-backprop.cc b/gcc/gimple-ssa-backprop.cc\nindex 3ac44116d27..0e36489691b 100644\n--- a/gcc/gimple-ssa-backprop.cc\n+++ b/gcc/gimple-ssa-backprop.cc\n@@ -23,12 +23,13 @@ along with GCC; see the file COPYING3. If not see\n fully or partially dead code, but the main focus is simplifying\n computations.\n \n- At the moment the pass only handles one piece of information: whether the\n- sign of a value matters, and therefore whether sign-changing operations\n- can be skipped. The pass could be extended to more interesting\n- information in future, such as which bits of an integer are significant.\n+ The pass only handles two distinct properties:\n+ (a) Whether the sign of a value matters, and therefore whether\n+\t sign-changing operations can be skipped.\n+ (b) The bits a variable demands. This opens up possibilities to\n+\t elide redundant bit masking.\n \n- For example, take the function:\n+ For an example of (a), take the function:\n \n double\n f (double *a, int n, double start)\n@@ -48,6 +49,28 @@ along with GCC; see the file COPYING3. If not see\n with start. Since there are no other uses of the fabs result,\n the call would get deleted as dead.\n \n+ A typical case for (b) is:\n+\n+ void use (unsigned);\n+\n+ void\n+ foo (unsigned x)\n+ {\n+ unsigned a = x & 0xff;\n+ unsigned b = a * 4;\n+ use (b & 0x10);\n+ use (b & 0xe0);\n+ }\n+\n+ Both use sites of B mask it and we cannot look through the multiplication to\n+ elide the masking directly (via e.g. match.pd or ccp). Seeing the demand\n+ on B (= 0xf0), we can back-propagate it to B's definition and deduce which\n+ bits A demands (= 0xf0 >> 2 = 0x3c).\n+ Then, continuing at A's definition we see that there is no bit demand\n+ outside of 0xff, so no necessary bit the mask would clear. As a\n+ consequence, the masking can be elided.\n+\n+\n The algorithm is:\n \n (1) Do a post-order traversal of the blocks in the function, walking\n@@ -110,9 +133,9 @@ namespace {\n class usage_info\n {\n public:\n- usage_info () : flag_word (0) {}\n+ usage_info () : flag_word (0), needed_bits (-1) {}\n+\n usage_info &operator &= (const usage_info &);\n- usage_info operator & (const usage_info &) const;\n bool operator == (const usage_info &) const;\n bool operator != (const usage_info &) const;\n bool is_useful () const;\n@@ -129,6 +152,9 @@ public:\n /* All the flag bits as a single int. */\n unsigned int flag_word;\n };\n+\n+ /* The live bits. */\n+ widest_int needed_bits;\n };\n \n /* Return an X such that X & Y == Y for all Y. This is the most\n@@ -139,6 +165,7 @@ usage_info::intersection_identity ()\n {\n usage_info ret;\n ret.flag_word = -1;\n+ ret.needed_bits = 0;\n return ret;\n }\n \n@@ -149,24 +176,15 @@ usage_info &\n usage_info::operator &= (const usage_info &other)\n {\n flag_word &= other.flag_word;\n+ needed_bits = needed_bits | other.needed_bits;\n return *this;\n }\n \n-/* Return the intersection of *THIS and OTHER, i.e. a structure that\n- describes all uses covered by *THIS and OTHER. */\n-\n-usage_info\n-usage_info::operator & (const usage_info &other) const\n-{\n- usage_info info (*this);\n- info &= other;\n- return info;\n-}\n-\n bool\n usage_info::operator == (const usage_info &other) const\n {\n- return flag_word == other.flag_word;\n+ return flag_word == other.flag_word\n+ && needed_bits == other.needed_bits;\n }\n \n bool\n@@ -180,7 +198,7 @@ usage_info::operator != (const usage_info &other) const\n bool\n usage_info::is_useful () const\n {\n- return flag_word != 0;\n+ return flag_word != 0 || needed_bits != -1;\n }\n \n /* Start a dump line about SSA name VAR. */\n@@ -203,6 +221,18 @@ dump_usage_info (FILE *file, tree var, usage_info *info)\n dump_usage_prefix (file, var);\n fprintf (file, \"sign bit not important\\n\");\n }\n+ if (info->needed_bits != -1)\n+ {\n+ tree type = TREE_TYPE (var);\n+ if (VECTOR_TYPE_P (type))\n+\ttype = TREE_TYPE (type);\n+ unsigned prec = TYPE_PRECISION (type);\n+ wide_int mask = wide_int::from (info->needed_bits, prec, UNSIGNED);\n+ dump_usage_prefix (file, var);\n+ fprintf (file, \"demand bit mask: \");\n+ print_hex (mask, file);\n+ fprintf (file, \"\\n\");\n+ }\n }\n \n /* Represents one execution of the pass. */\n@@ -233,6 +263,7 @@ private:\n void complete_change (gimple *);\n void optimize_builtin_call (gcall *, tree, const usage_info *);\n void replace_assign_rhs (gassign *, tree, tree, tree, tree);\n+ void build_nop_rhs (gassign *, tree);\n void optimize_assign (gassign *, tree, const usage_info *);\n void optimize_phi (gphi *, tree, const usage_info *);\n \n@@ -417,7 +448,12 @@ void\n backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)\n {\n tree lhs = gimple_assign_lhs (assign);\n- switch (gimple_assign_rhs_code (assign))\n+ const usage_info *lhs_info = lookup_operand (lhs);\n+ info->needed_bits = -1;\n+\n+ tree_code code = gimple_assign_rhs_code (assign);\n+\n+ switch (code)\n {\n case ABS_EXPR:\n case ABSU_EXPR:\n@@ -430,17 +466,56 @@ backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)\n \t to C and D. */\n if (rhs != gimple_assign_rhs1 (assign))\n \t{\n-\t const usage_info *lhs_info = lookup_operand (lhs);\n \t if (lhs_info)\n \t *info = *lhs_info;\n \t}\n break;\n \n case MULT_EXPR:\n- /* In X * X, the sign of X doesn't matter. */\n- if (gimple_assign_rhs1 (assign) == rhs\n-\t && gimple_assign_rhs2 (assign) == rhs)\n-\tinfo->flags.ignore_sign = true;\n+\t{\n+\t /* In X * X, the sign of X doesn't matter. */\n+\t if (gimple_assign_rhs1 (assign) == rhs\n+\t && gimple_assign_rhs2 (assign) == rhs)\n+\t info->flags.ignore_sign = true;\n+\n+\t tree type = TREE_TYPE (lhs);\n+\t if (VECTOR_TYPE_P (type))\n+\t type = TREE_TYPE (type);\n+\n+\t tree other = (rhs == gimple_assign_rhs1 (assign))\n+\t\t ? gimple_assign_rhs2 (assign)\n+\t\t : gimple_assign_rhs1 (assign);\n+\t wide_int nz;\n+\n+\t /* Given the output demand, we assume that all input bits not\n+\t higher than the output's highest set bit can contribute to the\n+\t output. If we know that a number of low bits are zero, we\n+\t have a lower bound on the bits.\n+\t For a multiplication by a power of two there is no carry and\n+\t we can simply shift the output.\n+\t */\n+\t if (INTEGRAL_TYPE_P (type) && lhs_info\n+\t && lhs_info->needed_bits != -1\n+\t && (nz = get_nonzero_bits (other)).get_precision () != 0)\n+\t {\n+\t widest_int wnz = widest_int::from (nz, UNSIGNED);\n+\t HOST_WIDE_INT lo = wi::ctz (wnz);\n+\t HOST_WIDE_INT hi = wi::floor_log2 (lhs_info->needed_bits);\n+\n+\t if (wnz == 0)\n+\t\tinfo->needed_bits = 0;\n+\t else if (wi::popcount (wnz) == 1)\n+\t\tinfo->needed_bits = lo > 0\n+\t\t ? wi::lrshift (lhs_info->needed_bits, lo)\n+\t\t : lhs_info->needed_bits;\n+\t else if (hi < lo)\n+\t\tinfo->needed_bits = 0;\n+\t else\n+\t\tinfo->needed_bits\n+\t\t = wi::mask (hi - lo + 1, false);\n+\t }\n+\t}\n+\n /* Fall through. */\n \n case NEGATE_EXPR:\n@@ -449,12 +524,203 @@ backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)\n \t doesn't matter either. */\n if (FLOAT_TYPE_P (TREE_TYPE (rhs)))\n \t{\n-\t const usage_info *lhs_info = lookup_operand (lhs);\n \t if (lhs_info)\n \t info->flags.ignore_sign = lhs_info->flags.ignore_sign;\n \t}\n break;\n \n+ case TRUNC_DIV_EXPR:\n+\t{\n+\t tree type = TREE_TYPE (rhs);\n+\t if (VECTOR_TYPE_P (type))\n+\t type = TREE_TYPE (type);\n+\t if (!INTEGRAL_TYPE_P (type) || !TYPE_UNSIGNED (type))\n+\t break;\n+\n+\t tree rhs1 = gimple_assign_rhs1 (assign);\n+\t tree rhs2 = gimple_assign_rhs2 (assign);\n+\t if (rhs != rhs1 || TREE_CODE (rhs2) != INTEGER_CST)\n+\t break;\n+\n+\t if (!lhs_info || lhs_info->needed_bits == -1)\n+\t break;\n+\n+\t widest_int div = widest_int::from (wi::to_wide (rhs2), UNSIGNED);\n+\t if (div == 0)\n+\t break;\n+\n+\t /* Opposite to multiplication, with division at least all LHS bits\n+\t contribute. As the input is not smaller than the output, the\n+\t RHS determines the number of bits that contribute on top,\n+\t with the highest bit marking the upper bound.\n+\n+\t An example is that we're looking for IN's bits that could\n+\t contribute to the known bits of A:\n+\n+\t char a = in / 3;\n+\t\t |\n+\t 0b00001101 = ? / 3\n+\n+\t =>\n+\n+\t 0b00001101 = 0b00??1101 / 3\n+\n+\t So the lower bits come from the output (A), while the next higher\n+\t ones come from the division by 3. */\n+\n+\t HOST_WIDE_INT log_k = wi::exact_log2 (div);\n+\t if (log_k >= 0)\n+\t info->needed_bits = wi::lshift (lhs_info->needed_bits, log_k);\n+\t else\n+\t {\n+\t HOST_WIDE_INT needed_out\n+\t\t= wi::floor_log2 (lhs_info->needed_bits);\n+\t HOST_WIDE_INT needed_cst = wi::floor_log2 (div - 1) + 1;\n+\t HOST_WIDE_INT width = needed_out + needed_cst + 1;\n+\t unsigned prec = TYPE_PRECISION (type);\n+\t if (width >= (HOST_WIDE_INT) prec)\n+\t\tinfo->needed_bits = -1;\n+\t else\n+\t\tinfo->needed_bits = wi::mask (width, false);\n+\t }\n+\t}\n+ break;\n+\n+ case BIT_AND_EXPR:\n+\t{\n+\t if (lhs_info)\n+\t info->needed_bits = lhs_info->needed_bits;\n+\n+\t tree other;\n+\t if (rhs == gimple_assign_rhs1 (assign))\n+\t other = gimple_assign_rhs2 (assign);\n+\t else\n+\t other = gimple_assign_rhs1 (assign);\n+\n+\t wide_int nz = get_nonzero_bits (other);\n+\t widest_int wnz (-1);\n+\t if (nz.get_precision () != 0)\n+\t wnz = widest_int::from (nz, UNSIGNED);\n+\t info->needed_bits &= wnz;\n+\t}\n+ break;\n+\n+ case LSHIFT_EXPR:\n+ case RSHIFT_EXPR:\n+ if (rhs == gimple_assign_rhs1 (assign))\n+\t{\n+\t tree rhs2 = gimple_assign_rhs2 (assign);\n+\t if (TREE_CODE (rhs2) == INTEGER_CST\n+\t && lhs_info)\n+\t {\n+\t info->needed_bits = lhs_info->needed_bits;\n+\t widest_int shift_count\n+\t\t= widest_int::from (wi::to_wide (rhs2), UNSIGNED);\n+\n+\t if (code == LSHIFT_EXPR)\n+\t\tinfo->needed_bits = wi::lrshift (info->needed_bits,\n+\t\t\t\t\t\t shift_count);\n+\t else\n+\t\t{\n+\t\t if (TYPE_UNSIGNED (TREE_TYPE (rhs)))\n+\t\t info->needed_bits = wi::lshift (info->needed_bits,\n+\t\t\t\t\t\t shift_count);\n+\t\t /* ??? Treat sign extension conservatively for now. */\n+\t\t else\n+\t\t info->needed_bits = -1;\n+\t\t}\n+\t }\n+\t}\n+ break;\n+\n+ case PLUS_EXPR:\n+ case MINUS_EXPR:\n+ if (rhs == gimple_assign_rhs1 (assign)\n+\t || rhs == gimple_assign_rhs2 (assign))\n+\t{\n+\t if (lhs_info)\n+\t info->needed_bits = lhs_info->needed_bits;\n+\n+\t tree type = TREE_TYPE (rhs);\n+\t if (VECTOR_TYPE_P (type))\n+\t type = TREE_TYPE (type);\n+\n+\t if (info->needed_bits != -1)\n+\t {\n+\t int hi = wi::floor_log2 (info->needed_bits);\n+\t info->needed_bits = wi::mask (hi + 1, false);\n+\t }\n+\t}\n+ break;\n+\n+ case LROTATE_EXPR:\n+ case RROTATE_EXPR:\n+ if (rhs == gimple_assign_rhs1 (assign))\n+\t{\n+\t tree rhs2 = gimple_assign_rhs2 (assign);\n+\t tree type = TREE_TYPE (rhs);\n+\t if (VECTOR_TYPE_P (type))\n+\t type = TREE_TYPE (type);\n+\t HOST_WIDE_INT prec = TYPE_PRECISION (type);\n+\n+\t if (TREE_CODE (rhs2) == INTEGER_CST)\n+\t {\n+\t widest_int count\n+\t\t= widest_int::from (wi::to_wide (rhs2), UNSIGNED);\n+\n+\t if (lhs_info)\n+\t\tinfo->needed_bits = lhs_info->needed_bits;\n+\n+\t if (code == LROTATE_EXPR)\n+\t\tinfo->needed_bits = wi::rrotate (info->needed_bits, count,\n+\t\t\t\t\t\t prec);\n+\t else\n+\t\tinfo->needed_bits = wi::lrotate (info->needed_bits, count,\n+\t\t\t\t\t\t prec);\n+\t }\n+\t}\n+ break;\n+\n+ case NOP_EXPR:\n+ case CONVERT_EXPR:\n+\t{\n+\t tree rhs1 = gimple_assign_rhs1 (assign);\n+\t tree rhs_type = TREE_TYPE (rhs1);\n+\t tree lhs_type = TREE_TYPE (lhs);\n+\t if (VECTOR_TYPE_P (lhs_type))\n+\t {\n+\t lhs_type = TREE_TYPE (lhs_type);\n+\t rhs_type = TREE_TYPE (rhs_type);\n+\t }\n+\n+\t if (!INTEGRAL_TYPE_P (lhs_type) || !INTEGRAL_TYPE_P (rhs_type)\n+\t || !lhs_info)\n+\t break;\n+\n+\t HOST_WIDE_INT rhs_prec = TYPE_PRECISION (rhs_type);\n+\t HOST_WIDE_INT lhs_prec = TYPE_PRECISION (lhs_type);\n+\n+\t if (lhs_prec <= rhs_prec)\n+\t info->needed_bits = lhs_info->needed_bits;\n+\t else if (TYPE_UNSIGNED (rhs_type))\n+\t info->needed_bits\n+\t = lhs_info->needed_bits & wi::mask (rhs_prec, false);\n+\t else\n+\t /* As in the RSHIFT case above, treat sign extension\n+\t conservatively for now. */\n+\t info->needed_bits = -1;\n+\t}\n+ break;\n+\n+ /* The following expressions don't affect the needed bits so we can just\n+\t pass through the output. */\n+ case BIT_IOR_EXPR:\n+ case BIT_XOR_EXPR:\n+ case BIT_NOT_EXPR:\n+ if (lhs_info)\n+\tinfo->needed_bits = lhs_info->needed_bits;\n+ break;\n+\n default:\n break;\n }\n@@ -468,6 +734,8 @@ backprop::process_phi_use (gphi *phi, usage_info *info)\n tree result = gimple_phi_result (phi);\n if (const usage_info *result_info = lookup_operand (result))\n *info = *result_info;\n+ else\n+ info->needed_bits = -1;\n }\n \n /* Make INFO describe all uses of RHS in STMT. */\n@@ -601,7 +869,10 @@ backprop::process_var (tree var)\n else if (info != *map_info)\n \t{\n \t /* Recording information that is less optimistic than before. */\n-\t gcc_checking_assert ((info & *map_info) == info);\n+\t gcc_checking_assert ((info.flag_word & map_info->flag_word)\n+\t\t\t == info.flag_word\n+\t\t\t && (map_info->needed_bits\n+\t\t\t\t | info.needed_bits) == info.needed_bits);\n \t *map_info = info;\n \t if (dump_file && (dump_flags & TDF_DETAILS))\n \t dump_var_info (var, map_info, \"Updating information\");\n@@ -813,13 +1084,24 @@ backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1,\n complete_change (assign);\n }\n \n+void\n+backprop::build_nop_rhs (gassign *assign, tree lhs)\n+{\n+ prepare_change (lhs);\n+ gimple_stmt_iterator gsi = gsi_for_stmt (assign);\n+ gimple_assign_set_rhs_from_tree (&gsi, gimple_assign_rhs1\n+\t\t\t\t (assign));\n+ complete_change (assign);\n+}\n+\n /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO\n describes all uses of LHS. */\n \n void\n backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info)\n {\n- switch (gimple_assign_rhs_code (assign))\n+ tree_code code = gimple_assign_rhs_code (assign);\n+ switch (code)\n {\n case MULT_EXPR:\n case RDIV_EXPR:\n@@ -842,6 +1124,101 @@ backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info)\n \t\t\t strip_sign_op (gimple_assign_rhs3 (assign)));\n break;\n \n+ case BIT_AND_EXPR:\n+ case BIT_IOR_EXPR:\n+ case BIT_XOR_EXPR:\n+ if (info->needed_bits != -1)\n+\t{\n+\t tree rhs2 = gimple_assign_rhs2 (assign);\n+\t if (TREE_CODE (rhs2) == INTEGER_CST)\n+\t {\n+\t bool elide_p = false;\n+\t widest_int mask\n+\t\t= widest_int::from (wi::to_wide (rhs2), UNSIGNED);\n+\n+\t /* If we mask off bits that are being discarded later on anyway,\n+\t\t we can elide the mask. */\n+\t if (code == BIT_AND_EXPR\n+\t\t && (info->needed_bits & ~mask) == 0)\n+\t\telide_p = true;\n+\n+\t /* For IOR and XOR it's the other way around. If all we modify\n+\t\t is a range outside of the needed bits, elide. */\n+\t if ((code == BIT_IOR_EXPR || code == BIT_XOR_EXPR)\n+\t\t && (info->needed_bits & mask) == 0)\n+\t\telide_p = true;\n+\n+\t if (elide_p)\n+\t\t{\n+\t\t /* Just make the assignment a nop here. */\n+\t\t if (dump_file && (dump_flags & TDF_DETAILS))\n+\t\t {\n+\t\t fprintf (dump_file, \"Eliding redundant mask in \");\n+\t\t print_gimple_stmt (dump_file, assign, 0, TDF_SLIM);\n+\t\t }\n+\n+\t\t build_nop_rhs (assign, lhs);\n+\t\t}\n+\t }\n+\t}\n+ break;\n+\n+ case PLUS_EXPR:\n+ case MINUS_EXPR:\n+ if (info->needed_bits != -1)\n+\t{\n+\t tree rhs2 = gimple_assign_rhs2 (assign);\n+\t wide_int nz = get_nonzero_bits (rhs2);\n+\t widest_int wnz (-1);\n+\t if (nz.get_precision ())\n+\t wnz = widest_int::from (nz, UNSIGNED);\n+\n+\t widest_int shared_bits = info->needed_bits & wnz;\n+\t if (shared_bits == 0\n+\t && wi::ctz (wnz) > wi::floor_log2 (info->needed_bits))\n+\t {\n+\t if (dump_file && (dump_flags & TDF_DETAILS))\n+\t\t{\n+\t\t fprintf (dump_file, \"Eliding redundant\"\n+\t\t\t\t \" addition/subtraction in \");\n+\t\t print_gimple_stmt (dump_file, assign, 0, TDF_SLIM);\n+\t\t}\n+\n+\t build_nop_rhs (assign, lhs);\n+\t }\n+\t}\n+ break;\n+\n+ case LSHIFT_EXPR:\n+ if (info->needed_bits != -1)\n+\t{\n+\t tree rhs2 = gimple_assign_rhs2 (assign);\n+\t if (TREE_CODE (rhs2) == INTEGER_CST)\n+\t {\n+\t widest_int shift_count\n+\t\t= widest_int::from (wi::to_wide (rhs2), UNSIGNED);\n+\n+\t widest_int shifted\n+\t\t= wi::lrshift (info->needed_bits, shift_count);\n+\n+\t if (shifted == 0)\n+\t\t{\n+\t\t if (dump_file && (dump_flags & TDF_DETAILS))\n+\t\t {\n+\t\t fprintf (dump_file, \"Eliding redundant shift in \");\n+\t\t print_gimple_stmt (dump_file, assign, 0, TDF_SLIM);\n+\t\t }\n+\n+\t\t prepare_change (lhs);\n+\t\t gimple_stmt_iterator gsi = gsi_for_stmt (assign);\n+\t\t gimple_assign_set_rhs_from_tree\n+\t\t (&gsi, build_zero_cst (TREE_TYPE (lhs)));\n+\t\t complete_change (assign);\n+\t\t}\n+\t }\n+\t}\n+ break;\n+\n default:\n break;\n }\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-1.c b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-1.c\nnew file mode 100644\nindex 00000000000..e46adce4bdb\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-1.c\n@@ -0,0 +1,16 @@\n+/* { dg-do compile } */\n+/* { dg-additional-options \"-O -fdump-tree-backprop-details\" } */\n+\n+#include \n+\n+void use (unsigned);\n+\n+void\n+src (bool c, unsigned a, unsigned b) {\n+ unsigned s = c ? a & 24 : b & 25;\n+ use(s & 8);\n+ use(s & 16);\n+}\n+\n+/* { dg-final { scan-tree-dump-not \" s_8 = a_7(D) & 24;\" \"backprop\" } } */\n+/* { dg-final { scan-tree-dump-not \" s_6 = b_5(D) & 25;\" \"backprop\" } } */\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-2.c b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-2.c\nnew file mode 100644\nindex 00000000000..3a4af6b8a10\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-2.c\n@@ -0,0 +1,29 @@\n+/* { dg-do compile } */\n+/* { dg-additional-options \"-O -fdump-tree-optimized\" } */\n+\n+int\n+foo (int t)\n+{\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+\n+ return t;\n+}\n+\n+/* { dg-final { scan-tree-dump \"4095\" \"optimized\" } } */\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-3.c b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-3.c\nnew file mode 100644\nindex 00000000000..d7b573edf88\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-3.c\n@@ -0,0 +1,29 @@\n+/* { dg-do compile { target bitint } } */\n+/* { dg-additional-options \"-O -fdump-tree-optimized\" } */\n+\n+int\n+foo (int t)\n+{\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+ t += 3 + 3 * t;\n+ t &= 0xFFF;\n+\n+ return t;\n+}\n+\n+/* { dg-final { scan-tree-dump \"return\" \"optimized\" } } */\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-4.c b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-4.c\nnew file mode 100644\nindex 00000000000..7fcc90c7adf\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-4.c\n@@ -0,0 +1,34 @@\n+/* { dg-do compile } */\n+/* { dg-additional-options \"-O -fdump-tree-backprop-details -std=gnu99\" } */\n+\n+void use (unsigned);\n+\n+void\n+foo (unsigned x)\n+{\n+ unsigned a = x & 0xff;\n+ unsigned b = a * 4;\n+ use (b & 0x10);\n+ use (b & 0xe0);\n+}\n+\n+void\n+bar (unsigned x)\n+{\n+ unsigned a = x & 0xff;\n+ unsigned b = a / 3;\n+ use (b & 0x3);\n+ use (b & 0xc);\n+}\n+\n+void\n+baz (unsigned x)\n+{\n+ unsigned a = x & 0xffff;\n+ unsigned a2 = a * 2;\n+ unsigned b = a2 & 0xff;\n+ use (b & 0x3);\n+ use (b & 0xc);\n+}\n+\n+/* { dg-final { scan-tree-dump-times \"Eliding redundant mask\" 3 \"backprop\" } } */\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-5.c b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-5.c\nnew file mode 100644\nindex 00000000000..7a0ab3ade7d\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-5.c\n@@ -0,0 +1,39 @@\n+/* { dg-do compile } */\n+/* { dg-additional-options \"-O -fdump-tree-backprop-details -std=gnu99\" } */\n+\n+void use (unsigned);\n+\n+void\n+foo (unsigned x)\n+{\n+ unsigned a = x & 0xff;\n+ use (a & 0xf);\n+ use (a);\n+}\n+\n+void\n+bar (unsigned x, unsigned y)\n+{\n+ unsigned a = x & 0xff;\n+ unsigned b = a + y;\n+ use (b & 0xf);\n+}\n+\n+void\n+baz (unsigned x, unsigned s)\n+{\n+ unsigned a = x & 0xff;\n+ unsigned b = a << s;\n+ use (b & 0xf);\n+}\n+\n+unsigned\n+baf (unsigned x, int n)\n+{\n+ unsigned a = x & 0xff;\n+ for (int i = 0; i < n; i++)\n+ a = (a + 1) & 0xff;\n+ return a;\n+}\n+\n+/* { dg-final { scan-tree-dump-not \"Eliding redundant mask\" \"backprop\" } } */\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-6.c b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-6.c\nnew file mode 100644\nindex 00000000000..6cedb819c81\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-6.c\n@@ -0,0 +1,18 @@\n+/* { dg-do compile } */\n+/* { dg-additional-options \"-O -fdump-tree-backprop-details -std=gnu99\" } */\n+\n+void use (unsigned);\n+\n+void\n+f_phi (int c, unsigned x, unsigned y)\n+{\n+ unsigned t;\n+ if (c)\n+ t = x & 0xff;\n+ else\n+ t = y & 0xff;\n+ use (t & 0x3);\n+ use (t & 0xc);\n+}\n+\n+/* { dg-final { scan-tree-dump-times \"Eliding redundant mask\" 2 \"backprop\" } } */\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-7.c b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-7.c\nnew file mode 100644\nindex 00000000000..795e461160f\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-7.c\n@@ -0,0 +1,41 @@\n+/* { dg-do compile } */\n+/* { dg-additional-options \"-O -fdump-tree-backprop-details -std=gnu99\" } */\n+\n+void use (unsigned);\n+\n+void\n+foo (unsigned x)\n+{\n+ unsigned a = x | 0xff00;\n+ unsigned b = a * 2;\n+ use (b & 0x3);\n+ use (b & 0xc);\n+}\n+\n+void\n+bar (unsigned x)\n+{\n+ unsigned a = x ^ 0xff00;\n+ unsigned b = a * 2;\n+ use (b & 0x3);\n+ use (b & 0xc);\n+}\n+\n+void\n+baz (unsigned x)\n+{\n+ unsigned a = x | 0x18;\n+ use (a & 0x3);\n+ use (a & 0xc);\n+}\n+\n+void\n+baf (unsigned x)\n+{\n+ unsigned a = x ^ 0x18;\n+ use (a & 0x3);\n+ use (a & 0xc);\n+}\n+\n+/* foo and bar can be simplified by eliding the IOR. baz and baf can't. */\n+/* { dg-final { scan-tree-dump-times \"Eliding redundant\" 2 \"backprop\" } } */\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-8.c b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-8.c\nnew file mode 100644\nindex 00000000000..3f66c4f84a6\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/backprop-bits-8.c\n@@ -0,0 +1,31 @@\n+/* { dg-do compile } */\n+/* { dg-additional-options \"-O -fdump-tree-backprop-details -std=gnu99\" } */\n+\n+void use (unsigned);\n+\n+void\n+foo (unsigned x)\n+{\n+ unsigned b = x + 0xff00;\n+ use (b & 0x1);\n+ use (b & 0xe);\n+}\n+\n+void\n+bar (unsigned x, unsigned y)\n+{\n+ unsigned m = y & 0xFF00;\n+ unsigned b = x - m;\n+ use (b & 0xf);\n+ use (b & 0xf0);\n+}\n+\n+void\n+baz (unsigned x)\n+{\n+ unsigned a = x << 8;\n+ unsigned b = a / 3;\n+ use (b & 0x3);\n+}\n+\n+/* { dg-final { scan-tree-dump-times \"Eliding redundant\" 3 \"backprop\" } } */\n","prefixes":[]}