The-Language.html 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
  2. <html>
  3. <!-- Copyright (C) 1988-2017 Free Software Foundation, Inc.
  4. Permission is granted to copy, distribute and/or modify this document
  5. under the terms of the GNU Free Documentation License, Version 1.3 or
  6. any later version published by the Free Software Foundation; with the
  7. Invariant Sections being "Funding Free Software", the Front-Cover
  8. Texts being (a) (see below), and with the Back-Cover Texts being (b)
  9. (see below). A copy of the license is included in the section entitled
  10. "GNU Free Documentation License".
  11. (a) The FSF's Front-Cover Text is:
  12. A GNU Manual
  13. (b) The FSF's Back-Cover Text is:
  14. You have freedom to copy and modify this GNU Manual, like GNU
  15. software. Copies published by the Free Software Foundation raise
  16. funds for GNU development. -->
  17. <!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
  18. <head>
  19. <title>GNU Compiler Collection (GCC) Internals: The Language</title>
  20. <meta name="description" content="GNU Compiler Collection (GCC) Internals: The Language">
  21. <meta name="keywords" content="GNU Compiler Collection (GCC) Internals: The Language">
  22. <meta name="resource-type" content="document">
  23. <meta name="distribution" content="global">
  24. <meta name="Generator" content="makeinfo">
  25. <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  26. <link href="index.html#Top" rel="start" title="Top">
  27. <link href="Option-Index.html#Option-Index" rel="index" title="Option Index">
  28. <link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
  29. <link href="Match-and-Simplify.html#Match-and-Simplify" rel="up" title="Match and Simplify">
  30. <link href="Funding.html#Funding" rel="next" title="Funding">
  31. <link href="GIMPLE-API.html#GIMPLE-API" rel="prev" title="GIMPLE API">
  32. <style type="text/css">
  33. <!--
  34. a.summary-letter {text-decoration: none}
  35. blockquote.smallquotation {font-size: smaller}
  36. div.display {margin-left: 3.2em}
  37. div.example {margin-left: 3.2em}
  38. div.indentedblock {margin-left: 3.2em}
  39. div.lisp {margin-left: 3.2em}
  40. div.smalldisplay {margin-left: 3.2em}
  41. div.smallexample {margin-left: 3.2em}
  42. div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
  43. div.smalllisp {margin-left: 3.2em}
  44. kbd {font-style:oblique}
  45. pre.display {font-family: inherit}
  46. pre.format {font-family: inherit}
  47. pre.menu-comment {font-family: serif}
  48. pre.menu-preformatted {font-family: serif}
  49. pre.smalldisplay {font-family: inherit; font-size: smaller}
  50. pre.smallexample {font-size: smaller}
  51. pre.smallformat {font-family: inherit; font-size: smaller}
  52. pre.smalllisp {font-size: smaller}
  53. span.nocodebreak {white-space:nowrap}
  54. span.nolinebreak {white-space:nowrap}
  55. span.roman {font-family:serif; font-weight:normal}
  56. span.sansserif {font-family:sans-serif; font-weight:normal}
  57. ul.no-bullet {list-style: none}
  58. -->
  59. </style>
  60. </head>
  61. <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
  62. <a name="The-Language"></a>
  63. <div class="header">
  64. <p>
  65. Previous: <a href="GIMPLE-API.html#GIMPLE-API" accesskey="p" rel="prev">GIMPLE API</a>, Up: <a href="Match-and-Simplify.html#Match-and-Simplify" accesskey="u" rel="up">Match and Simplify</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html#Option-Index" title="Index" rel="index">Index</a>]</p>
  66. </div>
  67. <hr>
  68. <a name="The-Language-1"></a>
  69. <h3 class="section">25.2 The Language</h3>
  70. <a name="index-The-Language"></a>
  71. <p>The language to write expression simplifications in resembles other
  72. domain-specific languages GCC uses. Thus it is lispy. Lets start
  73. with an example from the match.pd file:
  74. </p>
  75. <div class="smallexample">
  76. <pre class="smallexample">(simplify
  77. (bit_and @0 integer_all_onesp)
  78. @0)
  79. </pre></div>
  80. <p>This example contains all required parts of an expression simplification.
  81. A simplification is wrapped inside a <code>(simplify ...)</code> expression.
  82. That contains at least two operands - an expression that is matched
  83. with the GIMPLE or GENERIC IL and a replacement expression that is
  84. returned if the match was successful.
  85. </p>
  86. <p>Expressions have an operator ID, <code>bit_and</code> in this case. Expressions can
  87. be lower-case tree codes with <code>_expr</code> stripped off or builtin
  88. function code names in all-caps, like <code>BUILT_IN_SQRT</code>.
  89. </p>
  90. <p><code>@n</code> denotes a so-called capture. It captures the operand and lets
  91. you refer to it in other places of the match-and-simplify. In the
  92. above example it is refered to in the replacement expression. Captures
  93. are <code>@</code> followed by a number or an identifier.
  94. </p>
  95. <div class="smallexample">
  96. <pre class="smallexample">(simplify
  97. (bit_xor @0 @0)
  98. { build_zero_cst (type); })
  99. </pre></div>
  100. <p>In this example <code>@0</code> is mentioned twice which constrains the matched
  101. expression to have two equal operands. Usually matches are constraint
  102. to equal types. If operands may be constants and conversions are involved
  103. matching by value might be preferred in which case use <code>@@0</code> to
  104. denote a by value match and the specific operand you want to refer to
  105. in the result part. This example also introduces
  106. operands written in C code. These can be used in the expression
  107. replacements and are supposed to evaluate to a tree node which has to
  108. be a valid GIMPLE operand (so you cannot generate expressions in C code).
  109. </p>
  110. <div class="smallexample">
  111. <pre class="smallexample">(simplify
  112. (trunc_mod integer_zerop@0 @1)
  113. (if (!integer_zerop (@1))
  114. @0))
  115. </pre></div>
  116. <p>Here <code>@0</code> captures the first operand of the trunc_mod expression
  117. which is also predicated with <code>integer_zerop</code>. Expression operands
  118. may be either expressions, predicates or captures. Captures
  119. can be unconstrained or capture expresions or predicates.
  120. </p>
  121. <p>This example introduces an optional operand of simplify,
  122. the if-expression. This condition is evaluated after the
  123. expression matched in the IL and is required to evaluate to true
  124. to enable the replacement expression in the second operand
  125. position. The expression operand of the <code>if</code> is a standard C
  126. expression which may contain references to captures. The <code>if</code>
  127. has an optional third operand which may contain the replacement
  128. expression that is enabled when the condition evaluates to false.
  129. </p>
  130. <p>A <code>if</code> expression can be used to specify a common condition
  131. for multiple simplify patterns, avoiding the need
  132. to repeat that multiple times:
  133. </p>
  134. <div class="smallexample">
  135. <pre class="smallexample">(if (!TYPE_SATURATING (type)
  136. &amp;&amp; !FLOAT_TYPE_P (type) &amp;&amp; !FIXED_POINT_TYPE_P (type))
  137. (simplify
  138. (minus (plus @0 @1) @0)
  139. @1)
  140. (simplify
  141. (minus (minus @0 @1) @0)
  142. (negate @1)))
  143. </pre></div>
  144. <p>Note that <code>if</code>s in outer position do not have the optional
  145. else clause but instead have multiple then clauses.
  146. </p>
  147. <p>Ifs can be nested.
  148. </p>
  149. <p>There exists a <code>switch</code> expression which can be used to
  150. chain conditions avoiding nesting <code>if</code>s too much:
  151. </p>
  152. <div class="smallexample">
  153. <pre class="smallexample">(simplify
  154. (simple_comparison @0 REAL_CST@1)
  155. (switch
  156. /* a CMP (-0) -&gt; a CMP 0 */
  157. (if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (@1)))
  158. (cmp @0 { build_real (TREE_TYPE (@1), dconst0); }))
  159. /* x != NaN is always true, other ops are always false. */
  160. (if (REAL_VALUE_ISNAN (TREE_REAL_CST (@1))
  161. &amp;&amp; ! HONOR_SNANS (@1))
  162. { constant_boolean_node (cmp == NE_EXPR, type); })))
  163. </pre></div>
  164. <p>Is equal to
  165. </p>
  166. <div class="smallexample">
  167. <pre class="smallexample">(simplify
  168. (simple_comparison @0 REAL_CST@1)
  169. (switch
  170. /* a CMP (-0) -&gt; a CMP 0 */
  171. (if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (@1)))
  172. (cmp @0 { build_real (TREE_TYPE (@1), dconst0); })
  173. /* x != NaN is always true, other ops are always false. */
  174. (if (REAL_VALUE_ISNAN (TREE_REAL_CST (@1))
  175. &amp;&amp; ! HONOR_SNANS (@1))
  176. { constant_boolean_node (cmp == NE_EXPR, type); }))))
  177. </pre></div>
  178. <p>which has the second <code>if</code> in the else operand of the first.
  179. The <code>switch</code> expression takes <code>if</code> expressions as
  180. operands (which may not have else clauses) and as a last operand
  181. a replacement expression which should be enabled by default if
  182. no other condition evaluated to true.
  183. </p>
  184. <p>Captures can also be used for capturing results of sub-expressions.
  185. </p>
  186. <div class="smallexample">
  187. <pre class="smallexample">#if GIMPLE
  188. (simplify
  189. (pointer_plus (addr@2 @0) INTEGER_CST_P@1)
  190. (if (is_gimple_min_invariant (@2)))
  191. {
  192. HOST_WIDE_INT off;
  193. tree base = get_addr_base_and_unit_offset (@0, &amp;off);
  194. off += tree_to_uhwi (@1);
  195. /* Now with that we should be able to simply write
  196. (addr (mem_ref (addr @base) (plus @off @1))) */
  197. build1 (ADDR_EXPR, type,
  198. build2 (MEM_REF, TREE_TYPE (TREE_TYPE (@2)),
  199. build_fold_addr_expr (base),
  200. build_int_cst (ptr_type_node, off)));
  201. })
  202. #endif
  203. </pre></div>
  204. <p>In the above example, <code>@2</code> captures the result of the expression
  205. <code>(addr @0)</code>. For outermost expression only its type can be captured,
  206. and the keyword <code>type</code> is reserved for this purpose. The above
  207. example also gives a way to conditionalize patterns to only apply
  208. to <code>GIMPLE</code> or <code>GENERIC</code> by means of using the pre-defined
  209. preprocessor macros <code>GIMPLE</code> and <code>GENERIC</code> and using
  210. preprocessor directives.
  211. </p>
  212. <div class="smallexample">
  213. <pre class="smallexample">(simplify
  214. (bit_and:c integral_op_p@0 (bit_ior:c (bit_not @0) @1))
  215. (bit_and @1 @0))
  216. </pre></div>
  217. <p>Here we introduce flags on match expressions. The flag used
  218. above, <code>c</code>, denotes that the expression should
  219. be also matched commutated. Thus the above match expression
  220. is really the following four match expressions:
  221. </p>
  222. <div class="smallexample">
  223. <pre class="smallexample"> (bit_and integral_op_p@0 (bit_ior (bit_not @0) @1))
  224. (bit_and (bit_ior (bit_not @0) @1) integral_op_p@0)
  225. (bit_and integral_op_p@0 (bit_ior @1 (bit_not @0)))
  226. (bit_and (bit_ior @1 (bit_not @0)) integral_op_p@0)
  227. </pre></div>
  228. <p>Usual canonicalizations you know from GENERIC expressions are
  229. applied before matching, so for example constant operands always
  230. come second in commutative expressions.
  231. </p>
  232. <p>The second supported flag is <code>s</code> which tells the code
  233. generator to fail the pattern if the expression marked with
  234. <code>s</code> does have more than one use. For example in
  235. </p>
  236. <div class="smallexample">
  237. <pre class="smallexample">(simplify
  238. (pointer_plus (pointer_plus:s @0 @1) @3)
  239. (pointer_plus @0 (plus @1 @3)))
  240. </pre></div>
  241. <p>this avoids the association if <code>(pointer_plus @0 @1)</code> is
  242. used outside of the matched expression and thus it would stay
  243. live and not trivially removed by dead code elimination.
  244. </p>
  245. <p>More features exist to avoid too much repetition.
  246. </p>
  247. <div class="smallexample">
  248. <pre class="smallexample">(for op (plus pointer_plus minus bit_ior bit_xor)
  249. (simplify
  250. (op @0 integer_zerop)
  251. @0))
  252. </pre></div>
  253. <p>A <code>for</code> expression can be used to repeat a pattern for each
  254. operator specified, substituting <code>op</code>. <code>for</code> can be
  255. nested and a <code>for</code> can have multiple operators to iterate.
  256. </p>
  257. <div class="smallexample">
  258. <pre class="smallexample">(for opa (plus minus)
  259. opb (minus plus)
  260. (for opc (plus minus)
  261. (simplify...
  262. </pre></div>
  263. <p>In this example the pattern will be repeated four times with
  264. <code>opa, opb, opc</code> being <code>plus, minus, plus</code>,
  265. <code>plus, minus, minus</code>, <code>minus, plus, plus</code>,
  266. <code>minus, plus, minus</code>.
  267. </p>
  268. <p>To avoid repeating operator lists in <code>for</code> you can name
  269. them via
  270. </p>
  271. <div class="smallexample">
  272. <pre class="smallexample">(define_operator_list pmm plus minus mult)
  273. </pre></div>
  274. <p>and use them in <code>for</code> operator lists where they get expanded.
  275. </p>
  276. <div class="smallexample">
  277. <pre class="smallexample">(for opa (pmm trunc_div)
  278. (simplify...
  279. </pre></div>
  280. <p>So this example iterates over <code>plus</code>, <code>minus</code>, <code>mult</code>
  281. and <code>trunc_div</code>.
  282. </p>
  283. <p>Using operator lists can also remove the need to explicitely write
  284. a <code>for</code>. All operator list uses that appear in a <code>simplify</code>
  285. or <code>match</code> pattern in operator positions will implicitely
  286. be added to a new <code>for</code>. For example
  287. </p>
  288. <div class="smallexample">
  289. <pre class="smallexample">(define_operator_list SQRT BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL)
  290. (define_operator_list POW BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL)
  291. (simplify
  292. (SQRT (POW @0 @1))
  293. (POW (abs @0) (mult @1 { built_real (TREE_TYPE (@1), dconsthalf); })))
  294. </pre></div>
  295. <p>is the same as
  296. </p>
  297. <div class="smallexample">
  298. <pre class="smallexample">(for SQRT (BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL)
  299. POW (BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL)
  300. (simplify
  301. (SQRT (POW @0 @1))
  302. (POW (abs @0) (mult @1 { built_real (TREE_TYPE (@1), dconsthalf); }))))
  303. </pre></div>
  304. <p><code>for</code>s and operator lists can include the special identifier
  305. <code>null</code> that matches nothing and can never be generated. This can
  306. be used to pad an operator list so that it has a standard form,
  307. even if there isn&rsquo;t a suitable operator for every form.
  308. </p>
  309. <p>Another building block are <code>with</code> expressions in the
  310. result expression which nest the generated code in a new C block
  311. followed by its argument:
  312. </p>
  313. <div class="smallexample">
  314. <pre class="smallexample">(simplify
  315. (convert (mult @0 @1))
  316. (with { tree utype = unsigned_type_for (type); }
  317. (convert (mult (convert:utype @0) (convert:utype @1)))))
  318. </pre></div>
  319. <p>This allows code nested in the <code>with</code> to refer to the declared
  320. variables. In the above case we use the feature to specify the
  321. type of a generated expression with the <code>:type</code> syntax where
  322. <code>type</code> needs to be an identifier that refers to the desired type.
  323. Usually the types of the generated result expressions are
  324. determined from the context, but sometimes like in the above case
  325. it is required that you specify them explicitely.
  326. </p>
  327. <p>As intermediate conversions are often optional there is a way to
  328. avoid the need to repeat patterns both with and without such
  329. conversions. Namely you can mark a conversion as being optional
  330. with a <code>?</code>:
  331. </p>
  332. <div class="smallexample">
  333. <pre class="smallexample">(simplify
  334. (eq (convert@0 @1) (convert? @2))
  335. (eq @1 (convert @2)))
  336. </pre></div>
  337. <p>which will match both <code>(eq (convert @1) (convert @2))</code> and
  338. <code>(eq (convert @1) @2)</code>. The optional converts are supposed
  339. to be all either present or not, thus
  340. <code>(eq (convert? @1) (convert? @2))</code> will result in two
  341. patterns only. If you want to match all four combinations you
  342. have access to two additional conditional converts as in
  343. <code>(eq (convert1? @1) (convert2? @2))</code>.
  344. </p>
  345. <p>Predicates available from the GCC middle-end need to be made
  346. available explicitely via <code>define_predicates</code>:
  347. </p>
  348. <div class="smallexample">
  349. <pre class="smallexample">(define_predicates
  350. integer_onep integer_zerop integer_all_onesp)
  351. </pre></div>
  352. <p>You can also define predicates using the pattern matching language
  353. and the <code>match</code> form:
  354. </p>
  355. <div class="smallexample">
  356. <pre class="smallexample">(match negate_expr_p
  357. INTEGER_CST
  358. (if (TYPE_OVERFLOW_WRAPS (type)
  359. || may_negate_without_overflow_p (t))))
  360. (match negate_expr_p
  361. (negate @0))
  362. </pre></div>
  363. <p>This shows that for <code>match</code> expressions there is <code>t</code>
  364. available which captures the outermost expression (something
  365. not possible in the <code>simplify</code> context). As you can see
  366. <code>match</code> has an identifier as first operand which is how
  367. you refer to the predicate in patterns. Multiple <code>match</code>
  368. for the same identifier add additional cases where the predicate
  369. matches.
  370. </p>
  371. <p>Predicates can also match an expression in which case you need
  372. to provide a template specifying the identifier and where to
  373. get its operands from:
  374. </p>
  375. <div class="smallexample">
  376. <pre class="smallexample">(match (logical_inverted_value @0)
  377. (eq @0 integer_zerop))
  378. (match (logical_inverted_value @0)
  379. (bit_not truth_valued_p@0))
  380. </pre></div>
  381. <p>You can use the above predicate like
  382. </p>
  383. <div class="smallexample">
  384. <pre class="smallexample">(simplify
  385. (bit_and @0 (logical_inverted_value @0))
  386. { build_zero_cst (type); })
  387. </pre></div>
  388. <p>Which will match a bitwise and of an operand with its logical
  389. inverted value.
  390. </p>
  391. <hr>
  392. <div class="header">
  393. <p>
  394. Previous: <a href="GIMPLE-API.html#GIMPLE-API" accesskey="p" rel="prev">GIMPLE API</a>, Up: <a href="Match-and-Simplify.html#Match-and-Simplify" accesskey="u" rel="up">Match and Simplify</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html#Option-Index" title="Index" rel="index">Index</a>]</p>
  395. </div>
  396. </body>
  397. </html>