|
0
|
1 /*
|
|
|
2 * Copyright 1997-2004 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
|
|
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or
|
|
|
21 * have any 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);
|
|
|
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 {
|
|
|
461 enum { count = 2 };
|
|
|
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 ' ':
|
|
|
482 return dfa_shared_preds::valid_loc(pred, prev);
|
|
|
483 case '!':
|
|
|
484 case '(':
|
|
|
485 case '<':
|
|
|
486 case '=':
|
|
|
487 return true;
|
|
|
488 case '|':
|
|
|
489 if( prev != pred && *(prev-1) == '|' ) return true;
|
|
|
490 case '&':
|
|
|
491 if( prev != pred && *(prev-1) == '&' ) return true;
|
|
|
492 default:
|
|
|
493 return false;
|
|
|
494 }
|
|
|
495
|
|
|
496 return false;
|
|
|
497 }
|
|
|
498
|
|
|
499 public:
|
|
|
500
|
|
|
501 static bool found(int index){ check_index(index); return _found[index]; }
|
|
|
502 static void set_found(int index, bool val) { check_index(index); _found[index] = val; }
|
|
|
503 static void reset_found() {
|
|
|
504 for( int i = 0; i < count; ++i ) { _found[i] = false; }
|
|
|
505 };
|
|
|
506
|
|
|
507 static const char* type(int index) { check_index(index); return _type[index]; }
|
|
|
508 static const char* var (int index) { check_index(index); return _var [index]; }
|
|
|
509 static const char* pred(int index) { check_index(index); return _pred[index]; }
|
|
|
510
|
|
|
511 // Check each predicate in the MatchList for common sub-expressions
|
|
|
512 static void cse_matchlist(MatchList *matchList) {
|
|
|
513 for( MatchList *mList = matchList; mList != NULL; mList = mList->get_next() ) {
|
|
|
514 Predicate* predicate = mList->get_pred_obj();
|
|
|
515 char* pred = mList->get_pred();
|
|
|
516 if( pred != NULL ) {
|
|
|
517 for(int index = 0; index < count; ++index ) {
|
|
|
518 const char *shared_pred = dfa_shared_preds::pred(index);
|
|
|
519 const char *shared_pred_var = dfa_shared_preds::var(index);
|
|
|
520 bool result = dfa_shared_preds::cse_predicate(predicate, shared_pred, shared_pred_var);
|
|
|
521 if( result ) dfa_shared_preds::set_found(index, true);
|
|
|
522 }
|
|
|
523 }
|
|
|
524 }
|
|
|
525 }
|
|
|
526
|
|
|
527 // If the Predicate contains a common sub-expression, replace the Predicate's
|
|
|
528 // string with one that uses the variable name.
|
|
|
529 static bool cse_predicate(Predicate* predicate, const char *shared_pred, const char *shared_pred_var) {
|
|
|
530 bool result = false;
|
|
|
531 char *pred = predicate->_pred;
|
|
|
532 if( pred != NULL ) {
|
|
|
533 char *new_pred = pred;
|
|
|
534 for( char *shared_pred_loc = strstr(new_pred, shared_pred);
|
|
|
535 shared_pred_loc != NULL && dfa_shared_preds::valid_loc(new_pred,shared_pred_loc);
|
|
|
536 shared_pred_loc = strstr(new_pred, shared_pred) ) {
|
|
|
537 // Do not modify the original predicate string, it is shared
|
|
|
538 if( new_pred == pred ) {
|
|
|
539 new_pred = strdup(pred);
|
|
|
540 shared_pred_loc = strstr(new_pred, shared_pred);
|
|
|
541 }
|
|
|
542 // Replace shared_pred with variable name
|
|
|
543 strncpy(shared_pred_loc, shared_pred_var, strlen(shared_pred_var));
|
|
|
544 }
|
|
|
545 // Install new predicate
|
|
|
546 if( new_pred != pred ) {
|
|
|
547 predicate->_pred = new_pred;
|
|
|
548 result = true;
|
|
|
549 }
|
|
|
550 }
|
|
|
551 return result;
|
|
|
552 }
|
|
|
553
|
|
|
554 // Output the hoisted common sub-expression if we found it in predicates
|
|
|
555 static void generate_cse(FILE *fp) {
|
|
|
556 for(int j = 0; j < count; ++j ) {
|
|
|
557 if( dfa_shared_preds::found(j) ) {
|
|
|
558 const char *shared_pred_type = dfa_shared_preds::type(j);
|
|
|
559 const char *shared_pred_var = dfa_shared_preds::var(j);
|
|
|
560 const char *shared_pred = dfa_shared_preds::pred(j);
|
|
|
561 fprintf(fp, " %s %s = %s;\n", shared_pred_type, shared_pred_var, shared_pred);
|
|
|
562 }
|
|
|
563 }
|
|
|
564 }
|
|
|
565 };
|
|
|
566 // shared predicates, _var and _pred entry should be the same length
|
|
|
567 bool dfa_shared_preds::_found[dfa_shared_preds::count] = { false, false };
|
|
|
568 const char* dfa_shared_preds::_type[dfa_shared_preds::count] = { "int", "bool" };
|
|
|
569 const char* dfa_shared_preds::_var [dfa_shared_preds::count] = { "_n_get_int__", "Compile__current____select_24_bit_instr__" };
|
|
|
570 const char* dfa_shared_preds::_pred[dfa_shared_preds::count] = { "n->get_int()", "Compile::current()->select_24_bit_instr()" };
|
|
|
571
|
|
|
572
|
|
|
573 void ArchDesc::gen_dfa_state_body(FILE* fp, Dict &minimize, ProductionState &status, Dict &operands_chained_from, int i) {
|
|
|
574 // Start the body of each Op_XXX sub-dfa with a clean state.
|
|
|
575 status.initialize();
|
|
|
576
|
|
|
577 // Walk the list, compacting it
|
|
|
578 MatchList* mList = _mlistab[i];
|
|
|
579 do {
|
|
|
580 // Hash each entry using inputs as key and pointer as data.
|
|
|
581 // If there is already an entry, keep the one with lower cost, and
|
|
|
582 // remove the other one from the list.
|
|
|
583 prune_matchlist(minimize, *mList);
|
|
|
584 // Iterate
|
|
|
585 mList = mList->get_next();
|
|
|
586 } while(mList != NULL);
|
|
|
587
|
|
|
588 // Hoist previously specified common sub-expressions out of predicates
|
|
|
589 dfa_shared_preds::reset_found();
|
|
|
590 dfa_shared_preds::cse_matchlist(_mlistab[i]);
|
|
|
591 dfa_shared_preds::generate_cse(fp);
|
|
|
592
|
|
|
593 mList = _mlistab[i];
|
|
|
594
|
|
|
595 // Walk the list again, generating code
|
|
|
596 do {
|
|
|
597 // Each match can generate its own chains
|
|
|
598 operands_chained_from.Clear();
|
|
|
599 gen_match(fp, *mList, status, operands_chained_from);
|
|
|
600 mList = mList->get_next();
|
|
|
601 } while(mList != NULL);
|
|
|
602 // Fill in any chain rules which add instructions
|
|
|
603 // These can generate their own chains as well.
|
|
|
604 operands_chained_from.Clear(); //
|
|
|
605 if( debug_output1 ) { fprintf(fp, "// top level chain rules for: %s \n", (char *)NodeClassNames[i]); } // %%%%% Explanation
|
|
|
606 const Expr *zeroCost = new Expr("0");
|
|
|
607 chain_rule(fp, " ", (char *)NodeClassNames[i], zeroCost, "Invalid",
|
|
|
608 operands_chained_from, status);
|
|
|
609 }
|
|
|
610
|
|
|
611
|
|
|
612
|
|
|
613 //------------------------------Expr------------------------------------------
|
|
|
614 Expr *Expr::_unknown_expr = NULL;
|
|
|
615 char Expr::string_buffer[STRING_BUFFER_LENGTH];
|
|
|
616 char Expr::external_buffer[STRING_BUFFER_LENGTH];
|
|
|
617 bool Expr::_init_buffers = Expr::init_buffers();
|
|
|
618
|
|
|
619 Expr::Expr() {
|
|
|
620 _external_name = NULL;
|
|
|
621 _expr = "Invalid_Expr";
|
|
|
622 _min_value = Expr::Max;
|
|
|
623 _max_value = Expr::Zero;
|
|
|
624 }
|
|
|
625 Expr::Expr(const char *cost) {
|
|
|
626 _external_name = NULL;
|
|
|
627
|
|
|
628 int intval = 0;
|
|
|
629 if( cost == NULL ) {
|
|
|
630 _expr = "0";
|
|
|
631 _min_value = Expr::Zero;
|
|
|
632 _max_value = Expr::Zero;
|
|
|
633 }
|
|
|
634 else if( ADLParser::is_int_token(cost, intval) ) {
|
|
|
635 _expr = cost;
|
|
|
636 _min_value = intval;
|
|
|
637 _max_value = intval;
|
|
|
638 }
|
|
|
639 else {
|
|
|
640 assert( strcmp(cost,"0") != 0, "Recognize string zero as an int");
|
|
|
641 _expr = cost;
|
|
|
642 _min_value = Expr::Zero;
|
|
|
643 _max_value = Expr::Max;
|
|
|
644 }
|
|
|
645 }
|
|
|
646
|
|
|
647 Expr::Expr(const char *name, const char *expression, int min_value, int max_value) {
|
|
|
648 _external_name = name;
|
|
|
649 _expr = expression ? expression : name;
|
|
|
650 _min_value = min_value;
|
|
|
651 _max_value = max_value;
|
|
|
652 assert(_min_value >= 0 && _min_value <= Expr::Max, "value out of range");
|
|
|
653 assert(_max_value >= 0 && _max_value <= Expr::Max, "value out of range");
|
|
|
654 }
|
|
|
655
|
|
|
656 Expr *Expr::clone() const {
|
|
|
657 Expr *cost = new Expr();
|
|
|
658 cost->_external_name = _external_name;
|
|
|
659 cost->_expr = _expr;
|
|
|
660 cost->_min_value = _min_value;
|
|
|
661 cost->_max_value = _max_value;
|
|
|
662
|
|
|
663 return cost;
|
|
|
664 }
|
|
|
665
|
|
|
666 void Expr::add(const Expr *c) {
|
|
|
667 // Do not update fields until all computation is complete
|
|
|
668 const char *external = compute_external(this, c);
|
|
|
669 const char *expr = compute_expr(this, c);
|
|
|
670 int min_value = compute_min (this, c);
|
|
|
671 int max_value = compute_max (this, c);
|
|
|
672
|
|
|
673 _external_name = external;
|
|
|
674 _expr = expr;
|
|
|
675 _min_value = min_value;
|
|
|
676 _max_value = max_value;
|
|
|
677 }
|
|
|
678
|
|
|
679 void Expr::add(const char *c) {
|
|
|
680 Expr *cost = new Expr(c);
|
|
|
681 add(cost);
|
|
|
682 }
|
|
|
683
|
|
|
684 void Expr::add(const char *c, ArchDesc &AD) {
|
|
|
685 const Expr *e = AD.globalDefs()[c];
|
|
|
686 if( e != NULL ) {
|
|
|
687 // use the value of 'c' defined in <arch>.ad
|
|
|
688 add(e);
|
|
|
689 } else {
|
|
|
690 Expr *cost = new Expr(c);
|
|
|
691 add(cost);
|
|
|
692 }
|
|
|
693 }
|
|
|
694
|
|
|
695 const char *Expr::compute_external(const Expr *c1, const Expr *c2) {
|
|
|
696 const char * result = NULL;
|
|
|
697
|
|
|
698 // Preserve use of external name which has a zero value
|
|
|
699 if( c1->_external_name != NULL ) {
|
|
|
700 sprintf( string_buffer, "%s", c1->as_string());
|
|
|
701 if( !c2->is_zero() ) {
|
|
|
702 strcat( string_buffer, "+");
|
|
|
703 strcat( string_buffer, c2->as_string());
|
|
|
704 }
|
|
|
705 result = strdup(string_buffer);
|
|
|
706 }
|
|
|
707 else if( c2->_external_name != NULL ) {
|
|
|
708 if( !c1->is_zero() ) {
|
|
|
709 sprintf( string_buffer, "%s", c1->as_string());
|
|
|
710 strcat( string_buffer, " + ");
|
|
|
711 } else {
|
|
|
712 string_buffer[0] = '\0';
|
|
|
713 }
|
|
|
714 strcat( string_buffer, c2->_external_name );
|
|
|
715 result = strdup(string_buffer);
|
|
|
716 }
|
|
|
717 return result;
|
|
|
718 }
|
|
|
719
|
|
|
720 const char *Expr::compute_expr(const Expr *c1, const Expr *c2) {
|
|
|
721 if( !c1->is_zero() ) {
|
|
|
722 sprintf( string_buffer, "%s", c1->_expr);
|
|
|
723 if( !c2->is_zero() ) {
|
|
|
724 strcat( string_buffer, "+");
|
|
|
725 strcat( string_buffer, c2->_expr);
|
|
|
726 }
|
|
|
727 }
|
|
|
728 else if( !c2->is_zero() ) {
|
|
|
729 sprintf( string_buffer, "%s", c2->_expr);
|
|
|
730 }
|
|
|
731 else {
|
|
|
732 sprintf( string_buffer, "0");
|
|
|
733 }
|
|
|
734 char *cost = strdup(string_buffer);
|
|
|
735
|
|
|
736 return cost;
|
|
|
737 }
|
|
|
738
|
|
|
739 int Expr::compute_min(const Expr *c1, const Expr *c2) {
|
|
|
740 int result = c1->_min_value + c2->_min_value;
|
|
|
741 assert( result >= 0, "Invalid cost computation");
|
|
|
742
|
|
|
743 return result;
|
|
|
744 }
|
|
|
745
|
|
|
746 int Expr::compute_max(const Expr *c1, const Expr *c2) {
|
|
|
747 int result = c1->_max_value + c2->_max_value;
|
|
|
748 if( result < 0 ) { // check for overflow
|
|
|
749 result = Expr::Max;
|
|
|
750 }
|
|
|
751
|
|
|
752 return result;
|
|
|
753 }
|
|
|
754
|
|
|
755 void Expr::print() const {
|
|
|
756 if( _external_name != NULL ) {
|
|
|
757 printf(" %s == (%s) === [%d, %d]\n", _external_name, _expr, _min_value, _max_value);
|
|
|
758 } else {
|
|
|
759 printf(" %s === [%d, %d]\n", _expr, _min_value, _max_value);
|
|
|
760 }
|
|
|
761 }
|
|
|
762
|
|
|
763 void Expr::print_define(FILE *fp) const {
|
|
|
764 assert( _external_name != NULL, "definition does not have a name");
|
|
|
765 assert( _min_value == _max_value, "Expect user definitions to have constant value");
|
|
|
766 fprintf(fp, "#define %s (%s) \n", _external_name, _expr);
|
|
|
767 fprintf(fp, "// value == %d \n", _min_value);
|
|
|
768 }
|
|
|
769
|
|
|
770 void Expr::print_assert(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, " assert( %s == %d, \"Expect (%s) to equal %d\");\n", _external_name, _min_value, _expr, _min_value);
|
|
|
774 }
|
|
|
775
|
|
|
776 Expr *Expr::get_unknown() {
|
|
|
777 if( Expr::_unknown_expr == NULL ) {
|
|
|
778 Expr::_unknown_expr = new Expr();
|
|
|
779 }
|
|
|
780
|
|
|
781 return Expr::_unknown_expr;
|
|
|
782 }
|
|
|
783
|
|
|
784 bool Expr::init_buffers() {
|
|
|
785 // Fill buffers with 0
|
|
|
786 for( int i = 0; i < STRING_BUFFER_LENGTH; ++i ) {
|
|
|
787 external_buffer[i] = '\0';
|
|
|
788 string_buffer[i] = '\0';
|
|
|
789 }
|
|
|
790
|
|
|
791 return true;
|
|
|
792 }
|
|
|
793
|
|
|
794 bool Expr::check_buffers() {
|
|
|
795 // returns 'true' if buffer use may have overflowed
|
|
|
796 bool ok = true;
|
|
|
797 for( int i = STRING_BUFFER_LENGTH - 100; i < STRING_BUFFER_LENGTH; ++i) {
|
|
|
798 if( external_buffer[i] != '\0' || string_buffer[i] != '\0' ) {
|
|
|
799 ok = false;
|
|
|
800 assert( false, "Expr:: Buffer overflow");
|
|
|
801 }
|
|
|
802 }
|
|
|
803
|
|
|
804 return ok;
|
|
|
805 }
|
|
|
806
|
|
|
807
|
|
|
808 //------------------------------ExprDict---------------------------------------
|
|
|
809 // Constructor
|
|
|
810 ExprDict::ExprDict( CmpKey cmp, Hash hash, Arena *arena )
|
|
|
811 : _expr(cmp, hash, arena), _defines() {
|
|
|
812 }
|
|
|
813 ExprDict::~ExprDict() {
|
|
|
814 }
|
|
|
815
|
|
|
816 // Return # of name-Expr pairs in dict
|
|
|
817 int ExprDict::Size(void) const {
|
|
|
818 return _expr.Size();
|
|
|
819 }
|
|
|
820
|
|
|
821 // define inserts the given key-value pair into the dictionary,
|
|
|
822 // and records the name in order for later output, ...
|
|
|
823 const Expr *ExprDict::define(const char *name, Expr *expr) {
|
|
|
824 const Expr *old_expr = (*this)[name];
|
|
|
825 assert(old_expr == NULL, "Implementation does not support redefinition");
|
|
|
826
|
|
|
827 _expr.Insert(name, expr);
|
|
|
828 _defines.addName(name);
|
|
|
829
|
|
|
830 return old_expr;
|
|
|
831 }
|
|
|
832
|
|
|
833 // Insert inserts the given key-value pair into the dictionary. The prior
|
|
|
834 // value of the key is returned; NULL if the key was not previously defined.
|
|
|
835 const Expr *ExprDict::Insert(const char *name, Expr *expr) {
|
|
|
836 return (Expr*)_expr.Insert((void*)name, (void*)expr);
|
|
|
837 }
|
|
|
838
|
|
|
839 // Finds the value of a given key; or NULL if not found.
|
|
|
840 // The dictionary is NOT changed.
|
|
|
841 const Expr *ExprDict::operator [](const char *name) const {
|
|
|
842 return (Expr*)_expr[name];
|
|
|
843 }
|
|
|
844
|
|
|
845 void ExprDict::print_defines(FILE *fp) {
|
|
|
846 fprintf(fp, "\n");
|
|
|
847 const char *name = NULL;
|
|
|
848 for( _defines.reset(); (name = _defines.iter()) != NULL; ) {
|
|
|
849 const Expr *expr = (const Expr*)_expr[name];
|
|
|
850 assert( expr != NULL, "name in ExprDict without matching Expr in dictionary");
|
|
|
851 expr->print_define(fp);
|
|
|
852 }
|
|
|
853 }
|
|
|
854 void ExprDict::print_asserts(FILE *fp) {
|
|
|
855 fprintf(fp, "\n");
|
|
|
856 fprintf(fp, " // Following assertions generated from definition section\n");
|
|
|
857 const char *name = NULL;
|
|
|
858 for( _defines.reset(); (name = _defines.iter()) != NULL; ) {
|
|
|
859 const Expr *expr = (const Expr*)_expr[name];
|
|
|
860 assert( expr != NULL, "name in ExprDict without matching Expr in dictionary");
|
|
|
861 expr->print_assert(fp);
|
|
|
862 }
|
|
|
863 }
|
|
|
864
|
|
|
865 // Print out the dictionary contents as key-value pairs
|
|
|
866 static void dumpekey(const void* key) { fprintf(stdout, "%s", key); }
|
|
|
867 static void dumpexpr(const void* expr) { fflush(stdout); ((Expr*)expr)->print(); }
|
|
|
868
|
|
|
869 void ExprDict::dump() {
|
|
|
870 _expr.print(dumpekey, dumpexpr);
|
|
|
871 }
|
|
|
872
|
|
|
873
|
|
|
874 //------------------------------ExprDict::private------------------------------
|
|
|
875 // Disable public use of constructor, copy-ctor, operator =, operator ==
|
|
|
876 ExprDict::ExprDict( ) : _expr(cmpkey,hashkey), _defines() {
|
|
|
877 assert( false, "NotImplemented");
|
|
|
878 }
|
|
|
879 ExprDict::ExprDict( const ExprDict & ) : _expr(cmpkey,hashkey), _defines() {
|
|
|
880 assert( false, "NotImplemented");
|
|
|
881 }
|
|
|
882 ExprDict &ExprDict::operator =( const ExprDict &rhs) {
|
|
|
883 assert( false, "NotImplemented");
|
|
|
884 _expr = rhs._expr;
|
|
|
885 return *this;
|
|
|
886 }
|
|
|
887 // == compares two dictionaries; they must have the same keys (their keys
|
|
|
888 // must match using CmpKey) and they must have the same values (pointer
|
|
|
889 // comparison). If so 1 is returned, if not 0 is returned.
|
|
|
890 bool ExprDict::operator ==(const ExprDict &d) const {
|
|
|
891 assert( false, "NotImplemented");
|
|
|
892 return false;
|
|
|
893 }
|
|
|
894
|
|
|
895
|
|
|
896 //------------------------------Production-------------------------------------
|
|
|
897 Production::Production(const char *result, const char *constraint, const char *valid) {
|
|
|
898 initialize();
|
|
|
899 _result = result;
|
|
|
900 _constraint = constraint;
|
|
|
901 _valid = valid;
|
|
|
902 }
|
|
|
903
|
|
|
904 void Production::initialize() {
|
|
|
905 _result = NULL;
|
|
|
906 _constraint = NULL;
|
|
|
907 _valid = knownInvalid;
|
|
|
908 _cost_lb = Expr::get_unknown();
|
|
|
909 _cost_ub = Expr::get_unknown();
|
|
|
910 }
|
|
|
911
|
|
|
912 void Production::print() {
|
|
|
913 printf("%s", (_result == NULL ? "NULL" : _result ) );
|
|
|
914 printf("%s", (_constraint == NULL ? "NULL" : _constraint ) );
|
|
|
915 printf("%s", (_valid == NULL ? "NULL" : _valid ) );
|
|
|
916 _cost_lb->print();
|
|
|
917 _cost_ub->print();
|
|
|
918 }
|
|
|
919
|
|
|
920
|
|
|
921 //------------------------------ProductionState--------------------------------
|
|
|
922 void ProductionState::initialize() {
|
|
|
923 _constraint = noConstraint;
|
|
|
924
|
|
|
925 // reset each Production currently in the dictionary
|
|
|
926 DictI iter( &_production );
|
|
|
927 const void *x, *y = NULL;
|
|
|
928 for( ; iter.test(); ++iter) {
|
|
|
929 x = iter._key;
|
|
|
930 y = iter._value;
|
|
|
931 Production *p = (Production*)y;
|
|
|
932 if( p != NULL ) {
|
|
|
933 p->initialize();
|
|
|
934 }
|
|
|
935 }
|
|
|
936 }
|
|
|
937
|
|
|
938 Production *ProductionState::getProduction(const char *result) {
|
|
|
939 Production *p = (Production *)_production[result];
|
|
|
940 if( p == NULL ) {
|
|
|
941 p = new Production(result, _constraint, knownInvalid);
|
|
|
942 _production.Insert(result, p);
|
|
|
943 }
|
|
|
944
|
|
|
945 return p;
|
|
|
946 }
|
|
|
947
|
|
|
948 void ProductionState::set_constraint(const char *constraint) {
|
|
|
949 _constraint = constraint;
|
|
|
950 }
|
|
|
951
|
|
|
952 const char *ProductionState::valid(const char *result) {
|
|
|
953 return getProduction(result)->valid();
|
|
|
954 }
|
|
|
955
|
|
|
956 void ProductionState::set_valid(const char *result) {
|
|
|
957 Production *p = getProduction(result);
|
|
|
958
|
|
|
959 // Update valid as allowed by current constraints
|
|
|
960 if( _constraint == noConstraint ) {
|
|
|
961 p->_valid = knownValid;
|
|
|
962 } else {
|
|
|
963 if( p->_valid != knownValid ) {
|
|
|
964 p->_valid = unknownValid;
|
|
|
965 }
|
|
|
966 }
|
|
|
967 }
|
|
|
968
|
|
|
969 Expr *ProductionState::cost_lb(const char *result) {
|
|
|
970 return getProduction(result)->cost_lb();
|
|
|
971 }
|
|
|
972
|
|
|
973 Expr *ProductionState::cost_ub(const char *result) {
|
|
|
974 return getProduction(result)->cost_ub();
|
|
|
975 }
|
|
|
976
|
|
|
977 void ProductionState::set_cost_bounds(const char *result, const Expr *cost, bool has_state_check, bool has_cost_check) {
|
|
|
978 Production *p = getProduction(result);
|
|
|
979
|
|
|
980 if( p->_valid == knownInvalid ) {
|
|
|
981 // Our cost bounds are not unknown, just not defined.
|
|
|
982 p->_cost_lb = cost->clone();
|
|
|
983 p->_cost_ub = cost->clone();
|
|
|
984 } else if (has_state_check || _constraint != noConstraint) {
|
|
|
985 // The production is protected by a condition, so
|
|
|
986 // the cost bounds may expand.
|
|
|
987 // _cost_lb = min(cost, _cost_lb)
|
|
|
988 if( cost->less_than_or_equal(p->_cost_lb) ) {
|
|
|
989 p->_cost_lb = cost->clone();
|
|
|
990 }
|
|
|
991 // _cost_ub = max(cost, _cost_ub)
|
|
|
992 if( p->_cost_ub->less_than_or_equal(cost) ) {
|
|
|
993 p->_cost_ub = cost->clone();
|
|
|
994 }
|
|
|
995 } else if (has_cost_check) {
|
|
|
996 // The production has no condition check, but does
|
|
|
997 // have a cost check that could reduce the upper
|
|
|
998 // and/or lower bound.
|
|
|
999 // _cost_lb = min(cost, _cost_lb)
|
|
|
1000 if( cost->less_than_or_equal(p->_cost_lb) ) {
|
|
|
1001 p->_cost_lb = cost->clone();
|
|
|
1002 }
|
|
|
1003 // _cost_ub = min(cost, _cost_ub)
|
|
|
1004 if( cost->less_than_or_equal(p->_cost_ub) ) {
|
|
|
1005 p->_cost_ub = cost->clone();
|
|
|
1006 }
|
|
|
1007 } else {
|
|
|
1008 // The costs are unconditionally set.
|
|
|
1009 p->_cost_lb = cost->clone();
|
|
|
1010 p->_cost_ub = cost->clone();
|
|
|
1011 }
|
|
|
1012
|
|
|
1013 }
|
|
|
1014
|
|
|
1015 // Print out the dictionary contents as key-value pairs
|
|
|
1016 static void print_key (const void* key) { fprintf(stdout, "%s", key); }
|
|
|
1017 static void print_production(const void* production) { fflush(stdout); ((Production*)production)->print(); }
|
|
|
1018
|
|
|
1019 void ProductionState::print() {
|
|
|
1020 _production.print(print_key, print_production);
|
|
|
1021 }
|
