5 /* #define DEBUGPRINT 1 */
7 # include <ctype.h> /* for isdigit */
8 # include "lclintMacros.nf"
10 # include "cgrammar.h"
11 # include "cgrammar_tokens.h"
13 # include "exprChecks.h"
14 # include "exprNodeSList.h"
16 # include "exprDataQuite.i"
18 /*@access constraint, exprNode @*/
20 /*@access constraintExpr @*/
22 static bool isInc (/*@observer@*/ constraintExpr c) /*@*/
25 llassert(constraintExpr_isDefined(c) );
26 if (c->kind == binaryexpr )
28 constraintExprBinaryOpKind binOP;
29 constraintExpr t1, t2;
30 t1 = constraintExprData_binaryExprGetExpr1 (c->data);
31 t2 = constraintExprData_binaryExprGetExpr2 (c->data);
33 binOP = constraintExprData_binaryExprGetOp (c->data);
35 if (constraintExpr_isLit (t2) && constraintExpr_getValue (t2) == 1 )
44 /* look for constraints like cexrp = cexrp + 1 */
45 static bool incVar (/*@notnull@*/ constraint c) /*@*/
52 if (! isInc (c->expr ) )
55 llassert (constraintExpr_isDefined(c->expr) );
56 llassert (c->expr->kind == binaryexpr);
58 t1 = constraintExprData_binaryExprGetExpr1 (c->expr->data);
59 if (constraintExpr_similar (c->lexpr, t1) )
64 /*@noaccess constraintExpr @*/
67 static bool increments (/*@observer@*/ constraint c,
68 /*@observer@*/ constraintExpr var)
70 llassert(constraint_isDefined(c) );
72 if (constraint_isUndefined(c) )
77 llassert (incVar (c));
78 if (constraintExpr_similar (c->lexpr, var) )
84 static bool canGetForTimes (/*@notnull@*/ exprNode forPred, /*@notnull@*/ exprNode forBody)
87 exprNode init, test, inc, t1, t2;
90 llassert(exprNode_isDefined (forPred) );
91 llassert(exprNode_isDefined (forBody) );
93 init = exprData_getTripleInit (forPred->edata);
94 test = exprData_getTripleTest (forPred->edata);
95 inc = exprData_getTripleInc (forPred->edata);
97 llassert(exprNode_isDefined(test) );
99 if (exprNode_isUndefined(test) )
104 llassert(exprNode_isDefined(inc) );
106 if (exprNode_isUndefined(inc) )
111 if (test->kind != XPR_PREOP)
114 tok = (exprData_getUopTok (test->edata));
115 if (!lltok_isMult (tok) )
120 /* should check preop too */
121 if (inc->kind != XPR_POSTOP)
126 tok = (exprData_getUopTok (inc->edata));
127 if (lltok_isInc_Op (tok) )
129 t1 = exprData_getUopNode (test->edata);
130 t2 = exprData_getUopNode (inc->edata);
131 llassert(exprNode_isDefined(t2) && exprNode_isDefined(t2) );
133 if (exprNode_isUndefined(t1) || exprNode_isUndefined(t2) )
138 if (sRef_sameName (t1->sref, t2->sref) )
146 static /*@only@*/ constraintList getLessThanConstraints (/*@observer@*/ constraintList c)
150 ret = constraintList_makeNew();
151 constraintList_elements (c, el)
153 llassert(constraint_isDefined(el));
154 if ( constraint_isUndefined(el) )
157 if (el->ar == LT || el->ar == LTE)
160 temp = constraint_copy(el);
162 ret = constraintList_add (ret, temp);
165 end_constraintList_elements;
170 static /*@only@*/ constraintList getIncConstraints (/*@observer@*/ constraintList c)
174 ret = constraintList_makeNew();
175 constraintList_elements (c, el)
177 llassert (constraint_isDefined (el));
182 temp = constraint_copy(el);
183 ret = constraintList_add (ret, temp);
186 end_constraintList_elements;
191 static /*@only@*/ constraintExpr getForTimes (/*@notnull@*/ exprNode forPred, /*@notnull@*/ exprNode forBody)
194 exprNode init, test, inc, t1, t2;
195 constraintList ltCon;
196 constraintList incCon;
201 init = exprData_getTripleInit (forPred->edata);
202 test = exprData_getTripleTest (forPred->edata);
203 inc = exprData_getTripleInc (forPred->edata);
205 llassert(exprNode_isDefined(test) );
206 llassert(exprNode_isDefined(inc) );
208 ltCon = getLessThanConstraints (test->trueEnsuresConstraints);
209 incCon = getIncConstraints (inc->ensuresConstraints);
211 DPRINTF(( message ("getForTimes: ltCon: %s from %s", constraintList_print(ltCon), constraintList_print(test->trueEnsuresConstraints) ) ));
213 DPRINTF(( message ("getForTimes: incCon: %s from %s", constraintList_print(incCon), constraintList_print(inc->ensuresConstraints) ) ));
215 constraintList_elements (ltCon, el)
217 constraintList_elements(incCon, el2)
219 if ( increments(el2, el->lexpr) )
221 DPRINTF(( message ("getForTimes: %s increments %s", constraint_print(el2), constraint_print(el) ) ));
222 ret = constraintExpr_copy (el->expr);
223 constraintList_free(ltCon);
224 constraintList_free(incCon);
229 DPRINTF(( message ("getForTimes: %s doesn't increment %s", constraint_print(el2), constraint_print(el) ) ));
231 end_constraintList_elements;
234 end_constraintList_elements;
236 constraintList_free(ltCon);
237 constraintList_free(incCon);
239 DPRINTF (( message ("getForTimes: %s %s resorting to ugly hack", exprNode_unparse(forPred), exprNode_unparse(forBody) ) ));
240 if (! canGetForTimes (forPred, forBody) )
246 if (test->kind != XPR_PREOP)
249 tok = (exprData_getUopTok (test->edata));
250 if (!lltok_isMult (tok) )
255 /* should check preop too */
256 if (inc->kind != XPR_POSTOP)
261 tok = (exprData_getUopTok (inc->edata));
262 if (lltok_isInc_Op (tok) )
264 t1 = exprData_getUopNode (test->edata);
265 t2 = exprData_getUopNode (inc->edata);
266 if (sRef_sameName (t1->sref, t2->sref) )
268 return (constraintExpr_makeMaxSetExpr (t1) );
275 /*@access constraintExpr @*/
277 static /*@only@*/ constraintExpr constraintExpr_searchAndAdd (/*@only@*/ constraintExpr c, /*@observer@*/ constraintExpr find, /*@observer@*/ constraintExpr add)
279 constraintExprKind kind;
282 DPRINTF(( message ("Doing constraintExpr_searchAndAdd %s %s %s ",
283 constraintExpr_unparse(c), constraintExpr_unparse(find), constraintExpr_unparse(add) ) ) );
285 if ( constraintExpr_similar (c, find) )
288 constraintExpr newExpr;
292 cPrint = constraintExpr_unparse(c);
295 newExpr = constraintExpr_makeAddExpr (c, constraintExpr_copy(add) );
297 DPRINTF((message ("Replacing %q with %q",
298 cPrint, constraintExpr_unparse(newExpr)
310 temp = constraintExprData_unaryExprGetExpr (c->data);
311 temp = constraintExpr_searchAndAdd (constraintExpr_copy(temp), find, add);
312 c->data = constraintExprData_unaryExprSetExpr (c->data, temp);
316 temp = constraintExprData_binaryExprGetExpr1 (c->data);
317 temp = constraintExpr_searchAndAdd (constraintExpr_copy(temp), find, add);
318 c->data = constraintExprData_binaryExprSetExpr1 (c->data, temp);
320 temp = constraintExprData_binaryExprGetExpr2 (c->data);
321 temp = constraintExpr_searchAndAdd (constraintExpr_copy(temp), find, add);
322 c->data = constraintExprData_binaryExprSetExpr2 (c->data, temp);
331 /*@noaccess constraintExpr @*/
333 static constraint constraint_searchAndAdd (/*@returned@*/ constraint c, /*@observer@*/ constraintExpr find, /*@observer@*/ constraintExpr add)
336 llassert (constraint_search (c, find) );
337 DPRINTF(( message ("Doing constraint_searchAndAdd %s %s %s ",
338 constraint_print(c), constraintExpr_unparse(find), constraintExpr_unparse(add) ) ) );
340 c->lexpr = constraintExpr_searchAndAdd (c->lexpr, find, add);
341 c->expr = constraintExpr_searchAndAdd (c->expr, find, add);
343 c = constraint_simplify (c);
344 c = constraint_simplify (c);
350 static constraintList constraintList_searchAndAdd (/*@returned@*/ constraintList list,
351 /*@observer@*/ constraintExpr find, /*@observer@*/ constraintExpr add)
353 constraintList newConstraints;
356 newConstraints = constraintList_makeNew();
358 constraintList_elements (list, el)
360 if (constraint_search (el, find) )
363 newExpr = constraint_copy (el);
365 newExpr = constraint_searchAndAdd (newExpr, find, add);
366 DPRINTF (( (message ("Adding constraint %s ", constraint_print (newExpr)) ) ));
367 newConstraints = constraintList_add (newConstraints, newExpr);
371 end_constraintList_elements;
373 ret = constraintList_addListFree (list, newConstraints);
377 static void doAdjust(/*@unused@*/ exprNode e, /*@unused@*/ exprNode forPred, /*@observer@*/ exprNode forBody, /*@observer@*/ constraintExpr iterations)
380 constraintList_elements (forBody->ensuresConstraints, el)
382 /* look for var = var + 1 */
385 DPRINTF((message ("Found inc variable constraint : %s", constraint_print (el) ) ));
386 forBody->requiresConstraints = constraintList_searchAndAdd(forBody->requiresConstraints, el->lexpr, iterations);
389 end_constraintList_elements;
392 void exprNode_forLoopHeuristics( exprNode e, exprNode forPred, exprNode forBody)
394 exprNode init, test, inc;
396 constraintExpr iterations;
398 init = exprData_getTripleInit (forPred->edata);
399 test = exprData_getTripleTest (forPred->edata);
400 inc = exprData_getTripleInc (forPred->edata);
402 if (exprNode_isError (test) || exprNode_isError (inc) )
405 iterations = getForTimes (forPred, forBody );
407 if (constraintExpr_isDefined (iterations) )
409 doAdjust ( e, forPred, forBody, iterations);
410 constraintExpr_free(iterations);
417 /* DPRINTF (("Can't get for time ")); */
420 /* if (exprNode_isError(init) ) */
425 /* if (init->kind == XPR_ASSIGN) */
427 /* t1 = exprData_getOpA (init->edata); */
428 /* t2 = exprData_getOpB (init->edata); */
430 /* if (! (t1->kind == XPR_VAR) ) */
436 /* if (test->kind == XPR_FETCH) */
438 /* t3 = exprData_getPairA (test->edata); */
439 /* t4 = exprData_getPairB (test->edata); */
441 /* if (sRef_sameName(t1->sref, t4->sref) ) */
443 /* DPRINTF((message ("Found a for loop matching heuristic:%s", exprNode_unparse (forPred) ) )); */
444 /* con = constraint_makeEnsureLteMaxRead(t1, t3); */
445 /* forPred->ensuresConstraints = constraintList_add(forPred->ensuresConstraints, con); */
449 /* DPRINTF((message ("Didn't Find a for loop matching heuristic:%s %s and %s differ", exprNode_unparse (forPred), exprNode_unparse(t1), exprNode_unparse(t3) ) )); */