From patchwork Tue Aug 5 10:11:00 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 376641 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id A7CE2140077 for ; Tue, 5 Aug 2014 20:14:16 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=UNQmrq3F582d2+rE/jIEr4/4o278eAHMBueDHrXWhyS5oAG0RtIe6 7oj3lTHLwkPBh+7QxfcYTuNjMDY+x9hfoA93vcL4oDJDG7FHDBOpUCQd8TBHdLDK ZtRM4M0gxoyl2IXeAG+oBGpclh2tlVO2Wm8SWG298vyBsV4zK05I0k= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=TIKXSmHN0yvWQtgoPCHijlaYW/A=; b=KS+hlrx7GH1w9YoBIAj7 sRyoCMbvX3YnMqQJMrQ0j/FPTXiYvxIaqjax+E06d7MUsWSbYHHdf3AVC6EAdIb+ JlTFas/IlV7tfl1Px8hAGrj+kj69z6oOaHwINxMHR+HKMZnFaeI5ozvqpmDxZpdS sjAAw5jzBjnQRxcdE6pjf+A= Received: (qmail 14348 invoked by alias); 5 Aug 2014 10:14:09 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 14337 invoked by uid 89); 5 Aug 2014 10:14:08 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.6 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx2.suse.de Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Tue, 05 Aug 2014 10:14:06 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id C75FDAD8F for ; Tue, 5 Aug 2014 10:14:03 +0000 (UTC) Date: Tue, 5 Aug 2014 12:11:00 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH][match-and-simplify] Initial drop of match-and-simplify.texi Message-ID: User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Converted from my plain-text notes I did for writing the Cauldron presntation slides. Built and installed. Richard. 2014-08-05 Richard Biener * doc/match-and-simplify.texi: New file. * doc/gccint.texi: Include match-and-simplify.texi. * Makefile.in (TEXI_GCCINT_FILES): Add match-and-simplify.texi. Index: gcc/doc/match-and-simplify.texi =================================================================== --- gcc/doc/match-and-simplify.texi (revision 0) +++ gcc/doc/match-and-simplify.texi (working copy) @@ -0,0 +1,202 @@ +@c Copyright (C) 2014 Free Software Foundation, Inc. +@c Free Software Foundation, Inc. +@c This is part of the GCC manual. +@c For copying conditions, see the file gcc.texi. + +@node Match and Simplify +@chapter Match and Simplify +@cindex Match and Simplify + +The GIMPLE and GENERIC pattern matching project match-and-simplify +tries to address several issues. + +@enumerate +@item unify expression simplifications currently spread and duplicated + over separate files like fold-const.c, gimple-fold.c and builtins.c +@item allow for a cheap way to implement building and simplifying + non-trivial GIMPLE expressions, avoiding the need to go through + building and simplifying GENERIC via fold_buildN and then + gimplifying via force_gimple_operand +@end enumerate + +To address these the project introduces a simple domain specific language +to write expression simplifications from which code targeting GIMPLE +and GENERIC is auto-generated. The GENERIC variant follows the +fold_buildN API while for the GIMPLE variant and to addres 2) new +APIs are introduced. + +@menu +* GIMPLE API:: +* The Language:: +@end menu + +@node GIMPLE API +@section GIMPLE API +@cindex GIMPLE API + +The main GIMPLE API entry to the expression simplifications mimics +that of the GENERIC fold_@{unary,binary,ternary@} API: + +@deftypefn +tree gimple_match_and_simplify (enum tree_code, tree, tree, + gimple_seq *, tree (*)(tree)); +@end deftypefn +@deftypefn +tree gimple_match_and_simplify (enum tree_code, tree, tree, tree, + gimple_seq *, tree (*)(tree)); +@end deftypefn +@deftypefn +tree gimple_match_and_simplify (enum tree_code, tree, tree, tree, tree, + gimple_seq *, tree (*)(tree)); +@end deftypefn +@deftypefn +tree gimple_match_and_simplify (enum built_in_function, tree, tree, + gimple_seq *, tree (*)(tree)); +@end deftypefn + +thus providing n-ary overloads for operation or function. The +additional arguments are a gimple_seq where built statements are +inserted on (if @code{NULL} then simplifications requiring new statements +are not performed) and a valueization hook that can be used to +tie simplifications to a SSA lattice. + +In addition to those APIs a fold_stmt-like interface is provided with + +@deftypefn +bool gimple_match_and_simplify (gimple_stmt_iterator *, tree (*)(tree)); +@end deftypefn + +which also has the additional valueization hook. + +Ontop of these a @code{fold_buildN}-like API for GIMPLE is introduced: + +@deftypefn +tree gimple_build (gimple_seq *, location_t, + enum tree_code, tree, tree, + tree (*valueize) (tree) = NULL); +@end deftypefn +@deftypefn +tree gimple_build (gimple_seq *, location_t, + enum tree_code, tree, tree, tree, + tree (*valueize) (tree) = NULL); +@end deftypefn +@deftypefn +tree gimple_build (gimple_seq *, location_t, + enum tree_code, tree, tree, tree, tree, + tree (*valueize) (tree) = NULL); +@end deftypefn +@deftypefn +tree gimple_build (gimple_seq *, location_t, + enum built_in_function, tree, tree, + tree (*valueize) (tree) = NULL); +@end deftypefn + +which is supposed to replace @code{force_gimple_operand (fold_buildN (...), ...)}. + + +@node The Language +@section The Language +@cindex The Language + +The language to write expression simplifications in resembles other +domain-specific languages GCC uses. Thus it is lispy. Lets start +with an example from the match.pd file on the branch: + +@smallexample +(match_and_simplify + (bit_and @@0 integer_all_onesp) + @@0) +@end smallexample + +This example contains all required parts of an expression simplification. +A simplification is wrapped inside a @code{(match_and_simplify ...)} expression. +That contains at least two operands - an expression that is matched +with the GIMPLE or GENERIC IL and a replacement expression that is +returned if the match was successful. + +Expressions have an ID, @code{bit_and} in this case. Expressions can +be lower-case tree codes with @code{_expr} stripped off or builtin +function code names in all-caps, like @code{BUILT_IN_SQRT}. + +@code{@@n} denotes a so-called capture. It captures the operand and lets +you refer to it in other places of the match-and-simplify. In the +above example it is refered to in the replacement expression. + +@smallexample +(match_and_simplify + (bit_xor @@0 @@0) + @{ build_zero_cst (type); @}) +@end smallexample + +In this example @code{@@0} is mentioned twice which constrains the matched +expression to have two equal operands. This example also introduces +operands written in C code. These can be used in the expression +replacements and are supposed to evaluate to a tree node. + +@smallexample +(match_and_simplify + (trunc_mod integer_zerop@@0 @@1) + (if (!integer_zerop (@@1))) + @@0) +@end smallexample + +Here @code{@@0} captures the first operand of the trunc_mod expression +which is also predicated with @code{integer_zerop}. Expression operands +may be either expressions, predicates or captures. Captures +can be unconstrained or capture expresions or predicates. + +This example introduces an optional operand of match_and_simplify, +the if-expression. This condition is evaluated after the +expression matched in the IL and is required to evaluate to true +to enable the replacement expression. The expression operand +of the @code{if} is a standard C expression which may contain references +to captures. + +@smallexample +(match_and_simplify + (bit_and:c integral_op_p@@0 (bit_ior:c (bit_not @@0) @@1)) + (bit_and @@1 @@0)) +@end smallexample + +Here we introduce flags on match expressions. There is currently +a single flag, @code{c}, which denotes that the expression should +be also matched commutated. Thus the above match expression +is really the following four match expressions: + + (bit_and integral_op_p@@0 (bit_ior (bit_not @@0) @@1)) + (bit_and (bit_ior (bit_not @@0) @@1) integral_op_p@@0) + (bit_and integral_op_p@@0 (bit_ior @@1 (bit_not @@0))) + (bit_and (bit_ior @@1 (bit_not @@0)) integral_op_p@@0) + +Usual canonicalizations you know from GENERIC expressions are +applied before matching, so for example constant operands always +come second in commutative expressions. + +Two more features exist to avoid too much repetition. + +@smallexample +(for op in plus pointer_plus minus bit_ior bit_xor + (match_and_simplify + (op @@0 integer_zerop) + @@0)) +@end smallexample + +A @code{for} expression can be used to repeat a pattern for each +operator specified, substituting @code{op}. + +@smallexample +(if (!TYPE_SATURATING (type) + && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type)) + (match_and_simplify + (minus (plus @@0 @@1) @@0) + @@1) + (match_and_simplify + (minus (minus @@0 @@1) @@0) + (negate @@1))) +@end smallexample + +A @code{if} expression can be used to specify a common condition +for multiple match-and-simplify patterns, avoiding the need +to repeat that multiple times. + + Index: gcc/doc/gccint.texi =================================================================== --- gcc/doc/gccint.texi (revision 213544) +++ gcc/doc/gccint.texi (working copy) @@ -123,6 +123,7 @@ Additional tutorial information is linke * Plugins:: Extending the compiler with plugins. * LTO:: Using Link-Time Optimization. +* Match and Simplify:: How to write expression simplification patterns for GIMPLE and GENERIC * Funding:: How to help assure funding for free software. * GNU Project:: The GNU Project and GNU/Linux. @@ -158,6 +159,7 @@ Additional tutorial information is linke @include gty.texi @include plugins.texi @include lto.texi +@include match-and-simplify.texi @include funding.texi @include gnu.texi Index: gcc/Makefile.in =================================================================== --- gcc/Makefile.in (revision 213574) +++ gcc/Makefile.in (working copy) @@ -2865,7 +2865,8 @@ TEXI_GCCINT_FILES = gccint.texi gcc-comm configfiles.texi collect2.texi headerdirs.texi funding.texi \ gnu.texi gpl_v3.texi fdl.texi contrib.texi languages.texi \ sourcebuild.texi gty.texi libgcc.texi cfg.texi tree-ssa.texi \ - loop.texi generic.texi gimple.texi plugins.texi optinfo.texi + loop.texi generic.texi gimple.texi plugins.texi optinfo.texi \ + match-and-simplify.texi TEXI_GCCINSTALL_FILES = install.texi install-old.texi fdl.texi \ gcc-common.texi gcc-vers.texi