Only add bound values for alias AST when the bound values are produced from conditino...
[dyninst.git] / parseAPI / src / BoundFactData.C
1 #include "dyntypes.h"
2 #include "BoundFactData.h"
3 #include "debug_parse.h"
4 #include "Instruction.h"
5 #include "IndirectASTVisitor.h"
6 #include "SymEval.h"
7 #include "CodeSource.h"
8 #include "CodeObject.h"
9 #include "CFG.h"
10 #include <iostream>
11
12 #define MAX_TABLE_ENTRY 1000000
13
14 using namespace Dyninst::InstructionAPI;
15 using namespace Dyninst::ParseAPI;
16 using namespace Dyninst::DataflowAPI;
17
18 const StridedInterval StridedInterval::top = StridedInterval(1, StridedInterval::minValue, StridedInterval::maxValue);
19 const StridedInterval StridedInterval::bottom = StridedInterval();
20
21 const BoundValue BoundValue::top = BoundValue(StridedInterval::top);
22 const BoundValue BoundValue::bottom = BoundValue();
23
24 // Greatest common divisor
25 static int64_t GCD(int64_t a, int64_t b) {
26     if (a == 0 && b == 0) return 0;
27     else if (a == 0) return b;
28     else if (b == 0) return a;
29     int64_t r = a % b;
30     while (r != 0) {
31         a = b;
32         b = r;
33         r = a % b;
34     }
35     return b;
36 }
37
38 // Find out x and y such that
39 // ax + by = gcd(a,b)
40 // Check http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
41 static int64_t ExtendEuclidean(int64_t a, int64_t b, int64_t &x, int64_t &y) {
42     int64_t old_x, old_y, r, old_r, q, tmp;
43     x = 0; y = 1; r = b;
44     old_x = 1; old_y = 0; old_r = a;
45     while (r != 0) {
46         q = old_r / r;
47
48         tmp = old_r;
49         old_r = r;
50         r = tmp - q * r;
51
52         tmp = old_x;
53         old_x = x;
54         x = tmp - q * x;
55
56         tmp = old_y;
57         old_y = y;
58         y = tmp - q * y;
59     }
60     x = old_x;
61     y = old_y;
62     return old_r;
63 }
64
65 void StridedInterval::Join(const StridedInterval &rhs) {
66     // Union of two intervals
67     if (stride < 0 && rhs.stride < 0) {
68         // Bottom
69         stride = -1;
70         low = high = 0;
71     } else if (stride < 0) {
72         *this = rhs;
73     } else if (rhs.stride < 0) {
74         // Anything joining bottom stays unchanged
75     } else {
76         set<int64_t> values;
77         values.insert(low);
78         values.insert(high);
79         values.insert(rhs.low);
80         values.insert(rhs.high);
81         // if values.size() == 1, then both intervals are the
82         // same constants. Nothing needs to be done
83         if (values.size() != 1) {
84             // Otherwise, new stride is GCD(stride, rhs.stride, |low - rhs.low|)
85             int newStride = GCD(stride, rhs.stride);
86             set<int64_t>::iterator cur, next;
87             for (cur = values.begin(), next = values.begin(), ++next; next != values.end(); ++cur, ++next)
88                 newStride = GCD(newStride, *next - *cur);
89             low = *(values.begin());
90             high = *cur;
91             stride = newStride;
92         }       
93     }
94 }
95
96 void StridedInterval::Neg() {
97     if (stride < 0) return;
98     int64_t tmpLow = low;
99     low = -high;
100     high = -tmpLow;
101 }
102
103 void StridedInterval::Not() {
104     if (stride < 0) return;
105     // Assume not is always used to 
106     // calculates its two's complement to 
107     // do a subtraction
108     int64_t tmpLow = low;
109     low = -high+1;
110     high = -tmpLow+1;
111
112 }
113
114 void StridedInterval::Add(const StridedInterval &rhs) {
115     // It is not clear what it means to 
116     // add a number with a number in empy set.
117     // Assume to be bottom
118     if (stride < 0 || rhs.stride < 0) {
119         *this = bottom;
120         return;
121     }
122     // If any of the interval is top,
123     // then the result of the add can take
124     // any value, thus is still top
125     if (*this == top || rhs == top) {
126         *this = top;
127         return;
128     }
129
130     // Assume no arithmetic overflow.
131     // May need to rewite this
132     stride = GCD(stride, rhs.stride);
133     low += rhs.low;
134     high += rhs.high;
135
136     // This is likely to be caused by arithmetic overflow.
137     // In this case, a strided interval cannot accurately 
138     // capture the value range. Set to top.
139     if (low > high) {
140         *this = top;
141     }
142 }
143
144 void StridedInterval::Sub(const StridedInterval& minuend) {
145    StridedInterval neg(minuend);
146    neg.Neg();
147    Add(neg);
148 }
149
150 void StridedInterval::And(const StridedInterval &rhs) {
151     // Currently only consider the case where at least one of them is constant
152     if (stride == 0) {
153        // CONSTANT and any thing ==> 1[1, CONSTANT]
154        low = 0;
155        stride = 1;
156     } else if (rhs.stride == 0) {
157        stride = 1;
158        low = 0;
159        high = rhs.low;
160     } else {
161         // Otherwise, widen
162         *this = top;
163     }
164 }
165
166 void StridedInterval::Or(const StridedInterval &rhs) {
167     // currently only consider the case where
168     // one of them is 1[0, high], the other is a constant
169     if (stride == 0 && rhs.stride == 1 && rhs.low == 0) {
170         stride = 1;
171         low = 0;
172         high |= rhs.high;
173     } else if (stride == 1 && low == 0 && rhs.stride == 0) {
174         high |= rhs.high;
175     } else {
176         // Otherwise, widen
177         *this = top;
178     }
179 }
180
181 void StridedInterval::Xor(const StridedInterval&) {
182     parsing_printf("StridedInterval::Xor: not implemented, widen\n");
183     *this = top;
184 }
185
186 void StridedInterval::Mul(const StridedInterval &rhs) {
187     // Currently only handle the case where
188     // one of the interval is a constant
189     if (stride == 0 || rhs.stride == 0) {
190         if (stride == 0) {
191             int64_t val = low;
192             low = rhs.low * val;
193             high = rhs.high * val;
194             stride = rhs.stride * val;
195         } else {
196             int64_t val = rhs.low;
197             low = low * val;
198             high = high * val;
199             stride = stride * val;
200         }
201         // If the constant value is negative,
202         // we need to swap the lower bound and the upper bound
203         if (stride < 0) {
204             stride = -stride;
205             int64_t tmp = low;
206             low = high;
207             high = tmp;
208         }
209     } else {
210         // In other case, we widen
211         *this = top;
212     }
213 }
214
215 void StridedInterval::Div(const StridedInterval &rhs) {
216     if (rhs.stride == 0) {
217         low /= rhs.low;
218         high /= rhs.low;
219         stride /= rhs.low;
220         if (stride == 0 && low != high) stride = 1;
221     } else {
222         *this = top;
223     }
224 }
225
226 void StridedInterval::ShiftLeft(const StridedInterval &rhs) {
227     if (rhs.stride == 0) {
228         Mul(StridedInterval(1 << rhs.low));
229     } else {
230         // In other case, we widen
231         *this = top;
232     }
233 }
234 void StridedInterval::ShiftRight(const StridedInterval &rhs) {
235     if (rhs.stride == 0) {
236         Div(StridedInterval(1 << rhs.low));
237     } else {
238         // In other case, we widen
239         *this = top;
240     }
241 }
242 StridedInterval & StridedInterval::operator = (const StridedInterval &rhs) {
243     stride = rhs.stride;
244     low = rhs.low;
245     high = rhs.high;
246     return *this;
247 }
248
249
250 bool StridedInterval::operator == (const StridedInterval &rhs) const {
251     if (stride != rhs.stride) return false;
252     if (low != rhs.low) return false;
253     if (high != rhs.high) return false;
254     return true;
255 }
256
257 bool StridedInterval::operator != (const StridedInterval &rhs) const {
258     return !(*this == rhs);
259 }
260
261
262 bool StridedInterval:: operator < (const StridedInterval &rhs) const {
263     if (stride != rhs.stride) return stride < rhs.stride;
264     if (low != rhs.low) return low < rhs.low;
265     return high < rhs.high;
266 }
267
268 void StridedInterval::Intersect(StridedInterval &rhs) {
269     if (stride == 0) {
270         if (rhs.stride == 0) {
271             if (low != rhs.low) {
272                 // Intersect two different constants,
273                 // we get an empty set
274                 *this = bottom;
275                 parsing_printf("Interval set to bottom!\n");
276             }
277         } else {
278             if (low < rhs.low || low > rhs.high || (low - rhs.low) % rhs.stride != 0) {
279                 // The constant is not in the rhs's interval
280                 *this = bottom;
281                 parsing_printf("Interval set to bottom!\n");
282             }
283         }
284     } else {
285         if (rhs.stride == 0) {
286             if (low > rhs.low || high < rhs.low  || ((rhs.low - low) % stride != 0)) {
287                 // The rhs is a constant and it is not in this interval
288                 *this = bottom;
289                 parsing_printf("Interval set to bottom!\n");
290             }
291             else {
292                 // The rhs is a constant and it is in this interval,
293                 // then rhs is the result of the intersection
294                 *this = rhs;
295             }
296         } else {
297             // Both are intervals
298             int64_t gcd = GCD(stride, rhs.stride);
299             if (low > rhs.high || high < rhs.low || (low - rhs.low) % gcd != 0) {
300                 *this = bottom;         
301             } else {
302                 int64_t x, k1, k2;
303                 ExtendEuclidean(stride / gcd, rhs.stride / gcd, k1, k2);
304                 x = (low - rhs.low) / gcd;
305                 k1 *= x;
306                 k2 *= -x;
307
308                 int newStride = stride * rhs.stride / GCD(stride, rhs.stride);
309                 int64_t newLow = low + k1 * stride, newHigh = high;
310                 if (newLow < low) newLow += ((low - newLow - 1) / newStride + 1) * newStride;
311                 if (newLow < rhs.low) newLow += ((rhs.low - newLow - 1) / newStride + 1) * newStride;
312                 if (rhs.high < newHigh) newHigh = rhs.high;
313                 if (newHigh < newLow) {
314                     *this = bottom;
315                 } else {
316                     newHigh -= (newHigh - newLow) % newStride;
317                     stride = newStride;
318                     low = newLow;
319                     high = newHigh;
320                 }
321             }
322         }
323     }
324 }
325
326 void StridedInterval::DeleteElement(int64_t val) {
327     // Need to figure out a general way to calculate it
328     if (val == low) low += stride;
329     if (val == high) low -= stride;
330 }
331
332 string StridedInterval::format() {
333     stringstream o;
334         o << stride << "[" << low << "," << high << "] ";
335         o << hex << stride << "[" << low << "," << high << "]";
336     return o.str();
337 }
338
339 uint64_t StridedInterval::size() const {
340     if (stride < 0) return 0;
341     else if (stride == 0) return 1;
342     else return (high - low) / stride;
343 }
344
345 bool StridedInterval::IsConst(int64_t v) const {
346     return (stride == 0) && (low == v) && (high == v);
347 }
348
349 bool StridedInterval::IsConst() const{
350     return stride == 0;
351 }
352
353 BoundValue::BoundValue(int64_t val):
354         interval(val), 
355         targetBase(0), 
356         isTableRead(false), 
357         isInverted(false),
358         isSubReadContent(false) {}
359
360 BoundValue::BoundValue(const StridedInterval &si):
361         interval(si), 
362         targetBase(0), 
363         isTableRead(false), 
364         isInverted(false),
365         isSubReadContent(false) {}
366
367 BoundValue::BoundValue():
368         interval(),
369         targetBase(0),
370         isTableRead(false),
371         isInverted(false),
372         isSubReadContent(false) {}
373
374 BoundValue::BoundValue(const BoundValue & bv):
375         targetBase(bv.targetBase),
376         isTableRead(bv.isTableRead),
377         isInverted(bv.isInverted),
378         isSubReadContent(bv.isSubReadContent) 
379 {
380     interval = bv.interval;
381 }
382
383
384 bool BoundValue::operator == (const BoundValue &bv) const {
385     return (interval == bv.interval) &&
386            (targetBase == bv.targetBase) &&
387            (isTableRead == bv.isTableRead) &&
388            (isInverted == bv.isInverted) &&
389            (isSubReadContent == bv.isSubReadContent);
390 }
391
392 bool BoundValue::operator != (const BoundValue &bv) const {
393     return !(*this == bv);
394 }
395
396 BoundValue & BoundValue::operator = (const BoundValue &bv) {
397
398     interval = bv.interval;
399     targetBase = bv.targetBase;
400     isTableRead = bv.isTableRead;
401     isInverted = bv.isInverted;
402     isSubReadContent = bv.isSubReadContent;
403     return *this;
404
405 }
406
407 void BoundValue::Print() {
408     parsing_printf("Interval %s, ", interval.format().c_str() );
409     parsing_printf("targetBase %lx, ",targetBase);
410     parsing_printf("isTableRead %d, ", isTableRead);
411     parsing_printf("isInverted %d, ", isInverted);
412     parsing_printf("isSubReadContent %d\n", isSubReadContent);
413 }
414
415
416
417 BoundValue* BoundFact::GetBound(const AST::Ptr ast) {
418     return GetBound(ast.get());
419 }
420
421 BoundValue* BoundFact::GetBound(const AST* ast) {
422     BoundValue *ret = NULL;
423     for (auto fit = fact.begin(); fit != fact.end(); ++fit)
424         if (*(fit->first) == *ast) {
425             ret = fit->second;
426             break;
427         }
428     return ret;
429 }
430
431 void BoundValue::IntersectInterval(StridedInterval &si) {
432     if (isTableRead) {
433         // We are not going to continue tracking
434         // how the memory read is used.
435         // The read contents can be anything, so set to top
436         *this = top;    
437     }
438     interval.Intersect(si);
439 }
440
441 void BoundValue::DeleteElementFromInterval(int64_t val) {
442     interval.DeleteElement(val);
443 }
444
445 void BoundValue::Join(BoundValue &bv) {
446     if (isTableRead != bv.isTableRead) {
447         // Unless boths are table reads, we stop trakcing
448         // how the read is used.
449         // Also, since a memory read can be any value,
450         // we set to top.
451         *this = top;
452     } else {
453         interval.Join(bv.interval);
454         if (targetBase != bv.targetBase) targetBase = 0;
455         if (isInverted != bv.isInverted) isInverted = false;
456         if (isSubReadContent != bv.isSubReadContent) isSubReadContent = false;
457     }
458 }
459
460 void BoundValue::ClearTableCheck(){
461     isTableRead = false;
462     targetBase = 0;
463     isInverted = false;
464     isSubReadContent = false;
465 }
466
467 void BoundValue::Add(const BoundValue &rhs) {
468     // First consider the case for: Imm - [table read address]
469     // where the isInverted is true
470     if (isTableRead && isInverted && rhs.interval.IsConst(1)) {
471         isInverted = false;
472         isSubReadContent = true;
473     } else if (rhs.isTableRead && rhs.isInverted && interval.IsConst(1)) {
474         *this = rhs;
475         isInverted = false;
476         isSubReadContent = true;
477     }
478     // Then check if we find the target base
479     else if (isTableRead && !isInverted && rhs.interval.IsConst() && !rhs.isTableRead) {
480         targetBase = rhs.interval.low;
481     } else if (rhs.isTableRead && !rhs.isInverted && interval.IsConst() && !isTableRead) {
482         int64_t val = interval.low;
483         *this = rhs;
484         targetBase = val;
485     } 
486     // In other case, we only track the values
487     else {
488         // If either one of the operand is a table read,
489         // then the result can be anything
490         if (isTableRead || rhs.isTableRead) {
491             *this = top;
492         } else {
493             interval.Add(rhs.interval);
494             ClearTableCheck();
495         }
496     }
497 }
498
499 void BoundValue::And(const BoundValue &rhs) { 
500     if (isTableRead) {        
501         // The memory read content can be anything
502         *this = top;
503     }
504     if (rhs.isTableRead)
505         interval.And(StridedInterval::top);
506     else
507         interval.And(rhs.interval);
508     
509     // The result is not a table read
510     ClearTableCheck();
511 }
512
513 void BoundValue::Mul(const BoundValue &rhs) { 
514     if (isTableRead) {        
515         // The memory read content can be anything
516         *this = top;
517     }
518     if (rhs.isTableRead)
519         interval.Mul(StridedInterval::top);
520     else
521         interval.Mul(rhs.interval);
522     
523     // The result is not a table read
524     ClearTableCheck();
525 }
526
527 void BoundValue::ShiftLeft(const BoundValue &rhs) {
528     if (isTableRead) {        
529         // The memory read content can be anything
530         *this = top;
531     }
532     if (rhs.isTableRead)
533         interval.ShiftLeft(StridedInterval::top);
534     else
535         interval.ShiftLeft(rhs.interval);
536     
537     // The result is not a table read
538     ClearTableCheck();
539 }
540 void BoundValue::ShiftRight(const BoundValue &rhs) {
541     if (isTableRead) {        
542         // The memory read content can be anything
543         *this = top;
544     }
545     if (rhs.isTableRead)
546         interval.ShiftRight(StridedInterval::top);
547     else
548         interval.ShiftRight(rhs.interval);
549     
550     // The result is not a table read
551     ClearTableCheck();
552 }
553
554 void BoundValue::Or(const BoundValue &rhs) { 
555     if (isTableRead) {        
556         // The memory read content can be anything
557         *this = top;
558     }
559     if (rhs.isTableRead)
560         interval.Or(StridedInterval::top);
561     else
562         interval.Or(rhs.interval);
563     
564     // The result is not a table read
565     ClearTableCheck();
566 }
567
568 void BoundValue::Invert() {
569     if (isTableRead) {        
570         // The memory read content can be anything
571         *this = top;
572     } else {
573         interval.Not();
574     }    
575     // The result is not a table read
576     ClearTableCheck();
577
578 }
579
580 static bool IsInReadOnlyRegion(Block *b, Address low, Address high) {   
581 #if defined(os_windows)
582     low -= b->obj()->cs()->loadAddress();
583     high -= b->obj()->cs()->loadAddress();
584 #endif
585         // Now let's assume it is always in a read only region
586         // unless it is reading a single memory location
587         return low != high;
588
589 }
590
591 static bool IsTableIndex(set<uint64_t> &values) {
592         // Check if this is a set of [0, high]
593         if (values.empty()) return false;
594         if (*(values.begin()) != 0) return false;
595         if (*(values.rbegin()) + 1 != values.size()) return false;
596         return true;
597 }
598
599 void BoundValue::MemoryRead(Block* b) {
600         if (interval != StridedInterval::top) {
601                 if (IsInReadOnlyRegion(b, interval.low, interval.high)) {
602                     set<uint64_t> values;
603                     Address memAddrLow = interval.low;
604                     Address memAddrHigh = interval.high;
605 #if defined(os_windows)
606                     memAddrLow -= b->obj()->cs()->loadAddress();
607                     memAddrHigh -= b->obj()->cs()->loadAddress();
608 #endif
609                     if (interval.size() <= MAX_TABLE_ENTRY && b->obj()->cs()->isValidAddress(memAddrLow)) {
610                         for (Address memAddr = memAddrLow ; memAddr <= memAddrHigh; memAddr += interval.stride) {
611                             if (!b->obj()->cs()->isValidAddress(memAddr)) {
612                                 parsing_printf("INVALID ADDRESS %lx\n", memAddr);
613                                 continue;                       
614                             }
615                             uint64_t val;
616                             switch (interval.stride) {
617                                 case 8:
618                                     val = *(const uint64_t *) b->obj()->cs()->getPtrToInstruction(memAddr);
619                                     break;
620                                 case 4:
621                                     val = *(const uint32_t *) b->obj()->cs()->getPtrToInstruction(memAddr);
622                                     break;
623                                 case 2:
624                                     val = *(const uint16_t *) b->obj()->cs()->getPtrToInstruction(memAddr);
625                                     break;
626                                 case 1:
627                                     val = *(const uint8_t *) b->obj()->cs()->getPtrToInstruction(memAddr);
628                                     break;
629                                 default:
630                                     parsing_printf("Invalid table stride %d\n", interval.stride);
631                                     *this = top;
632                                     return;
633                             }
634                             values.insert(val);
635                         }                                           
636                     }
637                     if (IsTableIndex(values)) {
638                         // This is a table for indexing a next level table
639                         interval.low = *(values.begin());
640                         interval.high = *(values.rbegin());
641                         interval.stride = 1;
642                         ClearTableCheck();
643                     } else {
644                         isTableRead = true;
645                     }
646             } 
647         }       
648 }
649
650 void BoundFact::Meet(BoundFact &bf) {
651         for (auto fit = fact.begin(); fit != fact.end();) {
652             BoundValue *val2 = bf.GetBound(fit->first);
653             // if ast fit->first cannot be found in bf,
654             // then fit->first is top on this path.
655             // Anything joins top becomes top
656             if (val2 != NULL) {
657                 BoundValue *val1 = fit->second;
658                 val1->Join(*val2);
659                 ++fit;
660             } else {
661                 auto toErase = fit;
662                 ++fit;
663                 if (toErase->second != NULL) delete toErase->second;
664                 fact.erase(toErase);
665             }
666         }
667
668         // Meet the relation vector     
669         for (auto rit = relation.begin(); rit != relation.end();) {
670             bool find = false;
671             for (auto it = bf.relation.begin(); it != bf.relation.end(); ++it)
672                 if (*((*rit)->left) == *((*it)->left) && *((*rit)->right) == *((*it)->right) && (*rit)->type == (*it)->type) {
673                     find = true;
674                     break;
675                 }
676             if (!find) {
677                 if (*rit != NULL) delete *rit;
678                 rit = relation.erase(rit);
679             } else ++rit;
680         }
681
682         // Meet the flag predicate
683         if (pred != bf.pred) pred.valid = false;
684
685         // Mee the alias map
686         for (auto ait = aliasMap.begin(); ait != aliasMap.end(); ) {
687             auto bit = bf.aliasMap.find(ait->first);
688             if (bit == bf.aliasMap.end() || !(*(ait->second) == *(bit->second))) {
689                 auto toErase = ait;
690                 ++ait;
691                 aliasMap.erase(toErase);
692             } else {
693                 ++ait;
694             }
695         }
696 }
697
698 void BoundFact::Print() {
699     if (pred.valid) {
700         parsing_printf("\t\t\tCurrent predicate:");
701         parsing_printf(" element 1 is %s;", pred.e1->format().c_str());
702         parsing_printf(" element 2 is %s\n", pred.e2->format().c_str());
703     } else
704         parsing_printf("\t\t\tDo not track predicate\n");
705     for (auto fit = fact.begin(); fit != fact.end(); ++fit) {
706         parsing_printf("\t\t\tVar: %s, ", fit->first->format().c_str());
707         fit->second->Print();
708     }
709     parsing_printf("\t\t\tRelations:\n");
710     for (auto rit = relation.begin(); rit != relation.end(); ++rit) {
711         parsing_printf("\t\t\t\t%s and %s, relation: %d\n", (*rit)->left->format().c_str(), (*rit)->right->format().c_str(), (*rit)->type);
712     }
713     parsing_printf("\t\t\tAliasing:\n");
714     for (auto ait = aliasMap.begin(); ait != aliasMap.end(); ++ait) {
715         parsing_printf("\t\t\t\t%s = %s\n", ait->first.format().c_str(), ait->second->format().c_str());
716     }
717 }
718
719 void BoundFact::GenFact(const AST::Ptr ast, BoundValue* bv, bool isConditionalJump) {
720     KillFact(ast);
721     fact.insert(make_pair(ast,bv));
722     for (auto rit = relation.begin(); rit != relation.end(); ++rit) {
723         if ((*rit)->type == Equal) {
724             if (*((*rit)->left) == *ast) fact.insert(make_pair((*rit)->right, new BoundValue(*bv)));
725             if (*((*rit)->right) == *ast) fact.insert(make_pair((*rit)->left, new BoundValue(*bv))); 
726         }
727     }
728
729     // Check alias
730     if (isConditionalJump && ast->getID() == AST::V_VariableAST) {
731         VariableAST::Ptr varAST = boost::static_pointer_cast<VariableAST>(ast);
732         const AbsRegion &ar = varAST->val().reg;
733         if (aliasMap.find(ar) != aliasMap.end() && aliasMap[ar]->getID() != AST::V_ConstantAST) {
734             fact.insert(make_pair(aliasMap[ar], new BoundValue(*bv)));
735         }
736     }
737 }
738
739 static bool IsSubTree(AST::Ptr tree, AST::Ptr sub) {
740     if (*tree == *sub) return true;
741     bool ret = false;
742     unsigned totalChildren = tree->numChildren();
743     for (unsigned i = 0 ; i < totalChildren && !ret; ++i) {
744         ret |= IsSubTree(tree->child(i), sub);
745     } 
746     return ret;
747 }
748
749 void BoundFact::KillFact(const AST::Ptr ast) {
750     for (auto fit = fact.begin(); fit != fact.end();)
751         if (IsSubTree(fit->first, ast)) {
752             auto toErase = fit;
753             ++fit;
754             if (toErase->second != NULL) delete toErase->second;
755             fact.erase(toErase);
756         } else ++fit;
757     // It also affects the relation map
758     for (auto rit = relation.begin(); rit != relation.end();) {
759         // If the one of them is changed,
760         // we no longer know their relationship
761         if (*((*rit)->left) == *ast || *((*rit)->right) == *ast) {
762             if (*rit != NULL) delete *rit;
763             rit = relation.erase(rit);
764         } else ++rit;
765     }
766 }
767
768
769 bool BoundFact::operator != (const BoundFact &bf) const {    
770     if (pred != bf.pred) return true; 
771     if (fact.size() != bf.fact.size()) return true;
772     if (relation.size() != bf.relation.size()) return true;
773     for (size_t i = 0; i < relation.size(); ++i)
774         if (*relation[i] != *bf.relation[i]) return true;
775     if (aliasMap.size() != bf.aliasMap.size()) return true;
776     for (auto ait = aliasMap.begin(); ait != aliasMap.end(); ++ait) {
777         auto bit = bf.aliasMap.find(ait->first);
778         if (bit == bf.aliasMap.end()) return true;
779         if (!(*(ait->second) == *(bit->second))) return true;
780     }
781     return !equal(fact.begin(), fact.end(), bf.fact.begin());
782 }
783
784 BoundFact::BoundFact() {
785     fact.clear();
786     relation.clear();
787     aliasMap.clear();
788 }
789
790 BoundFact::~BoundFact() {
791     for (auto fit = fact.begin(); fit != fact.end(); ++fit)
792         if (fit->second != NULL)
793             delete fit->second;
794     fact.clear();   
795     for (auto rit = relation.begin(); rit != relation.end(); ++rit)
796         if (*rit != NULL)
797             delete *rit;
798     relation.clear();
799     aliasMap.clear();
800 }
801
802 BoundFact& BoundFact::operator = (const BoundFact &bf) {
803     pred = bf.pred;
804     for (auto fit = fact.begin(); fit != fact.end(); ++fit)
805         if (fit->second != NULL) delete fit->second;
806     fact.clear();
807     for (auto fit = bf.fact.begin(); fit != bf.fact.end(); ++fit)     
808         fact.insert(make_pair(fit->first, new BoundValue(*(fit->second))));
809
810     for (auto rit = relation.begin(); rit != relation.end(); ++rit)
811         if (*rit != NULL) delete *rit;
812     relation.clear();
813     for (auto rit = bf.relation.begin(); rit != bf.relation.end(); ++rit)
814         relation.push_back(new RelationShip(**rit));
815     aliasMap = bf.aliasMap;
816
817     return *this;
818 }
819
820 BoundFact::BoundFact(const BoundFact &bf) {
821     *this = bf;
822 }   
823
824
825 bool BoundFact::ConditionalJumpBound(Instruction::Ptr insn, EdgeTypeEnum type) {
826     if (!pred.valid) {
827         parsing_printf("WARNING: We reach a conditional jump, but have not tracked the flag! Do nothing and return\n");
828         return true;
829     }
830     entryID id = insn->getOperation().getID();
831     parsing_printf("\t\tproduce conditional bound for %s, edge type %d\n", insn->format().c_str(), type);
832     if (type == COND_TAKEN) {
833         switch (id) {
834             // unsigned 
835             case e_jnbe: {
836                 if (pred.e1->getID() == AST::V_ConstantAST) {
837                     if (pred.e2->getID() == AST::V_ConstantAST) {
838                         // If both elements are constant,
839                         // it means the conditional jump is actually unconditional.
840                         // It is possible to happen, but should be unlikely 
841                         parsing_printf("WARNING: both predicate elements are constants!\n");
842                     } else {
843                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
844                         GenFact(pred.e2, new BoundValue(StridedInterval(1, 0, constAST->val().val - 1)), true);
845                     }
846                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
847                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
848                     IntersectInterval(pred.e1, StridedInterval(1, constAST->val().val + 1, StridedInterval::maxValue));
849                 } else {
850                     relation.push_back(new RelationShip(pred.e1, pred.e2,UnsignedLargerThan));
851                 }
852                 break;
853             }
854             case e_jnb: 
855             case e_jnb_jae_j: {
856                 if (pred.e1->getID() == AST::V_ConstantAST) {
857                     if (pred.e2->getID() == AST::V_ConstantAST) {
858                         parsing_printf("WARNING: both predicate elements are constants!\n");
859                     } else {
860                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
861                         GenFact(pred.e2, new BoundValue(StridedInterval(1, 0, constAST->val().val)), true);
862                     }
863                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
864                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
865                     IntersectInterval(pred.e1, StridedInterval(1, constAST->val().val, StridedInterval::maxValue));
866                 } else {
867                     relation.push_back(new RelationShip(pred.e1, pred.e2, UnsignedLargerThanOrEqual));
868                 }
869                 break;
870             }
871             case e_jb: 
872             case e_jb_jnaej_j: {
873                 if (pred.e1->getID() == AST::V_ConstantAST) {
874                     if (pred.e2->getID() == AST::V_ConstantAST) {
875                         parsing_printf("WARNING: both predicate elements are constants!\n");
876                     } else {
877                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
878                         IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val + 1, StridedInterval::maxValue));
879                     }
880                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
881                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
882                     // Assuming a-loc pred.e1 is always used as 
883                     // unsigned value before it gets rewritten.
884                     GenFact(pred.e1, new BoundValue(StridedInterval(1, 0 , constAST->val().val - 1)), true);
885                 } else {
886                     relation.push_back(new RelationShip(pred.e1, pred.e2, UnsignedLessThan));
887                 }
888                 break;
889             }
890             case e_jbe: {
891                 if (pred.e1->getID() == AST::V_ConstantAST) {
892                     if (pred.e2->getID() == AST::V_ConstantAST) {
893                         parsing_printf("WARNING: both predicate elements are constants!\n");
894                     } else {
895                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
896                         IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val, StridedInterval::maxValue));
897                     }
898                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
899                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
900                     // Assuming a-loc pred.e1 is always used as 
901                     // unsigned value before it gets rewritten.
902                     GenFact(pred.e1, new BoundValue(StridedInterval(1, 0 , constAST->val().val)), true);
903                 } else {
904                     relation.push_back(new RelationShip(pred.e1, pred.e2,UnsignedLessThanOrEqual));
905                 }
906                 break;
907             }
908             case e_jz: {
909                 if (pred.e1->getID() == AST::V_ConstantAST) {
910                     if (pred.e2->getID() == AST::V_ConstantAST) {
911                         parsing_printf("WARNING: both predicate elements are constants!\n");
912                     } else {
913                         // the predicate sometimes is between the low 8 bits of a register
914                         // and a constant. If I simply extends the predicate to the whole
915                         // 64 bits of a register. I may get wrong constant value. 
916                         // IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val, constAST->val().val));
917                         parsing_printf("WARNING: do not track equal predicate\n");
918                     }
919                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
920                     parsing_printf("WARNING: do not track equal predicate\n");
921                     //IntersectInterval(pred.e1, StridedInterval(0, constAST->val().val , constAST->val().val));
922                 } else {
923                     relation.push_back(new RelationShip(pred.e1, pred.e2,Equal));
924                 }
925                 break;
926             }
927             case e_jnz: {
928                 if (pred.e1->getID() == AST::V_ConstantAST) {
929                     if (pred.e2->getID() == AST::V_ConstantAST) {
930                         parsing_printf("WARNING: both predicate elements are constants!\n");
931                     } else {
932                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
933                         DeleteElementFromInterval(pred.e2, constAST->val().val);
934                     }
935                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
936                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
937                     DeleteElementFromInterval(pred.e1, constAST->val().val);
938                 } else {
939                     relation.push_back(new RelationShip(pred.e1, pred.e2, NotEqual));
940                 }
941                 break;
942             }
943
944             // signed
945             case e_jnle: {
946                 if (pred.e1->getID() == AST::V_ConstantAST) {
947                     if (pred.e2->getID() == AST::V_ConstantAST) {
948                         parsing_printf("WARNING: both predicate elements are constants!\n");
949                     } else {
950                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
951                         IntersectInterval(pred.e2, StridedInterval(1, 0 , constAST->val().val - 1));
952                     }
953                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
954                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
955                     IntersectInterval(pred.e1, StridedInterval(1, constAST->val().val + 1, StridedInterval::maxValue));
956                 } else {
957                     relation.push_back(new RelationShip(pred.e1, pred.e2, SignedLargerThan));
958                 }
959                 break;
960             }
961             case e_jnl: {
962                 if (pred.e1->getID() == AST::V_ConstantAST) {
963                     if (pred.e2->getID() == AST::V_ConstantAST) {
964                         parsing_printf("WARNING: both predicate elements are constants!\n");
965                     } else {
966                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
967                         IntersectInterval(pred.e2, StridedInterval(1, 0, constAST->val().val));
968                     }
969                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
970                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
971                     IntersectInterval(pred.e1, StridedInterval(1, constAST->val().val, StridedInterval::maxValue));
972                 } else {
973                     relation.push_back(new RelationShip(pred.e1, pred.e2,SignedLargerThanOrEqual));
974                 }
975                 break;
976             }
977             case e_jl: {
978                 if (pred.e1->getID() == AST::V_ConstantAST) {
979                     if (pred.e2->getID() == AST::V_ConstantAST) {
980                         parsing_printf("WARNING: both predicate elements are constants!\n");
981                     } else {
982                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
983                         IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val + 1, StridedInterval::maxValue));
984                     }
985                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
986                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
987                     IntersectInterval(pred.e1, StridedInterval(1,  0 , constAST->val().val - 1));
988                 } else {
989                     relation.push_back(new RelationShip(pred.e1, pred.e2,SignedLessThan));
990                 }
991                 break;
992
993             }
994             case e_jle: {
995                 if (pred.e1->getID() == AST::V_ConstantAST) {
996                     if (pred.e2->getID() == AST::V_ConstantAST) {
997                         parsing_printf("WARNING: both predicate elements are constants!\n");
998                     } else {
999                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1000                         IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val, StridedInterval::maxValue));
1001                     }
1002                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1003                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1004                     IntersectInterval(pred.e1, StridedInterval(1, 0 , constAST->val().val));
1005                 } else {
1006                     relation.push_back(new RelationShip(pred.e1, pred.e2,SignedLessThanOrEqual));
1007                 }
1008                 break;
1009             }
1010             default:
1011                 fprintf(stderr, "Unhandled conditional jump type. entry id is %d\n", id);
1012         }
1013
1014     } else if (type == COND_NOT_TAKEN) {
1015         // the following switch statement is almost
1016         // the same as the above one, except case label
1017         // all cases of e_jnxx corresponds to cases of e_jxx
1018         // and cases of e_jxx corresponds to cases of e_jnxx
1019         switch (id) {
1020             // unsigned 
1021             case e_jbe: {
1022                 if (pred.e1->getID() == AST::V_ConstantAST) {
1023                     if (pred.e2->getID() == AST::V_ConstantAST) {
1024                         // If both elements are constant,
1025                         // it means the conditional jump is actually unconditional.
1026                         // It is possible to happen, but should be unlikely 
1027                         parsing_printf("WARNING: both predicate elements are constants!\n");
1028                     } else {
1029                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1030                         GenFact(pred.e2, new BoundValue(StridedInterval(1, 0, constAST->val().val - 1)), true);
1031                     }
1032                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1033                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1034                     IntersectInterval(pred.e1, StridedInterval(1, constAST->val().val + 1, StridedInterval::maxValue));
1035                 } else {
1036                     relation.push_back(new RelationShip(pred.e1, pred.e2,UnsignedLargerThan));
1037                 }
1038                 break;
1039             }
1040             case e_jb: 
1041             case e_jb_jnaej_j: {
1042                 if (pred.e1->getID() == AST::V_ConstantAST) {
1043                     if (pred.e2->getID() == AST::V_ConstantAST) {
1044                         parsing_printf("WARNING: both predicate elements are constants!\n");
1045                     } else {
1046                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1047                         GenFact(pred.e2, new BoundValue(StridedInterval(1, 0, constAST->val().val)), true);
1048                     }
1049                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1050                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1051                     IntersectInterval(pred.e1, StridedInterval(1, constAST->val().val, StridedInterval::maxValue));
1052                 } else {
1053                     relation.push_back(new RelationShip(pred.e1, pred.e2 ,UnsignedLargerThanOrEqual));
1054                 }
1055                 break;
1056             }
1057             case e_jnb:
1058             case e_jnb_jae_j: {
1059                 if (pred.e1->getID() == AST::V_ConstantAST) {
1060                     if (pred.e2->getID() == AST::V_ConstantAST) {
1061                         parsing_printf("WARNING: both predicate elements are constants!\n");
1062                     } else {
1063                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1064                         IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val + 1, StridedInterval::maxValue));
1065                     }
1066                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1067                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1068                     // Assuming a-loc pred.e1 is always used as 
1069                     // unsigned value before it gets rewritten.
1070                     GenFact(pred.e1, new BoundValue(StridedInterval(1, 0 , constAST->val().val - 1)), true);
1071                 } else {
1072                     relation.push_back(new RelationShip(pred.e1, pred.e2, UnsignedLessThan));
1073                 }
1074                 break;
1075             }
1076             case e_jnbe: {
1077                 if (pred.e1->getID() == AST::V_ConstantAST) {
1078                     if (pred.e2->getID() == AST::V_ConstantAST) {
1079                         parsing_printf("WARNING: both predicate elements are constants!\n");
1080                     } else {
1081                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1082                         IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val, StridedInterval::maxValue));
1083                     }
1084                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1085                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1086                     // Assuming a-loc pred.e1 is always used as 
1087                     // unsigned value before it gets rewritten.
1088                     GenFact(pred.e1, new BoundValue(StridedInterval(1, 0 , constAST->val().val)), true);
1089                 } else {
1090                     relation.push_back(new RelationShip(pred.e1, pred.e2, UnsignedLessThanOrEqual));
1091                 }
1092                 break;
1093             }
1094             case e_jnz: {
1095                 if (pred.e1->getID() == AST::V_ConstantAST) {
1096                     if (pred.e2->getID() == AST::V_ConstantAST) {
1097                         parsing_printf("WARNING: both predicate elements are constants!\n");
1098                     } else {
1099                         parsing_printf("WARNING: do not track equal predicate\n");
1100                         //IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val, constAST->val().val));
1101                     }
1102                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1103                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1104                     // the predicate sometimes is between the low 8 bits of a register
1105                     // and a constant. If I simply extends the predicate to the whole
1106                     // 64 bits of a register. I may get wrong constant value. 
1107                     // IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val, constAST->val().val));
1108                     parsing_printf("WARNING: do not track equal predicate\n");
1109                     //IntersectInterval(pred.e1, StridedInterval(0, constAST->val().val , constAST->val().val));
1110                 } else {
1111                     relation.push_back(new RelationShip(pred.e1, pred.e2, Equal));
1112                 }
1113                 break;
1114             }
1115             case e_jz: {
1116                 if (pred.e1->getID() == AST::V_ConstantAST) {
1117                     if (pred.e2->getID() == AST::V_ConstantAST) {
1118                         parsing_printf("WARNING: both predicate elements are constants!\n");
1119                     } else {
1120                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1121                         DeleteElementFromInterval(pred.e2, constAST->val().val);
1122                     }
1123                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1124                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1125                     DeleteElementFromInterval(pred.e1, constAST->val().val);
1126                 } else {
1127                     relation.push_back(new RelationShip(pred.e1, pred.e2,NotEqual));
1128                 }
1129                 break;
1130             }
1131
1132             // signed
1133             case e_jle: {
1134                 if (pred.e1->getID() == AST::V_ConstantAST) {
1135                     if (pred.e2->getID() == AST::V_ConstantAST) {
1136                         parsing_printf("WARNING: both predicate elements are constants!\n");
1137                     } else {
1138                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1139                         IntersectInterval(pred.e2, StridedInterval(1, 0, constAST->val().val - 1));
1140                     }
1141                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1142                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1143                     IntersectInterval(pred.e1, StridedInterval(1, constAST->val().val + 1, StridedInterval::maxValue));
1144                 } else {
1145                     relation.push_back(new RelationShip(pred.e1, pred.e2, SignedLargerThan));
1146                 }
1147                 break;
1148             }
1149             case e_jl: {
1150                 if (pred.e1->getID() == AST::V_ConstantAST) {
1151                     if (pred.e2->getID() == AST::V_ConstantAST) {
1152                         parsing_printf("WARNING: both predicate elements are constants!\n");
1153                     } else {
1154                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1155                         IntersectInterval(pred.e2, StridedInterval(1, 0, constAST->val().val));
1156                     }
1157                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1158                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1159                     IntersectInterval(pred.e1, StridedInterval(1, constAST->val().val, StridedInterval::maxValue));
1160                 } else {
1161                     relation.push_back(new RelationShip(pred.e1, pred.e2, SignedLargerThanOrEqual));
1162                 }
1163                 break;
1164             }
1165             case e_jnl: {
1166                 if (pred.e1->getID() == AST::V_ConstantAST) {
1167                     if (pred.e2->getID() == AST::V_ConstantAST) {
1168                         parsing_printf("WARNING: both predicate elements are constants!\n");
1169                     } else {
1170                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1171                         IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val + 1, StridedInterval::maxValue));
1172                     }
1173                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1174                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1175                     IntersectInterval(pred.e1, StridedInterval(1, 0 , constAST->val().val - 1));
1176                 } else {
1177                     relation.push_back(new RelationShip(pred.e1, pred.e2,SignedLessThan));
1178                 }
1179                 break;
1180
1181             }
1182             case e_jnle: {
1183                 if (pred.e1->getID() == AST::V_ConstantAST) {
1184                     if (pred.e2->getID() == AST::V_ConstantAST) {
1185                         parsing_printf("WARNING: both predicate elements are constants!\n");
1186                     } else {
1187                         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1188                         IntersectInterval(pred.e2, StridedInterval(1, constAST->val().val, StridedInterval::maxValue));
1189                     }
1190                 } else if (pred.e2->getID() == AST::V_ConstantAST) {
1191                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1192                     IntersectInterval(pred.e1, StridedInterval(1, 0 , constAST->val().val));
1193                 } else {
1194                     relation.push_back(new RelationShip(pred.e1, pred.e2,SignedLessThanOrEqual));
1195                 }
1196                 break;
1197             }
1198             default:
1199                 fprintf(stderr, "Unhandled conditional jump type. entry id is %d\n", id);
1200                 assert(0);
1201         }
1202
1203     } else {
1204         fprintf(stderr, "Instruction %s\n", insn->format().c_str());
1205         fprintf(stderr, "type should be either COND_TAKEN or COND_NOT_TAKEN");
1206         return false;
1207     }
1208
1209     if (pred.id == e_sub) {
1210         if (pred.e2->getID() == AST::V_ConstantAST) {
1211             BoundValue *val = GetBound(pred.e1);
1212             if (val != NULL) {
1213                 ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e2);
1214                 val->interval.Sub(StridedInterval(constAST->val().val));
1215             }
1216         } else if (pred.e1->getID() == AST::V_ConstantAST) {
1217             BoundValue *val = GetBound(pred.e2);
1218             if (val != NULL) {
1219                 ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(pred.e1);
1220                 val->interval.Sub(StridedInterval(constAST->val().val));
1221             }
1222
1223         }
1224     }
1225     return true;
1226 }
1227
1228
1229 void BoundFact::SetPredicate(Assignment::Ptr assign ) {   
1230     Instruction::Ptr insn = assign->insn();
1231     entryID id = insn->getOperation().getID();
1232     pred.valid = true;
1233     parsing_printf("\t\tLook for predicates for instruction %s, assign %s\n", insn->format().c_str(), assign->format().c_str());
1234     pair<AST::Ptr, bool> expandRet = SymEval::expand(assign, false);
1235     if (expandRet.first == NULL) {
1236         // If the instruction is outside the set of instrutions we
1237         // add instruction semantics. We assume this instruction
1238         // kills all bound fact.
1239         parsing_printf("\t\t (Should not happen here) No semantic support for this instruction. Kill all bound fact\n");
1240         SetToBottom();
1241         return;
1242     }
1243     parsing_printf("\t\texpand to %s\n", expandRet.first->format().c_str());
1244     AST::Ptr simplifiedAST = SimplifyAnAST(expandRet.first, insn->size());
1245     parsing_printf("\t\tafter simplifying %s\n", simplifiedAST->format().c_str());
1246     switch (id) {
1247         case e_cmp:
1248         case e_sub: {   
1249             ComparisonVisitor cv;
1250             expandRet.first->accept(&cv);
1251             pred.e1 = cv.subtrahend;
1252             pred.e2 = cv.minuend; 
1253             pred.id = id;
1254             // The effect of the subtraction can only
1255             // be evaluated when there is a conditional jump
1256             // after it. Currently, we do not know anything.
1257             break;
1258         }
1259         case e_test: {
1260             if (simplifiedAST->getID() == AST::V_RoseAST) {
1261                 RoseAST::Ptr rootRoseAST = boost::static_pointer_cast<RoseAST>(simplifiedAST);
1262                 if (rootRoseAST->val().op == ROSEOperation::equalToZeroOp && 
1263                     rootRoseAST->child(0)->getID() == AST::V_RoseAST) {
1264                     RoseAST::Ptr childAST = boost::static_pointer_cast<RoseAST>(rootRoseAST->child(0));
1265                     if (childAST->val().op == ROSEOperation::andOp) {
1266                         if (*childAST->child(0) == *childAST->child(1)) {
1267                             pred.e1 = childAST->child(0);
1268                             pred.e2 = ConstantAST::create(Constant(0));
1269                             pred.id = id;
1270                             break;
1271                         }
1272                         else {
1273                             parsing_printf("\t\t For test instruction, now only handle the case where two operands are the same\n");
1274                         }
1275                     }
1276                 }
1277             }
1278             pred.valid = false;
1279             break;
1280         }
1281         case e_and: {
1282             if (simplifiedAST->getID() == AST::V_RoseAST) {
1283                 RoseAST::Ptr rootRoseAST = boost::static_pointer_cast<RoseAST>(simplifiedAST);
1284                 if (rootRoseAST->val().op == ROSEOperation::equalToZeroOp && 
1285                     rootRoseAST->child(0)->getID() == AST::V_RoseAST) {
1286                     RoseAST::Ptr childAST = boost::static_pointer_cast<RoseAST>(rootRoseAST->child(0));
1287                     if (childAST->val().op == ROSEOperation::andOp) {
1288                         // The effect of the and instruction can be 
1289                         // evaluated now. And the predicate is actually
1290                         // simply comparing value to 0
1291                         if (childAST->child(1)->getID() == AST::V_ConstantAST) {
1292                             ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(childAST->child(1));
1293                             StridedInterval si(1,0,constAST->val().val);
1294                             IntersectInterval(childAST->child(0), si);
1295                             pred.e1 = childAST->child(0);
1296                             pred.e2 = ConstantAST::create(Constant(0));
1297                             pred.id = id;
1298                             break;
1299                         } else if (childAST->child(0)->getID() == AST::V_ConstantAST){
1300                             ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(childAST->child(0));
1301                             StridedInterval si(1,0,constAST->val().val);
1302                             IntersectInterval(childAST->child(1), si);
1303                             pred.e1 = ConstantAST::create(Constant(0));
1304                             pred.e2 = childAST->child(0);
1305                             pred.id = id;
1306                             break;
1307                         } else {
1308                             parsing_printf("\t\t None of the operands is constant, do not handle this case\n");
1309                         }
1310                     }
1311                 }
1312             }
1313             pred.valid = false;
1314             break;
1315         }
1316         default:
1317             parsing_printf("Not tracking this instruction that sets flags: %s\n", insn->format().c_str());
1318             pred.valid = false;
1319     }
1320 }
1321
1322 void BoundFact::SetToBottom() {
1323     pred.valid = false;
1324     relation.clear();
1325     for (auto fit = fact.begin(); fit != fact.end(); ++fit) 
1326         if (fit->second != NULL)
1327             delete fit->second;
1328     fact.clear();
1329     aliasMap.clear();
1330 }
1331
1332 void BoundFact::IntersectInterval(const AST::Ptr ast, StridedInterval si) {
1333     BoundValue *bv = GetBound(ast);
1334     if (bv != NULL) {
1335         GenFact(ast, new BoundValue(si), true);
1336 //        bv->IntersectInterval(si); 
1337     } else {
1338         // If the fact value does not exist,
1339         // it means it is top and can be any value.
1340         fact.insert(make_pair(ast, new BoundValue(si)));
1341     }
1342 }
1343
1344 void BoundFact::DeleteElementFromInterval(const AST::Ptr ast, int64_t val) {
1345     BoundValue *bv = GetBound(ast);
1346     if (bv != NULL) {
1347         bv->DeleteElementFromInterval(val);
1348     }
1349 }
1350
1351 void BoundFact::InsertRelation(AST::Ptr left, AST::Ptr right, RelationType r) {
1352     parsing_printf("\t\t\t inserting relation %s and %s, type %d\n",left->format().c_str(), right->format().c_str(), r); 
1353     relation.push_back(new RelationShip(left, right, r));
1354 }
1355
1356 void BoundFact::AdjustPredicate(AST::Ptr out, AST::Ptr in) {
1357     if (!pred.valid) return;
1358     if (*out == *pred.e1 && pred.e2->getID() == AST::V_ConstantAST) {
1359         parsing_printf("\t\t\t Adjust predicate\n");
1360         if (in->getID() == AST::V_RoseAST) {
1361             RoseAST::Ptr root = boost::static_pointer_cast<RoseAST>(in);
1362             if (root->val().op == ROSEOperation::addOp && *pred.e1 == *(root->child(0)) && in->child(1)->getID() == AST::V_ConstantAST) {
1363                 ConstantAST::Ptr v1 = boost::static_pointer_cast<ConstantAST>(pred.e2);
1364                 ConstantAST::Ptr v2 = boost::static_pointer_cast<ConstantAST>(in->child(1));
1365                 uint64_t newV = v1->val().val + v2->val().val;
1366                 pred.e2 = ConstantAST::create(Constant(newV, v1->val().size));
1367             }
1368         }
1369
1370     } else if (*out == *pred.e2 && pred.e1->getID() == AST::V_ConstantAST) {
1371         parsing_printf("\t\t\t Adjust predicate\n");
1372         if (in->getID() == AST::V_RoseAST) {
1373             RoseAST::Ptr root = boost::static_pointer_cast<RoseAST>(in);
1374             if (root->val().op == ROSEOperation::addOp && *pred.e2 == *(root->child(0)) && in->child(1)->getID() == AST::V_ConstantAST) {
1375                 ConstantAST::Ptr v1 = boost::static_pointer_cast<ConstantAST>(pred.e1);
1376                 ConstantAST::Ptr v2 = boost::static_pointer_cast<ConstantAST>(in->child(1));
1377                 uint64_t newV = v1->val().val + v2->val().val;
1378                 pred.e1 = ConstantAST::create(Constant(newV, v1->val().size));
1379             }
1380         }
1381
1382     }
1383 }
1384
1385 void BoundFact::TrackAlias(AST::Ptr expr, AbsRegion ar) {
1386     expr = SubstituteAnAST(expr, aliasMap);
1387     aliasMap[ar] = expr;
1388     BoundValue *substiBound = GetBound(expr);
1389     if (substiBound != NULL) {
1390         GenFact(VariableAST::create(Variable(ar)), new BoundValue(*substiBound), false);
1391     }
1392 }