ART vectorizer.
Rationale:
Make SIMD great again with a retargetable and easily extendable vectorizer.
Provides a full x86/x86_64 and a proof-of-concept ARM implementation. Sample
improvement (without any perf tuning yet) for Linpack on x86 is about 20% to 50%.
Test: test-art-host, test-art-target (angler)
Bug: 34083438, 30933338
Change-Id: Ifb77a0f25f690a87cd65bf3d5e9f6be7ea71d6c1
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 8df513f..42ed04d 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -16,11 +16,21 @@
#include "loop_optimization.h"
+#include "arch/instruction_set.h"
+#include "arch/arm/instruction_set_features_arm.h"
+#include "arch/arm64/instruction_set_features_arm64.h"
+#include "arch/mips/instruction_set_features_mips.h"
+#include "arch/mips64/instruction_set_features_mips64.h"
+#include "arch/x86/instruction_set_features_x86.h"
+#include "arch/x86_64/instruction_set_features_x86_64.h"
#include "driver/compiler_driver.h"
#include "linear_order.h"
namespace art {
+// Enables vectorization (SIMDization) in the loop optimizer.
+static constexpr bool kEnableVectorization = true;
+
// Remove the instruction from the graph. A bit more elaborate than the usual
// instruction removal, since there may be a cycle in the use structure.
static void RemoveFromCycle(HInstruction* instruction) {
@@ -53,6 +63,19 @@
return false;
}
+// Test vector restrictions.
+static bool HasVectorRestrictions(uint64_t restrictions, uint64_t tested) {
+ return (restrictions & tested) != 0;
+}
+
+// Inserts an instruction.
+static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) {
+ DCHECK(block != nullptr);
+ DCHECK(instruction != nullptr);
+ block->InsertInstructionBefore(instruction, block->GetLastInstruction());
+ return instruction;
+}
+
//
// Class methods.
//
@@ -64,11 +87,15 @@
compiler_driver_(compiler_driver),
induction_range_(induction_analysis),
loop_allocator_(nullptr),
+ global_allocator_(graph_->GetArena()),
top_loop_(nullptr),
last_loop_(nullptr),
iset_(nullptr),
induction_simplication_count_(0),
- simplified_(false) {
+ simplified_(false),
+ vector_length_(0),
+ vector_refs_(nullptr),
+ vector_map_(nullptr) {
}
void HLoopOptimization::Run() {
@@ -81,15 +108,13 @@
// Phase-local allocator that draws from the global pool. Since the allocator
// itself resides on the stack, it is destructed on exiting Run(), which
// implies its underlying memory is released immediately.
- ArenaAllocator allocator(graph_->GetArena()->GetArenaPool());
+ ArenaAllocator allocator(global_allocator_->GetArenaPool());
loop_allocator_ = &allocator;
// Perform loop optimizations.
LocalRun();
-
if (top_loop_ == nullptr) {
- // All loops have been eliminated.
- graph_->SetHasLoops(false);
+ graph_->SetHasLoops(false); // no more loops
}
// Detach.
@@ -111,18 +136,29 @@
}
// Traverse the loop hierarchy inner-to-outer and optimize. Traversal can use
- // a temporary set that stores instructions using the phase-local allocator.
+ // temporary data structures using the phase-local allocator. All new HIR
+ // should use the global allocator.
if (top_loop_ != nullptr) {
ArenaSet<HInstruction*> iset(loop_allocator_->Adapter(kArenaAllocLoopOptimization));
+ ArenaSet<ArrayReference> refs(loop_allocator_->Adapter(kArenaAllocLoopOptimization));
+ ArenaSafeMap<HInstruction*, HInstruction*> map(
+ std::less<HInstruction*>(), loop_allocator_->Adapter(kArenaAllocLoopOptimization));
+ // Attach.
iset_ = &iset;
+ vector_refs_ = &refs;
+ vector_map_ = ↦
+ // Traverse.
TraverseLoopsInnerToOuter(top_loop_);
- iset_ = nullptr; // detach
+ // Detach.
+ iset_ = nullptr;
+ vector_refs_ = nullptr;
+ vector_map_ = nullptr;
}
}
void HLoopOptimization::AddLoop(HLoopInformation* loop_info) {
DCHECK(loop_info != nullptr);
- LoopNode* node = new (loop_allocator_) LoopNode(loop_info); // phase-local allocator
+ LoopNode* node = new (loop_allocator_) LoopNode(loop_info);
if (last_loop_ == nullptr) {
// First loop.
DCHECK(top_loop_ == nullptr);
@@ -170,7 +206,7 @@
void HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) {
for ( ; node != nullptr; node = node->next) {
// Visit inner loops first.
- int current_induction_simplification_count = induction_simplication_count_;
+ uint32_t current_induction_simplification_count = induction_simplication_count_;
if (node->inner != nullptr) {
TraverseLoopsInnerToOuter(node->inner);
}
@@ -179,7 +215,7 @@
if (current_induction_simplification_count != induction_simplication_count_) {
induction_range_.ReVisit(node->loop_info);
}
- // Repeat simplifications in the body of this loop until no more changes occur.
+ // Repeat simplifications in the loop-body until no more changes occur.
// Note that since each simplification consists of eliminating code (without
// introducing new code), this process is always finite.
do {
@@ -187,13 +223,17 @@
SimplifyInduction(node);
SimplifyBlocks(node);
} while (simplified_);
- // Simplify inner loop.
+ // Optimize inner loop.
if (node->inner == nullptr) {
- SimplifyInnerLoop(node);
+ OptimizeInnerLoop(node);
}
}
}
+//
+// Optimization.
+//
+
void HLoopOptimization::SimplifyInduction(LoopNode* node) {
HBasicBlock* header = node->loop_info->GetHeader();
HBasicBlock* preheader = node->loop_info->GetPreHeader();
@@ -204,13 +244,9 @@
// for (int i = 0; i < 10; i++, k++) { .... no k .... } return k;
for (HInstructionIterator it(header->GetPhis()); !it.Done(); it.Advance()) {
HPhi* phi = it.Current()->AsPhi();
- iset_->clear();
- int32_t use_count = 0;
- if (IsPhiInduction(phi) &&
- IsOnlyUsedAfterLoop(node->loop_info, phi, /*collect_loop_uses*/ false, &use_count) &&
- // No uses, or no early-exit with proper replacement.
- (use_count == 0 ||
- (!IsEarlyExit(node->loop_info) && TryReplaceWithLastValue(phi, preheader)))) {
+ iset_->clear(); // prepare phi induction
+ if (TrySetPhiInduction(phi, /*restrict_uses*/ true) &&
+ TryAssignLastValue(node->loop_info, phi, preheader, /*collect_loop_uses*/ false)) {
for (HInstruction* i : *iset_) {
RemoveFromCycle(i);
}
@@ -256,49 +292,47 @@
}
}
-bool HLoopOptimization::SimplifyInnerLoop(LoopNode* node) {
+void HLoopOptimization::OptimizeInnerLoop(LoopNode* node) {
HBasicBlock* header = node->loop_info->GetHeader();
HBasicBlock* preheader = node->loop_info->GetPreHeader();
// Ensure loop header logic is finite.
- int64_t tc = 0;
- if (!induction_range_.IsFinite(node->loop_info, &tc)) {
- return false;
+ int64_t trip_count = 0;
+ if (!induction_range_.IsFinite(node->loop_info, &trip_count)) {
+ return;
}
+
// Ensure there is only a single loop-body (besides the header).
HBasicBlock* body = nullptr;
for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) {
if (it.Current() != header) {
if (body != nullptr) {
- return false;
+ return;
}
body = it.Current();
}
}
// Ensure there is only a single exit point.
if (header->GetSuccessors().size() != 2) {
- return false;
+ return;
}
HBasicBlock* exit = (header->GetSuccessors()[0] == body)
? header->GetSuccessors()[1]
: header->GetSuccessors()[0];
// Ensure exit can only be reached by exiting loop.
if (exit->GetPredecessors().size() != 1) {
- return false;
+ return;
}
// Detect either an empty loop (no side effects other than plain iteration) or
// a trivial loop (just iterating once). Replace subsequent index uses, if any,
// with the last value and remove the loop, possibly after unrolling its body.
HInstruction* phi = header->GetFirstPhi();
- iset_->clear();
- int32_t use_count = 0;
- if (IsEmptyHeader(header)) {
+ iset_->clear(); // prepare phi induction
+ if (TrySetSimpleLoopHeader(header)) {
bool is_empty = IsEmptyBody(body);
- if ((is_empty || tc == 1) &&
- IsOnlyUsedAfterLoop(node->loop_info, phi, /*collect_loop_uses*/ true, &use_count) &&
- // No uses, or proper replacement.
- (use_count == 0 || TryReplaceWithLastValue(phi, preheader))) {
+ if ((is_empty || trip_count == 1) &&
+ TryAssignLastValue(node->loop_info, phi, preheader, /*collect_loop_uses*/ true)) {
if (!is_empty) {
- // Unroll the loop body, which sees initial value of the index.
+ // Unroll the loop-body, which sees initial value of the index.
phi->ReplaceWith(phi->InputAt(0));
preheader->MergeInstructionsWith(body);
}
@@ -308,28 +342,649 @@
header->RemoveDominatedBlock(exit);
header->DisconnectAndDelete();
preheader->AddSuccessor(exit);
- preheader->AddInstruction(new (graph_->GetArena()) HGoto()); // global allocator
+ preheader->AddInstruction(new (global_allocator_) HGoto());
preheader->AddDominatedBlock(exit);
exit->SetDominator(preheader);
RemoveLoop(node); // update hierarchy
+ return;
+ }
+ }
+
+ // Vectorize loop, if possible and valid.
+ if (kEnableVectorization) {
+ iset_->clear(); // prepare phi induction
+ if (TrySetSimpleLoopHeader(header) &&
+ CanVectorize(node, body, trip_count) &&
+ TryAssignLastValue(node->loop_info, phi, preheader, /*collect_loop_uses*/ true)) {
+ Vectorize(node, body, exit, trip_count);
+ graph_->SetHasSIMD(true); // flag SIMD usage
+ return;
+ }
+ }
+}
+
+//
+// Loop vectorization. The implementation is based on the book by Aart J.C. Bik:
+// "The Software Vectorization Handbook. Applying Multimedia Extensions for Maximum Performance."
+// Intel Press, June, 2004 (http://www.aartbik.com/).
+//
+
+bool HLoopOptimization::CanVectorize(LoopNode* node, HBasicBlock* block, int64_t trip_count) {
+ // Reset vector bookkeeping.
+ vector_length_ = 0;
+ vector_refs_->clear();
+ vector_runtime_test_a_ =
+ vector_runtime_test_b_= nullptr;
+
+ // Phis in the loop-body prevent vectorization.
+ if (!block->GetPhis().IsEmpty()) {
+ return false;
+ }
+
+ // Scan the loop-body, starting a right-hand-side tree traversal at each left-hand-side
+ // occurrence, which allows passing down attributes down the use tree.
+ for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+ if (!VectorizeDef(node, it.Current(), /*generate_code*/ false)) {
+ return false; // failure to vectorize a left-hand-side
+ }
+ }
+
+ // Heuristics. Does vectorization seem profitable?
+ // TODO: refine
+ if (vector_length_ == 0) {
+ return false; // nothing found
+ } else if (0 < trip_count && trip_count < vector_length_) {
+ return false; // insufficient iterations
+ }
+
+ // Data dependence analysis. Find each pair of references with same type, where
+ // at least one is a write. Each such pair denotes a possible data dependence.
+ // This analysis exploits the property that differently typed arrays cannot be
+ // aliased, as well as the property that references either point to the same
+ // array or to two completely disjoint arrays, i.e., no partial aliasing.
+ // Other than a few simply heuristics, no detailed subscript analysis is done.
+ for (auto i = vector_refs_->begin(); i != vector_refs_->end(); ++i) {
+ for (auto j = i; ++j != vector_refs_->end(); ) {
+ if (i->type == j->type && (i->lhs || j->lhs)) {
+ // Found same-typed a[i+x] vs. b[i+y], where at least one is a write.
+ HInstruction* a = i->base;
+ HInstruction* b = j->base;
+ HInstruction* x = i->offset;
+ HInstruction* y = j->offset;
+ if (a == b) {
+ // Found a[i+x] vs. a[i+y]. Accept if x == y (loop-independent data dependence).
+ // Conservatively assume a loop-carried data dependence otherwise, and reject.
+ if (x != y) {
+ return false;
+ }
+ } else {
+ // Found a[i+x] vs. b[i+y]. Accept if x == y (at worst loop-independent data dependence).
+ // Conservatively assume a potential loop-carried data dependence otherwise, avoided by
+ // generating an explicit a != b disambiguation runtime test on the two references.
+ if (x != y) {
+ // For now, we reject after one test to avoid excessive overhead.
+ if (vector_runtime_test_a_ != nullptr) {
+ return false;
+ }
+ vector_runtime_test_a_ = a;
+ vector_runtime_test_b_ = b;
+ }
+ }
+ }
+ }
+ }
+
+ // Success!
+ return true;
+}
+
+void HLoopOptimization::Vectorize(LoopNode* node,
+ HBasicBlock* block,
+ HBasicBlock* exit,
+ int64_t trip_count) {
+ Primitive::Type induc_type = Primitive::kPrimInt;
+ HBasicBlock* header = node->loop_info->GetHeader();
+ HBasicBlock* preheader = node->loop_info->GetPreHeader();
+
+ // A cleanup is needed for any unknown trip count or for a known trip count
+ // with remainder iterations after vectorization.
+ bool needs_cleanup = trip_count == 0 || (trip_count % vector_length_) != 0;
+
+ // Adjust vector bookkeeping.
+ iset_->clear(); // prepare phi induction
+ bool is_simple_loop_header = TrySetSimpleLoopHeader(header); // fills iset_
+ DCHECK(is_simple_loop_header);
+
+ // Generate preheader:
+ // stc = <trip-count>;
+ // vtc = stc - stc % VL;
+ HInstruction* stc = induction_range_.GenerateTripCount(node->loop_info, graph_, preheader);
+ HInstruction* vtc = stc;
+ if (needs_cleanup) {
+ DCHECK(IsPowerOfTwo(vector_length_));
+ HInstruction* rem = Insert(
+ preheader, new (global_allocator_) HAnd(induc_type,
+ stc,
+ graph_->GetIntConstant(vector_length_ - 1)));
+ vtc = Insert(preheader, new (global_allocator_) HSub(induc_type, stc, rem));
+ }
+
+ // Generate runtime disambiguation test:
+ // vtc = a != b ? vtc : 0;
+ if (vector_runtime_test_a_ != nullptr) {
+ HInstruction* rt = Insert(
+ preheader,
+ new (global_allocator_) HNotEqual(vector_runtime_test_a_, vector_runtime_test_b_));
+ vtc = Insert(preheader,
+ new (global_allocator_) HSelect(rt, vtc, graph_->GetIntConstant(0), kNoDexPc));
+ needs_cleanup = true;
+ }
+
+ // Generate vector loop:
+ // for (i = 0; i < vtc; i += VL)
+ // <vectorized-loop-body>
+ vector_mode_ = kVector;
+ GenerateNewLoop(node,
+ block,
+ graph_->TransformLoopForVectorization(header, block, exit),
+ graph_->GetIntConstant(0),
+ vtc,
+ graph_->GetIntConstant(vector_length_));
+ HLoopInformation* vloop = vector_header_->GetLoopInformation();
+
+ // Generate cleanup loop, if needed:
+ // for ( ; i < stc; i += 1)
+ // <loop-body>
+ if (needs_cleanup) {
+ vector_mode_ = kSequential;
+ GenerateNewLoop(node,
+ block,
+ graph_->TransformLoopForVectorization(vector_header_, vector_body_, exit),
+ vector_phi_,
+ stc,
+ graph_->GetIntConstant(1));
+ }
+
+ // Remove the original loop by disconnecting the body block
+ // and removing all instructions from the header.
+ block->DisconnectAndDelete();
+ while (!header->GetFirstInstruction()->IsGoto()) {
+ header->RemoveInstruction(header->GetFirstInstruction());
+ }
+ // Update loop hierarchy: the old header now resides in the
+ // same outer loop as the old preheader.
+ header->SetLoopInformation(preheader->GetLoopInformation()); // outward
+ node->loop_info = vloop;
+}
+
+void HLoopOptimization::GenerateNewLoop(LoopNode* node,
+ HBasicBlock* block,
+ HBasicBlock* new_preheader,
+ HInstruction* lo,
+ HInstruction* hi,
+ HInstruction* step) {
+ Primitive::Type induc_type = Primitive::kPrimInt;
+ // Prepare new loop.
+ vector_map_->clear();
+ vector_preheader_ = new_preheader,
+ vector_header_ = vector_preheader_->GetSingleSuccessor();
+ vector_body_ = vector_header_->GetSuccessors()[1];
+ vector_phi_ = new (global_allocator_) HPhi(global_allocator_,
+ kNoRegNumber,
+ 0,
+ HPhi::ToPhiType(induc_type));
+ // Generate header.
+ // for (i = lo; i < hi; i += step)
+ // <loop-body>
+ HInstruction* cond = new (global_allocator_) HAboveOrEqual(vector_phi_, hi);
+ vector_header_->AddPhi(vector_phi_);
+ vector_header_->AddInstruction(cond);
+ vector_header_->AddInstruction(new (global_allocator_) HIf(cond));
+ // Suspend check and environment.
+ HInstruction* suspend = vector_header_->GetFirstInstruction();
+ suspend->CopyEnvironmentFromWithLoopPhiAdjustment(
+ node->loop_info->GetSuspendCheck()->GetEnvironment(), vector_header_);
+ // Generate body.
+ for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+ bool vectorized_def = VectorizeDef(node, it.Current(), /*generate_code*/ true);
+ DCHECK(vectorized_def);
+ }
+ for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+ auto i = vector_map_->find(it.Current());
+ if (i != vector_map_->end() && !i->second->IsInBlock()) {
+ Insert(vector_body_, i->second); // lays out in original order
+ if (i->second->NeedsEnvironment()) {
+ i->second->CopyEnvironmentFromWithLoopPhiAdjustment(
+ suspend->GetEnvironment(), vector_header_);
+ }
+ }
+ }
+ // Finalize increment and phi.
+ HInstruction* inc = new (global_allocator_) HAdd(induc_type, vector_phi_, step);
+ vector_phi_->AddInput(lo);
+ vector_phi_->AddInput(Insert(vector_body_, inc));
+}
+
+// TODO: accept reductions at left-hand-side, mixed-type store idioms, etc.
+bool HLoopOptimization::VectorizeDef(LoopNode* node,
+ HInstruction* instruction,
+ bool generate_code) {
+ // Accept a left-hand-side array base[index] for
+ // (1) supported vector type,
+ // (2) loop-invariant base,
+ // (3) unit stride index,
+ // (4) vectorizable right-hand-side value.
+ uint64_t restrictions = kNone;
+ if (instruction->IsArraySet()) {
+ Primitive::Type type = instruction->AsArraySet()->GetComponentType();
+ HInstruction* base = instruction->InputAt(0);
+ HInstruction* index = instruction->InputAt(1);
+ HInstruction* value = instruction->InputAt(2);
+ HInstruction* offset = nullptr;
+ if (TrySetVectorType(type, &restrictions) &&
+ node->loop_info->IsDefinedOutOfTheLoop(base) &&
+ induction_range_.IsUnitStride(index, &offset) &&
+ VectorizeUse(node, value, generate_code, type, restrictions)) {
+ if (generate_code) {
+ GenerateVecSub(index, offset);
+ GenerateVecMem(instruction, vector_map_->Get(index), vector_map_->Get(value), type);
+ } else {
+ vector_refs_->insert(ArrayReference(base, offset, type, /*lhs*/ true));
+ }
return true;
}
+ return false;
+ }
+ // Branch back okay.
+ if (instruction->IsGoto()) {
+ return true;
+ }
+ // Otherwise accept only expressions with no effects outside the immediate loop-body.
+ // Note that actual uses are inspected during right-hand-side tree traversal.
+ return !IsUsedOutsideLoop(node->loop_info, instruction) && !instruction->DoesAnyWrite();
+}
+
+// TODO: more operations and intrinsics, detect saturation arithmetic, etc.
+bool HLoopOptimization::VectorizeUse(LoopNode* node,
+ HInstruction* instruction,
+ bool generate_code,
+ Primitive::Type type,
+ uint64_t restrictions) {
+ // Accept anything for which code has already been generated.
+ if (generate_code) {
+ if (vector_map_->find(instruction) != vector_map_->end()) {
+ return true;
+ }
+ }
+ // Continue the right-hand-side tree traversal, passing in proper
+ // types and vector restrictions along the way. During code generation,
+ // all new nodes are drawn from the global allocator.
+ if (node->loop_info->IsDefinedOutOfTheLoop(instruction)) {
+ // Accept invariant use, using scalar expansion.
+ if (generate_code) {
+ GenerateVecInv(instruction, type);
+ }
+ return true;
+ } else if (instruction->IsArrayGet()) {
+ // Accept a right-hand-side array base[index] for
+ // (1) exact matching vector type,
+ // (2) loop-invariant base,
+ // (3) unit stride index,
+ // (4) vectorizable right-hand-side value.
+ HInstruction* base = instruction->InputAt(0);
+ HInstruction* index = instruction->InputAt(1);
+ HInstruction* offset = nullptr;
+ if (type == instruction->GetType() &&
+ node->loop_info->IsDefinedOutOfTheLoop(base) &&
+ induction_range_.IsUnitStride(index, &offset)) {
+ if (generate_code) {
+ GenerateVecSub(index, offset);
+ GenerateVecMem(instruction, vector_map_->Get(index), nullptr, type);
+ } else {
+ vector_refs_->insert(ArrayReference(base, offset, type, /*lhs*/ false));
+ }
+ return true;
+ }
+ } else if (instruction->IsTypeConversion()) {
+ // Accept particular type conversions.
+ HTypeConversion* conversion = instruction->AsTypeConversion();
+ HInstruction* opa = conversion->InputAt(0);
+ Primitive::Type from = conversion->GetInputType();
+ Primitive::Type to = conversion->GetResultType();
+ if ((to == Primitive::kPrimByte ||
+ to == Primitive::kPrimChar ||
+ to == Primitive::kPrimShort) && from == Primitive::kPrimInt) {
+ // Accept a "narrowing" type conversion from a "wider" computation for
+ // (1) conversion into final required type,
+ // (2) vectorizable operand,
+ // (3) "wider" operations cannot bring in higher order bits.
+ if (to == type && VectorizeUse(node, opa, generate_code, type, restrictions | kNoHiBits)) {
+ if (generate_code) {
+ if (vector_mode_ == kVector) {
+ vector_map_->Put(instruction, vector_map_->Get(opa)); // operand pass-through
+ } else {
+ GenerateVecOp(instruction, vector_map_->Get(opa), nullptr, type);
+ }
+ }
+ return true;
+ }
+ } else if (to == Primitive::kPrimFloat && from == Primitive::kPrimInt) {
+ DCHECK_EQ(to, type);
+ // Accept int to float conversion for
+ // (1) supported int,
+ // (2) vectorizable operand.
+ if (TrySetVectorType(from, &restrictions) &&
+ VectorizeUse(node, opa, generate_code, from, restrictions)) {
+ if (generate_code) {
+ GenerateVecOp(instruction, vector_map_->Get(opa), nullptr, type);
+ }
+ return true;
+ }
+ }
+ return false;
+ } else if (instruction->IsNeg() || instruction->IsNot() || instruction->IsBooleanNot()) {
+ // Accept unary operator for vectorizable operand.
+ HInstruction* opa = instruction->InputAt(0);
+ if (VectorizeUse(node, opa, generate_code, type, restrictions)) {
+ if (generate_code) {
+ GenerateVecOp(instruction, vector_map_->Get(opa), nullptr, type);
+ }
+ return true;
+ }
+ } else if (instruction->IsAdd() || instruction->IsSub() ||
+ instruction->IsMul() || instruction->IsDiv() ||
+ instruction->IsAnd() || instruction->IsOr() || instruction->IsXor()) {
+ // Deal with vector restrictions.
+ if ((instruction->IsMul() && HasVectorRestrictions(restrictions, kNoMul)) ||
+ (instruction->IsDiv() && HasVectorRestrictions(restrictions, kNoDiv))) {
+ return false;
+ }
+ // Accept binary operator for vectorizable operands.
+ HInstruction* opa = instruction->InputAt(0);
+ HInstruction* opb = instruction->InputAt(1);
+ if (VectorizeUse(node, opa, generate_code, type, restrictions) &&
+ VectorizeUse(node, opb, generate_code, type, restrictions)) {
+ if (generate_code) {
+ GenerateVecOp(instruction, vector_map_->Get(opa), vector_map_->Get(opb), type);
+ }
+ return true;
+ }
+ } else if (instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()) {
+ // Deal with vector restrictions.
+ if ((HasVectorRestrictions(restrictions, kNoShift)) ||
+ (instruction->IsShr() && HasVectorRestrictions(restrictions, kNoShr))) {
+ return false; // unsupported instruction
+ } else if ((instruction->IsShr() || instruction->IsUShr()) &&
+ HasVectorRestrictions(restrictions, kNoHiBits)) {
+ return false; // hibits may impact lobits; TODO: we can do better!
+ }
+ // Accept shift operator for vectorizable/invariant operands.
+ // TODO: accept symbolic, albeit loop invariant shift factors.
+ HInstruction* opa = instruction->InputAt(0);
+ HInstruction* opb = instruction->InputAt(1);
+ if (VectorizeUse(node, opa, generate_code, type, restrictions) && opb->IsIntConstant()) {
+ if (generate_code) {
+ // Make sure shift factor only looks at lower bits, as defined for sequential shifts.
+ // Note that even the narrower SIMD shifts do the right thing after that.
+ int32_t mask = (instruction->GetType() == Primitive::kPrimLong)
+ ? kMaxLongShiftDistance
+ : kMaxIntShiftDistance;
+ HInstruction* s = graph_->GetIntConstant(opb->AsIntConstant()->GetValue() & mask);
+ GenerateVecOp(instruction, vector_map_->Get(opa), s, type);
+ }
+ return true;
+ }
+ } else if (instruction->IsInvokeStaticOrDirect()) {
+ // TODO: coming soon.
+ return false;
}
return false;
}
-bool HLoopOptimization::IsPhiInduction(HPhi* phi) {
+bool HLoopOptimization::TrySetVectorType(Primitive::Type type, uint64_t* restrictions) {
+ const InstructionSetFeatures* features = compiler_driver_->GetInstructionSetFeatures();
+ switch (compiler_driver_->GetInstructionSet()) {
+ case kArm:
+ case kThumb2:
+ return false;
+ case kArm64:
+ // Allow vectorization for all ARM devices, because Android assumes that
+ // ARMv8 AArch64 always supports advanced SIMD. For now, only D registers
+ // (64-bit vectors) not Q registers (128-bit vectors).
+ switch (type) {
+ case Primitive::kPrimBoolean:
+ case Primitive::kPrimByte:
+ *restrictions |= kNoDiv;
+ return TrySetVectorLength(8);
+ case Primitive::kPrimChar:
+ case Primitive::kPrimShort:
+ *restrictions |= kNoDiv;
+ return TrySetVectorLength(4);
+ case Primitive::kPrimInt:
+ *restrictions |= kNoDiv;
+ return TrySetVectorLength(2);
+ case Primitive::kPrimFloat:
+ return TrySetVectorLength(2);
+ default:
+ return false;
+ }
+ case kX86:
+ case kX86_64:
+ // Allow vectorization for SSE4-enabled X86 devices only (128-bit vectors).
+ if (features->AsX86InstructionSetFeatures()->HasSSE4_1()) {
+ switch (type) {
+ case Primitive::kPrimBoolean:
+ case Primitive::kPrimByte:
+ *restrictions |= kNoMul | kNoDiv | kNoShift;
+ return TrySetVectorLength(16);
+ case Primitive::kPrimChar:
+ case Primitive::kPrimShort:
+ *restrictions |= kNoDiv;
+ return TrySetVectorLength(8);
+ case Primitive::kPrimInt:
+ *restrictions |= kNoDiv;
+ return TrySetVectorLength(4);
+ case Primitive::kPrimLong:
+ *restrictions |= kNoMul | kNoDiv | kNoShr;
+ return TrySetVectorLength(2);
+ case Primitive::kPrimFloat:
+ return TrySetVectorLength(4);
+ case Primitive::kPrimDouble:
+ return TrySetVectorLength(2);
+ default:
+ break;
+ } // switch type
+ }
+ return false;
+ case kMips:
+ case kMips64:
+ // TODO: implement MIPS SIMD.
+ return false;
+ default:
+ return false;
+ } // switch instruction set
+}
+
+bool HLoopOptimization::TrySetVectorLength(uint32_t length) {
+ DCHECK(IsPowerOfTwo(length) && length >= 2u);
+ // First time set?
+ if (vector_length_ == 0) {
+ vector_length_ = length;
+ }
+ // Different types are acceptable within a loop-body, as long as all the corresponding vector
+ // lengths match exactly to obtain a uniform traversal through the vector iteration space
+ // (idiomatic exceptions to this rule can be handled by further unrolling sub-expressions).
+ return vector_length_ == length;
+}
+
+void HLoopOptimization::GenerateVecInv(HInstruction* org, Primitive::Type type) {
+ if (vector_map_->find(org) == vector_map_->end()) {
+ // In scalar code, just use a self pass-through for scalar invariants
+ // (viz. expression remains itself).
+ if (vector_mode_ == kSequential) {
+ vector_map_->Put(org, org);
+ return;
+ }
+ // In vector code, explicit scalar expansion is needed.
+ HInstruction* vector = new (global_allocator_) HVecReplicateScalar(
+ global_allocator_, org, type, vector_length_);
+ vector_map_->Put(org, Insert(vector_preheader_, vector));
+ }
+}
+
+void HLoopOptimization::GenerateVecSub(HInstruction* org, HInstruction* offset) {
+ if (vector_map_->find(org) == vector_map_->end()) {
+ HInstruction* subscript = vector_phi_;
+ if (offset != nullptr) {
+ subscript = new (global_allocator_) HAdd(Primitive::kPrimInt, subscript, offset);
+ if (org->IsPhi()) {
+ Insert(vector_body_, subscript); // lacks layout placeholder
+ }
+ }
+ vector_map_->Put(org, subscript);
+ }
+}
+
+void HLoopOptimization::GenerateVecMem(HInstruction* org,
+ HInstruction* opa,
+ HInstruction* opb,
+ Primitive::Type type) {
+ HInstruction* vector = nullptr;
+ if (vector_mode_ == kVector) {
+ // Vector store or load.
+ if (opb != nullptr) {
+ vector = new (global_allocator_) HVecStore(
+ global_allocator_, org->InputAt(0), opa, opb, type, vector_length_);
+ } else {
+ vector = new (global_allocator_) HVecLoad(
+ global_allocator_, org->InputAt(0), opa, type, vector_length_);
+ }
+ } else {
+ // Scalar store or load.
+ DCHECK(vector_mode_ == kSequential);
+ if (opb != nullptr) {
+ vector = new (global_allocator_) HArraySet(org->InputAt(0), opa, opb, type, kNoDexPc);
+ } else {
+ vector = new (global_allocator_) HArrayGet(org->InputAt(0), opa, type, kNoDexPc);
+ }
+ }
+ vector_map_->Put(org, vector);
+}
+
+#define GENERATE_VEC(x, y) \
+ if (vector_mode_ == kVector) { \
+ vector = (x); \
+ } else { \
+ DCHECK(vector_mode_ == kSequential); \
+ vector = (y); \
+ } \
+ break;
+
+void HLoopOptimization::GenerateVecOp(HInstruction* org,
+ HInstruction* opa,
+ HInstruction* opb,
+ Primitive::Type type) {
+ if (vector_mode_ == kSequential) {
+ // Scalar code follows implicit integral promotion.
+ if (type == Primitive::kPrimBoolean ||
+ type == Primitive::kPrimByte ||
+ type == Primitive::kPrimChar ||
+ type == Primitive::kPrimShort) {
+ type = Primitive::kPrimInt;
+ }
+ }
+ HInstruction* vector = nullptr;
+ switch (org->GetKind()) {
+ case HInstruction::kNeg:
+ DCHECK(opb == nullptr);
+ GENERATE_VEC(
+ new (global_allocator_) HVecNeg(global_allocator_, opa, type, vector_length_),
+ new (global_allocator_) HNeg(type, opa));
+ case HInstruction::kNot:
+ DCHECK(opb == nullptr);
+ GENERATE_VEC(
+ new (global_allocator_) HVecNot(global_allocator_, opa, type, vector_length_),
+ new (global_allocator_) HNot(type, opa));
+ case HInstruction::kBooleanNot:
+ DCHECK(opb == nullptr);
+ GENERATE_VEC(
+ new (global_allocator_) HVecNot(global_allocator_, opa, type, vector_length_),
+ new (global_allocator_) HBooleanNot(opa));
+ case HInstruction::kTypeConversion:
+ DCHECK(opb == nullptr);
+ GENERATE_VEC(
+ new (global_allocator_) HVecCnv(global_allocator_, opa, type, vector_length_),
+ new (global_allocator_) HTypeConversion(type, opa, kNoDexPc));
+ case HInstruction::kAdd:
+ GENERATE_VEC(
+ new (global_allocator_) HVecAdd(global_allocator_, opa, opb, type, vector_length_),
+ new (global_allocator_) HAdd(type, opa, opb));
+ case HInstruction::kSub:
+ GENERATE_VEC(
+ new (global_allocator_) HVecSub(global_allocator_, opa, opb, type, vector_length_),
+ new (global_allocator_) HSub(type, opa, opb));
+ case HInstruction::kMul:
+ GENERATE_VEC(
+ new (global_allocator_) HVecMul(global_allocator_, opa, opb, type, vector_length_),
+ new (global_allocator_) HMul(type, opa, opb));
+ case HInstruction::kDiv:
+ GENERATE_VEC(
+ new (global_allocator_) HVecDiv(global_allocator_, opa, opb, type, vector_length_),
+ new (global_allocator_) HDiv(type, opa, opb, kNoDexPc));
+ case HInstruction::kAnd:
+ GENERATE_VEC(
+ new (global_allocator_) HVecAnd(global_allocator_, opa, opb, type, vector_length_),
+ new (global_allocator_) HAnd(type, opa, opb));
+ case HInstruction::kOr:
+ GENERATE_VEC(
+ new (global_allocator_) HVecOr(global_allocator_, opa, opb, type, vector_length_),
+ new (global_allocator_) HOr(type, opa, opb));
+ case HInstruction::kXor:
+ GENERATE_VEC(
+ new (global_allocator_) HVecXor(global_allocator_, opa, opb, type, vector_length_),
+ new (global_allocator_) HXor(type, opa, opb));
+ case HInstruction::kShl:
+ GENERATE_VEC(
+ new (global_allocator_) HVecShl(global_allocator_, opa, opb, type, vector_length_),
+ new (global_allocator_) HShl(type, opa, opb));
+ case HInstruction::kShr:
+ GENERATE_VEC(
+ new (global_allocator_) HVecShr(global_allocator_, opa, opb, type, vector_length_),
+ new (global_allocator_) HShr(type, opa, opb));
+ case HInstruction::kUShr:
+ GENERATE_VEC(
+ new (global_allocator_) HVecUShr(global_allocator_, opa, opb, type, vector_length_),
+ new (global_allocator_) HUShr(type, opa, opb));
+ case HInstruction::kInvokeStaticOrDirect: {
+ // TODO: coming soon.
+ break;
+ }
+ default:
+ break;
+ } // switch
+ CHECK(vector != nullptr) << "Unsupported SIMD operator";
+ vector_map_->Put(org, vector);
+}
+
+#undef GENERATE_VEC
+
+//
+// Helpers.
+//
+
+bool HLoopOptimization::TrySetPhiInduction(HPhi* phi, bool restrict_uses) {
+ DCHECK(iset_->empty());
ArenaSet<HInstruction*>* set = induction_range_.LookupCycle(phi);
if (set != nullptr) {
- DCHECK(iset_->empty());
for (HInstruction* i : *set) {
// Check that, other than instructions that are no longer in the graph (removed earlier)
- // each instruction is removable and, other than the phi, uses are contained in the cycle.
+ // each instruction is removable and, when restrict uses are requested, other than for phi,
+ // all uses are contained within the cycle.
if (!i->IsInBlock()) {
continue;
} else if (!i->IsRemovable()) {
return false;
- } else if (i != phi) {
+ } else if (i != phi && restrict_uses) {
for (const HUseListNode<HInstruction*>& use : i->GetUses()) {
if (set->find(use.GetUser()) == set->end()) {
return false;
@@ -348,10 +1003,12 @@
// c: Condition(phi, bound)
// i: If(c)
// TODO: Find a less pattern matching approach?
-bool HLoopOptimization::IsEmptyHeader(HBasicBlock* block) {
+bool HLoopOptimization::TrySetSimpleLoopHeader(HBasicBlock* block) {
DCHECK(iset_->empty());
HInstruction* phi = block->GetFirstPhi();
- if (phi != nullptr && phi->GetNext() == nullptr && IsPhiInduction(phi->AsPhi())) {
+ if (phi != nullptr &&
+ phi->GetNext() == nullptr &&
+ TrySetPhiInduction(phi->AsPhi(), /*restrict_uses*/ false)) {
HInstruction* s = block->GetFirstInstruction();
if (s != nullptr && s->IsSuspendCheck()) {
HInstruction* c = s->GetNext();
@@ -369,14 +1026,24 @@
}
bool HLoopOptimization::IsEmptyBody(HBasicBlock* block) {
- if (block->GetFirstPhi() == nullptr) {
- for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
- HInstruction* instruction = it.Current();
- if (!instruction->IsGoto() && iset_->find(instruction) == iset_->end()) {
- return false;
- }
+ if (!block->GetPhis().IsEmpty()) {
+ return false;
+ }
+ for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+ HInstruction* instruction = it.Current();
+ if (!instruction->IsGoto() && iset_->find(instruction) == iset_->end()) {
+ return false;
}
- return true;
+ }
+ return true;
+}
+
+bool HLoopOptimization::IsUsedOutsideLoop(HLoopInformation* loop_info,
+ HInstruction* instruction) {
+ for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
+ if (use.GetUser()->GetBlock()->GetLoopInformation() != loop_info) {
+ return true;
+ }
}
return false;
}
@@ -438,6 +1105,19 @@
return false;
}
+bool HLoopOptimization::TryAssignLastValue(HLoopInformation* loop_info,
+ HInstruction* instruction,
+ HBasicBlock* block,
+ bool collect_loop_uses) {
+ // Assigning the last value is always successful if there are no uses.
+ // Otherwise, it succeeds in a no early-exit loop by generating the
+ // proper last value assignment.
+ int32_t use_count = 0;
+ return IsOnlyUsedAfterLoop(loop_info, instruction, collect_loop_uses, &use_count) &&
+ (use_count == 0 ||
+ (!IsEarlyExit(loop_info) && TryReplaceWithLastValue(instruction, block)));
+}
+
void HLoopOptimization::RemoveDeadInstructions(const HInstructionList& list) {
for (HBackwardInstructionIterator i(list); !i.Done(); i.Advance()) {
HInstruction* instruction = i.Current();