-These are simple guidelines:
-- Only simple comparisons between variables are understood.
-- Only increment-decrement operations are handled.
-- "switch" statements are not yet handled.
-
-This means that code like this will be handled well:
-
-for (int i = 0; i < a.Length; i++) {
- a [i] = .....
-}
-
-The "i" variable could be declared out of the "for", the "for" could be a
-"while", and maybe even implemented with "goto", the array could be scanned
-in reverse order, and everything would still work.
-I could have a temporary variable storing the array length, and check on
-it inside the loop, and the abc removal would still occurr, like this:
-
-int i = 0;
-int l = a.Length;
-while ( i < l ) {
- a [i] ......
-}
-
-or this:
-
-int l = a.Length;
-for (int i = l; i > 0; i--) {
- a [i] = .....
-}
-
-
-But just something like this
-
-for (int i = 0; i < (a.Length -1); i++) .....
-
-or like this
-
-for (int i = 0; i < a.Length; i += 2) .....
-
-would not work, the check would stay there, sorry :-(
-
-Just to make you understand how things are tricky... this would work!
-
-int limit = a.Length - 1;
-for (int i = 0; i < limit; i++) {
- a [i] = .....
-}
-
-
-A detailed explanation of the reason why things are done like this is given
-below...
-
-All in all, the compiling phase is generally non so fast, and the abc removed
-are so few, that there is hardly a performance gain in using the "abcrem"
-flag in the compiling options for short programs like the ones I tried.
-
-Anyway, various bound checks *are* removed, and this is good :-)
-
-------------------------------------------------------------------------------
-THE ALGORITHM
-
-Unfortunately, this time google has not been my friend, and I did not
-find an algorithm I could reasonably implement in the time frame I had,
-so I had to invent one. The two cleasses of algorithms I found were either
-simply an analisys of variable ranges (which is not very different from
-what I'm doing), or they were based on type systems richer than the .NET
-one (particularly, they required integer types to have an explicit range,
-which could be related to array ranges). By the way, it seems that the
-gcj people do not have an array bound check removal optimization (they
-just have a compiler flag that unconditionally removes all the checks,
-but this is not what we want).
-
-This array bound check removal (abc removal) algorithm is based on
-symbolic execution concepts. I handle the removal like an "unreachable
-code elimination" (and in fact the optimization could be extended to remove
-also other unreachable sections of code, due to branches that "always go the
-same way").
-
-In symbolic execution, variables do not have actual (numeric) values, but
-instead symbolic expressions (like "a", or "x+y").
-Also, branch conditions are handled like symbolic conditions (like "i<k"),
-which state relations between variable values.
-
-The SSA representation inside mini is somewhat close to a symbolic
-representation of the execution of the compiled method.
-Particularly, the representation of variable values is exactly a symbolic
-one. It is enough to find all CEE_STIND_* instructions which store to a
-local variable, and their second argument is exactly the variable value.
-Actually, "cfg->vars [<variable-index>]->def" should contain exactly
-those store instructions, and the "get_variable_value_from_ssa_store"
-function extracts the variable value from there.
-
-On the other hand, the conditions under which each basic block is
-executed are not made fully explicit.
-
-However, it is not difficult to make them so.
-Each BB that has more than one exit BB, in practice must end either with
-a conditional branch instruction or with a switch instruction.
-In the first case, the BB has exactly two exit BBs, and their execution
-conditions are easy to get from the condition of the branch (see the
-"get_relation_from_branch_instruction" function, and expecially the end of
-"analyze_block" in abcremoval.c.
-If there is a switch, the jump condition of every exit BB is the equality
-of the switch argument with the particular index associated with its case
-(but the current implementation does not handle switch statements yet).
-
-These individual conditions are in practice associated to each arc that
-connects BBs in the CFG (with the simple case that unconditional branches
-have a "TRUE" condition, because they always happen).
-
-So, for each BB, its *proper* entry condition is the union of all the
-conditions associated to arcs that enter the BB. The "union" is like a
-logical "or", in the sense that either of the condition could be true,
-they are not necessarily all true. This means that if I can enter a BB
-in two ways, and in one case I know that "x>0", and in the other that
-"x==0", actually in the BB I know that "x>=0", which is a weaker
-condition (the union of the two).
-
-Also, the *complete* entry condition for a BB is the "intersection" of all
-the entry conditions of its dominators. This is true because each dominator
-is the only way to reach the BB, so the entry condition of each dominator
-must be true if the control flow reached the BB. This translates to the
-logical "and" of all the "proper" conditions of the BBs met walking up in the
-dominator tree. So, if one says "x>0", and another "x==1", then I know
-that "x==1", which is a stronger condition (the intersection of the two).
-Note that, if the two conditions were "x>0" and "x==0", then the block would
-be unreachable (the intersection is empty), because some branch is impossible.
-
-Another observation is that, inside each BB, every variable is subject to the
-complete entry condition of that very same BB, and not the one in which it is
-defined (with the "complete entry condition" being the thing I defined before,
-sorry if these terms "proper" and "complete" are strange, I found nothing
-better).
-This happens because the branch conditions are related to the control flow.
-I can define "i=a", and if I am in a BB where "a>0", then "i>0", but not
-otherwise.
-
-So, intuitively, if the available conditions say "i>=0", and i is used as an
-index in an array access, then the lower bound check can be omitted.
-If the condition also says "(i>=0)&&(i<array.length)", the abc removal can
-occur.
-
-So, a complete solution to the problem of abc removal would be the following:
-for each array access, build a system of equations containing:
-[1] all the symbolic variable definitions
-[2] the complete entry condition of the BB in which the array access occurs
-[3] the two "goal functions" ("index >=0" and "index < array.length")
-If the system is valid for *each possible* variable value, then the goal
-functions are always true, and the abc can be removed.
-
-All this discussion is useful to give a precise specification to the problem
-we are trying to solve.
-The trouble is that, in the general case, the resulting system of equations
-is like a predicate in first order logic, which is semi-decidable, and its
-general solution is anyway too complex to be attempted in a JIT compiler
-(which should not contain a full fledged theorem prover).
-
-Therefore, we must cut some corner.
-
-
-By the way, there is also another big problem, which is caused by "recursive"
-symbolic definitions. These definition can (and generally do) happen every
-time there is a loop. For instance, in the following piece of code
-
-for ( int i = 0; i < array.length; i++ ) {
- Console.WriteLine( "array [i] = " + array [i] );
-}
-
-one of the definitions of i is a PHI that can be either 0 or "i + 1".
-
-Now, we know that mathematically "i = i + 1" does not make sense, and in
-fact symbolic values are not "equations", they are "symbolic definitions".
-
-The symbolic value of i is a generic "n", where "n" is the number of
-iterations of the loop, but this is terrible to handle (and in more complex
-examples the symbolic definition of i simply cannot be written, because i is
-calculated in an iterative way).
-
-However, the definition "i = i + 1" tells us something about i: it tells us
-that i "grows". So (from the PHI definition) we know that i is either 0, or
-"grows". This is enough to tell that "i>=0", which is what we want!
-It is important to note that recursive definitions can only occurr inside
-PHI definitions, because actually a variable cannot be defined *only* in terms
-of itself!
-
-
-At this point, I can explain which corners I want to cut to make the
-problem solvable. It will not remove all the abc that could theoretically
-be removed, but at least it will work.
-
-The easiest way to cut corners is to only handle expressions which are
-"reasonably simple", and ignore the rest.
-Keep in mind that ignoring an expression is not harmful in itself.
-The algorithm will be simply "less powerful", because it will ignore
-conditions that could have caused to the removal of an abc, but will
-not remove checks "by mistake" (so the resulting code will be in any case
-correct).
-
-In a first attempt, we can consider only conditions that have the simple
-possible form, which is "(compare simpleExpression simpleExpression)",
-where "simpleExpression" is either "(ldind.* local[*])" or
-"(ldlen (ldind.ref local[*]))" (or a constant, of course).
-
-We can also "summarize" variable definitions, keeping only what is relevant
-to know: if they are greater or smaller than zero or other variables.
-
-One particular note on PHI functions: they work (obviously) like the logical
-"or" of their definitions, and therefore are equivalent to the "logical or"
-of the summarization of their definitions.
-
-About recursive definitions (which, believe me, are the worst thing in all
-this mess), we handle only "monotonic" ones. That is, we try to understand
-if the recursive definition (which, as we said above, must happen because
-of a loop) always "grows" or "gets smaller". In all other cases, we decide
-we cannot handle it.
-
-So, the algorithm to optimize one method could be something like:
-
-[1] Build the SSA representation.
-[2] Analyze each BB. Particularly, do the following:
- [2a] summarize its exit conditions
- [2b] summarize all the variable definitions occurring in the BB
- [2c] check if it contains array accesses (only as optimization, so that
- step 3 will be performed only when necessary)
-[3] Perform the removal. For each BB that contains array accesses, do:
- [3a] build an evaluation area where for each variable we keep track
- of its relations with zero and with each other variable.
- [3b] populate the evaluation area with the initial data (the variable
- definitions and the complete entry condition of the BB)
- [3c] propagate the relations between variables (so that from "a<b" and
- "b<c" we know that "a<c") in the evaluation area
- [3d] for each array access in the BB, use the evaluation area to "match
- conditions", to see if the goal functions are satisfied
-
-
-------------------------------------------------------------------------------
-LOW LEVEL DESIGN DECISIONS
-
-One of the problems I had to solve was the representation of the relations
-between symbolic values.
-The "canonical" solution would be to have a complex, potentially recursive
-data structure, somewhat similar to MonoInst, and use it all the time (maybe
-MonoInst could be used "as is").
-The problem is that, at this point, the software would have to "play" with
-these structures, for instance to deduce "b < a-1" from "a > b+1", because we
-are interested in what value b has, and not a. And maybe the software should
-be able to do this without modifying the original condition, because it was
-used elsewhere (or could be reused).
-Then, the software should also be able to apply logical relations to
-conditions (like "(a>0)||(c<1)"), and manipulate them, too.
-
-In my opinion, an optimizer written in this way risks to be too complex, and
-its performance not acceptable in a JIT compiler.
-Therefore, I decided to represent values in a "summarized" way.
-For instance, "x = a + 1" becomes "x > a" (and, by the way, "x = x + 1"
-would look like "x > x", which means that "x grows").
-So, each variable value is simply a "relation" of the variable with other
-variables or constants. Anything more complex is ignored.
-Relations are represented with flags (EQ, LT and GT), so that it is easy
-to combine them logically (it is enough to perform the bitwise operations
-on the flags). The condition (EQ|LT|GT) means we know nothing special, any
-value is possible. The empty condition would mean an unreachable statement
-(because no value is acceptable).
-
-There is still the problem of identifying variables, and where to store all
-these relations. After some thinking, I decided that a "brute force" approach
-is the easier, and probably also the fastest. In practice, I keep in memory
-an array of "variable relations", where for each variable I record its
-relation with the constants 0 and 1 and an array of its relations with all
-other variables. The evaluation area, therefore, looks like a square matrix
-as large as the number of variables. I *know* that the matrix is rather sparse
-(in the sense that only few of its cells are significant), but I decided that
-this data structure was the simplest and more efficient anyway. After all,
-each cell takes just one byte, and any other data structure must be some
-kind of associative array (like a g_hash_table). Such a data structue is
-difficult to use with a MonoMemPool, and in the end is slower than a plain
-array, and has the storage overhead of all the pointers... in the end, maybe
-the full matrix is not a waste at all.
-<note>
-After a few benchmarks, I clearly see that the matrix works well if the
-variables are not too much, otherwise it gets "too sparse", and much time
-is wasted in the propagation phase. Maybe the data structure could be changed
-after a more careful evaluation of the problem...
-</note>
-
-With these assumptions, all the memory used to represent values, conditions
-and the evaluation area can be allocated in advance (from a MonoMemPool), and
-used for all the analysis of one method. Moreover, the performance of logical
-operations is high (they are simple bitwise operations on bytes).
-<note>
-For the propagation phase, there was a function I could not easily code
-with bitwise operations. As that phase is a real pain for the performance
-(the complexity is quadratic, and it must be executed iteratively until
-nothing changes), I decided to code it in perl, and generate a precomputed
-table then used by the C code (just 64 bytes). I think this is faster than
-all those branches... Really, I could think again to phases 3c and 3d (see
-above), maybe there is a better way to do them.
-</note>
-
-Of course not all expressions can be handled by the summarization, so the
-optimizer is not as effective as a full blown theorem prover...
-
-Another thing related to design... the implementation is as less intrusive
-as possible.
-I "patched" the main files to add an option for abc removal, and handle it
-just like any other option, and then wrote all the relevant code in two
-separated files (one header for data structures, and a C file for the code).
-If the patch turns out to be useful also for other pourposes (like a more
-generic "unreachable code elimination", that detects branches that will never
-be taken using the analysis of variable values), it will not be difficult
-to integrate the branch summarizations into the BasicBlock data structures,
-and so on.
-
-One last thing... in some places, I knowingly coded in an inefficient way.
-For instance, "remove_abc_from_block" does something only if the flag
-"has_array_access_instructions" is true, but I call it anyway, letting it
-do nothing (calling it conditionally would be better). There are several
-things like this in the code, but I was in a hurry, and preferred to make
-the code more readable (it is already difficult to understand as it is).
-
-------------------------------------------------------------------------------
-WHEN IS ABC REMOVAL POSSIBLE? WHEN IS IT USEFUL?
-
-Warning! Random ideas ahead!
-
-In general, managed code should be safe, so abc removal is possible only if
-there already is some branch in the method that does the check.
-So, one check on the index is "mandatory", the abc removal can only avoid a
-second one (which is useless *because* of the first one).
-If in the code there is not a conditional branch that "avoids" to access
-an array out of its bounds, in general the abc removal cannot occur.
-
-It could happen, however, that one method is called from another one, and
-the check on the index is performed in the caller.
-
-For instance:
-
-void
-caller( int[] a, int n ) {
- if ( n <= a.Length ) {
- for ( int i = 0; i < n; i++ ) {
- callee( a, i );