A new optimization which detects an effectively constant array and uses the constant array implementation for it.
An effectively constant array can be created in two ways:
- In the declaration, e.g.
var array[] = ("foo", "bar", "baz", "qux", "quux", "corge");
- By assigning all element values once programmatically, e.g.
var array[10]; for i in 0 ... 10 do array[i] = sin(10 * i); end;
The first case could be reasonably easily detected from the AST tree, but the second one is universal. We'll aim at implementing the second case.
Optimization mechanism
The optimization would effectively convert the array to a constant one. A constant array uses @counter tables, folded when possible, for example:
const a[] = ("foo", "bar", "baz", "qux", "quux", "corge");
print(a[floor(rand(length(a)))]);
compiles to:
op rand *tmp0 6 0
read @counter "������" *tmp0
select *tmp4 lessThan *tmp2 3 "baz" "corge" # Origin: 1, keys: 2, 5
jump 7 always 0 0
select *tmp4 lessThan *tmp2 3 "bar" "quux" # Origin: 1, keys: 1, 4
jump 7 always 0 0
select *tmp4 lessThan *tmp2 3 "foo" "qux" # Origin: 1, keys: 0, 3
print *tmp4
Costs and benefits
The actual costs and benefits will be computed by the optimizer. We only need to make sure the optimization will actually get selected by the optimizer under some circumstances, otherwise we wouldn't have to implement it at all.
Targets 6.x and 7.x
In targets older than 8.0, constant arrays are implemented the same as variable arrays, and the optimization saves the initialization code, which reduces both code size and execution speed. As the cost is negative and the benefit is positive, the optimization will be done whenever possible.
Targets 8.0 and 8.1
In target 8.0, the constant array table is unfolded. In target 8.1, it can be folded. The cost/benefic analysis depends on the implementation currently assigned to the array.
Lookup array
Converting from a lookup array to the constant array saves the initialization code, improving the execution time. Even when text-based jump tables are used, the array-access execution time remains the same for inlined tables, or is worsened. Code size can't decrease.
When the optimization goal is size or neutral, the optimization won't be performed.
When the optimization goal is speed, the optimization may happen assuming all array accesses are inlined and text-based jump tables are used.
There's an additional benefit that converting a lookup array into a constant array frees up the lookup to be considered for another array. However, we assume that lookup array assignment is already performed optimally, and the freed lookup array type will simply be reused in the next optimization pass. So we won't assign an additional benefit to the fact a lookup array was freed during the optimization.
Compact tables
Replacing a compact array with a constant regular array always shortens the access code size/time. On top of this, the array initialization code is entirely eliminated.
Regular tables
Regular tables of constant arrays are identical to read-only tables of variable arrays, so the optimization again saves the initialization code, which reduces both code size and execution speed. As the cost is negative and the benefit is positive, the optimization will be done whenever possible.
Determining the optimization is possible
The optimization is possible when the following conditions are true:
- All random accesses to the array are read-only, and each element variable is initialized exactly once to a mlog-representable constant value in the entire program (a cheap precondition check).
- The write to each of the element variable dominates all accesses to the array.
A CFG graph will be constructed and the domination checks will be made on it. The CFG is already build for the Atomic Block Resolver, and will be generalized and reused in the optimization.
Optimization progression
Each lookup array will be considered for constant conversion.
Both compact and regular (shared and inlined) arrays will be considered for constant conversion.
Once converted to a constant array, the array will never be converted back. The initialization code gets removed.
A new optimization which detects an effectively constant array and uses the constant array implementation for it.
An effectively constant array can be created in two ways:
var array[] = ("foo", "bar", "baz", "qux", "quux", "corge");var array[10]; for i in 0 ... 10 do array[i] = sin(10 * i); end;The first case could be reasonably easily detected from the AST tree, but the second one is universal. We'll aim at implementing the second case.
Optimization mechanism
The optimization would effectively convert the array to a constant one. A constant array uses
@countertables, folded when possible, for example:compiles to:
Costs and benefits
The actual costs and benefits will be computed by the optimizer. We only need to make sure the optimization will actually get selected by the optimizer under some circumstances, otherwise we wouldn't have to implement it at all.
Targets 6.x and 7.x
In targets older than 8.0, constant arrays are implemented the same as variable arrays, and the optimization saves the initialization code, which reduces both code size and execution speed. As the cost is negative and the benefit is positive, the optimization will be done whenever possible.
Targets 8.0 and 8.1
In target 8.0, the constant array table is unfolded. In target 8.1, it can be folded. The cost/benefic analysis depends on the implementation currently assigned to the array.
Lookup array
Converting from a lookup array to the constant array saves the initialization code, improving the execution time. Even when text-based jump tables are used, the array-access execution time remains the same for inlined tables, or is worsened. Code size can't decrease.
When the optimization goal is size or neutral, the optimization won't be performed.
When the optimization goal is speed, the optimization may happen assuming all array accesses are inlined and text-based jump tables are used.
There's an additional benefit that converting a lookup array into a constant array frees up the lookup to be considered for another array. However, we assume that lookup array assignment is already performed optimally, and the freed lookup array type will simply be reused in the next optimization pass. So we won't assign an additional benefit to the fact a lookup array was freed during the optimization.
Compact tables
Replacing a compact array with a constant regular array always shortens the access code size/time. On top of this, the array initialization code is entirely eliminated.
Regular tables
Regular tables of constant arrays are identical to read-only tables of variable arrays, so the optimization again saves the initialization code, which reduces both code size and execution speed. As the cost is negative and the benefit is positive, the optimization will be done whenever possible.
Determining the optimization is possible
The optimization is possible when the following conditions are true:
A CFG graph will be constructed and the domination checks will be made on it. The CFG is already build for the Atomic Block Resolver, and will be generalized and reused in the optimization.
Optimization progression
Each lookup array will be considered for constant conversion.
Both compact and regular (shared and inlined) arrays will be considered for constant conversion.
Once converted to a constant array, the array will never be converted back. The initialization code gets removed.