001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2006 Nomair A. Naeem
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019: package soot.dava.toolkits.base.AST.transformations;
020:
021: import soot.BooleanType;
022: import soot.Value;
023: import soot.dava.internal.AST.ASTAggregatedCondition;
024: import soot.dava.internal.AST.ASTAndCondition;
025: import soot.dava.internal.AST.ASTBinaryCondition;
026: import soot.dava.internal.AST.ASTCondition;
027: import soot.dava.internal.AST.ASTControlFlowNode;
028: import soot.dava.internal.AST.ASTDoWhileNode;
029: import soot.dava.internal.AST.ASTForLoopNode;
030: import soot.dava.internal.AST.ASTIfElseNode;
031: import soot.dava.internal.AST.ASTIfNode;
032: import soot.dava.internal.AST.ASTOrCondition;
033: import soot.dava.internal.AST.ASTUnaryCondition;
034: import soot.dava.internal.AST.ASTWhileNode;
035: import soot.dava.internal.javaRep.DIntConstant;
036: import soot.dava.internal.javaRep.DNotExpr;
037: import soot.dava.toolkits.base.AST.analysis.DepthFirstAdapter;
038: import soot.jimple.ConditionExpr;
039: import soot.jimple.DoubleConstant;
040: import soot.jimple.FloatConstant;
041: import soot.jimple.IntConstant;
042: import soot.jimple.LongConstant;
043:
044: /*
045: * 5 == 5 true DONE
046: * 5 != 5 false DONE (all other relational operators done)
047: *
048: * !true --> false DONE
049: * !false --> true DONE
050: *
051: * DONE WHEN one or both are constants (did all combinations)
052: * true || b ----> true
053: * true && b -----> b
054: * false || b -----> b
055: * false && b -------> false
056: *
057: * if ( (z0 && z1) || ( ! ( ! (z2) || ! (z3)) ) )
058: * ---> if ( (z0 && z1) || (z2 && z3) ) DONE
059: *
060: *
061: *
062: * TODO currently only doing primtype comparison of same types not handled are following types
063: * long <= int
064: * int <=long
065: * bla bla
066: *
067: *
068: * TODO IDEA if(io==0 && io==0) --> if(io==0)
069: */
070: public class SimplifyConditions extends DepthFirstAdapter {
071: public static boolean DEBUG = false;
072: public boolean changed = false;
073:
074: public SimplifyConditions() {
075: super ();
076: }
077:
078: public SimplifyConditions(boolean verbose) {
079: super (verbose);
080: }
081:
082: public void fixedPoint(ASTControlFlowNode node) {
083:
084: ASTCondition returned;
085: do {
086: if (DEBUG)
087: System.out.println("Invoking simplify");
088: changed = false;
089: ASTCondition cond = node.get_Condition();
090: returned = simplifyTheCondition(cond);
091: if (returned != null)
092: node.set_Condition(returned);
093: } while (changed);
094: }
095:
096: public void outASTIfNode(ASTIfNode node) {
097: fixedPoint(node);
098: }
099:
100: public void outASTIfElseNode(ASTIfElseNode node) {
101: fixedPoint(node);
102: }
103:
104: public void outASTWhileNode(ASTWhileNode node) {
105: fixedPoint(node);
106: }
107:
108: public void outASTDoWhileNode(ASTDoWhileNode node) {
109: fixedPoint(node);
110: }
111:
112: public void outASTForLoopNode(ASTForLoopNode node) {
113: fixedPoint(node);
114: }
115:
116: /*
117: * !z0 && !z1 ----> !(z0 || z1)
118: * !z0 || !z1 ----> !(z0 && z1)
119: *
120: * Send null if no change else send new condition CONDITION
121: */
122: public ASTCondition applyDeMorgans(ASTAggregatedCondition aggCond) {
123: ASTCondition left = aggCond.getLeftOp();
124: ASTCondition right = aggCond.getRightOp();
125:
126: if (aggCond.isNotted() && left instanceof ASTBinaryCondition
127: && right instanceof ASTBinaryCondition) {
128: //we can remove the not sign by simply flipping the two conditions
129: // ! ( x==y && a<b )
130: left.flip();
131: right.flip();
132: if (aggCond instanceof ASTAndCondition)
133: aggCond = new ASTOrCondition(left, right);
134: else
135: aggCond = new ASTAndCondition(left, right);
136:
137: return aggCond;
138: }
139:
140: if ((left.isNotted() && right.isNotted() && (!(left instanceof ASTBinaryCondition) && !(right instanceof ASTBinaryCondition)))
141: || (left.isNotted() && aggCond.isNotted() && !(left instanceof ASTBinaryCondition))
142: || (right.isNotted() && aggCond.isNotted() && !(right instanceof ASTBinaryCondition))) {
143: //both are notted and atleast one is not a binaryCondition
144: left.flip();
145: right.flip();
146:
147: ASTAggregatedCondition newCond;
148: if (aggCond instanceof ASTAndCondition)
149: newCond = new ASTOrCondition(left, right);
150: else
151: newCond = new ASTAndCondition(left, right);
152:
153: if (aggCond.isNotted())
154: return newCond;
155: else {
156: newCond.flip();
157: return newCond;
158: }
159: }
160:
161: return null;
162: }
163:
164: /*
165: * When this method is invoked we are sure that there are no occurences of !true or !false since
166: * this is AFTER doing depth first of the children so the unaryCondition must have simplified the above
167: *
168: * Return Null if no change else return changed condition
169: */
170: public ASTCondition simplifyIfAtleastOneConstant(
171: ASTAggregatedCondition aggCond) {
172: ASTCondition left = aggCond.getLeftOp();
173: ASTCondition right = aggCond.getRightOp();
174:
175: Boolean leftBool = null;
176: Boolean rightBool = null;
177: if (left instanceof ASTUnaryCondition)
178: leftBool = isBooleanConstant(((ASTUnaryCondition) left)
179: .getValue());
180:
181: if (right instanceof ASTUnaryCondition)
182: rightBool = isBooleanConstant(((ASTUnaryCondition) right)
183: .getValue());
184:
185: /*
186: * a && b NOCHANGE DONE
187: * b && a NOCHANGE DONE
188: *
189: * a || b NOCHANGE DONE
190: * b || a NOCHANGE DONE
191: *
192: */
193: if (leftBool == null && rightBool == null) {
194: // meaning both are not constants
195: return null;
196: }
197:
198: if (aggCond instanceof ASTAndCondition) {
199: /*
200: * true && true ---> true DONE
201: * true && false --> false DONE
202: * false && false ---> false DONE
203: * false && true --> false DONE
204: *
205: * true && b -----> b DONE
206: * false && b -------> false DONE
207: *
208: * b && true ---> b DONE
209: * b && false ---> b && false (since b could have side effects and the overall condition has to be false) DONE
210: *
211: */
212:
213: if (leftBool != null && rightBool != null) {
214: // meaning both are constants
215: if (leftBool.booleanValue() && rightBool.booleanValue()) {
216: // both are true
217: return new ASTUnaryCondition(DIntConstant.v(1,
218: BooleanType.v()));
219: } else {
220: // atleast one of the two is false
221: return new ASTUnaryCondition(DIntConstant.v(0,
222: BooleanType.v()));
223: }
224: }
225:
226: if (leftBool != null) {
227: // implicityly means that rigthBool is null since the above
228: // condition passed
229: if (leftBool.booleanValue()) {
230: // left bool is a true meaning we have to evaluate right
231: // condition.......just return the right condition
232: return right;
233: } else {
234: // left bool is false meaning no need to continue since we
235: // will never execute the right condition
236: // return a unary false
237: return new ASTUnaryCondition(DIntConstant.v(0,
238: BooleanType.v()));
239: }
240: }
241:
242: if (rightBool != null) {
243: // implicityly means that the leftBool is null
244: if (rightBool.booleanValue()) {
245: // rightBool is true so it all depends on left
246: return left;
247: } else {
248: // although we know the condition overall is false we cant
249: // remove the leftBool since there might be side effects
250: return aggCond;
251: }
252: }
253:
254: } else if (aggCond instanceof ASTOrCondition) {
255: /*
256: *
257: * true || false ---> true DONE
258: * true || true --> true DONE
259: * false || true --> true DONE
260: * false || false ---> false DONE
261: *
262: *
263: * true || b ----> true DONE
264: * false || b -----> b DONE
265: *
266: * b || true ---> b || true .... although we know the condition is true we have to evaluate b because of possible side effects DONE
267: * b || false ---> b DONE
268: *
269: */
270: if (leftBool != null && rightBool != null) {
271: // meaning both are constants
272: if (!leftBool.booleanValue()
273: && !rightBool.booleanValue()) {
274: // both are false
275: return new ASTUnaryCondition(DIntConstant.v(0,
276: BooleanType.v()));
277: } else {
278: // atleast one of the two is true
279: return new ASTUnaryCondition(DIntConstant.v(1,
280: BooleanType.v()));
281: }
282: }
283:
284: if (leftBool != null) {
285: // implicityly means that rigthBool is null since the above
286: // condition passed
287: if (leftBool.booleanValue()) {
288: //left bool is true that means we will stop evaluation of condition, just return true
289: return new ASTUnaryCondition(DIntConstant.v(1,
290: BooleanType.v()));
291: } else {
292: //left bool is false so we have to continue evaluating right
293: return right;
294: }
295: }
296:
297: if (rightBool != null) {
298: // implicityly means that the leftBool is null
299: if (rightBool.booleanValue()) {
300: // rightBool is true but leftBool must be evaluated beforehand
301: return aggCond;
302: } else {
303: //rightBool is false so everything depends on left
304: return left;
305: }
306: }
307: } else
308: throw new RuntimeException(
309: "Found unknown aggregated condition");
310:
311: return null;
312: }
313:
314: /*
315: * Method returns null if the Value is not a constant or not a boolean constant
316: * return true if the constant is true
317: * return false if the constant is false
318: */
319: public Boolean isBooleanConstant(Value internal) {
320:
321: if (!(internal instanceof DIntConstant))
322: return null;
323:
324: if (DEBUG)
325: System.out.println("Found Constant");
326:
327: DIntConstant intConst = (DIntConstant) internal;
328:
329: if (!(intConst.type instanceof BooleanType))
330: return null;
331:
332: //either true or false
333: if (DEBUG)
334: System.out.println("Found Boolean Constant");
335:
336: if (intConst.value == 1) {
337: return new Boolean(true);
338: } else if (intConst.value == 0) {
339: return new Boolean(false);
340: } else
341: throw new RuntimeException(
342: "BooleanType found with value different than 0 or 1");
343: }
344:
345: /*
346: * In a loop keep simplifying the condition as much as possible
347: *
348: */
349: public ASTCondition simplifyTheCondition(ASTCondition cond) {
350: if (cond instanceof ASTAggregatedCondition) {
351: ASTAggregatedCondition aggCond = (ASTAggregatedCondition) cond;
352: ASTCondition leftCond = simplifyTheCondition(aggCond
353: .getLeftOp());
354: ASTCondition rightCond = simplifyTheCondition(aggCond
355: .getRightOp());
356:
357: //if returned values are non null then set leftop /rightop to new condition
358: if (leftCond != null) {
359: aggCond.setLeftOp(leftCond);
360: }
361:
362: if (rightCond != null) {
363: aggCond.setRightOp(rightCond);
364: }
365:
366: ASTCondition returned = simplifyIfAtleastOneConstant(aggCond);
367: if (returned != null) {
368: changed = true;
369: return returned;
370: }
371:
372: returned = applyDeMorgans(aggCond);
373: if (returned != null) {
374: changed = true;
375: return returned;
376: }
377:
378: return aggCond;
379: } else if (cond instanceof ASTUnaryCondition) {
380: //dont do anything with unary conditions
381: ASTUnaryCondition unary = (ASTUnaryCondition) cond;
382:
383: /*
384: * if unary is a noted constant simplify it
385: * !true to be converted to false
386: * !false to be converted to true
387: */
388: Value unaryVal = unary.getValue();
389: if (unaryVal instanceof DNotExpr) {
390: if (DEBUG)
391: System.out
392: .println("Found NotExpr in unary COndition"
393: + unaryVal);
394:
395: DNotExpr notted = (DNotExpr) unaryVal;
396: Value internal = notted.getOp();
397:
398: Boolean isIt = isBooleanConstant(internal);
399: if (isIt != null) {
400: //is a boolean constant truth value will give whether its true or false
401: //convert !true to false
402: if (isIt.booleanValue()) {
403: //true
404: if (DEBUG)
405: System.out
406: .println("CONVERTED !true to false");
407: changed = true;
408: return new ASTUnaryCondition(DIntConstant.v(0,
409: BooleanType.v()));
410: } else if (!isIt.booleanValue()) {
411: //false
412: if (DEBUG)
413: System.out
414: .println("CONVERTED !false to true");
415: changed = true;
416: return new ASTUnaryCondition(DIntConstant.v(1,
417: BooleanType.v()));
418: } else
419: throw new RuntimeException(
420: "BooleanType found with value different than 0 or 1");
421: } else {
422: if (DEBUG)
423: System.out.println("Not boolean type");
424: }
425: }
426: return unary;
427: } else if (cond instanceof ASTBinaryCondition) {
428: ASTBinaryCondition binary = (ASTBinaryCondition) cond;
429: ConditionExpr expr = binary.getConditionExpr();
430:
431: //returns null if no change
432: ASTUnaryCondition temp = evaluateBinaryCondition(expr);
433: if (DEBUG)
434: System.out.println("changed binary condition " + cond
435: + " to" + temp);
436: if (temp != null)
437: changed = true;
438: return temp;
439: } else {
440: throw new RuntimeException(
441: "Method getUseList in ASTUsesAndDefs encountered unknown condition type");
442: }
443: }
444:
445: //return condition if was able to simplify (convert to a boolean true or false) else null
446: public ASTUnaryCondition evaluateBinaryCondition(ConditionExpr expr) {
447: String symbol = expr.getSymbol();
448:
449: int op = -1;
450: if (symbol.indexOf("==") > -1) {
451: if (DEBUG)
452: System.out.println("==");
453: op = 1;
454: } else if (symbol.indexOf(">=") > -1) {
455: if (DEBUG)
456: System.out.println(">=");
457: op = 2;
458: } else if (symbol.indexOf('>') > -1) {
459: if (DEBUG)
460: System.out.println(">");
461: op = 3;
462: } else if (symbol.indexOf("<=") > -1) {
463: if (DEBUG)
464: System.out.println("<=");
465: op = 4;
466: } else if (symbol.indexOf('<') > -1) {
467: if (DEBUG)
468: System.out.println("<");
469: op = 5;
470: } else if (symbol.indexOf("!=") > -1) {
471: if (DEBUG)
472: System.out.println("!=");
473: op = 6;
474: }
475:
476: Value leftOp = expr.getOp1();
477: Value rightOp = expr.getOp2();
478:
479: Boolean result = null;
480: if (leftOp instanceof LongConstant
481: && rightOp instanceof LongConstant) {
482: if (DEBUG)
483: System.out.println("long constants!!");
484: long left = ((LongConstant) leftOp).value;
485: long right = ((LongConstant) rightOp).value;
486: result = longSwitch(op, left, right);
487: } else if (leftOp instanceof DoubleConstant
488: && rightOp instanceof DoubleConstant) {
489: double left = ((DoubleConstant) leftOp).value;
490: double right = ((DoubleConstant) rightOp).value;
491: result = doubleSwitch(op, left, right);
492: } else if (leftOp instanceof FloatConstant
493: && rightOp instanceof FloatConstant) {
494: float left = ((FloatConstant) leftOp).value;
495: float right = ((FloatConstant) rightOp).value;
496: result = floatSwitch(op, left, right);
497: } else if (leftOp instanceof IntConstant
498: && rightOp instanceof IntConstant) {
499: int left = ((IntConstant) leftOp).value;
500: int right = ((IntConstant) rightOp).value;
501: result = intSwitch(op, left, right);
502: }
503:
504: if (result != null) {
505: if (result.booleanValue())
506: return new ASTUnaryCondition(DIntConstant.v(1,
507: BooleanType.v()));
508: else
509: return new ASTUnaryCondition(DIntConstant.v(0,
510: BooleanType.v()));
511: }
512: return null;
513: }
514:
515: public Boolean longSwitch(int op, long l, long r) {
516: switch (op) {
517: case 1:
518: // ==
519: if (l == r)
520: return new Boolean(true);
521: else
522: return new Boolean(false);
523:
524: case 2:
525: // >=
526: if (l >= r)
527: return new Boolean(true);
528: else
529: return new Boolean(false);
530:
531: case 3:
532: // >
533: if (l > r)
534: return new Boolean(true);
535: else
536: return new Boolean(false);
537:
538: case 4:
539: // <=
540: if (l <= r)
541: return new Boolean(true);
542: else
543: return new Boolean(false);
544:
545: case 5:
546: // <
547:
548: if (l < r)
549: return new Boolean(true);
550: else
551: return new Boolean(false);
552:
553: case 6:
554: // !=
555: if (l != r)
556: return new Boolean(true);
557: else
558: return new Boolean(false);
559:
560: default:
561: if (DEBUG)
562: System.out.println("got here");
563: return null;
564: }
565: }
566:
567: public Boolean doubleSwitch(int op, double l, double r) {
568: switch (op) {
569: case 1:
570: // ==
571: if (l == r)
572: return new Boolean(true);
573: else
574: return new Boolean(false);
575:
576: case 2:
577: // >=
578: if (l >= r)
579: return new Boolean(true);
580: else
581: return new Boolean(false);
582:
583: case 3:
584: // >
585: if (l > r)
586: return new Boolean(true);
587: else
588: return new Boolean(false);
589:
590: case 4:
591: // <=
592: if (l <= r)
593: return new Boolean(true);
594: else
595: return new Boolean(false);
596:
597: case 5:
598: // <
599:
600: if (l < r)
601: return new Boolean(true);
602: else
603: return new Boolean(false);
604:
605: case 6:
606: // !=
607: if (l != r)
608: return new Boolean(true);
609: else
610: return new Boolean(false);
611:
612: default:
613: return null;
614: }
615: }
616:
617: public Boolean floatSwitch(int op, float l, float r) {
618: switch (op) {
619: case 1:
620: // ==
621: if (l == r)
622: return new Boolean(true);
623: else
624: return new Boolean(false);
625:
626: case 2:
627: // >=
628: if (l >= r)
629: return new Boolean(true);
630: else
631: return new Boolean(false);
632:
633: case 3:
634: // >
635: if (l > r)
636: return new Boolean(true);
637: else
638: return new Boolean(false);
639:
640: case 4:
641: // <=
642: if (l <= r)
643: return new Boolean(true);
644: else
645: return new Boolean(false);
646:
647: case 5:
648: // <
649:
650: if (l < r)
651: return new Boolean(true);
652: else
653: return new Boolean(false);
654:
655: case 6:
656: // !=
657: if (l != r)
658: return new Boolean(true);
659: else
660: return new Boolean(false);
661:
662: default:
663: return null;
664: }
665: }
666:
667: public Boolean intSwitch(int op, int l, int r) {
668: switch (op) {
669: case 1:
670: // ==
671: if (l == r)
672: return new Boolean(true);
673: else
674: return new Boolean(false);
675:
676: case 2:
677: // >=
678: if (l >= r)
679: return new Boolean(true);
680: else
681: return new Boolean(false);
682:
683: case 3:
684: // >
685: if (l > r)
686: return new Boolean(true);
687: else
688: return new Boolean(false);
689:
690: case 4:
691: // <=
692: if (l <= r)
693: return new Boolean(true);
694: else
695: return new Boolean(false);
696:
697: case 5:
698: // <
699:
700: if (l < r)
701: return new Boolean(true);
702: else
703: return new Boolean(false);
704:
705: case 6:
706: // !=
707: if (l != r)
708: return new Boolean(true);
709: else
710: return new Boolean(false);
711:
712: default:
713: return null;
714: }
715: }
716:
717: }
|