46091 – missed optimization: x86 bt/btc/bts instructions

Bug 46091 - missed optimization: x86 bt/btc/bts instructions

Summary: missed optimization: x86 bt/btc/bts instructions

Status:	RESOLVED FIXED

Alias:	None

Product:	gcc
Classification:	Unclassified
Component:	target (show other bugs)
Version:	4.3.5

Importance:	P3 enhancement
Target Milestone:	---
Assignee:	Not yet assigned to anyone

URL:
Keywords:	missed-optimization

Depends on:
Blocks:

Reported:	2010-10-20 05:42 UTC by Jay
Modified:	2018-11-19 12:10 UTC (History)
CC List:	1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.

Description Jay 2010-10-20 05:42:00 UTC

The following code, at least when optimizing for space, should use x86 bt/btc/bts instructions.

#include <limits.h>
#include <stddef.h>

void set_bit(size_t* a, size_t b)
{
  const unsigned c = sizeof(size_t) * CHAR_BIT;
  a[b / c] |= (((size_t)1) << (b % c));
}
 
void clear_bit(size_t* a, size_t b)
{
  const unsigned c = sizeof(size_t) * CHAR_BIT;
  a[b / c] &=  ~(((size_t)1) << (b % c));
}
 
int get_bit(size_t* a, size_t b)
{
  const unsigned c = sizeof(size_t) * CHAR_BIT;
  return !!(a[b / c] & (((size_t)1) << (b % c)));
}

Comment 1 Avi Kivity 2014-08-18 19:38:58 UTC

This is even more important in conjunction with _Atomic.

Note the code as posted cannot be optimized to use bts, since the BitOffset operand is signed.

Comment 2 Avi Kivity 2017-08-11 22:23:38 UTC

Another instance:

unsigned long clear(unsigned long x) {
    return x & ~ ((unsigned long)1 << 63);
}


This compiles to movabs+andq, while it could compile to a single btr instruction.

Comment 3 uros 2017-08-16 15:26:07 UTC

Author: uros
Date: Wed Aug 16 15:25:34 2017
New Revision: 251124

URL: https://gcc.gnu.org/viewcvs?rev=251124&root=gcc&view=rev
Log:
	PR target/46091
	* config/i386/i386.md (*anddi_1_btr): Change predicates of
	operand 0 and operand 1 to nomimmediate_operand. Add "m" constraint.
	Add ix86_binary_operator_ok to insn constraint.
	(*iordi_1_bts): Ditto.
	(*xordi_1_btc): Ditto.
	(*btsq): Change predicate of operand 0 to nonimmediate_operand.
	Update corresponding peephole2 pattern.
	(*btrq): Ditto.
	(*btcq): Ditto.

testsuite/ChangeLog:

	PR target/46091
	* gcc.target/i386/pr46091-1.c: Update scan-assembler-times.
	(testm): New test function.
	* gcc.target/i386/pr46091-2.c: Ditto.
	* gcc.target/i386/pr46091-3.c: Ditto.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/config/i386/i386.md
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.target/i386/pr46091-1.c
    trunk/gcc/testsuite/gcc.target/i386/pr46091-2.c
    trunk/gcc/testsuite/gcc.target/i386/pr46091-3.c

Comment 4 uros 2017-08-21 15:16:25 UTC

Author: uros
Date: Mon Aug 21 15:15:07 2017
New Revision: 251235

URL: https://gcc.gnu.org/viewcvs?rev=251235&root=gcc&view=rev
Log:
	PR target/46091
	* config/i386/i386.md (*btsq_imm): Rename from *btsq.
	(*btrq_imm): Rename from *btrq.
	(*btcq_imm): Rename from *btcq.
	(btsc): New code attribute.
	(*<btsc><mode>): New insn pattern.
	(*btr<mode>): Ditto.
	(*<btsc><mode>_mask): New insn_and_split pattern.
	(*btr<mode>_mask): Ditto.

testsuite/ChangeLog:

	PR target/46091
	* gcc.target/i386/pr46091-4.c: New test.
	* gcc.target/i386/pr46091-4a.c: Ditto.
	* gcc.target/i386/pr46091-5.c: Ditto.
	* gcc.target/i386/pr46091-5a.c: Ditto.


Added:
    trunk/gcc/testsuite/gcc.target/i386/pr46091-4.c
    trunk/gcc/testsuite/gcc.target/i386/pr46091-4a.c
    trunk/gcc/testsuite/gcc.target/i386/pr46091-5.c
    trunk/gcc/testsuite/gcc.target/i386/pr46091-5a.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/config/i386/i386.md
    trunk/gcc/testsuite/ChangeLog

