1 /*
2 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
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 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
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);
~Production()61 ~Production() {};
62
63 void initialize(); // reset to be an empty container
64
valid() const65 const char *valid() const { return _valid; }
cost_lb() const66 Expr *cost_lb() const { return (Expr *)_cost_lb; }
cost_ub() const67 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.
ProductionState(Arena * arena)83 ProductionState(Arena *arena) : _production(cmpstr, hashstr, arena) { initialize(); };
~ProductionState()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, ...
ProductionState()106 ProductionState( ) : _production(cmpstr, hashstr, Form::arena) { assert( false, "NotImplemented"); };
ProductionState(const ProductionState &)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 //
cost_check(FILE * fp,const char * spaces,const char * arrayIdx,const Expr * cost,const char * rule,ProductionState & status)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 //
child_test(FILE * fp,MatchList & mList)193 static void child_test(FILE *fp, MatchList &mList) {
194 if (mList._lchild) { // If left child, check it
195 const char* lchild_to_upper = ArchDesc::getMachOperEnum(mList._lchild);
196 fprintf(fp, "STATE__VALID_CHILD(_kids[0], %s)", lchild_to_upper);
197 delete[] lchild_to_upper;
198 }
199 if (mList._lchild && mList._rchild) { // If both, add the "&&"
200 fprintf(fp, " && ");
201 }
202 if (mList._rchild) { // If right child, check it
203 const char* rchild_to_upper = ArchDesc::getMachOperEnum(mList._rchild);
204 fprintf(fp, "STATE__VALID_CHILD(_kids[1], %s)", rchild_to_upper);
205 delete[] rchild_to_upper;
206 }
207 }
208
209 //---------------------------calc_cost-----------------------------------------
210 // Example:
211 // unsigned int c = _kids[0]->_cost[FOO] + _kids[1]->_cost[BAR] + 5;
212 //
calc_cost(FILE * fp,const char * spaces,MatchList & mList,ProductionState & status)213 Expr *ArchDesc::calc_cost(FILE *fp, const char *spaces, MatchList &mList, ProductionState &status) {
214 fprintf(fp, "%sunsigned int c = ", spaces);
215 Expr *c = new Expr("0");
216 if (mList._lchild) { // If left child, add it in
217 const char* lchild_to_upper = ArchDesc::getMachOperEnum(mList._lchild);
218 sprintf(Expr::buffer(), "_kids[0]->_cost[%s]", lchild_to_upper);
219 c->add(Expr::buffer());
220 delete[] lchild_to_upper;
221 }
222 if (mList._rchild) { // If right child, add it in
223 const char* rchild_to_upper = ArchDesc::getMachOperEnum(mList._rchild);
224 sprintf(Expr::buffer(), "_kids[1]->_cost[%s]", rchild_to_upper);
225 c->add(Expr::buffer());
226 delete[] rchild_to_upper;
227 }
228 // Add in cost of this rule
229 const char *mList_cost = mList.get_cost();
230 c->add(mList_cost, *this);
231
232 fprintf(fp, "%s;\n", c->as_string());
233 c->set_external_name("c");
234 return c;
235 }
236
237
238 //---------------------------gen_match-----------------------------------------
gen_match(FILE * fp,MatchList & mList,ProductionState & status,Dict & operands_chained_from)239 void ArchDesc::gen_match(FILE *fp, MatchList &mList, ProductionState &status, Dict &operands_chained_from) {
240 const char *spaces4 = " ";
241 const char *spaces6 = " ";
242
243 fprintf(fp, "%s", spaces4);
244 // Only generate child tests if this is not a leaf node
245 bool has_child_constraints = mList._lchild || mList._rchild;
246 const char *predicate_test = mList.get_pred();
247 if (has_child_constraints || predicate_test) {
248 // Open the child-and-predicate-test braces
249 fprintf(fp, "if( ");
250 status.set_constraint(hasConstraint);
251 child_test(fp, mList);
252 // Only generate predicate test if one exists for this match
253 if (predicate_test) {
254 if (has_child_constraints) {
255 fprintf(fp," &&\n");
256 }
257 fprintf(fp, "%s %s", spaces6, predicate_test);
258 }
259 // End of outer tests
260 fprintf(fp," ) ");
261 } else {
262 // No child or predicate test needed
263 status.set_constraint(noConstraint);
264 }
265
266 // End of outer tests
267 fprintf(fp,"{\n");
268
269 // Calculate cost of this match
270 const Expr *cost = calc_cost(fp, spaces6, mList, status);
271 // Check against other match costs, and update cost & rule vectors
272 cost_check(fp, spaces6, ArchDesc::getMachOperEnum(mList._resultStr), cost, mList._opcode, status);
273
274 // If this is a member of an operand class, update the class cost & rule
275 expand_opclass( fp, spaces6, cost, mList._resultStr, status);
276
277 // Check if this rule should be used to generate the chains as well.
278 const char *rule = /* set rule to "Invalid" for internal operands */
279 strcmp(mList._opcode,mList._resultStr) ? mList._opcode : "Invalid";
280
281 // If this rule produces an operand which has associated chain rules,
282 // update the operands with the chain rule + this rule cost & this rule.
283 chain_rule(fp, spaces6, mList._resultStr, cost, rule, operands_chained_from, status);
284
285 // Close the child-and-predicate-test braces
286 fprintf(fp, " }\n");
287
288 }
289
290
291 //---------------------------expand_opclass------------------------------------
292 // Chain from one result_type to all other members of its operand class
expand_opclass(FILE * fp,const char * indent,const Expr * cost,const char * result_type,ProductionState & status)293 void ArchDesc::expand_opclass(FILE *fp, const char *indent, const Expr *cost,
294 const char *result_type, ProductionState &status) {
295 const Form *form = _globalNames[result_type];
296 OperandForm *op = form ? form->is_operand() : NULL;
297 if( op && op->_classes.count() > 0 ) {
298 if( debug_output ) { fprintf(fp, "// expand operand classes for operand: %s \n", (char *)op->_ident ); } // %%%%% Explanation
299 // Iterate through all operand classes which include this operand
300 op->_classes.reset();
301 const char *oclass;
302 // Expr *cCost = new Expr(cost);
303 while( (oclass = op->_classes.iter()) != NULL )
304 // Check against other match costs, and update cost & rule vectors
305 cost_check(fp, indent, ArchDesc::getMachOperEnum(oclass), cost, result_type, status);
306 }
307 }
308
309 //---------------------------chain_rule----------------------------------------
310 // Starting at 'operand', check if we know how to automatically generate other results
chain_rule(FILE * fp,const char * indent,const char * operand,const Expr * icost,const char * irule,Dict & operands_chained_from,ProductionState & status)311 void ArchDesc::chain_rule(FILE *fp, const char *indent, const char *operand,
312 const Expr *icost, const char *irule, Dict &operands_chained_from, ProductionState &status) {
313
314 // Check if we have already generated chains from this starting point
315 if( operands_chained_from[operand] != NULL ) {
316 return;
317 } else {
318 operands_chained_from.Insert( operand, operand);
319 }
320 if( debug_output ) { fprintf(fp, "// chain rules starting from: %s and %s \n", (char *)operand, (char *)irule); } // %%%%% Explanation
321
322 ChainList *lst = (ChainList *)_chainRules[operand];
323 if (lst) {
324 // printf("\nChain from <%s> at cost #%s\n",operand, icost ? icost : "_");
325 const char *result, *cost, *rule;
326 for(lst->reset(); (lst->iter(result,cost,rule)) == true; ) {
327 // Do not generate operands that are already available
328 if( operands_chained_from[result] != NULL ) {
329 continue;
330 } else {
331 // Compute the cost for previous match + chain_rule_cost
332 // total_cost = icost + cost;
333 Expr *total_cost = icost->clone(); // icost + cost
334 total_cost->add(cost, *this);
335
336 // Check for transitive chain rules
337 Form *form = (Form *)_globalNames[rule];
338 if ( ! form->is_instruction()) {
339 // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule);
340 // Check against other match costs, and update cost & rule vectors
341 const char *reduce_rule = strcmp(irule,"Invalid") ? irule : rule;
342 cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, reduce_rule, status);
343 chain_rule(fp, indent, result, total_cost, irule, operands_chained_from, status);
344 } else {
345 // printf(" result=%s cost=%s rule=%s\n", result, total_cost, rule);
346 // Check against other match costs, and update cost & rule vectors
347 cost_check(fp, indent, ArchDesc::getMachOperEnum(result), total_cost, rule, status);
348 chain_rule(fp, indent, result, total_cost, rule, operands_chained_from, status);
349 }
350
351 // If this is a member of an operand class, update class cost & rule
352 expand_opclass( fp, indent, total_cost, result, status );
353 }
354 }
355 }
356 }
357
358 //---------------------------prune_matchlist-----------------------------------
359 // Check for duplicate entries in a matchlist, and prune out the higher cost
360 // entry.
prune_matchlist(Dict & minimize,MatchList & mlist)361 void ArchDesc::prune_matchlist(Dict &minimize, MatchList &mlist) {
362
363 }
364
365 //---------------------------buildDFA------------------------------------------
366 // DFA is a large switch with case statements for each ideal opcode encountered
367 // in any match rule in the ad file. Each case has a series of if's to handle
368 // the match or fail decisions. The matches test the cost function of that
369 // rule, and prune any cases which are higher cost for the same reduction.
370 // In order to generate the DFA we walk the table of ideal opcode/MatchList
371 // pairs generated by the ADLC front end to build the contents of the case
372 // statements (a series of if statements).
buildDFA(FILE * fp)373 void ArchDesc::buildDFA(FILE* fp) {
374 int i;
375 // Remember operands that are the starting points for chain rules.
376 // Prevent cycles by checking if we have already generated chain.
377 Dict operands_chained_from(cmpstr, hashstr, Form::arena);
378
379 // Hash inputs to match rules so that final DFA contains only one entry for
380 // each match pattern which is the low cost entry.
381 Dict minimize(cmpstr, hashstr, Form::arena);
382
383 // Track status of dfa for each resulting production
384 // reset for each ideal root.
385 ProductionState status(Form::arena);
386
387 // Output the start of the DFA method into the output file
388
389 fprintf(fp, "\n");
390 fprintf(fp, "//------------------------- Source -----------------------------------------\n");
391 // Do not put random source code into the DFA.
392 // If there are constants which need sharing, put them in "source_hpp" forms.
393 // _source.output(fp);
394 fprintf(fp, "\n");
395 fprintf(fp, "//------------------------- Attributes -------------------------------------\n");
396 _attributes.output(fp);
397 fprintf(fp, "\n");
398 fprintf(fp, "//------------------------- Macros -----------------------------------------\n");
399 // #define DFA_PRODUCTION(result, rule, cost)\
400 // _cost[ (result) ] = cost; _rule[ (result) ] = rule;
401 fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production);
402 fprintf(fp, " _cost[ (result) ] = cost; _rule[ (result) ] = rule;\n");
403 fprintf(fp, "\n");
404
405 // #define DFA_PRODUCTION__SET_VALID(result, rule, cost)\
406 // DFA_PRODUCTION( (result), (rule), (cost) ); STATE__SET_VALID( (result) );
407 fprintf(fp, "#define %s(result, rule, cost)\\\n", dfa_production_set_valid);
408 fprintf(fp, " %s( (result), (rule), (cost) ); STATE__SET_VALID( (result) );\n", dfa_production);
409 fprintf(fp, "\n");
410
411 fprintf(fp, "//------------------------- DFA --------------------------------------------\n");
412
413 fprintf(fp,
414 "// DFA is a large switch with case statements for each ideal opcode encountered\n"
415 "// in any match rule in the ad file. Each case has a series of if's to handle\n"
416 "// the match or fail decisions. The matches test the cost function of that\n"
417 "// rule, and prune any cases which are higher cost for the same reduction.\n"
418 "// In order to generate the DFA we walk the table of ideal opcode/MatchList\n"
419 "// pairs generated by the ADLC front end to build the contents of the case\n"
420 "// statements (a series of if statements).\n"
421 );
422 fprintf(fp, "\n");
423 fprintf(fp, "\n");
424 if (_dfa_small) {
425 // Now build the individual routines just like the switch entries in large version
426 // Iterate over the table of MatchLists, start at first valid opcode of 1
427 for (i = 1; i < _last_opcode; i++) {
428 if (_mlistab[i] == NULL) continue;
429 // Generate the routine header statement for this opcode
430 fprintf(fp, "void State::_sub_Op_%s(const Node *n){\n", NodeClassNames[i]);
431 // Generate body. Shared for both inline and out-of-line version
432 gen_dfa_state_body(fp, minimize, status, operands_chained_from, i);
433 // End of routine
434 fprintf(fp, "}\n");
435 }
436 }
437 fprintf(fp, "bool State::DFA");
438 fprintf(fp, "(int opcode, const Node *n) {\n");
439 fprintf(fp, " switch(opcode) {\n");
440
441 // Iterate over the table of MatchLists, start at first valid opcode of 1
442 for (i = 1; i < _last_opcode; i++) {
443 if (_mlistab[i] == NULL) continue;
444 // Generate the case statement for this opcode
445 if (_dfa_small) {
446 fprintf(fp, " case Op_%s: { _sub_Op_%s(n);\n", NodeClassNames[i], NodeClassNames[i]);
447 } else {
448 fprintf(fp, " case Op_%s: {\n", NodeClassNames[i]);
449 // Walk the list, compacting it
450 gen_dfa_state_body(fp, minimize, status, operands_chained_from, i);
451 }
452 // Print the "break"
453 fprintf(fp, " break;\n");
454 fprintf(fp, " }\n");
455 }
456
457 // Generate the default case for switch(opcode)
458 fprintf(fp, " \n");
459 fprintf(fp, " default:\n");
460 fprintf(fp, " tty->print(\"Default case invoked for: \\n\");\n");
461 fprintf(fp, " tty->print(\" opcode = %cd, \\\"%cs\\\"\\n\", opcode, NodeClassNames[opcode]);\n", '%', '%');
462 fprintf(fp, " return false;\n");
463 fprintf(fp, " }\n");
464
465 // Return status, indicating a successful match.
466 fprintf(fp, " return true;\n");
467 // Generate the closing brace for method Matcher::DFA
468 fprintf(fp, "}\n");
469 Expr::check_buffers();
470 }
471
472
473 class dfa_shared_preds {
474 enum { count = 3 IA32_ONLY( + 1 ) };
475
476 static bool _found[count];
477 static const char* _type [count];
478 static const char* _var [count];
479 static const char* _pred [count];
480
check_index(int index)481 static void check_index(int index) { assert( 0 <= index && index < count, "Invalid index"); }
482
483 // Confirm that this is a separate sub-expression.
484 // Only need to catch common cases like " ... && shared ..."
485 // and avoid hazardous ones like "...->shared"
valid_loc(char * pred,char * shared)486 static bool valid_loc(char *pred, char *shared) {
487 // start of predicate is valid
488 if( shared == pred ) return true;
489
490 // Check previous character and recurse if needed
491 char *prev = shared - 1;
492 char c = *prev;
493 switch( c ) {
494 case ' ':
495 case '\n':
496 return dfa_shared_preds::valid_loc(pred, prev);
497 case '!':
498 case '(':
499 case '<':
500 case '=':
501 return true;
502 case '"': // such as: #line 10 "myfile.ad"\n mypredicate
503 return true;
504 case '|':
505 if (prev != pred && *(prev-1) == '|') return true;
506 break;
507 case '&':
508 if (prev != pred && *(prev-1) == '&') return true;
509 break;
510 default:
511 return false;
512 }
513
514 return false;
515 }
516
517 public:
518
found(int index)519 static bool found(int index){ check_index(index); return _found[index]; }
set_found(int index,bool val)520 static void set_found(int index, bool val) { check_index(index); _found[index] = val; }
reset_found()521 static void reset_found() {
522 for( int i = 0; i < count; ++i ) { _found[i] = false; }
523 };
524
type(int index)525 static const char* type(int index) { check_index(index); return _type[index]; }
var(int index)526 static const char* var (int index) { check_index(index); return _var [index]; }
pred(int index)527 static const char* pred(int index) { check_index(index); return _pred[index]; }
528
529 // Check each predicate in the MatchList for common sub-expressions
cse_matchlist(MatchList * matchList)530 static void cse_matchlist(MatchList *matchList) {
531 for( MatchList *mList = matchList; mList != NULL; mList = mList->get_next() ) {
532 Predicate* predicate = mList->get_pred_obj();
533 char* pred = mList->get_pred();
534 if( pred != NULL ) {
535 for(int index = 0; index < count; ++index ) {
536 const char *shared_pred = dfa_shared_preds::pred(index);
537 const char *shared_pred_var = dfa_shared_preds::var(index);
538 bool result = dfa_shared_preds::cse_predicate(predicate, shared_pred, shared_pred_var);
539 if( result ) dfa_shared_preds::set_found(index, true);
540 }
541 }
542 }
543 }
544
545 // If the Predicate contains a common sub-expression, replace the Predicate's
546 // string with one that uses the variable name.
cse_predicate(Predicate * predicate,const char * shared_pred,const char * shared_pred_var)547 static bool cse_predicate(Predicate* predicate, const char *shared_pred, const char *shared_pred_var) {
548 bool result = false;
549 char *pred = predicate->_pred;
550 if( pred != NULL ) {
551 char *new_pred = pred;
552 for( char *shared_pred_loc = strstr(new_pred, shared_pred);
553 shared_pred_loc != NULL && dfa_shared_preds::valid_loc(new_pred,shared_pred_loc);
554 shared_pred_loc = strstr(new_pred, shared_pred) ) {
555 // Do not modify the original predicate string, it is shared
556 if( new_pred == pred ) {
557 new_pred = strdup(pred);
558 shared_pred_loc = strstr(new_pred, shared_pred);
559 }
560 // Replace shared_pred with variable name
561 strncpy(shared_pred_loc, shared_pred_var, strlen(shared_pred_var));
562 }
563 // Install new predicate
564 if( new_pred != pred ) {
565 predicate->_pred = new_pred;
566 result = true;
567 }
568 }
569 return result;
570 }
571
572 // Output the hoisted common sub-expression if we found it in predicates
generate_cse(FILE * fp)573 static void generate_cse(FILE *fp) {
574 for(int j = 0; j < count; ++j ) {
575 if( dfa_shared_preds::found(j) ) {
576 const char *shared_pred_type = dfa_shared_preds::type(j);
577 const char *shared_pred_var = dfa_shared_preds::var(j);
578 const char *shared_pred = dfa_shared_preds::pred(j);
579 fprintf(fp, " %s %s = %s;\n", shared_pred_type, shared_pred_var, shared_pred);
580 }
581 }
582 }
583 };
584 // shared predicates, _var and _pred entry should be the same length
585 bool dfa_shared_preds::_found[dfa_shared_preds::count] = { false, false, false IA32_ONLY(COMMA false) };
586 const char* dfa_shared_preds::_type [dfa_shared_preds::count] = { "int", "jlong", "intptr_t" IA32_ONLY(COMMA "bool") };
587 const char* dfa_shared_preds::_var [dfa_shared_preds::count] = { "_n_get_int__", "_n_get_long__", "_n_get_intptr_t__" IA32_ONLY(COMMA "Compile__current____select_24_bit_instr__") };
588 const char* dfa_shared_preds::_pred [dfa_shared_preds::count] = { "n->get_int()", "n->get_long()", "n->get_intptr_t()" IA32_ONLY(COMMA "Compile::current()->select_24_bit_instr()") };
589
gen_dfa_state_body(FILE * fp,Dict & minimize,ProductionState & status,Dict & operands_chained_from,int i)590 void ArchDesc::gen_dfa_state_body(FILE* fp, Dict &minimize, ProductionState &status, Dict &operands_chained_from, int i) {
591 // Start the body of each Op_XXX sub-dfa with a clean state.
592 status.initialize();
593
594 // Walk the list, compacting it
595 MatchList* mList = _mlistab[i];
596 do {
597 // Hash each entry using inputs as key and pointer as data.
598 // If there is already an entry, keep the one with lower cost, and
599 // remove the other one from the list.
600 prune_matchlist(minimize, *mList);
601 // Iterate
602 mList = mList->get_next();
603 } while(mList != NULL);
604
605 // Hoist previously specified common sub-expressions out of predicates
606 dfa_shared_preds::reset_found();
607 dfa_shared_preds::cse_matchlist(_mlistab[i]);
608 dfa_shared_preds::generate_cse(fp);
609
610 mList = _mlistab[i];
611
612 // Walk the list again, generating code
613 do {
614 // Each match can generate its own chains
615 operands_chained_from.Clear();
616 gen_match(fp, *mList, status, operands_chained_from);
617 mList = mList->get_next();
618 } while(mList != NULL);
619 // Fill in any chain rules which add instructions
620 // These can generate their own chains as well.
621 operands_chained_from.Clear(); //
622 if( debug_output1 ) { fprintf(fp, "// top level chain rules for: %s \n", (char *)NodeClassNames[i]); } // %%%%% Explanation
623 const Expr *zeroCost = new Expr("0");
624 chain_rule(fp, " ", (char *)NodeClassNames[i], zeroCost, "Invalid",
625 operands_chained_from, status);
626 }
627
628
629
630 //------------------------------Expr------------------------------------------
631 Expr *Expr::_unknown_expr = NULL;
632 char Expr::string_buffer[STRING_BUFFER_LENGTH];
633 char Expr::external_buffer[STRING_BUFFER_LENGTH];
634 bool Expr::_init_buffers = Expr::init_buffers();
635
Expr()636 Expr::Expr() {
637 _external_name = NULL;
638 _expr = "Invalid_Expr";
639 _min_value = Expr::Max;
640 _max_value = Expr::Zero;
641 }
Expr(const char * cost)642 Expr::Expr(const char *cost) {
643 _external_name = NULL;
644
645 int intval = 0;
646 if( cost == NULL ) {
647 _expr = "0";
648 _min_value = Expr::Zero;
649 _max_value = Expr::Zero;
650 }
651 else if( ADLParser::is_int_token(cost, intval) ) {
652 _expr = cost;
653 _min_value = intval;
654 _max_value = intval;
655 }
656 else {
657 assert( strcmp(cost,"0") != 0, "Recognize string zero as an int");
658 _expr = cost;
659 _min_value = Expr::Zero;
660 _max_value = Expr::Max;
661 }
662 }
663
Expr(const char * name,const char * expression,int min_value,int max_value)664 Expr::Expr(const char *name, const char *expression, int min_value, int max_value) {
665 _external_name = name;
666 _expr = expression ? expression : name;
667 _min_value = min_value;
668 _max_value = max_value;
669 assert(_min_value >= 0 && _min_value <= Expr::Max, "value out of range");
670 assert(_max_value >= 0 && _max_value <= Expr::Max, "value out of range");
671 }
672
clone() const673 Expr *Expr::clone() const {
674 Expr *cost = new Expr();
675 cost->_external_name = _external_name;
676 cost->_expr = _expr;
677 cost->_min_value = _min_value;
678 cost->_max_value = _max_value;
679
680 return cost;
681 }
682
add(const Expr * c)683 void Expr::add(const Expr *c) {
684 // Do not update fields until all computation is complete
685 const char *external = compute_external(this, c);
686 const char *expr = compute_expr(this, c);
687 int min_value = compute_min (this, c);
688 int max_value = compute_max (this, c);
689
690 _external_name = external;
691 _expr = expr;
692 _min_value = min_value;
693 _max_value = max_value;
694 }
695
add(const char * c)696 void Expr::add(const char *c) {
697 Expr *cost = new Expr(c);
698 add(cost);
699 }
700
add(const char * c,ArchDesc & AD)701 void Expr::add(const char *c, ArchDesc &AD) {
702 const Expr *e = AD.globalDefs()[c];
703 if( e != NULL ) {
704 // use the value of 'c' defined in <arch>.ad
705 add(e);
706 } else {
707 Expr *cost = new Expr(c);
708 add(cost);
709 }
710 }
711
compute_external(const Expr * c1,const Expr * c2)712 const char *Expr::compute_external(const Expr *c1, const Expr *c2) {
713 const char * result = NULL;
714
715 // Preserve use of external name which has a zero value
716 if( c1->_external_name != NULL ) {
717 if( c2->is_zero() ) {
718 snprintf(string_buffer, STRING_BUFFER_LENGTH, "%s", c1->as_string());
719 } else {
720 snprintf(string_buffer, STRING_BUFFER_LENGTH, "%s+%s", c1->as_string(), c2->as_string());
721 }
722 string_buffer[STRING_BUFFER_LENGTH - 1] = '\0';
723 result = strdup(string_buffer);
724 }
725 else if( c2->_external_name != NULL ) {
726 if( c1->is_zero() ) {
727 snprintf(string_buffer, STRING_BUFFER_LENGTH, "%s", c2->_external_name);
728 } else {
729 snprintf(string_buffer, STRING_BUFFER_LENGTH, "%s + %s", c1->as_string(), c2->as_string());
730 }
731 string_buffer[STRING_BUFFER_LENGTH - 1] = '\0';
732 result = strdup(string_buffer);
733 }
734 return result;
735 }
736
compute_expr(const Expr * c1,const Expr * c2)737 const char *Expr::compute_expr(const Expr *c1, const Expr *c2) {
738 if( !c1->is_zero() ) {
739 if( c2->is_zero() ) {
740 snprintf(string_buffer, STRING_BUFFER_LENGTH, "%s", c1->_expr);
741 } else {
742 snprintf(string_buffer, STRING_BUFFER_LENGTH, "%s+%s", c1->_expr, c2->_expr);
743 }
744 }
745 else if( !c2->is_zero() ) {
746 snprintf(string_buffer, STRING_BUFFER_LENGTH, "%s", c2->_expr);
747 }
748 else {
749 sprintf( string_buffer, "0");
750 }
751 string_buffer[STRING_BUFFER_LENGTH - 1] = '\0';
752 char *cost = strdup(string_buffer);
753
754 return cost;
755 }
756
compute_min(const Expr * c1,const Expr * c2)757 int Expr::compute_min(const Expr *c1, const Expr *c2) {
758 int v1 = c1->_min_value;
759 int v2 = c2->_min_value;
760 assert(0 <= v2 && v2 <= Expr::Max, "sanity");
761 assert(v1 <= Expr::Max - v2, "Invalid cost computation");
762
763 return v1 + v2;
764 }
765
766
compute_max(const Expr * c1,const Expr * c2)767 int Expr::compute_max(const Expr *c1, const Expr *c2) {
768 int v1 = c1->_max_value;
769 int v2 = c2->_max_value;
770
771 // Check for overflow without producing UB. If v2 is positive
772 // and not larger than Max, the subtraction cannot underflow.
773 assert(0 <= v2 && v2 <= Expr::Max, "sanity");
774 if (v1 > Expr::Max - v2) {
775 return Expr::Max;
776 }
777
778 return v1 + v2;
779 }
780
print() const781 void Expr::print() const {
782 if( _external_name != NULL ) {
783 printf(" %s == (%s) === [%d, %d]\n", _external_name, _expr, _min_value, _max_value);
784 } else {
785 printf(" %s === [%d, %d]\n", _expr, _min_value, _max_value);
786 }
787 }
788
print_define(FILE * fp) const789 void Expr::print_define(FILE *fp) const {
790 assert( _external_name != NULL, "definition does not have a name");
791 assert( _min_value == _max_value, "Expect user definitions to have constant value");
792 fprintf(fp, "#define %s (%s) \n", _external_name, _expr);
793 fprintf(fp, "// value == %d \n", _min_value);
794 }
795
print_assert(FILE * fp) const796 void Expr::print_assert(FILE *fp) const {
797 assert( _external_name != NULL, "definition does not have a name");
798 assert( _min_value == _max_value, "Expect user definitions to have constant value");
799 fprintf(fp, " assert( %s == %d, \"Expect (%s) to equal %d\");\n", _external_name, _min_value, _expr, _min_value);
800 }
801
get_unknown()802 Expr *Expr::get_unknown() {
803 if( Expr::_unknown_expr == NULL ) {
804 Expr::_unknown_expr = new Expr();
805 }
806
807 return Expr::_unknown_expr;
808 }
809
init_buffers()810 bool Expr::init_buffers() {
811 // Fill buffers with 0
812 for( int i = 0; i < STRING_BUFFER_LENGTH; ++i ) {
813 external_buffer[i] = '\0';
814 string_buffer[i] = '\0';
815 }
816
817 return true;
818 }
819
check_buffers()820 bool Expr::check_buffers() {
821 // returns 'true' if buffer use may have overflowed
822 bool ok = true;
823 for( int i = STRING_BUFFER_LENGTH - 100; i < STRING_BUFFER_LENGTH; ++i) {
824 if( external_buffer[i] != '\0' || string_buffer[i] != '\0' ) {
825 ok = false;
826 assert( false, "Expr:: Buffer overflow");
827 }
828 }
829
830 return ok;
831 }
832
833
834 //------------------------------ExprDict---------------------------------------
835 // Constructor
ExprDict(CmpKey cmp,Hash hash,Arena * arena)836 ExprDict::ExprDict( CmpKey cmp, Hash hash, Arena *arena )
837 : _expr(cmp, hash, arena), _defines() {
838 }
~ExprDict()839 ExprDict::~ExprDict() {
840 }
841
842 // Return # of name-Expr pairs in dict
Size(void) const843 int ExprDict::Size(void) const {
844 return _expr.Size();
845 }
846
847 // define inserts the given key-value pair into the dictionary,
848 // and records the name in order for later output, ...
define(const char * name,Expr * expr)849 const Expr *ExprDict::define(const char *name, Expr *expr) {
850 const Expr *old_expr = (*this)[name];
851 assert(old_expr == NULL, "Implementation does not support redefinition");
852
853 _expr.Insert(name, expr);
854 _defines.addName(name);
855
856 return old_expr;
857 }
858
859 // Insert inserts the given key-value pair into the dictionary. The prior
860 // value of the key is returned; NULL if the key was not previously defined.
Insert(const char * name,Expr * expr)861 const Expr *ExprDict::Insert(const char *name, Expr *expr) {
862 return (Expr*)_expr.Insert((void*)name, (void*)expr);
863 }
864
865 // Finds the value of a given key; or NULL if not found.
866 // The dictionary is NOT changed.
operator [](const char * name) const867 const Expr *ExprDict::operator [](const char *name) const {
868 return (Expr*)_expr[name];
869 }
870
print_defines(FILE * fp)871 void ExprDict::print_defines(FILE *fp) {
872 fprintf(fp, "\n");
873 const char *name = NULL;
874 for( _defines.reset(); (name = _defines.iter()) != NULL; ) {
875 const Expr *expr = (const Expr*)_expr[name];
876 assert( expr != NULL, "name in ExprDict without matching Expr in dictionary");
877 expr->print_define(fp);
878 }
879 }
print_asserts(FILE * fp)880 void ExprDict::print_asserts(FILE *fp) {
881 fprintf(fp, "\n");
882 fprintf(fp, " // Following assertions generated from definition section\n");
883 const char *name = NULL;
884 for( _defines.reset(); (name = _defines.iter()) != NULL; ) {
885 const Expr *expr = (const Expr*)_expr[name];
886 assert( expr != NULL, "name in ExprDict without matching Expr in dictionary");
887 expr->print_assert(fp);
888 }
889 }
890
891 // Print out the dictionary contents as key-value pairs
dumpekey(const void * key)892 static void dumpekey(const void* key) { fprintf(stdout, "%s", (char*) key); }
dumpexpr(const void * expr)893 static void dumpexpr(const void* expr) { fflush(stdout); ((Expr*)expr)->print(); }
894
dump()895 void ExprDict::dump() {
896 _expr.print(dumpekey, dumpexpr);
897 }
898
899
900 //------------------------------ExprDict::private------------------------------
901 // Disable public use of constructor, copy-ctor, operator =, operator ==
ExprDict()902 ExprDict::ExprDict( ) : _expr(cmpkey,hashkey), _defines() {
903 assert( false, "NotImplemented");
904 }
ExprDict(const ExprDict &)905 ExprDict::ExprDict( const ExprDict & ) : _expr(cmpkey,hashkey), _defines() {
906 assert( false, "NotImplemented");
907 }
operator =(const ExprDict & rhs)908 ExprDict &ExprDict::operator =( const ExprDict &rhs) {
909 assert( false, "NotImplemented");
910 _expr = rhs._expr;
911 return *this;
912 }
913 // == compares two dictionaries; they must have the same keys (their keys
914 // must match using CmpKey) and they must have the same values (pointer
915 // comparison). If so 1 is returned, if not 0 is returned.
operator ==(const ExprDict & d) const916 bool ExprDict::operator ==(const ExprDict &d) const {
917 assert( false, "NotImplemented");
918 return false;
919 }
920
921
922 //------------------------------Production-------------------------------------
Production(const char * result,const char * constraint,const char * valid)923 Production::Production(const char *result, const char *constraint, const char *valid) {
924 initialize();
925 _result = result;
926 _constraint = constraint;
927 _valid = valid;
928 }
929
initialize()930 void Production::initialize() {
931 _result = NULL;
932 _constraint = NULL;
933 _valid = knownInvalid;
934 _cost_lb = Expr::get_unknown();
935 _cost_ub = Expr::get_unknown();
936 }
937
print()938 void Production::print() {
939 printf("%s", (_result == NULL ? "NULL" : _result ) );
940 printf("%s", (_constraint == NULL ? "NULL" : _constraint ) );
941 printf("%s", (_valid == NULL ? "NULL" : _valid ) );
942 _cost_lb->print();
943 _cost_ub->print();
944 }
945
946
947 //------------------------------ProductionState--------------------------------
initialize()948 void ProductionState::initialize() {
949 _constraint = noConstraint;
950
951 // reset each Production currently in the dictionary
952 DictI iter( &_production );
953 const void *x, *y = NULL;
954 for( ; iter.test(); ++iter) {
955 x = iter._key;
956 y = iter._value;
957 Production *p = (Production*)y;
958 if( p != NULL ) {
959 p->initialize();
960 }
961 }
962 }
963
getProduction(const char * result)964 Production *ProductionState::getProduction(const char *result) {
965 Production *p = (Production *)_production[result];
966 if( p == NULL ) {
967 p = new Production(result, _constraint, knownInvalid);
968 _production.Insert(result, p);
969 }
970
971 return p;
972 }
973
set_constraint(const char * constraint)974 void ProductionState::set_constraint(const char *constraint) {
975 _constraint = constraint;
976 }
977
valid(const char * result)978 const char *ProductionState::valid(const char *result) {
979 return getProduction(result)->valid();
980 }
981
set_valid(const char * result)982 void ProductionState::set_valid(const char *result) {
983 Production *p = getProduction(result);
984
985 // Update valid as allowed by current constraints
986 if( _constraint == noConstraint ) {
987 p->_valid = knownValid;
988 } else {
989 if( p->_valid != knownValid ) {
990 p->_valid = unknownValid;
991 }
992 }
993 }
994
cost_lb(const char * result)995 Expr *ProductionState::cost_lb(const char *result) {
996 return getProduction(result)->cost_lb();
997 }
998
cost_ub(const char * result)999 Expr *ProductionState::cost_ub(const char *result) {
1000 return getProduction(result)->cost_ub();
1001 }
1002
set_cost_bounds(const char * result,const Expr * cost,bool has_state_check,bool has_cost_check)1003 void ProductionState::set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check) {
1004 Production *p = getProduction(result);
1005
1006 if( p->_valid == knownInvalid ) {
1007 // Our cost bounds are not unknown, just not defined.
1008 p->_cost_lb = cost->clone();
1009 p->_cost_ub = cost->clone();
1010 } else if (has_state_check || _constraint != noConstraint) {
1011 // The production is protected by a condition, so
1012 // the cost bounds may expand.
1013 // _cost_lb = min(cost, _cost_lb)
1014 if( cost->less_than_or_equal(p->_cost_lb) ) {
1015 p->_cost_lb = cost->clone();
1016 }
1017 // _cost_ub = max(cost, _cost_ub)
1018 if( p->_cost_ub->less_than_or_equal(cost) ) {
1019 p->_cost_ub = cost->clone();
1020 }
1021 } else if (has_cost_check) {
1022 // The production has no condition check, but does
1023 // have a cost check that could reduce the upper
1024 // and/or lower bound.
1025 // _cost_lb = min(cost, _cost_lb)
1026 if( cost->less_than_or_equal(p->_cost_lb) ) {
1027 p->_cost_lb = cost->clone();
1028 }
1029 // _cost_ub = min(cost, _cost_ub)
1030 if( cost->less_than_or_equal(p->_cost_ub) ) {
1031 p->_cost_ub = cost->clone();
1032 }
1033 } else {
1034 // The costs are unconditionally set.
1035 p->_cost_lb = cost->clone();
1036 p->_cost_ub = cost->clone();
1037 }
1038
1039 }
1040
1041 // Print out the dictionary contents as key-value pairs
print_key(const void * key)1042 static void print_key (const void* key) { fprintf(stdout, "%s", (char*) key); }
print_production(const void * production)1043 static void print_production(const void* production) { fflush(stdout); ((Production*)production)->print(); }
1044
print()1045 void ProductionState::print() {
1046 _production.print(print_key, print_production);
1047 }
1048