Mercurial > hg > graal-compiler
annotate src/share/vm/adlc/dfa.cpp @ 4970:33df1aeaebbf
Merge with http://hg.openjdk.java.net/hsx/hsx24/hotspot/
author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
---|---|
date | Mon, 27 Feb 2012 13:10:13 +0100 |
parents | f95d63e2154a |
children | 573cf206e381 |
rev | line source |
---|---|
0 | 1 /* |
1972 | 2 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. |
0 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 * | |
5 * This code is free software; you can redistribute it and/or modify it | |
6 * under the terms of the GNU General Public License version 2 only, as | |
7 * published by the Free Software Foundation. | |
8 * | |
9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
12 * version 2 for more details (a copy is included in the LICENSE file that | |
13 * accompanied this code). | |
14 * | |
15 * You should have received a copy of the GNU General Public License version | |
16 * 2 along with this work; if not, write to the Free Software Foundation, | |
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
18 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
628
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
628
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
628
diff
changeset
|
21 * questions. |
0 | 22 * |
23 */ | |
24 | |
25 // DFA.CPP - Method definitions for outputting the matcher DFA from ADLC | |
26 #include "adlc.hpp" | |
27 | |
28 //---------------------------Switches for debugging output--------------------- | |
29 static bool debug_output = false; | |
30 static bool debug_output1 = false; // top level chain rules | |
31 | |
32 //---------------------------Access to internals of class State---------------- | |
33 static const char *sLeft = "_kids[0]"; | |
34 static const char *sRight = "_kids[1]"; | |
35 | |
36 //---------------------------DFA productions----------------------------------- | |
37 static const char *dfa_production = "DFA_PRODUCTION"; | |
38 static const char *dfa_production_set_valid = "DFA_PRODUCTION__SET_VALID"; | |
39 | |
40 //---------------------------Production State---------------------------------- | |
41 static const char *knownInvalid = "knownInvalid"; // The result does NOT have a rule defined | |
42 static const char *knownValid = "knownValid"; // The result must be produced by a rule | |
43 static const char *unknownValid = "unknownValid"; // Unknown (probably due to a child or predicate constraint) | |
44 | |
45 static const char *noConstraint = "noConstraint"; // No constraints seen so far | |
46 static const char *hasConstraint = "hasConstraint"; // Within the first constraint | |
47 | |
48 | |
49 //------------------------------Production------------------------------------ | |
50 // Track the status of productions for a particular result | |
51 class Production { | |
52 public: | |
53 const char *_result; | |
54 const char *_constraint; | |
55 const char *_valid; | |
56 Expr *_cost_lb; // Cost lower bound for this production | |
57 Expr *_cost_ub; // Cost upper bound for this production | |
58 | |
59 public: | |
60 Production(const char *result, const char *constraint, const char *valid); | |
61 ~Production() {}; | |
62 | |
63 void initialize(); // reset to be an empty container | |
64 | |
65 const char *valid() const { return _valid; } | |
66 Expr *cost_lb() const { return (Expr *)_cost_lb; } | |
67 Expr *cost_ub() const { return (Expr *)_cost_ub; } | |
68 | |
69 void print(); | |
70 }; | |
71 | |
72 | |
73 //------------------------------ProductionState-------------------------------- | |
74 // Track the status of all production rule results | |
75 // Reset for each root opcode (e.g., Op_RegI, Op_AddI, ...) | |
76 class ProductionState { | |
77 private: | |
78 Dict _production; // map result of production, char*, to information or NULL | |
79 const char *_constraint; | |
80 | |
81 public: | |
82 // cmpstr does string comparisions. hashstr computes a key. | |
83 ProductionState(Arena *arena) : _production(cmpstr, hashstr, arena) { initialize(); }; | |
84 ~ProductionState() { }; | |
85 | |
86 void initialize(); // reset local and dictionary state | |
87 | |
88 const char *constraint(); | |
89 void set_constraint(const char *constraint); // currently working inside of constraints | |
90 | |
91 const char *valid(const char *result); // unknownValid, or status for this production | |
92 void set_valid(const char *result); // if not constrained, set status to knownValid | |
93 | |
94 Expr *cost_lb(const char *result); | |
95 Expr *cost_ub(const char *result); | |
96 void set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check); | |
97 | |
98 // Return the Production associated with the result, | |
99 // or create a new Production and insert it into the dictionary. | |
100 Production *getProduction(const char *result); | |
101 | |
102 void print(); | |
103 | |
104 private: | |
105 // Disable public use of constructor, copy-ctor, ... | |
106 ProductionState( ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); }; | |
107 ProductionState( const ProductionState & ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); }; // Deep-copy | |
108 }; | |
109 | |
110 | |
111 //---------------------------Helper Functions---------------------------------- | |
112 // cost_check template: | |
113 // 1) if (STATE__NOT_YET_VALID(EBXREGI) || _cost[EBXREGI] > c) { | |
114 // 2) DFA_PRODUCTION__SET_VALID(EBXREGI, cmovI_memu_rule, c) | |
115 // 3) } | |
116 // | |
117 static void cost_check(FILE *fp, const char *spaces, | |
118 const char *arrayIdx, const Expr *cost, const char *rule, ProductionState &status) { | |
119 bool state_check = false; // true if this production needs to check validity | |
120 bool cost_check = false; // true if this production needs to check cost | |
121 bool cost_is_above_upper_bound = false; // true if this production is unnecessary due to high cost | |
122 bool cost_is_below_lower_bound = false; // true if this production replaces a higher cost production | |
123 | |
124 // Get information about this production | |
125 const Expr *previous_ub = status.cost_ub(arrayIdx); | |
126 if( !previous_ub->is_unknown() ) { | |
127 if( previous_ub->less_than_or_equal(cost) ) { | |
128 cost_is_above_upper_bound = true; | |
129 if( debug_output ) { fprintf(fp, "// Previous rule with lower cost than: %s === %s_rule costs %s\n", arrayIdx, rule, cost->as_string()); } | |
130 } | |
131 } | |
132 | |
133 const Expr *previous_lb = status.cost_lb(arrayIdx); | |
134 if( !previous_lb->is_unknown() ) { | |
135 if( cost->less_than_or_equal(previous_lb) ) { | |
136 cost_is_below_lower_bound = true; | |
137 if( debug_output ) { fprintf(fp, "// Previous rule with higher cost\n"); } | |
138 } | |
139 } | |
140 | |
141 // line 1) | |
142 // Check for validity and compare to other match costs | |
143 const char *validity_check = status.valid(arrayIdx); | |
144 if( validity_check == unknownValid ) { | |
145 fprintf(fp, "%sif (STATE__NOT_YET_VALID(%s) || _cost[%s] > %s) {\n", spaces, arrayIdx, arrayIdx, cost->as_string()); | |
146 state_check = true; | |
147 cost_check = true; | |
148 } | |
149 else if( validity_check == knownInvalid ) { | |
150 if( debug_output ) { fprintf(fp, "%s// %s KNOWN_INVALID \n", spaces, arrayIdx); } | |
151 } | |
152 else if( validity_check == knownValid ) { | |
153 if( cost_is_above_upper_bound ) { | |
154 // production cost is known to be too high. | |
155 return; | |
156 } else if( cost_is_below_lower_bound ) { | |
157 // production will unconditionally overwrite a previous production that had higher cost | |
158 } else { | |
159 fprintf(fp, "%sif ( /* %s KNOWN_VALID || */ _cost[%s] > %s) {\n", spaces, arrayIdx, arrayIdx, cost->as_string()); | |
160 cost_check = true; | |
161 } | |
162 } | |
163 | |
164 // line 2) | |
165 // no need to set State vector if our state is knownValid | |
166 const char *production = (validity_check == knownValid) ? dfa_production : dfa_production_set_valid; | |
167 fprintf(fp, "%s %s(%s, %s_rule, %s)", spaces, production, arrayIdx, rule, cost->as_string() ); | |
168 if( validity_check == knownValid ) { | |
169 if( cost_is_below_lower_bound ) { fprintf(fp, "\t // overwrites higher cost rule"); } | |
170 } | |
171 fprintf(fp, "\n"); | |
172 | |
173 // line 3) | |
174 if( cost_check || state_check ) { | |
175 fprintf(fp, "%s}\n", spaces); | |
176 } | |
177 | |
178 status.set_cost_bounds(arrayIdx, cost, state_check, cost_check); | |
179 | |
180 // Update ProductionState | |
181 if( validity_check != knownValid ) { | |
182 // set State vector if not previously known | |
183 status.set_valid(arrayIdx); | |
184 } | |
185 } | |
186 | |
187 | |
188 //---------------------------child_test---------------------------------------- | |
189 // Example: | |
190 // STATE__VALID_CHILD(_kids[0], FOO) && STATE__VALID_CHILD(_kids[1], BAR) | |
191 // Macro equivalent to: _kids[0]->valid(FOO) && _kids[1]->valid(BAR) | |
192 // | |
193 static void child_test(FILE *fp, MatchList &mList) { | |
194 if( mList._lchild ) // If left child, check it | |
195 fprintf(fp, "STATE__VALID_CHILD(_kids[0], %s)", ArchDesc::getMachOperEnum(mList._lchild)); | |
196 if( mList._lchild && mList._rchild ) // If both, add the "&&" | |
197 fprintf(fp, " && " ); | |
198 if( mList._rchild ) // If right child, check it | |
199 fprintf(fp, "STATE__VALID_CHILD(_kids[1], %s)", ArchDesc::getMachOperEnum(mList._rchild)); | |
200 } | |
201 | |
202 //---------------------------calc_cost----------------------------------------- | |
203 // Example: | |
204 // unsigned int c = _kids[0]->_cost[FOO] + _kids[1]->_cost[BAR] + 5; | |
205 // | |
206 Expr *ArchDesc::calc_cost(FILE *fp, const char *spaces, MatchList &mList, ProductionState &status) { | |
207 fprintf(fp, "%sunsigned int c = ", spaces); | |
208 Expr *c = new Expr("0"); | |
209 if (mList._lchild ) { // If left child, add it in | |
210 sprintf(Expr::buffer(), "_kids[0]->_cost[%s]", ArchDesc::getMachOperEnum(mList._lchild)); | |
211 c->add(Expr::buffer()); | |
212 } | |
213 if (mList._rchild) { // If right child, add it in | |
214 sprintf(Expr::buffer(), "_kids[1]->_cost[%s]", ArchDesc::getMachOperEnum(mList._rchild)); | |
215 c->add(Expr::buffer()); | |
216 } | |
217 // Add in cost of this rule | |
218 const char *mList_cost = mList.get_cost(); | |
219 c->add(mList_cost, *this); | |
220 | |
221 fprintf(fp, "%s;\n", c->as_string()); | |
222 c->set_external_name("c"); | |
223 return c; | |
224 } | |
225 | |
226 | |
227 //---------------------------gen_match----------------------------------------- | |
228 void ArchDesc::gen_match(FILE *fp, MatchList &mList, ProductionState &status, Dict &operands_chained_from) { | |
229 const char *spaces4 = " "; | |
230 const char *spaces6 = " "; | |
231 | |
232 fprintf(fp, "%s", spaces4); | |
233 // Only generate child tests if this is not a leaf node | |
234 bool has_child_constraints = mList._lchild || mList._rchild; | |
235 const char *predicate_test = mList.get_pred(); | |
236 if( has_child_constraints || predicate_test ) { | |
237 // Open the child-and-predicate-test braces | |
238 fprintf(fp, "if( "); | |
239 status.set_constraint(hasConstraint); | |
240 child_test(fp, mList); | |
241 // Only generate predicate test if one exists for this match | |
242 if( predicate_test ) { | |
243 if( has_child_constraints ) { fprintf(fp," &&\n"); } | |
244 fprintf(fp, "%s %s", spaces6, predicate_test); | |
245 } | |
246 // End of outer tests | |
247 fprintf(fp," ) "); | |
248 } else { | |
249 // No child or predicate test needed | |
250 status.set_constraint(noConstraint); | |
251 } | |
252 | |
253 // End of outer tests | |
254 fprintf(fp,"{\n"); | |
255 | |
256 // Calculate cost of this match | |
257 const Expr *cost = calc_cost(fp, spaces6, mList, status); | |
258 // Check against other match costs, and update cost & rule vectors | |
259 cost_check(fp, spaces6, ArchDesc::getMachOperEnum(mList._resultStr), cost, mList._opcode, status); | |
260 | |
261 // If this is a member of an operand class, update the class cost & rule | |
262 expand_opclass( fp, spaces6, cost, mList._resultStr, status); | |
263 | |
264 // Check if this rule should be used to generate the chains as well. | |
265 const char *rule = /* set rule to "Invalid" for internal operands */ | |
266 strcmp(mList._opcode,mList._resultStr) ? mList._opcode : "Invalid"; | |
267 | |
268 // If this rule produces an operand which has associated chain rules, | |
269 // update the operands with the chain rule + this rule cost & this rule. | |
270 chain_rule(fp, spaces6, mList._resultStr, cost, rule, operands_chained_from, status); | |
271 | |
272 // Close the child-and-predicate-test braces | |
273 fprintf(fp, " }\n"); | |
274 | |
275 } | |
276 | |
277 | |
278 //---------------------------expand_opclass------------------------------------ | |
279 // Chain from one result_type to all other members of its operand class | |
280 void ArchDesc::expand_opclass(FILE *fp, const char *indent, const Expr *cost, | |
281 const char *result_type, ProductionState &status) { | |
282 const Form *form = _globalNames[result_type]; | |
283 OperandForm *op = form ? form->is_operand() : NULL; | |
284 if( op && op->_classes.count() > 0 ) { | |
285 if( debug_output ) { fprintf(fp, "// expand operand classes for operand: %s \n", (char *)op->_ident ); } // %%%%% Explanation | |
286 // Iterate through all operand classes which include this operand | |
287 op->_classes.reset(); | |
288 const char *oclass; | |
289 // Expr *cCost = new Expr(cost); | |
290 while( (oclass = op->_classes.iter()) != NULL ) | |
291 // Check against other match costs, and update cost & rule vectors | |
292 cost_check(fp, indent, ArchDesc::getMachOperEnum(oclass), cost, result_type, status); | |
293 } | |
294 } | |
295 | |
296 //---------------------------chain_rule---------------------------------------- | |
297 // Starting at 'operand', check if we know how to automatically generate other results | |
298 void ArchDesc::chain_rule(FILE *fp, const char *indent, const char *operand, | |
299 const Expr *icost, const char *irule, Dict &operands_chained_from, ProductionState &status) { | |
300 | |
301 // Check if we have already generated chains from this starting point | |
302 if( operands_chained_from[operand] != NULL ) { | |
303 return; | |
304 } else { | |
305 operands_chained_from.Insert( operand, operand); | |
306 } | |
307 if( debug_output ) { fprintf(fp, "// chain rules starting from: %s and %s \n", (char *)operand, (char *)irule); } // %%%%% Explanation | |
308 | |
309 ChainList *lst = (ChainList *)_chainRules[operand]; | |
310 if (lst) { | |
311 // printf("\nChain from <%s> at cost #%s\n",operand, icost ? icost : "_"); | |
312 const char *result, *cost, *rule; | |
313 for(lst->reset(); (lst->iter(result,cost,rule)) == true; ) { | |
314 // Do not generate operands that are already available | |
315 if( operands_chained_from[result] != NULL ) { | |
316 continue; | |
317 } else { | |
318 // Compute the cost for previous match + chain_rule_cost | |
319 // total_cost = icost + cost; | |
320 Expr *total_cost = icost->clone(); // icost + cost | |
321 total_cost->add(cost, *this); | |
322 | |
323 // Check for transitive chain rules | |
324 Form *form = (Form *)_globalNames[rule]; | |
325 if ( ! form->is_instruction()) { | |
326 // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); | |
327 // Check against other match costs, and update cost & rule vectors | |
328 const char *reduce_rule = strcmp(irule,"Invalid") ? irule : rule; | |
329 cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, reduce_rule, status); | |
330 chain_rule(fp, indent, result, total_cost, irule, operands_chained_from, status); | |
331 } else { | |
332 // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule); | |
333 // Check against other match costs, and update cost & rule vectors | |
334 cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, rule, status); | |
335 chain_rule(fp, indent, result, total_cost, rule, operands_chained_from, status); | |
336 } | |
337 | |
338 // If this is a member of an operand class, update class cost & rule | |
339 expand_opclass( fp, indent, total_cost, result, status ); | |
340 } | |
341 } | |
342 } | |
343 } | |
344 | |
345 //---------------------------prune_matchlist----------------------------------- | |
346 // Check for duplicate entries in a matchlist, and prune out the higher cost | |
347 // entry. | |
348 void ArchDesc::prune_matchlist(Dict &minimize, MatchList &mlist) { | |
349 | |
350 } | |
351 | |
352 //---------------------------buildDFA------------------------------------------ | |
353 // DFA is a large switch with case statements for each ideal opcode encountered | |
354 // in any match rule in the ad file. Each case has a series of if's to handle | |
355 // the match or fail decisions. The matches test the cost function of that | |
356 // rule, and prune any cases which are higher cost for the same reduction. | |
357 // In order to generate the DFA we walk the table of ideal opcode/MatchList | |
358 // pairs generated by the ADLC front end to build the contents of the case | |
359 // statements (a series of if statements). | |
360 void ArchDesc::buildDFA(FILE* fp) { | |
361 int i; | |
362 // Remember operands that are the starting points for chain rules. | |
363 // Prevent cycles by checking if we have already generated chain. | |
364 Dict operands_chained_from(cmpstr, hashstr, Form::arena); | |
365 | |
366 // Hash inputs to match rules so that final DFA contains only one entry for | |
367 // each match pattern which is the low cost entry. | |
368 Dict minimize(cmpstr, hashstr, Form::arena); | |
369 | |
370 // Track status of dfa for each resulting production | |
371 // reset for each ideal root. | |
372 ProductionState status(Form::arena); | |
373 | |
374 // Output the start of the DFA method into the output file | |
375 | |
376 fprintf(fp, "\n"); | |
377 fprintf(fp, "//------------------------- Source -----------------------------------------\n"); | |
378 // Do not put random source code into the DFA. | |
379 // If there are constants which need sharing, put them in "source_hpp" forms. | |
380 // _source.output(fp); | |
381 fprintf(fp, "\n"); | |
382 fprintf(fp, "//------------------------- Attributes -------------------------------------\n"); | |
383 _attributes.output(fp); | |
384 fprintf(fp, "\n"); | |
385 fprintf(fp, "//------------------------- Macros -----------------------------------------\n"); | |
386 // #define DFA_PRODUCTION(result, rule, cost)\ | |
387 // _cost[ (result) ] = cost; _rule[ (result) ] = rule; | |
388 fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production); | |
389 fprintf(fp, " _cost[ (result) ] = cost; _rule[ (result) ] = rule;\n"); | |
390 fprintf(fp, "\n"); | |
391 | |
392 // #define DFA_PRODUCTION__SET_VALID(result, rule, cost)\ | |
393 // DFA_PRODUCTION( (result), (rule), (cost) ); STATE__SET_VALID( (result) ); | |
394 fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production_set_valid); | |
395 fprintf(fp, " %s( (result), (rule), (cost) ); STATE__SET_VALID( (result) );\n", dfa_production); | |
396 fprintf(fp, "\n"); | |
397 | |
398 fprintf(fp, "//------------------------- DFA --------------------------------------------\n"); | |
399 | |
400 fprintf(fp, | |
401 "// DFA is a large switch with case statements for each ideal opcode encountered\n" | |
402 "// in any match rule in the ad file. Each case has a series of if's to handle\n" | |
403 "// the match or fail decisions. The matches test the cost function of that\n" | |
404 "// rule, and prune any cases which are higher cost for the same reduction.\n" | |
405 "// In order to generate the DFA we walk the table of ideal opcode/MatchList\n" | |
406 "// pairs generated by the ADLC front end to build the contents of the case\n" | |
407 "// statements (a series of if statements).\n" | |
408 ); | |
409 fprintf(fp, "\n"); | |
410 fprintf(fp, "\n"); | |
411 if (_dfa_small) { | |
412 // Now build the individual routines just like the switch entries in large version | |
413 // Iterate over the table of MatchLists, start at first valid opcode of 1 | |
414 for (i = 1; i < _last_opcode; i++) { | |
415 if (_mlistab[i] == NULL) continue; | |
416 // Generate the routine header statement for this opcode | |
417 fprintf(fp, "void State::_sub_Op_%s(const Node *n){\n", NodeClassNames[i]); | |
418 // Generate body. Shared for both inline and out-of-line version | |
419 gen_dfa_state_body(fp, minimize, status, operands_chained_from, i); | |
420 // End of routine | |
421 fprintf(fp, "}\n"); | |
422 } | |
423 } | |
424 fprintf(fp, "bool State::DFA"); | |
425 fprintf(fp, "(int opcode, const Node *n) {\n"); | |
426 fprintf(fp, " switch(opcode) {\n"); | |
427 | |
428 // Iterate over the table of MatchLists, start at first valid opcode of 1 | |
429 for (i = 1; i < _last_opcode; i++) { | |
430 if (_mlistab[i] == NULL) continue; | |
431 // Generate the case statement for this opcode | |
432 if (_dfa_small) { | |
433 fprintf(fp, " case Op_%s: { _sub_Op_%s(n);\n", NodeClassNames[i], NodeClassNames[i]); | |
434 } else { | |
435 fprintf(fp, " case Op_%s: {\n", NodeClassNames[i]); | |
436 // Walk the list, compacting it | |
437 gen_dfa_state_body(fp, minimize, status, operands_chained_from, i); | |
438 } | |
439 // Print the "break" | |
440 fprintf(fp, " break;\n"); | |
441 fprintf(fp, " }\n"); | |
442 } | |
443 | |
444 // Generate the default case for switch(opcode) | |
445 fprintf(fp, " \n"); | |
446 fprintf(fp, " default:\n"); | |
447 fprintf(fp, " tty->print(\"Default case invoked for: \\n\");\n"); | |
448 fprintf(fp, " tty->print(\" opcode = %cd, \\\"%cs\\\"\\n\", opcode, NodeClassNames[opcode]);\n", '%', '%'); | |
449 fprintf(fp, " return false;\n"); | |
450 fprintf(fp, " }\n"); | |
451 | |
452 // Return status, indicating a successful match. | |
453 fprintf(fp, " return true;\n"); | |
454 // Generate the closing brace for method Matcher::DFA | |
455 fprintf(fp, "}\n"); | |
456 Expr::check_buffers(); | |
457 } | |
458 | |
459 | |
460 class dfa_shared_preds { | |
475
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
461 enum { count = 4 }; |
0 | 462 |
463 static bool _found[count]; | |
464 static const char* _type [count]; | |
465 static const char* _var [count]; | |
466 static const char* _pred [count]; | |
467 | |
468 static void check_index(int index) { assert( 0 <= index && index < count, "Invalid index"); } | |
469 | |
470 // Confirm that this is a separate sub-expression. | |
471 // Only need to catch common cases like " ... && shared ..." | |
472 // and avoid hazardous ones like "...->shared" | |
473 static bool valid_loc(char *pred, char *shared) { | |
474 // start of predicate is valid | |
475 if( shared == pred ) return true; | |
476 | |
477 // Check previous character and recurse if needed | |
478 char *prev = shared - 1; | |
479 char c = *prev; | |
480 switch( c ) { | |
481 case ' ': | |
475
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
482 case '\n': |
0 | 483 return dfa_shared_preds::valid_loc(pred, prev); |
484 case '!': | |
485 case '(': | |
486 case '<': | |
487 case '=': | |
488 return true; | |
475
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
489 case '"': // such as: #line 10 "myfile.ad"\n mypredicate |
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
490 return true; |
0 | 491 case '|': |
492 if( prev != pred && *(prev-1) == '|' ) return true; | |
493 case '&': | |
494 if( prev != pred && *(prev-1) == '&' ) return true; | |
495 default: | |
496 return false; | |
497 } | |
498 | |
499 return false; | |
500 } | |
501 | |
502 public: | |
503 | |
504 static bool found(int index){ check_index(index); return _found[index]; } | |
505 static void set_found(int index, bool val) { check_index(index); _found[index] = val; } | |
506 static void reset_found() { | |
507 for( int i = 0; i < count; ++i ) { _found[i] = false; } | |
508 }; | |
509 | |
510 static const char* type(int index) { check_index(index); return _type[index]; } | |
511 static const char* var (int index) { check_index(index); return _var [index]; } | |
512 static const char* pred(int index) { check_index(index); return _pred[index]; } | |
513 | |
514 // Check each predicate in the MatchList for common sub-expressions | |
515 static void cse_matchlist(MatchList *matchList) { | |
516 for( MatchList *mList = matchList; mList != NULL; mList = mList->get_next() ) { | |
517 Predicate* predicate = mList->get_pred_obj(); | |
518 char* pred = mList->get_pred(); | |
519 if( pred != NULL ) { | |
520 for(int index = 0; index < count; ++index ) { | |
521 const char *shared_pred = dfa_shared_preds::pred(index); | |
522 const char *shared_pred_var = dfa_shared_preds::var(index); | |
523 bool result = dfa_shared_preds::cse_predicate(predicate, shared_pred, shared_pred_var); | |
524 if( result ) dfa_shared_preds::set_found(index, true); | |
525 } | |
526 } | |
527 } | |
528 } | |
529 | |
530 // If the Predicate contains a common sub-expression, replace the Predicate's | |
531 // string with one that uses the variable name. | |
532 static bool cse_predicate(Predicate* predicate, const char *shared_pred, const char *shared_pred_var) { | |
533 bool result = false; | |
534 char *pred = predicate->_pred; | |
535 if( pred != NULL ) { | |
536 char *new_pred = pred; | |
537 for( char *shared_pred_loc = strstr(new_pred, shared_pred); | |
538 shared_pred_loc != NULL && dfa_shared_preds::valid_loc(new_pred,shared_pred_loc); | |
539 shared_pred_loc = strstr(new_pred, shared_pred) ) { | |
540 // Do not modify the original predicate string, it is shared | |
541 if( new_pred == pred ) { | |
542 new_pred = strdup(pred); | |
543 shared_pred_loc = strstr(new_pred, shared_pred); | |
544 } | |
545 // Replace shared_pred with variable name | |
546 strncpy(shared_pred_loc, shared_pred_var, strlen(shared_pred_var)); | |
547 } | |
548 // Install new predicate | |
549 if( new_pred != pred ) { | |
550 predicate->_pred = new_pred; | |
551 result = true; | |
552 } | |
553 } | |
554 return result; | |
555 } | |
556 | |
557 // Output the hoisted common sub-expression if we found it in predicates | |
558 static void generate_cse(FILE *fp) { | |
559 for(int j = 0; j < count; ++j ) { | |
560 if( dfa_shared_preds::found(j) ) { | |
561 const char *shared_pred_type = dfa_shared_preds::type(j); | |
562 const char *shared_pred_var = dfa_shared_preds::var(j); | |
563 const char *shared_pred = dfa_shared_preds::pred(j); | |
564 fprintf(fp, " %s %s = %s;\n", shared_pred_type, shared_pred_var, shared_pred); | |
565 } | |
566 } | |
567 } | |
568 }; | |
569 // shared predicates, _var and _pred entry should be the same length | |
475
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
570 bool dfa_shared_preds::_found[dfa_shared_preds::count] |
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
571 = { false, false, false, false }; |
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
572 const char* dfa_shared_preds::_type[dfa_shared_preds::count] |
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
573 = { "int", "jlong", "intptr_t", "bool" }; |
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
574 const char* dfa_shared_preds::_var [dfa_shared_preds::count] |
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
575 = { "_n_get_int__", "_n_get_long__", "_n_get_intptr_t__", "Compile__current____select_24_bit_instr__" }; |
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
576 const char* dfa_shared_preds::_pred[dfa_shared_preds::count] |
284d0af00d53
6771309: debugging AD files is difficult without #line directives in generated code
jrose
parents:
0
diff
changeset
|
577 = { "n->get_int()", "n->get_long()", "n->get_intptr_t()", "Compile::current()->select_24_bit_instr()" }; |
0 | 578 |
579 | |
580 void ArchDesc::gen_dfa_state_body(FILE* fp, Dict &minimize, ProductionState &status, Dict &operands_chained_from, int i) { | |
581 // Start the body of each Op_XXX sub-dfa with a clean state. | |
582 status.initialize(); | |
583 | |
584 // Walk the list, compacting it | |
585 MatchList* mList = _mlistab[i]; | |
586 do { | |
587 // Hash each entry using inputs as key and pointer as data. | |
588 // If there is already an entry, keep the one with lower cost, and | |
589 // remove the other one from the list. | |
590 prune_matchlist(minimize, *mList); | |
591 // Iterate | |
592 mList = mList->get_next(); | |
593 } while(mList != NULL); | |
594 | |
595 // Hoist previously specified common sub-expressions out of predicates | |
596 dfa_shared_preds::reset_found(); | |
597 dfa_shared_preds::cse_matchlist(_mlistab[i]); | |
598 dfa_shared_preds::generate_cse(fp); | |
599 | |
600 mList = _mlistab[i]; | |
601 | |
602 // Walk the list again, generating code | |
603 do { | |
604 // Each match can generate its own chains | |
605 operands_chained_from.Clear(); | |
606 gen_match(fp, *mList, status, operands_chained_from); | |
607 mList = mList->get_next(); | |
608 } while(mList != NULL); | |
609 // Fill in any chain rules which add instructions | |
610 // These can generate their own chains as well. | |
611 operands_chained_from.Clear(); // | |
612 if( debug_output1 ) { fprintf(fp, "// top level chain rules for: %s \n", (char *)NodeClassNames[i]); } // %%%%% Explanation | |
613 const Expr *zeroCost = new Expr("0"); | |
614 chain_rule(fp, " ", (char *)NodeClassNames[i], zeroCost, "Invalid", | |
615 operands_chained_from, status); | |
616 } | |
617 | |
618 | |
619 | |
620 //------------------------------Expr------------------------------------------ | |
621 Expr *Expr::_unknown_expr = NULL; | |
622 char Expr::string_buffer[STRING_BUFFER_LENGTH]; | |
623 char Expr::external_buffer[STRING_BUFFER_LENGTH]; | |
624 bool Expr::_init_buffers = Expr::init_buffers(); | |
625 | |
626 Expr::Expr() { | |
627 _external_name = NULL; | |
628 _expr = "Invalid_Expr"; | |
629 _min_value = Expr::Max; | |
630 _max_value = Expr::Zero; | |
631 } | |
632 Expr::Expr(const char *cost) { | |
633 _external_name = NULL; | |
634 | |
635 int intval = 0; | |
636 if( cost == NULL ) { | |
637 _expr = "0"; | |
638 _min_value = Expr::Zero; | |
639 _max_value = Expr::Zero; | |
640 } | |
641 else if( ADLParser::is_int_token(cost, intval) ) { | |
642 _expr = cost; | |
643 _min_value = intval; | |
644 _max_value = intval; | |
645 } | |
646 else { | |
647 assert( strcmp(cost,"0") != 0, "Recognize string zero as an int"); | |
648 _expr = cost; | |
649 _min_value = Expr::Zero; | |
650 _max_value = Expr::Max; | |
651 } | |
652 } | |
653 | |
654 Expr::Expr(const char *name, const char *expression, int min_value, int max_value) { | |
655 _external_name = name; | |
656 _expr = expression ? expression : name; | |
657 _min_value = min_value; | |
658 _max_value = max_value; | |
659 assert(_min_value >= 0 && _min_value <= Expr::Max, "value out of range"); | |
660 assert(_max_value >= 0 && _max_value <= Expr::Max, "value out of range"); | |
661 } | |
662 | |
663 Expr *Expr::clone() const { | |
664 Expr *cost = new Expr(); | |
665 cost->_external_name = _external_name; | |
666 cost->_expr = _expr; | |
667 cost->_min_value = _min_value; | |
668 cost->_max_value = _max_value; | |
669 | |
670 return cost; | |
671 } | |
672 | |
673 void Expr::add(const Expr *c) { | |
674 // Do not update fields until all computation is complete | |
675 const char *external = compute_external(this, c); | |
676 const char *expr = compute_expr(this, c); | |
677 int min_value = compute_min (this, c); | |
678 int max_value = compute_max (this, c); | |
679 | |
680 _external_name = external; | |
681 _expr = expr; | |
682 _min_value = min_value; | |
683 _max_value = max_value; | |
684 } | |
685 | |
686 void Expr::add(const char *c) { | |
687 Expr *cost = new Expr(c); | |
688 add(cost); | |
689 } | |
690 | |
691 void Expr::add(const char *c, ArchDesc &AD) { | |
692 const Expr *e = AD.globalDefs()[c]; | |
693 if( e != NULL ) { | |
694 // use the value of 'c' defined in <arch>.ad | |
695 add(e); | |
696 } else { | |
697 Expr *cost = new Expr(c); | |
698 add(cost); | |
699 } | |
700 } | |
701 | |
702 const char *Expr::compute_external(const Expr *c1, const Expr *c2) { | |
703 const char * result = NULL; | |
704 | |
705 // Preserve use of external name which has a zero value | |
706 if( c1->_external_name != NULL ) { | |
707 sprintf( string_buffer, "%s", c1->as_string()); | |
708 if( !c2->is_zero() ) { | |
709 strcat( string_buffer, "+"); | |
710 strcat( string_buffer, c2->as_string()); | |
711 } | |
712 result = strdup(string_buffer); | |
713 } | |
714 else if( c2->_external_name != NULL ) { | |
715 if( !c1->is_zero() ) { | |
716 sprintf( string_buffer, "%s", c1->as_string()); | |
717 strcat( string_buffer, " + "); | |
718 } else { | |
719 string_buffer[0] = '\0'; | |
720 } | |
721 strcat( string_buffer, c2->_external_name ); | |
722 result = strdup(string_buffer); | |
723 } | |
724 return result; | |
725 } | |
726 | |
727 const char *Expr::compute_expr(const Expr *c1, const Expr *c2) { | |
728 if( !c1->is_zero() ) { | |
729 sprintf( string_buffer, "%s", c1->_expr); | |
730 if( !c2->is_zero() ) { | |
731 strcat( string_buffer, "+"); | |
732 strcat( string_buffer, c2->_expr); | |
733 } | |
734 } | |
735 else if( !c2->is_zero() ) { | |
736 sprintf( string_buffer, "%s", c2->_expr); | |
737 } | |
738 else { | |
739 sprintf( string_buffer, "0"); | |
740 } | |
741 char *cost = strdup(string_buffer); | |
742 | |
743 return cost; | |
744 } | |
745 | |
746 int Expr::compute_min(const Expr *c1, const Expr *c2) { | |
747 int result = c1->_min_value + c2->_min_value; | |
748 assert( result >= 0, "Invalid cost computation"); | |
749 | |
750 return result; | |
751 } | |
752 | |
753 int Expr::compute_max(const Expr *c1, const Expr *c2) { | |
754 int result = c1->_max_value + c2->_max_value; | |
755 if( result < 0 ) { // check for overflow | |
756 result = Expr::Max; | |
757 } | |
758 | |
759 return result; | |
760 } | |
761 | |
762 void Expr::print() const { | |
763 if( _external_name != NULL ) { | |
764 printf(" %s == (%s) === [%d, %d]\n", _external_name, _expr, _min_value, _max_value); | |
765 } else { | |
766 printf(" %s === [%d, %d]\n", _expr, _min_value, _max_value); | |
767 } | |
768 } | |
769 | |
770 void Expr::print_define(FILE *fp) const { | |
771 assert( _external_name != NULL, "definition does not have a name"); | |
772 assert( _min_value == _max_value, "Expect user definitions to have constant value"); | |
773 fprintf(fp, "#define %s (%s) \n", _external_name, _expr); | |
774 fprintf(fp, "// value == %d \n", _min_value); | |
775 } | |
776 | |
777 void Expr::print_assert(FILE *fp) const { | |
778 assert( _external_name != NULL, "definition does not have a name"); | |
779 assert( _min_value == _max_value, "Expect user definitions to have constant value"); | |
780 fprintf(fp, " assert( %s == %d, \"Expect (%s) to equal %d\");\n", _external_name, _min_value, _expr, _min_value); | |
781 } | |
782 | |
783 Expr *Expr::get_unknown() { | |
784 if( Expr::_unknown_expr == NULL ) { | |
785 Expr::_unknown_expr = new Expr(); | |
786 } | |
787 | |
788 return Expr::_unknown_expr; | |
789 } | |
790 | |
791 bool Expr::init_buffers() { | |
792 // Fill buffers with 0 | |
793 for( int i = 0; i < STRING_BUFFER_LENGTH; ++i ) { | |
794 external_buffer[i] = '\0'; | |
795 string_buffer[i] = '\0'; | |
796 } | |
797 | |
798 return true; | |
799 } | |
800 | |
801 bool Expr::check_buffers() { | |
802 // returns 'true' if buffer use may have overflowed | |
803 bool ok = true; | |
804 for( int i = STRING_BUFFER_LENGTH - 100; i < STRING_BUFFER_LENGTH; ++i) { | |
805 if( external_buffer[i] != '\0' || string_buffer[i] != '\0' ) { | |
806 ok = false; | |
807 assert( false, "Expr:: Buffer overflow"); | |
808 } | |
809 } | |
810 | |
811 return ok; | |
812 } | |
813 | |
814 | |
815 //------------------------------ExprDict--------------------------------------- | |
816 // Constructor | |
817 ExprDict::ExprDict( CmpKey cmp, Hash hash, Arena *arena ) | |
818 : _expr(cmp, hash, arena), _defines() { | |
819 } | |
820 ExprDict::~ExprDict() { | |
821 } | |
822 | |
823 // Return # of name-Expr pairs in dict | |
824 int ExprDict::Size(void) const { | |
825 return _expr.Size(); | |
826 } | |
827 | |
828 // define inserts the given key-value pair into the dictionary, | |
829 // and records the name in order for later output, ... | |
830 const Expr *ExprDict::define(const char *name, Expr *expr) { | |
831 const Expr *old_expr = (*this)[name]; | |
832 assert(old_expr == NULL, "Implementation does not support redefinition"); | |
833 | |
834 _expr.Insert(name, expr); | |
835 _defines.addName(name); | |
836 | |
837 return old_expr; | |
838 } | |
839 | |
840 // Insert inserts the given key-value pair into the dictionary. The prior | |
841 // value of the key is returned; NULL if the key was not previously defined. | |
842 const Expr *ExprDict::Insert(const char *name, Expr *expr) { | |
843 return (Expr*)_expr.Insert((void*)name, (void*)expr); | |
844 } | |
845 | |
846 // Finds the value of a given key; or NULL if not found. | |
847 // The dictionary is NOT changed. | |
848 const Expr *ExprDict::operator [](const char *name) const { | |
849 return (Expr*)_expr[name]; | |
850 } | |
851 | |
852 void ExprDict::print_defines(FILE *fp) { | |
853 fprintf(fp, "\n"); | |
854 const char *name = NULL; | |
855 for( _defines.reset(); (name = _defines.iter()) != NULL; ) { | |
856 const Expr *expr = (const Expr*)_expr[name]; | |
857 assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"); | |
858 expr->print_define(fp); | |
859 } | |
860 } | |
861 void ExprDict::print_asserts(FILE *fp) { | |
862 fprintf(fp, "\n"); | |
863 fprintf(fp, " // Following assertions generated from definition section\n"); | |
864 const char *name = NULL; | |
865 for( _defines.reset(); (name = _defines.iter()) != NULL; ) { | |
866 const Expr *expr = (const Expr*)_expr[name]; | |
867 assert( expr != NULL, "name in ExprDict without matching Expr in dictionary"); | |
868 expr->print_assert(fp); | |
869 } | |
870 } | |
871 | |
872 // Print out the dictionary contents as key-value pairs | |
603
dbbe28fc66b5
6778669: Patch from Red Hat -- fixes compilation errors
twisti
parents:
475
diff
changeset
|
873 static void dumpekey(const void* key) { fprintf(stdout, "%s", (char*) key); } |
0 | 874 static void dumpexpr(const void* expr) { fflush(stdout); ((Expr*)expr)->print(); } |
875 | |
876 void ExprDict::dump() { | |
877 _expr.print(dumpekey, dumpexpr); | |
878 } | |
879 | |
880 | |
881 //------------------------------ExprDict::private------------------------------ | |
882 // Disable public use of constructor, copy-ctor, operator =, operator == | |
883 ExprDict::ExprDict( ) : _expr(cmpkey,hashkey), _defines() { | |
884 assert( false, "NotImplemented"); | |
885 } | |
886 ExprDict::ExprDict( const ExprDict & ) : _expr(cmpkey,hashkey), _defines() { | |
887 assert( false, "NotImplemented"); | |
888 } | |
889 ExprDict &ExprDict::operator =( const ExprDict &rhs) { | |
890 assert( false, "NotImplemented"); | |
891 _expr = rhs._expr; | |
892 return *this; | |
893 } | |
894 // == compares two dictionaries; they must have the same keys (their keys | |
895 // must match using CmpKey) and they must have the same values (pointer | |
896 // comparison). If so 1 is returned, if not 0 is returned. | |
897 bool ExprDict::operator ==(const ExprDict &d) const { | |
898 assert( false, "NotImplemented"); | |
899 return false; | |
900 } | |
901 | |
902 | |
903 //------------------------------Production------------------------------------- | |
904 Production::Production(const char *result, const char *constraint, const char *valid) { | |
905 initialize(); | |
906 _result = result; | |
907 _constraint = constraint; | |
908 _valid = valid; | |
909 } | |
910 | |
911 void Production::initialize() { | |
912 _result = NULL; | |
913 _constraint = NULL; | |
914 _valid = knownInvalid; | |
915 _cost_lb = Expr::get_unknown(); | |
916 _cost_ub = Expr::get_unknown(); | |
917 } | |
918 | |
919 void Production::print() { | |
920 printf("%s", (_result == NULL ? "NULL" : _result ) ); | |
921 printf("%s", (_constraint == NULL ? "NULL" : _constraint ) ); | |
922 printf("%s", (_valid == NULL ? "NULL" : _valid ) ); | |
923 _cost_lb->print(); | |
924 _cost_ub->print(); | |
925 } | |
926 | |
927 | |
928 //------------------------------ProductionState-------------------------------- | |
929 void ProductionState::initialize() { | |
930 _constraint = noConstraint; | |
931 | |
932 // reset each Production currently in the dictionary | |
933 DictI iter( &_production ); | |
934 const void *x, *y = NULL; | |
935 for( ; iter.test(); ++iter) { | |
936 x = iter._key; | |
937 y = iter._value; | |
938 Production *p = (Production*)y; | |
939 if( p != NULL ) { | |
940 p->initialize(); | |
941 } | |
942 } | |
943 } | |
944 | |
945 Production *ProductionState::getProduction(const char *result) { | |
946 Production *p = (Production *)_production[result]; | |
947 if( p == NULL ) { | |
948 p = new Production(result, _constraint, knownInvalid); | |
949 _production.Insert(result, p); | |
950 } | |
951 | |
952 return p; | |
953 } | |
954 | |
955 void ProductionState::set_constraint(const char *constraint) { | |
956 _constraint = constraint; | |
957 } | |
958 | |
959 const char *ProductionState::valid(const char *result) { | |
960 return getProduction(result)->valid(); | |
961 } | |
962 | |
963 void ProductionState::set_valid(const char *result) { | |
964 Production *p = getProduction(result); | |
965 | |
966 // Update valid as allowed by current constraints | |
967 if( _constraint == noConstraint ) { | |
968 p->_valid = knownValid; | |
969 } else { | |
970 if( p->_valid != knownValid ) { | |
971 p->_valid = unknownValid; | |
972 } | |
973 } | |
974 } | |
975 | |
976 Expr *ProductionState::cost_lb(const char *result) { | |
977 return getProduction(result)->cost_lb(); | |
978 } | |
979 | |
980 Expr *ProductionState::cost_ub(const char *result) { | |
981 return getProduction(result)->cost_ub(); | |
982 } | |
983 | |
984 void ProductionState::set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check) { | |
985 Production *p = getProduction(result); | |
986 | |
987 if( p->_valid == knownInvalid ) { | |
988 // Our cost bounds are not unknown, just not defined. | |
989 p->_cost_lb = cost->clone(); | |
990 p->_cost_ub = cost->clone(); | |
991 } else if (has_state_check || _constraint != noConstraint) { | |
992 // The production is protected by a condition, so | |
993 // the cost bounds may expand. | |
994 // _cost_lb = min(cost, _cost_lb) | |
995 if( cost->less_than_or_equal(p->_cost_lb) ) { | |
996 p->_cost_lb = cost->clone(); | |
997 } | |
998 // _cost_ub = max(cost, _cost_ub) | |
999 if( p->_cost_ub->less_than_or_equal(cost) ) { | |
1000 p->_cost_ub = cost->clone(); | |
1001 } | |
1002 } else if (has_cost_check) { | |
1003 // The production has no condition check, but does | |
1004 // have a cost check that could reduce the upper | |
1005 // and/or lower bound. | |
1006 // _cost_lb = min(cost, _cost_lb) | |
1007 if( cost->less_than_or_equal(p->_cost_lb) ) { | |
1008 p->_cost_lb = cost->clone(); | |
1009 } | |
1010 // _cost_ub = min(cost, _cost_ub) | |
1011 if( cost->less_than_or_equal(p->_cost_ub) ) { | |
1012 p->_cost_ub = cost->clone(); | |
1013 } | |
1014 } else { | |
1015 // The costs are unconditionally set. | |
1016 p->_cost_lb = cost->clone(); | |
1017 p->_cost_ub = cost->clone(); | |
1018 } | |
1019 | |
1020 } | |
1021 | |
1022 // Print out the dictionary contents as key-value pairs | |
603
dbbe28fc66b5
6778669: Patch from Red Hat -- fixes compilation errors
twisti
parents:
475
diff
changeset
|
1023 static void print_key (const void* key) { fprintf(stdout, "%s", (char*) key); } |
0 | 1024 static void print_production(const void* production) { fflush(stdout); ((Production*)production)->print(); } |
1025 | |
1026 void ProductionState::print() { | |
1027 _production.print(print_key, print_production); | |
1028 } |