Comment 5 Aldy Hernandez 2017-09-13 16:58:24 UTC

Author: aldyh
Date: Wed Sep 13 16:57:52 2017
New Revision: 252427

URL: https://gcc.gnu.org/viewcvs?rev=252427&root=gcc&view=rev
Log:
	PR target/46091
	* config/i386/i386.md (*anddi_1_btr): New insn_and_split pattern.
	(*iordi_1_bts): Ditto.
	(*xordi_1_btc): Ditto.

testsuite/ChangeLog:

	PR target/46091
	* gcc.target/i386/pr46091-1.c: New test.
	* gcc.target/i386/pr46091-2.c: Ditto.
	* gcc.target/i386/pr46091-3.c: Ditto.

Added:
    branches/range-gen2/gcc/testsuite/gcc.target/i386/pr46091-1.c
    branches/range-gen2/gcc/testsuite/gcc.target/i386/pr46091-2.c
    branches/range-gen2/gcc/testsuite/gcc.target/i386/pr46091-3.c
Modified:
    branches/range-gen2/gcc/ChangeLog
    branches/range-gen2/gcc/config/i386/i386.md
    branches/range-gen2/gcc/testsuite/ChangeLog

Comment 6 Aldy Hernandez 2017-09-13 17:02:40 UTC

Author: aldyh
Date: Wed Sep 13 17:02:09 2017
New Revision: 252445

URL: https://gcc.gnu.org/viewcvs?rev=252445&root=gcc&view=rev
Log:
	PR target/46091
	* config/i386/i386.md (*anddi_1_btr): Change predicates of
	operand 0 and operand 1 to nomimmediate_operand. Add "m" constraint.
	Add ix86_binary_operator_ok to insn constraint.
	(*iordi_1_bts): Ditto.
	(*xordi_1_btc): Ditto.
	(*btsq): Change predicate of operand 0 to nonimmediate_operand.
	Update corresponding peephole2 pattern.
	(*btrq): Ditto.
	(*btcq): Ditto.

testsuite/ChangeLog:

	PR target/46091
	* gcc.target/i386/pr46091-1.c: Update scan-assembler-times.
	(testm): New test function.
	* gcc.target/i386/pr46091-2.c: Ditto.
	* gcc.target/i386/pr46091-3.c: Ditto.

Modified:
    branches/range-gen2/gcc/ChangeLog
    branches/range-gen2/gcc/config/i386/i386.md
    branches/range-gen2/gcc/testsuite/ChangeLog
    branches/range-gen2/gcc/testsuite/gcc.target/i386/pr46091-1.c
    branches/range-gen2/gcc/testsuite/gcc.target/i386/pr46091-2.c
    branches/range-gen2/gcc/testsuite/gcc.target/i386/pr46091-3.c

Comment 7 Aldy Hernandez 2017-09-13 17:16:49 UTC

Author: aldyh
Date: Wed Sep 13 17:16:18 2017
New Revision: 252513

URL: https://gcc.gnu.org/viewcvs?rev=252513&root=gcc&view=rev
Log:
	PR target/46091
	* config/i386/i386.md (*btsq_imm): Rename from *btsq.
	(*btrq_imm): Rename from *btrq.
	(*btcq_imm): Rename from *btcq.
	(btsc): New code attribute.
	(*<btsc><mode>): New insn pattern.
	(*btr<mode>): Ditto.
	(*<btsc><mode>_mask): New insn_and_split pattern.
	(*btr<mode>_mask): Ditto.

testsuite/ChangeLog:

	PR target/46091
	* gcc.target/i386/pr46091-4.c: New test.
	* gcc.target/i386/pr46091-4a.c: Ditto.
	* gcc.target/i386/pr46091-5.c: Ditto.
	* gcc.target/i386/pr46091-5a.c: Ditto.

Added:
    branches/range-gen2/gcc/testsuite/gcc.target/i386/pr46091-4.c
    branches/range-gen2/gcc/testsuite/gcc.target/i386/pr46091-4a.c
    branches/range-gen2/gcc/testsuite/gcc.target/i386/pr46091-5.c
    branches/range-gen2/gcc/testsuite/gcc.target/i386/pr46091-5a.c
Modified:
    branches/range-gen2/gcc/ChangeLog
    branches/range-gen2/gcc/config/i386/i386.md
    branches/range-gen2/gcc/testsuite/ChangeLog

Comment 8 Martin Liška 2018-11-19 11:52:55 UTC

Can the bug be marked as resolved?

Comment 9 Uroš Bizjak 2018-11-19 12:10:02 UTC

(In reply to Martin Liška from comment #8)
> Can the bug be marked as resolved?

Yes.