Open rakudrama opened 2 years ago
I have been looking into this.
We can compensate for the too-late inlining of _ImmutableList.length
in constant propagation:
void ConstantPropagator::VisitStaticCall(StaticCallInstr* instr) {
...
case MethodRecognizer::kImmutableArrayLength:
case MethodRecognizer::kObjectArrayLength: {
ASSERT(instr->FirstArgIndex() == 0);
const Object& o = instr->ArgumentAt(0)->constant_value();
if (o.IsArray()) {
const auto& array = Array::Cast(o);
SetValue(instr, Integer::ZoneHandle(Z, Integer::New(array.Length())));
return;
}
break;
}
...
It is slightly unsatisfactory to have another place that knows how to reduce a load of the length of a fixed-length list.
The GenericCheckBound
is blocking further constant-folding because of this:
void ConstantPropagator::VisitGenericCheckBound(GenericCheckBoundInstr* instr) {
// Don't propagate constants through check, since it would eliminate
// the data dependence between the bound check and the load/store.
// Graph finalization will expose the constant eventually.
SetValue(instr, non_constant_);
}
I think we can have our cake and eat it too. We don't have to eliminate the data dependence. We can propagate the constant index, but not replace the GenericCheckBoound
with a constant.
This would enable the subsequent LoadIndexed
to be constant-folded, but other uses would still be guarded.
Question: Is this right?
An amusing aside: I tried replacing, in ConstantPropagator::LoadIndexed
, the index ->definition()->constant_value()
with ->definition->OriginalDefinition()->constant_value()
. This broke the dataflow, since the transfer function for an instruction was no longer a function of the inputs of the instruction. Lucky for me this broke the build.
Another approach is to add constant-folding of LoadIndexed
to canonicalization, where there is no dataflow invariants to uphold, and it is reasonable to inspect OriginalDefinition
s.
The JIT reduces some calls to dart2js's
CallStructure
factory constructor to a constant. AOT fails to do this.It appears that the reason is that not enough good things happen during canonicalization to make the inlinee look appealing:
_ImmutableList.length
is not replaced withLoadField
early enough to allow constant-folding to simplify the inlinee . Curiously,[]
is replaced with a bounds check and indexed load, but...GenericCheckBound
has no constant-inputs canonicalization, or perhaps it can't be removed but inhibits other reductions.Static calls to the getters of fields of user-defined constants are replaced by
LoadField
instructions earlier, making them available to reduction by canonicalization or constant-folding. This leaves constant lists at a disadvantage when compared to user-defined constants.(I believe the JIT succeeds simply because it is happy to inline larger methods and does the constant-folding later.)
The factory constructor does a lookup in a const table. An example of a call that the JIT inlines and reduces to a constant is here.
Consider this simplified version, using a single level of array:
When the inlining decision is made,
_common.length
is still a static call. It has not been reduced to4
, so the path with the constructor call is still in the callee graph:Interestingly, I can write a list wrapper :
This version gets inlined, and the final code for
demo1
contains a load of the constant value:The two-level version still does not work. This is because the
LoadIndexed
is not reduced to a constant. I suspect what is blocking this is thatGenericCheckBound
has a no-opCanonicalize
method, or is opaque to theLoadIndexed
canonicalization.This is a full stand-alone test,
demo1
should have the inlined constant:> _common = [ [NO_ARGS, CallStructure._(0, 1), CallStructure._(0, 2)], [ONE_ARG, CallStructure._(1, 1), CallStructure._(1, 2)], [TWO_ARGS, CallStructure._(2, 1), CallStructure._(2, 2)], [CallStructure._(3), CallStructure._(3, 1), CallStructure._(3, 2)], [CallStructure._(4), CallStructure._(4, 1), CallStructure._(4, 2)], [CallStructure._(5), CallStructure._(5, 1), CallStructure._(5, 2)], [CallStructure._(6)], [CallStructure._(7)], [CallStructure._(8)], [CallStructure._(9)], [CallStructure._(10)], ]; /// The number of type arguments of the call. final int typeArgumentCount; /// The numbers of arguments of the call. Includes named arguments. final int argumentCount; /// The number of named arguments of the call. int get namedArgumentCount => 0; /// The number of positional argument of the call. int get positionalArgumentCount => argumentCount; const CallStructure._(this.argumentCount, [this.typeArgumentCount = 0]); factory CallStructure.unnamed(int argumentCount, [int typeArgumentCount = 0]) { // This simple canonicalization of common call structures greatly reduces // the number of allocations of CallStructure objects. if (argumentCount < _common.length) { final row = _common[argumentCount]; if (typeArgumentCount < row.length) { final result = row[typeArgumentCount]; assert(result.argumentCount == argumentCount && result.typeArgumentCount == typeArgumentCount); return result; } } return CallStructure._(argumentCount, typeArgumentCount); } factory CallStructure(int argumentCount, [List? namedArguments, int typeArgumentCount = 0]) {
if (namedArguments == null || namedArguments.isEmpty) {
return CallStructure.unnamed(argumentCount, typeArgumentCount);
}
return _NamedCallStructure(
argumentCount, namedArguments, typeArgumentCount, null);
}
/// Returns `true` if this call structure is normalized, that is, its named
/// arguments are sorted.
bool get isNormalized => true;
/// Returns the normalized version of this call structure.
///
/// A [CallStructure] is normalized if its named arguments are sorted.
CallStructure toNormalized() => this;
CallStructure withTypeArgumentCount(int typeArgumentCount) =>
CallStructure(argumentCount, namedArguments, typeArgumentCount);
/// `true` if this call has named arguments.
bool get isNamed => false;
/// `true` if this call has no named arguments.
bool get isUnnamed => true;
/// The names of the named arguments in call-site order.
List get namedArguments => const [];
/// The names of the named arguments in canonicalized order.
List getOrderedNamedArguments() => const [];
CallStructure get nonGeneric => typeArgumentCount == 0
? this
: CallStructure(argumentCount, namedArguments);
/// A description of the argument structure.
String structureToString() {
StringBuffer sb = StringBuffer();
sb.write('arity=$argumentCount');
if (typeArgumentCount != 0) {
sb.write(', types=$typeArgumentCount');
}
return sb.toString();
}
@override
@pragma('vm:never-inline')
String toString() => 'CallStructure(${structureToString()})';
bool match(CallStructure other) {
if (identical(this, other)) return true;
return this.argumentCount == other.argumentCount &&
this.namedArgumentCount == other.namedArgumentCount &&
this.typeArgumentCount == other.typeArgumentCount &&
_sameNames(this.namedArguments, other.namedArguments);
}
@override
int get hashCode {
return Object.hash(Object.hashAll(namedArguments), argumentCount, typeArgumentCount);
}
@override
bool operator ==(other) {
if (other is! CallStructure) return false;
return match(other);
}
static bool _sameNames(List first, List second) {
assert(first.length == second.length);
for (int i = 0; i < first.length; i++) {
if (first[i] != second[i]) return false;
}
return true;
}
}
/// Call structure with named arguments. This is an implementation detail of the
/// CallStructure interface.
class _NamedCallStructure extends CallStructure {
@override
final List namedArguments;
/// The list of ordered named arguments is computed lazily. Initially `null`.
List? _orderedNamedArguments;
_NamedCallStructure(int argumentCount, this.namedArguments,
int typeArgumentCount, this._orderedNamedArguments)
: assert(namedArguments.isNotEmpty),
super._(argumentCount, typeArgumentCount);
@override
bool get isNamed => true;
@override
bool get isUnnamed => false;
@override
int get namedArgumentCount => namedArguments.length;
@override
int get positionalArgumentCount => argumentCount - namedArgumentCount;
@override
bool get isNormalized =>
identical(namedArguments, getOrderedNamedArguments());
@override
CallStructure toNormalized() => isNormalized
? this
: _NamedCallStructure(argumentCount, getOrderedNamedArguments(),
typeArgumentCount, getOrderedNamedArguments());
@override
List getOrderedNamedArguments() {
return _orderedNamedArguments ??= _getOrderedNamedArguments();
}
List _getOrderedNamedArguments() {
List ordered = List.of(namedArguments, growable: false);
ordered.sort((String first, String second) => first.compareTo(second));
// Use the same List if [namedArguments] is already ordered to indicate this
// _NamedCallStructure is normalized.
if (CallStructure._sameNames(ordered, namedArguments)) {
return namedArguments;
}
return ordered;
}
@override
String structureToString() {
StringBuffer sb = StringBuffer();
sb.write('arity=$argumentCount, named=[${namedArguments.join(', ')}]');
if (typeArgumentCount != 0) {
sb.write(', types=$typeArgumentCount');
}
return sb.toString();
}
}
```
Full code for simplified version:
Simplified version with wrapper: