| Polaris: range.h Source File | ||
|
Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members
range.hGo to the documentation of this file.00001 /// 00002 /// 00003 /// range.h 00004 /// 00005 #ifndef _RANGE_H 00006 #define _RANGE_H 00007 /// 00008 /// \class propagate 00009 /// \brief ranges pass - Propagate variable constraints throughout a program 00010 /// \defgroup Polaris 00011 /// \ingroup Polaris 00012 /// Range 00013 /// \see range.h 00014 /// \see range.h 00015 /// \see range.cc 00016 /// 00017 /// \endcode 00018 /// \section Overview Overview 00019 /// The propagate ranges pass generates the sets of variable 00020 /// constraints that hold for each Statement in the given program 00021 /// units. These variable constraints can then be used for the 00022 /// comparison of expressions at particular points in a program. 00023 /// 00024 /// \endcode 00025 /// \section Description Description 00026 /// In our experience, symbolic expression handling in compiler passes 00027 /// often need to compare symbolic expressions within a particular 00028 /// context. For example, is A < B within loop C? To support such 00029 /// operations, the range propagation pass was developed. This pass is 00030 /// essentially composed of two parts: (1) an algorithm to compute the 00031 /// contextual information needed to compare expressions, and (2) 00032 /// routines that compare expressions using this information. 00033 /// 00034 /// The two main classes of this pass are RangeDict and RangeAccessor. 00035 /// RangeDict objects are responsible for computing and storing the 00036 /// ranges of a program unit. RangeAccessor objects are responsible 00037 /// for comparing expressions using the ranges contained in the 00038 /// RangeDict object. 00039 /// 00040 /// The ranges of a program unit are calculated by calling the 00041 /// constructor of a subclass of RangeDict. (RangeDict is abstract, 00042 /// so you cannot call its constructor.) However, RangeDict does 00043 /// not offer any direct method to access these ranges. To use or 00044 /// temporarily modify the ranges in a RangeDict, one must create 00045 /// a RangeAccessor object. 00046 /// 00047 /// Comparison of expressions is done through the compare() method in 00048 /// RangeAccessor, (actually, the method itself is in its abstract 00049 /// superclass, RangeComparator). The compare() method determines the 00050 /// arithmatic relationship (i.e. <, =, >) between two expressions. A 00051 /// similar method is the sign() method, which determines the sign of 00052 /// an expression. See RangeAccessor.h, RangeComparator.h and 00053 /// Relation.h for more details. 00054 /// 00055 /// \endcode 00056 /// \section Examples Examples 00057 /// An example of using the range propagation pass is below. This code 00058 /// fragment prints out all zero-trip loops in a ProgramUnit named pgm: 00059 /// 00060 /// \code 00061 /// // Calculate the constraints for all the statements in the 00062 /// // program. 00063 /// 00064 /// AIRangeDict ranges(pgm); 00065 /// 00066 /// // Examine each DO loop in the program. 00067 /// 00068 /// Iterator<Statement> do_iter = pgm.stmts().stmts_of_type(DO_STMT); 00069 /// 00070 /// for ( ; do_iter.valid(); ++do_iter) { 00071 /// Statement &do_loop = do_iter.current(); 00072 /// RangeAccessor loop_ranges(ranges, do_loop); 00073 /// 00074 /// // Compare the lower and upper bounds of the DO statement. 00075 /// 00076 /// Relation bounds_rel = loop_ranges.compare(do_loop.init(), 00077 /// do_loop.limit()); 00078 /// 00079 /// // Now, determine whether the loop is a zero-trip loop, 00080 /// // based upon the results of the comparison above and upon 00081 /// // the sign of the loop's stride. 00082 /// 00083 /// switch (loop_ranges.sign(do_loop.stride())) { 00084 /// case POS_EXPR: 00085 /// // Loop has a positive stride 00086 /// if (bounds_rel.is_greater_than()) 00087 /// cout << "Loop: " << do_loop 00088 /// << " is a zero-trip loop\n"; 00089 /// break; 00090 /// 00091 /// case NEG_EXPR: 00092 /// // Loop has a negative stride 00093 /// if (bounds_rel.is_less_than()) 00094 /// cout << "Loop: " << do_loop 00095 /// << " is a zero-trip loop\n"; 00096 /// break; 00097 /// 00098 /// case POS_NEG_EXPR: 00099 /// // Loop may have a positive or negative stride; 00100 /// break; 00101 /// } 00102 /// } 00103 /// 00104 /// \endcode 00105 /// \section Switches Switches 00106 /// Switch "range_acc" is used to specify the default range join 00107 /// accuracy used by the range comparator when performing unions and 00108 /// intersections. See the methods range_join_accuracy() in 00109 /// RangeComparator.h for more details. 00110 /// 00111 /// By setting "range_block" to 1, the AIRangeDict constructor 00112 /// would automatically clear all ranges whenever it sees a BEGIN 00113 /// BLOCK or END BLOCK assertion when it is computing ranges. 00114 /// This switch should approximate the ranges computed for uninlined 00115 /// programs when run on a partially or fully inlined program. 00116 /// Basically, this switch causes the AIRangeDict to compute less 00117 /// accurate ranges so to increase speed and decrease memory used. 00118 /// 00119 /// Setting switch "pc_call_mods" to 1 causes the constructors of 00120 /// AIRangeDict and ControlRangeDict to assume that subroutine and 00121 /// function calls only modify thier arguments. That is, global 00122 /// varaibles and subroutine parameters are assumed to be unmodified 00123 /// by a subroutine call unless they also appear in that call's 00124 /// arguments. Results in more accurate ranges. May also result in 00125 /// incorrect ranges, if this assumption does not hold in actuality. 00126 /// 00127 /// \endcode 00128 /// \section Known Known bugs or limitations 00129 /// Expression comparisons can be very slow for certain types of 00130 /// expressions and ranges. Such expressions tend be very large, 00131 /// contain a mixture of intrinsic operations, have integer divisions, 00132 /// and/or use variables whose ranges are very large and reference each 00133 /// other a lot. Often, when a RangeDict object seems to be taking 00134 /// too much time to compute the ranges of some program, it is 00135 /// because it is performing one or more of these very expensive 00136 /// expression comparisons. 00137 /// 00138 /// AIRangeDict objects can consume large amounts of time and large 00139 /// amounts of memory. This is because the time and space requirements 00140 /// are O(V*S), where S is the number of statements in a program and 00141 /// V is the number of integer variables in a program. (In actuality, 00142 /// V can be improved to be the average number of integer variables 00143 /// that have constraints.) If one is willing to sacrifice some accuracy 00144 /// of the computed ranges, one can instead use ControlRangeDict, 00145 /// whose typical time and space requirements are much smaller. 00146 /// Another alternative is to set the switch "range_block" to 1. 00147 /// 00148 /// AIRangeDicts currently cannot handle GSA programs. 00149 /// 00150 /// RangeDict objects may act strangely when programs are modified, 00151 /// AIRangeDict and ControlRangeDict objects may possibly return incorrect 00152 /// ranges. More specifically, they would return the ranges that 00153 /// held before the modifications. GSAControlRangeDict and 00154 /// GSAFullRangeDict objects may return incorrect ranges or crash. 00155 /// 00156 #endif 00157 /// |
||
|