From df011c3bc3db8b327f2b2d93e108c3a53a9a4f34 Mon Sep 17 00:00:00 2001 From: Aart Bik Date: Thu, 28 Sep 2017 12:53:04 -0700 Subject: Generalized zero/sign-ext analysis. Generalized SAD. Rationale: The more, the better. Some of the analysis was overly conservative (e.g. extension does not need to happen from terminals only as long as vectorized guarantees higher order bits don't contribute). Also, added hidden-SUB for SAD. Test: test-art-host test-art-target Bug: 64091002 Change-Id: I66afd8fb4292ce5cf14f98f9c5ce2bf2b8c98488 --- compiler/optimizing/loop_optimization.cc | 136 +++++++++++++++++-------------- 1 file changed, 73 insertions(+), 63 deletions(-) (limited to 'compiler/optimizing/loop_optimization.cc') diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc index 7e37018229..fec64e2adf 100644 --- a/compiler/optimizing/loop_optimization.cc +++ b/compiler/optimizing/loop_optimization.cc @@ -74,19 +74,16 @@ static bool IsEarlyExit(HLoopInformation* loop_info) { // Forward declaration. static bool IsZeroExtensionAndGet(HInstruction* instruction, DataType::Type type, - /*out*/ HInstruction** operand, - bool to64 = false); + /*out*/ HInstruction** operand); -// Detect a sign extension in instruction from the given type. The to64 parameter -// denotes if result is long, and thus sign extension from int can be included. +// Detect a sign extension in instruction from the given type. // Returns the promoted operand on success. static bool IsSignExtensionAndGet(HInstruction* instruction, DataType::Type type, - /*out*/ HInstruction** operand, - bool to64 = false) { + /*out*/ HInstruction** operand) { // Accept any already wider constant that would be handled properly by sign // extension when represented in the *width* of the given narrower data type - // (the fact that char normally zero extends does not matter here). + // (the fact that Uint16 normally zero extends does not matter here). int64_t value = 0; if (IsInt64AndGet(instruction, /*out*/ &value)) { switch (type) { @@ -103,43 +100,39 @@ static bool IsSignExtensionAndGet(HInstruction* instruction, return true; } return false; - case DataType::Type::kInt32: - if (IsInt<32>(value)) { - *operand = instruction; - return to64; - } - return false; default: return false; } } - // An implicit widening conversion of a signed integer to an integral type sign-extends - // the two's-complement representation of the integer value to fill the wider format. - if (instruction->GetType() == type && (instruction->IsArrayGet() || - instruction->IsStaticFieldGet() || - instruction->IsInstanceFieldGet())) { + // An implicit widening conversion of any signed expression sign-extends. + if (instruction->GetType() == type) { switch (type) { case DataType::Type::kInt8: case DataType::Type::kInt16: *operand = instruction; return true; - case DataType::Type::kInt32: - *operand = instruction; - return to64; default: return false; } } - // Explicit type conversions. + // An explicit widening conversion of a signed expression sign-extends. if (instruction->IsTypeConversion()) { - DataType::Type from = instruction->InputAt(0)->GetType(); + HInstruction* conv = instruction->InputAt(0); + DataType::Type from = conv->GetType(); switch (instruction->GetType()) { + case DataType::Type::kInt32: case DataType::Type::kInt64: - return IsSignExtensionAndGet(instruction->InputAt(0), type, /*out*/ operand, /*to64*/ true); + if (type == from && (from == DataType::Type::kInt8 || + from == DataType::Type::kInt16 || + from == DataType::Type::kInt32)) { + *operand = conv; + return true; + } + return false; case DataType::Type::kInt16: return type == DataType::Type::kUint16 && from == DataType::Type::kUint16 && - IsZeroExtensionAndGet(instruction->InputAt(0), type, /*out*/ operand, to64); + IsZeroExtensionAndGet(instruction->InputAt(0), type, /*out*/ operand); default: return false; } @@ -147,16 +140,14 @@ static bool IsSignExtensionAndGet(HInstruction* instruction, return false; } -// Detect a zero extension in instruction from the given type. The to64 parameter -// denotes if result is long, and thus zero extension from int can be included. +// Detect a zero extension in instruction from the given type. // Returns the promoted operand on success. static bool IsZeroExtensionAndGet(HInstruction* instruction, DataType::Type type, - /*out*/ HInstruction** operand, - bool to64) { + /*out*/ HInstruction** operand) { // Accept any already wider constant that would be handled properly by zero // extension when represented in the *width* of the given narrower data type - // (the fact that byte/short/int normally sign extend does not matter here). + // (the fact that Int8/Int16 normally sign extend does not matter here). int64_t value = 0; if (IsInt64AndGet(instruction, /*out*/ &value)) { switch (type) { @@ -173,21 +164,12 @@ static bool IsZeroExtensionAndGet(HInstruction* instruction, return true; } return false; - case DataType::Type::kInt32: - if (IsUint<32>(value)) { - *operand = instruction; - return to64; - } - return false; default: return false; } } - // An implicit widening conversion of a char to an integral type zero-extends - // the representation of the char value to fill the wider format. - if (instruction->GetType() == type && (instruction->IsArrayGet() || - instruction->IsStaticFieldGet() || - instruction->IsInstanceFieldGet())) { + // An implicit widening conversion of any unsigned expression zero-extends. + if (instruction->GetType() == type) { if (type == DataType::Type::kUint16) { *operand = instruction; return true; @@ -195,6 +177,9 @@ static bool IsZeroExtensionAndGet(HInstruction* instruction, } // A sign (or zero) extension followed by an explicit removal of just the // higher sign bits is equivalent to a zero extension of the underlying operand. + // + // TODO: move this into simplifier and use new type system instead. + // if (instruction->IsAnd()) { int64_t mask = 0; HInstruction* a = instruction->InputAt(0); @@ -210,22 +195,26 @@ static bool IsZeroExtensionAndGet(HInstruction* instruction, case DataType::Type::kUint16: case DataType::Type::kInt16: return mask == std::numeric_limits::max(); - case DataType::Type::kInt32: - return mask == std::numeric_limits::max() && to64; default: return false; } } } - // Explicit type conversions. + // An explicit widening conversion of an unsigned expression zero-extends. if (instruction->IsTypeConversion()) { - DataType::Type from = instruction->InputAt(0)->GetType(); + HInstruction* conv = instruction->InputAt(0); + DataType::Type from = conv->GetType(); switch (instruction->GetType()) { + case DataType::Type::kInt32: case DataType::Type::kInt64: - return IsZeroExtensionAndGet(instruction->InputAt(0), type, /*out*/ operand, /*to64*/ true); + if (type == from && from == DataType::Type::kUint16) { + *operand = conv; + return true; + } + return false; case DataType::Type::kUint16: return type == DataType::Type::kInt16 && from == DataType::Type::kInt16 && - IsSignExtensionAndGet(instruction->InputAt(0), type, /*out*/ operand, to64); + IsSignExtensionAndGet(instruction->InputAt(0), type, /*out*/ operand); default: return false; } @@ -360,6 +349,22 @@ static bool IsAddConst(HInstruction* instruction, return false; } +// Detect a + c for constant c. +static bool IsAddConst(HInstruction* instruction, + /*out*/ HInstruction** a, + /*out*/ int64_t* c) { + if (instruction->IsAdd()) { + if (IsInt64AndGet(instruction->InputAt(0), c)) { + *a = instruction->InputAt(1); + return true; + } else if (IsInt64AndGet(instruction->InputAt(1), c)) { + *a = instruction->InputAt(0); + return true; + } + } + return false; +} + // Detect reductions of the following forms, // x = x_phi + .. // x = x_phi - .. @@ -1148,6 +1153,7 @@ bool HLoopOptimization::VectorizeUse(LoopNode* node, size_t size_vec = DataType::Size(type); size_t size_from = DataType::Size(from); size_t size_to = DataType::Size(to); + DataType::Type ctype = size_from == size_vec ? from : type; // Accept an integral conversion // (1a) narrowing into vector type, "wider" operations cannot bring in higher order bits, or // (1b) widening from at least vector type, and @@ -1157,7 +1163,7 @@ bool HLoopOptimization::VectorizeUse(LoopNode* node, VectorizeUse(node, opa, generate_code, type, restrictions | kNoHiBits)) || (size_to >= size_from && size_from >= size_vec && - VectorizeUse(node, opa, generate_code, type, restrictions))) { + VectorizeUse(node, opa, generate_code, ctype, restrictions))) { if (generate_code) { if (vector_mode_ == kVector) { vector_map_->Put(instruction, vector_map_->Get(opa)); // operand pass-through @@ -1896,9 +1902,14 @@ bool HLoopOptimization::VectorizeSADIdiom(LoopNode* node, (v->AsInvokeStaticOrDirect()->GetIntrinsic() == Intrinsics::kMathAbsInt || v->AsInvokeStaticOrDirect()->GetIntrinsic() == Intrinsics::kMathAbsLong)) { HInstruction* x = v->InputAt(0); - if (x->IsSub() && x->GetType() == reduction_type) { - a = x->InputAt(0); - b = x->InputAt(1); + if (x->GetType() == reduction_type) { + int64_t c = 0; + if (x->IsSub()) { + a = x->InputAt(0); + b = x->InputAt(1); + } else if (IsAddConst(x, /*out*/ &a, /*out*/ &c)) { + b = graph_->GetConstant(reduction_type, -c); // hidden SUB! + } } } if (a == nullptr || b == nullptr) { @@ -1906,22 +1917,21 @@ bool HLoopOptimization::VectorizeSADIdiom(LoopNode* node, } // Accept same-type or consistent sign extension for narrower-type on operands a and b. // The same-type or narrower operands are called r (a or lower) and s (b or lower). + // We inspect the operands carefully to pick the most suited type. HInstruction* r = a; HInstruction* s = b; bool is_unsigned = false; DataType::Type sub_type = a->GetType(); - if (a->IsTypeConversion()) { - HInstruction* hunt = a; - while (hunt->IsTypeConversion()) { - hunt = hunt->InputAt(0); - } - sub_type = hunt->GetType(); - } else if (b->IsTypeConversion()) { - HInstruction* hunt = a; - while (hunt->IsTypeConversion()) { - hunt = hunt->InputAt(0); - } - sub_type = hunt->GetType(); + if (DataType::Size(b->GetType()) < DataType::Size(sub_type)) { + sub_type = b->GetType(); + } + if (a->IsTypeConversion() && + DataType::Size(a->InputAt(0)->GetType()) < DataType::Size(sub_type)) { + sub_type = a->InputAt(0)->GetType(); + } + if (b->IsTypeConversion() && + DataType::Size(b->InputAt(0)->GetType()) < DataType::Size(sub_type)) { + sub_type = b->InputAt(0)->GetType(); } if (reduction_type != sub_type && (!IsNarrowerOperands(a, b, sub_type, &r, &s, &is_unsigned) || is_unsigned)) { -- cgit v1.2.3-59-g8ed1b