Opened 7 years ago

Closed 7 years ago

#7014 closed feature request (fixed)

RULES for bitwise logic and shift primops

Reported by: akio Owned by: simonpj
Priority: normal Milestone: 7.6.1
Component: Compiler Version: 7.4.2
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

I think it will be useful if expressions like (x .|. 0) and (shiftL x 0) are optimized away.

Attachments (4)

0001-add-RULES-for-bitwise-logic-and-shift-primops.patch (1.4 KB) - added by akio 7 years ago.
A proposed patch
7014-base.patch (3.3 KB) - added by pcapriotti 7 years ago.
7014.patch (25.5 KB) - added by pcapriotti 7 years ago.
7014-tests.patch (4.1 KB) - added by pcapriotti 7 years ago.

Download all attachments as: .zip

Change History (17)

Changed 7 years ago by akio

A proposed patch

comment:1 Changed 7 years ago by akio

Status: newpatch

comment:2 Changed 7 years ago by simonpj

difficulty: Unknown

You'd like to do more. We'd like to constant-fold (3# .|. 5#), just as we do arithmetic. This can't be done with a RULE in the source file, but it can be done with a BuiltinRule defined in the GHC module compiler/prelude/PrelRules. Would you care to try that? There are plenty of examples in that module to work from. Thanks!

Simon

comment:3 Changed 7 years ago by akio

I'm sure GHC already does constant-fold (3 .|. 5). I see AndOp, OrOp etc. mentioned in PrelRules.lhs.

comment:4 Changed 7 years ago by pcapriotti

Milestone: 7.6.1
Owner: set to pcapriotti

Changed 7 years ago by pcapriotti

Attachment: 7014-base.patch added

comment:5 Changed 7 years ago by pcapriotti

The attached patches add identity rules for shift and bitwise operations to PrelRules, as well as similar rules from GHC.Base.

I also refactored PrelRules a little to remove some duplication.

We're still missing rules like:

x and# (complement 0) ==> x
x or# (complement 0) ==> complement 0

since I'm not sure how we can match complement 0 in MachWord. We could convert to Word, but that is wrong for cross-compilation.

There were already other places where it is assumed that target == host, however, so maybe it's ok to add another one?

comment:6 Changed 7 years ago by simonmar

Don't add any assumptions that target == host when that could cause incorrect code to be generated, because that would make it impossible to cross-compile. (I believe at the moment the worst that could happen is that some floating-point constant folding is performed at the wrong precision).

comment:7 Changed 7 years ago by akio

Is the rightIdentity rule for IntRemOp wrong? It looks like it will rewrite (remInt# 1# 1#) into 1#.

Changed 7 years ago by pcapriotti

Attachment: 7014.patch added

Changed 7 years ago by pcapriotti

Attachment: 7014-tests.patch added

comment:8 Changed 7 years ago by pcapriotti

Is the rightIdentity rule for IntRemOp wrong?

Yes, thanks for catching that. I updated the patch and added some more tests.

comment:9 Changed 7 years ago by simonpj

Owner: changed from pcapriotti to simonpj

comment:10 Changed 7 years ago by simonpj

Paolo, I'm more or less happy with the patch, with the following suggestions:

  • The local function primop_rule now always returns a singleton list; any multi-rule stuff is done within that single rule. So I suggest making the top-level primOpRule function do the pattern matching, and return one rule:
    primOpRule :: PrimOp -> Name -> CoreRule
    primOpRule IntAddOp nm = mkPrimOpRule nm 2 [ binaryLit (intOp2 (+)) 
     		                           , identity zeroi ]
    ..etc...
    
  • That turns relop and rules into top-level functions, which can have type signatures and helpful names.
  • I'd prefer to eta-expand rules. Otherwise the msum is a bit cryptic.
  • You may be able to use convFloating less often, by having a variant of getLiteral or whatever for floating, et getFloatingLiteral, used for floating primops.
  • Can you comment the Int argument of getLiteral?

Then go ahead and commit. Thanks!

Simon

comment:11 Changed 7 years ago by p.capriotti@…

commit 949081a9e87aee633e43d8e1795036c106456cfe

Merge: c833546... 4f811e1...
Author: Paolo Capriotti <p.capriotti@gmail.com>
Date:   Thu Jul 26 21:50:56 2012 +0100

    Merge PrelRules refactoring (#7014)

 compiler/basicTypes/MkId.lhs   |    4 +-
 compiler/prelude/PrelRules.lhs |  660 +++++++++++++++++++++++-----------------
 2 files changed, 385 insertions(+), 279 deletions(-)

comment:12 Changed 7 years ago by p.capriotti@…

commit 6a43840c9d9e0bcbfac64ee7f5fbd22a5701af5a

Author: Paolo Capriotti <p.capriotti@gmail.com>
Date:   Wed Jul 4 11:47:55 2012 +0100

    Refactor PrelRules and add more rules (#7014)
    
    Ported various rules for numeric types from GHC.Base. Added new rules
    for bitwise operations, shifts and word comparisons.

 compiler/basicTypes/MkId.lhs   |    2 +-
 compiler/prelude/PrelRules.lhs |  580 +++++++++++++++++++++++-----------------
 2 files changed, 335 insertions(+), 247 deletions(-)

comment:13 Changed 7 years ago by pcapriotti

Resolution: fixed
Status: patchclosed
Note: See TracTickets for help on using tickets.