// Enable floating-point static evaluation during constant folding // only if all floating-point operations and constants evaluate in the // range and precision of the type used (i.e., 32-bit float, 64-bit // double). static constexpr bool kEnableFloatingPointStaticEvaluation = (FLT_EVAL_METHOD == 0);
// Remove the environment use records of the instruction for users. void HInstruction::RemoveEnvironmentUses() { for (HEnvironment* environment = GetEnvironment();
environment != nullptr;
environment = environment->GetParent()) { for (size_t i = 0, e = environment->Size(); i < e; ++i) { if (environment->GetInstructionAt(i) != nullptr) {
environment->RemoveAsUserOfInput(i);
}
}
}
}
// Return whether the instruction has an environment and it's used by others. bool HasEnvironmentUsedByOthers(HInstruction* instruction) { for (HEnvironment* environment = instruction->GetEnvironment();
environment != nullptr;
environment = environment->GetParent()) { for (size_t i = 0, e = environment->Size(); i < e; ++i) {
HInstruction* user = environment->GetInstructionAt(i); if (user != nullptr) { returntrue;
}
}
} returnfalse;
}
// Reset environment records of the instruction itself. void ResetEnvironmentInputRecords(HInstruction* instruction) { for (HEnvironment* environment = instruction->GetEnvironment();
environment != nullptr;
environment = environment->GetParent()) { for (size_t i = 0, e = environment->Size(); i < e; ++i) {
DCHECK(environment->GetHolder() == instruction); if (environment->GetInstructionAt(i) != nullptr) {
environment->SetRawEnvAt(i, nullptr);
}
}
}
}
// This method assumes `insn` has been removed from all users with the exception of catch // phis because of missing exceptional edges in the graph. It removes the // instruction from catch phi uses, together with inputs of other catch phis in // the catch block at the same index, as these must be dead too. staticvoid RemoveCatchPhiUsesOfDeadInstruction(HInstruction* insn) {
DCHECK(!insn->HasEnvironmentUses()); while (insn->HasNonEnvironmentUses()) { const HUseListNode<HInstruction*>& use = insn->GetUses().front();
size_t use_index = use.GetIndex();
HBasicBlock* user_block = use.GetUser()->GetBlock();
DCHECK(use.GetUser()->IsPhi());
DCHECK(user_block->IsCatchBlock()); for (HInstructionIteratorPrefetchNext phi_it(user_block->GetPhis()); !phi_it.Done();
phi_it.Advance()) {
phi_it.Current()->AsPhi()->RemoveInputAt(use_index);
}
}
}
bool HBasicBlock::Dominates(const HBasicBlock* other) const { // Walk up the dominator tree from `other`, to find out if `this` // is an ancestor. const HBasicBlock* current = other; while (current != nullptr) { if (current == this) { returntrue;
}
current = current->GetDominator();
} returnfalse;
}
staticvoid UpdateInputsUsers(HGraph* graph, HInstruction* instruction) {
HInputsRef inputs = instruction->GetInputs(); if (inputs.size() != 0u) {
ArenaAllocator* allocator = graph->GetAllocator(); for (size_t i = 0; i < inputs.size(); ++i) {
inputs[i]->AddUseAt(allocator, instruction, i);
}
} // Environment should be created later.
DCHECK(!instruction->HasEnvironment());
}
void HEnvironment::CopyFrom(ArenaAllocator* allocator, ArrayRef<HInstruction* const> locals) {
DCHECK_EQ(locals.size(), Size()); for (size_t i = 0; i < locals.size(); i++) {
HInstruction* instruction = locals[i];
SetRawEnvAt(i, instruction); if (instruction != nullptr) {
instruction->AddEnvUseAt(allocator, this, i);
}
}
}
void HEnvironment::CopyFrom(ArenaAllocator* allocator, const HEnvironment* env) {
DCHECK_EQ(env->Size(), Size()); for (size_t i = 0; i < env->Size(); i++) {
HInstruction* instruction = env->GetInstructionAt(i);
SetRawEnvAt(i, instruction); if (instruction != nullptr) {
instruction->AddEnvUseAt(allocator, this, i);
}
}
}
void HEnvironment::CopyFromWithLoopPhiAdjustment(ArenaAllocator* allocator,
HEnvironment* env,
HBasicBlock* loop_header) {
DCHECK(loop_header->IsLoopHeader()); for (size_t i = 0; i < env->Size(); i++) {
HInstruction* instruction = env->GetInstructionAt(i);
SetRawEnvAt(i, instruction); if (instruction == nullptr) { continue;
} if (instruction->IsLoopHeaderPhi() && (instruction->GetBlock() == loop_header)) { // At the end of the loop pre-header, the corresponding value for instruction // is the first input of the phi.
HInstruction* initial = instruction->AsPhi()->InputAt(0);
SetRawEnvAt(i, initial);
initial->AddEnvUseAt(allocator, this, i);
} else {
instruction->AddEnvUseAt(allocator, this, i);
}
}
}
bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const { if (other_instruction == this) { // An instruction does not strictly dominate itself. returnfalse;
}
HBasicBlock* block = GetBlock();
HBasicBlock* other_block = other_instruction->GetBlock(); if (block != other_block) { return GetBlock()->Dominates(other_instruction->GetBlock());
} else { // If both instructions are in the same block, ensure this // instruction comes before `other_instruction`. if (IsPhi()) { if (!other_instruction->IsPhi()) { // Phis appear before non phi-instructions so this instruction // dominates `other_instruction`. returntrue;
} else { // There is no order among phis.
LOG(FATAL) << "There is no dominance between phis of a same block.";
UNREACHABLE();
}
} else { // `this` is not a phi. if (other_instruction->IsPhi()) { // Phis appear before non phi-instructions so this instruction // does not dominate `other_instruction`. returnfalse;
} else { // Check whether this instruction comes before // `other_instruction` in the instruction list. return block->GetInstructions().FoundBefore(this, other_instruction);
}
}
}
}
// Lazily compute the dominated blocks to faster calculation of domination afterwards. auto maybe_generate_visited_blocks = [&visited_blocks, this, dominator_block]() { if (visited_blocks.SizeInBits() != 0u) {
DCHECK_EQ(visited_blocks.SizeInBits(), GetBlock()->GetGraph()->GetBlocks().size()); return;
}
HGraph* graph = GetBlock()->GetGraph(); const size_t size = graph->GetBlocks().size();
visited_blocks = ArenaBitVector::CreateFixedSize(graph->GetAllocator(), size, kArenaAllocMisc);
ScopedArenaAllocator allocator(graph->GetArenaStack());
ScopedArenaVector<const HBasicBlock*> worklist(allocator.Adapter(kArenaAllocMisc));
worklist.reserve(size);
worklist.push_back(dominator_block);
visited_blocks.SetBit(dominator_block->GetBlockId());
while (!worklist.empty()) { const HBasicBlock* current = worklist.back();
worklist.pop_back(); for (HBasicBlock* dominated : current->GetDominatedBlocks()) {
DCHECK(!visited_blocks.IsBitSet(dominated->GetBlockId()));
visited_blocks.SetBit(dominated->GetBlockId());
worklist.push_back(dominated);
}
}
};
const HUseList<HInstruction*>& uses = GetUses(); for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
HInstruction* user = it->GetUser();
HBasicBlock* block = user->GetBlock();
size_t index = it->GetIndex(); // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput().
++it; bool dominated = false; if (dominator_block == block) { // Trickier case, call the other methods.
dominated =
strictly_dominated ? dominator->StrictlyDominates(user) : dominator->Dominates(user);
} else { // Block domination.
maybe_generate_visited_blocks();
dominated = visited_blocks.IsBitSet(block->GetBlockId());
}
if (dominated) {
user->ReplaceInput(replacement, index);
} elseif (user->IsPhi() && !user->AsPhi()->IsCatchPhi()) { // If the input flows from a block dominated by `dominator`, we can replace it. // We do not perform this for catch phis as we don't have control flow support // for their inputs.
HBasicBlock* predecessor = block->GetPredecessors()[index];
maybe_generate_visited_blocks(); if (visited_blocks.IsBitSet(predecessor->GetBlockId())) {
user->ReplaceInput(replacement, index);
}
}
}
}
void HInstruction::ReplaceEnvUsesDominatedBy(HInstruction* dominator, HInstruction* replacement) { const HUseList<HEnvironment*>& uses = GetEnvUses(); for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
HEnvironment* user = it->GetUser();
size_t index = it->GetIndex(); // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput().
++it; if (dominator->StrictlyDominates(user->GetHolder())) {
user->ReplaceInput(replacement, index);
}
}
}
void HVariableInputSizeInstruction::InsertInputAt(size_t index, HInstruction* input) {
inputs_.insert(inputs_.begin() + index, HUserRecord<HInstruction*>(input)); // Update indexes in use nodes of inputs that have been pushed further back by the insert(). for (size_t i = index + 1u, e = inputs_.size(); i < e; ++i) {
DCHECK_EQ(inputs_[i].GetUseNode()->GetIndex(), i - 1u);
inputs_[i].GetUseNode()->SetIndex(i);
} // Add the use after updating the indexes. If the `input` is already used by `this`, // the fixup after use insertion can use those indexes.
input->AddUseAt(GetBlock()->GetGraph()->GetAllocator(), this, index);
}
void HVariableInputSizeInstruction::RemoveInputAt(size_t index) {
RemoveAsUserOfInput(index);
inputs_.erase(inputs_.begin() + index); // Update indexes in use nodes of inputs that have been pulled forward by the erase(). for (size_t i = index, e = inputs_.size(); i < e; ++i) {
DCHECK_EQ(inputs_[i].GetUseNode()->GetIndex(), i + 1u);
inputs_[i].GetUseNode()->SetIndex(i);
}
}
inlinevoid HPhi::ReplaceInputPhiWithItsInputsAt(ArenaAllocator* allocator, size_t index) {
DCHECK(inputs_[index].GetInstruction()->IsPhi());
HPhi* src = inputs_[index].GetInstruction()->AsPhi();
size_t num_src_inputs = src->inputs_.size();
DCHECK_GE(num_src_inputs, 2u); // Replace the `src` input with its first input.
ReplaceInput(src->inputs_[0].GetInstruction(), index); // Insert `src`'s other inputs.
inputs_.insert(inputs_.begin() + index + 1u, src->inputs_.begin() + 1u, src->inputs_.end()); // Update indexes in use nodes of inputs that have been pushed further back by the insert(). for (size_t i = index + num_src_inputs, e = inputs_.size(); i < e; ++i) {
DCHECK_EQ(inputs_[i].GetUseNode()->GetIndex(), i - (num_src_inputs - 1u));
inputs_[i].GetUseNode()->SetIndex(i);
} // Add the uses after updating the indexes. If the copied inputs are already used by `this`, // the fixup after use insertion can use those indexes. for (size_t new_index = index + 1u; new_index != index + num_src_inputs; ++new_index) {
inputs_[new_index].GetInstruction()->AddUseAt(allocator, this, new_index);
}
}
inlinevoid HPhi::DuplicateInputAt(ArenaAllocator* allocator, size_t index, size_t new_copies) {
DCHECK_NE(new_copies, 0u);
HInstruction* to_copy = inputs_[index].GetInstruction(); // Insert new copies of `to_copy`.
inputs_.insert(inputs_.begin() + index + 1u, new_copies, HUserRecord<HInstruction*>(to_copy));
size_t end_copies = index + 1u + new_copies; // Update indexes in use nodes of inputs that have been pushed further back by the insert(). for (size_t i = end_copies, e = inputs_.size(); i < e; ++i) {
DCHECK_EQ(inputs_[i].GetUseNode()->GetIndex(), i - new_copies);
inputs_[i].GetUseNode()->SetIndex(i);
} // Add the uses after updating the indexes. If the `to_copy` is already used by `this`, // the fixup after use insertion can use those indexes. for (size_t new_index = index + 1u; new_index != end_copies; ++new_index) {
to_copy->AddUseAt(allocator, this, new_index);
}
}
size_t HConstructorFence::RemoveConstructorFences(HInstruction* instruction) {
DCHECK(instruction->GetBlock() != nullptr); // Removing constructor fences only makes sense for instructions with an object return type.
DCHECK_EQ(DataType::Type::kReference, instruction->GetType());
// Return how many instructions were removed for statistic purposes.
size_t remove_count = 0;
// Efficient implementation that simultaneously (in one pass): // * Scans the uses list for all constructor fences. // * Deletes that constructor fence from the uses list of `instruction`. // * Deletes `instruction` from the constructor fence's inputs. // * Deletes the constructor fence if it now has 0 inputs.
const HUseList<HInstruction*>& uses = instruction->GetUses(); // Warning: Although this is "const", we might mutate the list when calling RemoveInputAt. for (auto it = uses.begin(), end = uses.end(); it != end; ) { const HUseListNode<HInstruction*>& use_node = *it;
HInstruction* const use_instruction = use_node.GetUser();
// Advance the iterator immediately once we fetch the use_node. // Warning: If the input is removed, the current iterator becomes invalid.
++it;
// Process the candidate instruction for removal // from the graph.
// Constructor fence instructions are never // used by other instructions. // // If we wanted to make this more generic, it // could be a runtime if statement.
DCHECK(!ctor_fence->HasUses());
// A constructor fence's return type is "kPrimVoid" // and therefore it can't have any environment uses.
DCHECK(!ctor_fence->HasEnvironmentUses());
// Remove the inputs first, otherwise removing the instruction // will try to remove its uses while we are already removing uses // and this operation will fail.
DCHECK_EQ(instruction, ctor_fence->InputAt(input_index));
// Removing the input will also remove the `use_node`. // (Do not look at `use_node` after this, it will be a dangling reference).
ctor_fence->RemoveInputAt(input_index);
// Once all inputs are removed, the fence is considered dead and // is removed. if (ctor_fence->InputCount() == 0u) {
ctor_fence->GetBlock()->RemoveInstruction(ctor_fence);
++remove_count;
}
}
}
if (kIsDebugBuild) { // Post-condition checks: // * None of the uses of `instruction` are a constructor fence. // * The `instruction` itself did not get removed from a block. for (const HUseListNode<HInstruction*>& use_node : instruction->GetUses()) {
CHECK(!use_node.GetUser()->IsConstructorFence());
}
CHECK(instruction->GetBlock() != nullptr);
}
return remove_count;
}
void HConstructorFence::Merge(HConstructorFence* other) { // Do not delete yourself from the graph.
DCHECK(this != other); // Don't try to merge with an instruction not associated with a block.
DCHECK(other->GetBlock() != nullptr); // A constructor fence's return type is "kPrimVoid" // and therefore it cannot have any environment uses.
DCHECK(!other->HasEnvironmentUses());
auto has_input = [](HInstruction* haystack, HInstruction* needle) { // Check if `haystack` has `needle` as any of its inputs. for (size_t input_count = 0; input_count < haystack->InputCount(); ++input_count) { if (haystack->InputAt(input_count) == needle) { returntrue;
}
} returnfalse;
};
// Add any inputs from `other` into `this` if it wasn't already an input. for (size_t input_count = 0; input_count < other->InputCount(); ++input_count) {
HInstruction* other_input = other->InputAt(input_count); if (!has_input(this, other_input)) {
AddInput(other_input);
}
}
other->GetBlock()->RemoveInstruction(other);
}
HInstruction* HConstructorFence::GetAssociatedAllocation(bool ignore_inputs) {
HInstruction* new_instance_inst = GetPrevious(); // Check if the immediately preceding instruction is a new-instance/new-array. // Otherwise this fence is for protecting final fields. if (new_instance_inst != nullptr &&
(new_instance_inst->IsNewInstance() || new_instance_inst->IsNewArray())) { if (ignore_inputs) { // If inputs are ignored, simply check if the predecessor is // *any* HNewInstance/HNewArray. // // Inputs are normally only ignored for prepare_for_register_allocation, // at which point *any* prior HNewInstance/Array can be considered // associated. return new_instance_inst;
} else { // Normal case: There must be exactly 1 input and the previous instruction // must be that input. if (InputCount() == 1u && InputAt(0) == new_instance_inst) { return new_instance_inst;
}
}
} return nullptr;
}
// If `GetConstantRight()` returns one of the input, this returns the other // one. Otherwise it returns null.
HInstruction* HBinaryOperation::GetLeastConstantLeft() const {
HInstruction* most_constant_right = GetConstantRight(); if (most_constant_right == nullptr) { return nullptr;
} elseif (most_constant_right == GetLeft()) { return GetRight();
} else { return GetLeft();
}
}
std::ostream& operator<<(std::ostream& os, ComparisonBias rhs) { // TODO: Replace with auto-generated operator<<. switch (rhs) { case ComparisonBias::kNoBias: return os << "none"; case ComparisonBias::kGtBias: return os << "gt"; case ComparisonBias::kLtBias: return os << "lt";
}
}
HCondition* HCondition::Create(HGraph* graph,
IfCondition cond,
HInstruction* lhs,
HInstruction* rhs,
uint32_t dex_pc) {
ArenaAllocator* allocator = graph->GetAllocator(); switch (cond) { case kCondEQ: returnnew (allocator) HEqual(lhs, rhs, dex_pc); case kCondNE: returnnew (allocator) HNotEqual(lhs, rhs, dex_pc); case kCondLT: returnnew (allocator) HLessThan(lhs, rhs, dex_pc); case kCondLE: returnnew (allocator) HLessThanOrEqual(lhs, rhs, dex_pc); case kCondGT: returnnew (allocator) HGreaterThan(lhs, rhs, dex_pc); case kCondGE: returnnew (allocator) HGreaterThanOrEqual(lhs, rhs, dex_pc); case kCondB: returnnew (allocator) HBelow(lhs, rhs, dex_pc); case kCondBE: returnnew (allocator) HBelowOrEqual(lhs, rhs, dex_pc); case kCondA: returnnew (allocator) HAbove(lhs, rhs, dex_pc); case kCondAE: returnnew (allocator) HAboveOrEqual(lhs, rhs, dex_pc); default:
LOG(FATAL) << "Unexpected condition " << cond;
UNREACHABLE();
}
}
std::ostream& operator<<(std::ostream& os, const HInstruction::NoArgsDump rhs) { // TODO Really this should be const but that would require const-ifying // graph-visualizer and HGraphVisitor which are tangled up everywhere. returnconst_cast<HInstruction*>(rhs.ins)->Dump(os, /* dump_args= */ false);
}
std::ostream& operator<<(std::ostream& os, const HInstruction::ArgsDump rhs) { // TODO Really this should be const but that would require const-ifying // graph-visualizer and HGraphVisitor which are tangled up everywhere. returnconst_cast<HInstruction*>(rhs.ins)->Dump(os, /* dump_args= */ true);
}
std::ostream& operator<<(std::ostream& os, const HUseList<HInstruction*>& lst) {
os << "Instructions["; bool first = true; for (constauto& hi : lst) { if (!first) {
os << ", ";
}
first = false;
os << hi.GetUser()->DebugName() << "[id: " << hi.GetUser()->GetId()
<< ", blk: " << hi.GetUser()->GetBlock()->GetBlockId() << "]@" << hi.GetIndex();
}
os << "]"; return os;
}
std::ostream& operator<<(std::ostream& os, const HUseList<HEnvironment*>& lst) {
os << "Environments["; bool first = true; for (constauto& hi : lst) { if (!first) {
os << ", ";
}
first = false;
os << *hi.GetUser()->GetHolder() << "@" << hi.GetIndex();
}
os << "]"; return os;
}
void HInstruction::MoveBefore(HInstruction* cursor, bool do_checks) { if (do_checks) {
DCHECK(!IsPhi());
DCHECK(!IsControlFlow());
DCHECK(CanBeMoved() || // `HShouldDeoptimizeFlag` can only be moved by `CHAGuardOptimization`.
IsShouldDeoptimizeFlag() || // `HCurrentMethod` can only be moved by `HGraph::InlineInto()` to the // outer graph where it shall represent the outer method.
IsCurrentMethod());
DCHECK(!cursor->IsPhi());
}
if (block_->instructions_.first_instruction_ == cursor) {
block_->instructions_.first_instruction_ = this;
}
}
void HInstruction::MoveBeforeFirstUserAndOutOfLoops() {
DCHECK(!CanThrow());
DCHECK(!HasSideEffects());
DCHECK(!HasEnvironmentUses());
DCHECK(HasNonEnvironmentUses());
DCHECK(!IsPhi()); // Makes no sense for Phi.
DCHECK_EQ(InputCount(), 0u);
// Find the target block. auto uses_it = GetUses().begin(); auto uses_end = GetUses().end();
HBasicBlock* target_block = uses_it->GetUser()->GetBlock();
++uses_it; while (uses_it != uses_end && uses_it->GetUser()->GetBlock() == target_block) {
++uses_it;
} if (uses_it != uses_end) { // This instruction has uses in two or more blocks. Find the common dominator.
CommonDominator finder(target_block); for (; uses_it != uses_end; ++uses_it) {
finder.Update(uses_it->GetUser()->GetBlock());
}
target_block = finder.Get();
DCHECK(target_block != nullptr);
} // Move to the first dominator not in a loop. while (target_block->IsInLoop()) {
target_block = target_block->GetDominator();
DCHECK(target_block != nullptr);
}
// Find insertion position.
HInstruction* insert_pos = nullptr; for (const HUseListNode<HInstruction*>& use : GetUses()) { if (use.GetUser()->GetBlock() == target_block &&
(insert_pos == nullptr || use.GetUser()->StrictlyDominates(insert_pos))) {
insert_pos = use.GetUser();
}
} if (insert_pos == nullptr) { // No user in `target_block`, insert before the control flow instruction.
insert_pos = target_block->GetLastInstruction();
DCHECK(insert_pos->IsControlFlow()); // Avoid splitting HCondition from HIf to prevent unnecessary materialization. if (insert_pos->IsIf()) {
HInstruction* if_input = insert_pos->AsIf()->InputAt(0); if (if_input == insert_pos->GetPrevious()) {
insert_pos = if_input;
}
}
}
MoveBefore(insert_pos);
}
HBasicBlock* HBasicBlock::CreateImmediateDominator() {
DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented.";
DCHECK(!IsCatchBlock()) << "Support for updating try/catch information not implemented.";
ArrayRef<HBasicBlock* const> HBasicBlock::GetNormalSuccessors() const { if (EndsWithTryBoundary()) { // The normal-flow successor of HTryBoundary is always stored at index zero.
DCHECK_EQ(successors_[0], GetLastInstruction()->AsTryBoundary()->GetNormalFlowSuccessor()); return ArrayRef<HBasicBlock* const>(successors_).SubArray(0u, 1u);
} else { // All successors of blocks not ending with TryBoundary are normal. return ArrayRef<HBasicBlock* const>(successors_);
}
}
ArrayRef<HBasicBlock* const> HBasicBlock::GetExceptionalSuccessors() const { if (EndsWithTryBoundary()) { return ArrayRef<HBasicBlock* const>(GetSuccessors()).SubArray(1u);
} else { // Blocks not ending with TryBoundary do not have exceptional successors. return ArrayRef<HBasicBlock* const>();
}
}
// Exception handlers need to be stored in the same order. for (size_t i = 0; i < length; ++i) { if (handlers1[i] != handlers2[i]) { returnfalse;
}
} returntrue;
}
void HBasicBlock::DisconnectAndDelete() { // Dominators must be removed after all the blocks they dominate. This way // a loop header is removed last, a requirement for correct loop information // iteration.
DCHECK(dominated_blocks_.empty());
// The following steps gradually remove the block from all its dependants in // post order (b/27683071).
// (1) Store a basic block that we'll use in step (5) to find loops to be updated. // We need to do this before step (4) which destroys the predecessor list.
HBasicBlock* loop_update_start = this; if (IsLoopHeader()) {
HLoopInformation* loop_info = GetLoopInformation(); // All other blocks in this loop should have been removed because the header // was their dominator. // Note that we do not remove `this` from `loop_info` as it is unreachable.
DCHECK(!loop_info->IsIrreducible());
DCHECK_EQ(loop_info->GetBlockMask().NumSetBits(), 1u);
DCHECK_EQ(static_cast<uint32_t>(loop_info->GetBlockMask().GetHighestBitSet()), GetBlockId());
loop_update_start = loop_info->GetPreHeader();
}
// (2) Disconnect the block from its successors and update their phis.
DisconnectFromSuccessors();
// (3) Remove instructions and phis. Instructions should have no remaining uses // except in catch phis. If an instruction is used by a catch phi at `index`, // remove `index`-th input of all phis in the catch block since they are // guaranteed dead. Note that we may miss dead inputs this way but the // graph will always remain consistent.
RemoveCatchPhiUsesAndInstruction(/* building_dominator_tree = */ false);
// (4) Disconnect the block from its predecessors and update their // control-flow instructions. for (HBasicBlock* predecessor : predecessors_) { // We should not see any back edges as they would have been removed by step (3).
DCHECK_IMPLIES(IsInLoop(), !GetLoopInformation()->IsBackEdge(*predecessor));
HInstruction* last_instruction = predecessor->GetLastInstruction(); if (last_instruction->IsTryBoundary() && !IsCatchBlock()) { // This block is the only normal-flow successor of the TryBoundary which // makes `predecessor` dead. Since DCE removes blocks in post order, // exception handlers of this TryBoundary were already visited and any // remaining handlers therefore must be live. We remove `predecessor` from // their list of predecessors.
DCHECK_EQ(last_instruction->AsTryBoundary()->GetNormalFlowSuccessor(), this); while (predecessor->GetSuccessors().size() > 1) {
HBasicBlock* handler = predecessor->GetSuccessors()[1];
DCHECK(handler->IsCatchBlock());
predecessor->RemoveSuccessor(handler);
handler->RemovePredecessor(predecessor);
}
}
predecessor->RemoveSuccessor(this);
uint32_t num_pred_successors = predecessor->GetSuccessors().size(); if (num_pred_successors == 1u) { // If we have one successor after removing one, then we must have // had an HIf, HPackedSwitch or HTryBoundary, as they have more than one // successor. Replace those with a HGoto.
DCHECK(last_instruction->IsIf() ||
last_instruction->IsPackedSwitch() ||
(last_instruction->IsTryBoundary() && IsCatchBlock()));
predecessor->RemoveInstruction(last_instruction);
predecessor->AddInstruction(new (graph_->GetAllocator()) HGoto(last_instruction->GetDexPc()));
} elseif (num_pred_successors == 0u) { // The predecessor has no remaining successors and therefore must be dead. // We deliberately leave it without a control-flow instruction so that the // GraphChecker fails unless it is not removed during the pass too.
predecessor->RemoveInstruction(last_instruction);
} else { // There are multiple successors left. The removed block might be a successor // of a PackedSwitch which will be completely removed (perhaps replaced with // a Goto), or we are deleting a catch block from a TryBoundary. In either // case, leave `last_instruction` as is for now.
DCHECK(last_instruction->IsPackedSwitch() ||
(last_instruction->IsTryBoundary() && IsCatchBlock()));
}
}
predecessors_.clear();
// (5) Remove the block from all loops it is included in. Skip the inner-most // loop if this is the loop header (see definition of `loop_update_start`) // because the loop header's predecessor list has been destroyed in step (4). for (HLoopInformationOutwardIterator it(*loop_update_start); !it.Done(); it.Advance()) {
HLoopInformation* loop_info = it.Current();
loop_info->Remove(this); if (loop_info->IsBackEdge(*this)) { // If this was the last back edge of the loop, we deliberately leave the // loop in an inconsistent state and will fail GraphChecker unless the // entire loop is removed during the pass.
loop_info->RemoveBackEdge(this);
}
}
// (6) Disconnect from the dominator.
dominator_->RemoveDominatedBlock(this);
SetDominator(nullptr);
// (7) Delete from the graph, update reverse post order.
graph_->DeleteDeadEmptyBlock(this);
}
void HBasicBlock::DisconnectFromSuccessors(BitVectorView<const size_t> visited) {
DCHECK_IMPLIES(visited.SizeInBits() != 0u, visited.SizeInBits() == graph_->GetBlocks().size()); for (HBasicBlock* successor : successors_) { // Delete this block from the list of predecessors.
size_t this_index = successor->GetPredecessorIndexOf(this);
successor->predecessors_.erase(successor->predecessors_.begin() + this_index);
if (visited.SizeInBits() != 0u && !visited.IsBitSet(successor->GetBlockId())) { // `successor` itself is dead. Therefore, there is no need to update its phis. continue;
}
DCHECK(!successor->predecessors_.empty());
// Remove this block's entries in the successor's phis. Skips exceptional // successors because catch phi inputs do not correspond to predecessor // blocks but throwing instructions. They are removed in `RemoveCatchPhiUses`. if (!successor->IsCatchBlock()) { if (successor->predecessors_.size() == 1u) { // The successor has just one predecessor left. Replace phis with the only // remaining input. for (HInstructionIteratorPrefetchNext phi_it(successor->GetPhis()); !phi_it.Done();
phi_it.Advance()) {
HPhi* phi = phi_it.Current()->AsPhi();
phi->ReplaceWith(phi->InputAt(1 - this_index));
successor->RemovePhi(phi);
}
} else { for (HInstructionIteratorPrefetchNext phi_it(successor->GetPhis()); !phi_it.Done();
phi_it.Advance()) {
phi_it.Current()->AsPhi()->RemoveInputAt(this_index);
}
}
}
}
successors_.clear();
}
// If we are building the dominator tree, we removed all input records previously. // `RemoveInstruction` will try to remove them again but that's not something we support and we // will crash. We check here since we won't be checking that in RemoveInstruction. if (building_dominator_tree) {
DCHECK(insn->GetUses().empty());
DCHECK(insn->GetEnvUses().empty());
}
RemoveInstruction(insn, /* ensure_safety= */ !building_dominator_tree);
} for (HInstructionIteratorPrefetchNext it(GetPhis()); !it.Done(); it.Advance()) {
HPhi* insn = it.Current()->AsPhi();
RemoveCatchPhiUsesOfDeadInstruction(insn);
// If we are building the dominator tree, we removed all input records previously. // `RemovePhi` will try to remove them again but that's not something we support and we // will crash. We check here since we won't be checking that in RemovePhi. if (building_dominator_tree) {
DCHECK(insn->GetUses().empty());
DCHECK(insn->GetEnvUses().empty());
}
RemovePhi(insn, /* ensure_safety= */ !building_dominator_tree);
}
}
// Move instructions from `other` to `this`.
MergeInstructionsWith(other);
// Remove `other` from the loops it is included in. for (HLoopInformationOutwardIterator it(*other); !it.Done(); it.Advance()) {
HLoopInformation* loop_info = it.Current();
loop_info->Remove(other); if (loop_info->IsBackEdge(*other)) {
loop_info->ReplaceBackEdge(other, this);
}
}
// Update links to the successors of `other`.
successors_.clear(); for (HBasicBlock* successor : other->GetSuccessors()) {
successor->predecessors_[successor->GetPredecessorIndexOf(other)] = this;
}
successors_.swap(other->successors_);
DCHECK(other->successors_.empty());
// Move instructions from `other` to `this`.
instructions_.Add(other->GetInstructions());
other->instructions_.SetBlockOfInstructions(this);
// Update links to the successors of `other`.
successors_.clear(); for (HBasicBlock* successor : other->GetSuccessors()) {
successor->predecessors_[successor->GetPredecessorIndexOf(other)] = this;
}
successors_.swap(other->successors_);
DCHECK(other->successors_.empty());
HBasicBlock* successor = GetSingleSuccessor();
ArenaVector<HBasicBlock*>& succ_preds = successor->predecessors_;
DCHECK_GE(succ_preds.size(), 2u);
// Redirect `successor`'s other predecessors to `this`. // We want to have the final predecessor order as if we inserted data from `this` // to the `successor`. However, this function prepares the data for `MergeWith()`, // so we shall move the data in the opposite direction and insert the other // `successor`'s predecessors around the existing predecessors of `this`.
size_t this_predecessor_index = successor->GetPredecessorIndexOf(this);
predecessors_.reserve(predecessors_.size() + succ_preds.size() - 1u);
predecessors_.insert(predecessors_.begin(),
succ_preds.begin(),
succ_preds.begin() + this_predecessor_index);
predecessors_.insert(predecessors_.begin() + this_predecessor_index + num_old_this_predecessors,
succ_preds.begin() + this_predecessor_index + 1u,
succ_preds.end()); // Move the `this` predecessor to the start where we shall keep it.
std::swap(succ_preds[0], succ_preds[this_predecessor_index]); for (HBasicBlock* pred : ArrayRef<HBasicBlock*>(succ_preds).SubArray(1u)) { // Do not use `ReplaceSuccessor(successor, this)` as that would update `predecessor_` // data in `successor` and `this` and we're already doing that explicitly.
ReplaceElement(pred->successors_, successor, this);
} // Keep the `this` predecessor of `successor` and erase the rest.
succ_preds.erase(succ_preds.begin() + 1u, succ_preds.end());
// Update `successor` `Phi`s' block and input from `this`.
ArenaAllocator* allocator = GetGraph()->GetAllocator(); for (HInstruction* phi = successor->GetFirstPhi(); phi != nullptr; phi = phi->GetNext()) {
DCHECK(phi->IsPhi());
phi->SetBlock(this);
HInstruction* input = phi->AsPhi()->InputAt(this_predecessor_index); if (input->GetBlock() == this) { // The input is defined in `this`, so it must be a `Phi`. (It cannot be the `Goto`.)
DCHECK(input->IsPhi()); // Replace the input `Phi` with its own inputs corresponding to the `this`'s predecessors.
phi->AsPhi()->ReplaceInputPhiWithItsInputsAt(allocator, this_predecessor_index);
} else { // Duplicate the input for additional predecessors of `this`.
phi->AsPhi()->DuplicateInputAt(
allocator, this_predecessor_index, num_old_this_predecessors - 1u);
}
}
// All `Phi`s in `this` are now dead. Remove them. while (GetFirstPhi() != nullptr) {
DCHECK(!GetFirstPhi()->HasUses());
RemovePhi(GetFirstPhi()->AsPhi());
}
// Move updated `Phi`s from `successor` to `this`.
phis_.Add(successor->GetPhis());
successor->phis_.Clear();
}
void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) { if (kIsDebugBuild) {
DCHECK_EQ(GetType(), DataType::Type::kReference);
DCHECK(rti.IsValid()) << "Invalid RTI for " << DebugName(); if (IsBoundType()) { // Having the test here spares us from making the method virtual just for // the sake of a DCHECK.
CheckAgainstUpperBound(rti, AsBoundType()->GetUpperBound());
}
}
reference_type_handle_ = rti.GetTypeHandle();
SetPackedFlag<kFlagReferenceTypeIsExact>(rti.IsExact());
}
void HInstruction::SetReferenceTypeInfoIfValid(ReferenceTypeInfo rti) { if (rti.IsValid()) {
SetReferenceTypeInfo(rti);
}
}
void HBoundType::SetUpperBound(const ReferenceTypeInfo& upper_bound, bool can_be_null) { if (kIsDebugBuild) {
DCHECK(upper_bound.IsValid());
DCHECK(!upper_bound_.IsValid()) << "Upper bound should only be set once.";
CheckAgainstUpperBound(GetReferenceTypeInfo(), upper_bound);
}
upper_bound_ = upper_bound;
SetPackedFlag<kFlagUpperCanBeNull>(can_be_null);
}
bool HInstruction::HasAnyEnvironmentUseBefore(HInstruction* other) { // For now, assume that instructions in different blocks may use the // environment. // TODO: Use the control flow to decide if this is true. if (GetBlock() != other->GetBlock()) { returntrue;
}
// We know that we are in the same block. Walk from 'this' to 'other', // checking to see if there is any instruction with an environment.
HInstruction* current = this; for (; current != other && current != nullptr; current = current->GetNext()) { // This is a conservative check, as the instruction result may not be in // the referenced environment. if (current->HasEnvironment()) { returntrue;
}
}
// We should have been called with 'this' before 'other' in the block. // Just confirm this.
DCHECK(current != nullptr); returnfalse;
}
// Adjust method's side effects from intrinsic table. switch (side_effects) { case kNoSideEffects: SetSideEffects(SideEffects::None()); break; case kReadSideEffects: SetSideEffects(SideEffects::AllReads()); break; case kWriteSideEffects: SetSideEffects(SideEffects::AllWrites()); break; case kAllSideEffects: SetSideEffects(SideEffects::AllExceptGCDependency()); break;
}
if (needs_env == kNoEnvironment) {
opt.SetDoesNotNeedEnvironment();
} else { // If we need an environment, that means there will be a call, which can trigger GC.
SetSideEffects(GetSideEffects().Union(SideEffects::CanTriggerGC()));
} // Adjust method's exception status from intrinsic table.
SetCanThrow(exceptions == kCanThrow);
}
const DexFile& HInvokeStaticOrDirect::GetDexFileForPcRelativeDexCache() const {
ArtMethod* caller = GetEnvironment()->GetMethod();
ScopedObjectAccess soa(Thread::Current()); // `caller` is null for a top-level graph representing a method whose declaring // class was not resolved. return caller == nullptr ? GetBlock()->GetGraph()->GetDexFile() : *caller->GetDexFile();
}
std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::ClinitCheckRequirement rhs) { switch (rhs) { case HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit: return os << "explicit"; case HInvokeStaticOrDirect::ClinitCheckRequirement::kImplicit: return os << "implicit"; case HInvokeStaticOrDirect::ClinitCheckRequirement::kNone: return os << "none";
}
}
bool HInvoke::CanBeNull() const { switch (GetIntrinsic()) { case Intrinsics::kThreadCurrentThread: case Intrinsics::kStringBufferAppend: case Intrinsics::kStringBufferToString: case Intrinsics::kStringBuilderAppendObject: case Intrinsics::kStringBuilderAppendString: case Intrinsics::kStringBuilderAppendCharSequence: case Intrinsics::kStringBuilderAppendCharArray: case Intrinsics::kStringBuilderAppendBoolean: case Intrinsics::kStringBuilderAppendChar: case Intrinsics::kStringBuilderAppendInt: case Intrinsics::kStringBuilderAppendLong: case Intrinsics::kStringBuilderAppendFloat: case Intrinsics::kStringBuilderAppendDouble: case Intrinsics::kStringBuilderToString: #define DEFINE_BOXED_CASE(name, unused1, unused2, unused3, unused4) \ case Intrinsics::k##name##ValueOf:
BOXED_TYPES(DEFINE_BOXED_CASE) #undef DEFINE_BOXED_CASE returnfalse; default: return GetType() == DataType::Type::kReference;
}
}
switch (access_mode_template) { case mirror::VarHandle::AccessModeTemplate::kGet: case mirror::VarHandle::AccessModeTemplate::kGetAndUpdate: case mirror::VarHandle::AccessModeTemplate::kCompareAndExchange: return GetType() == DataType::Type::kReference; case mirror::VarHandle::AccessModeTemplate::kSet: case mirror::VarHandle::AccessModeTemplate::kCompareAndSet: returnfalse;
}
}
bool HInvokeVirtual::CanDoImplicitNullCheckOn(HInstruction* obj) const { if (obj != InputAt(0)) { returnfalse;
} switch (GetIntrinsic()) { case Intrinsics::kNone: returntrue; case Intrinsics::kReferenceRefersTo: returntrue; default: // TODO: Add implicit null checks in more intrinsics. returnfalse;
}
}
bool HLoadClass::InstructionDataEquals(const HInstruction* other) const { const HLoadClass* other_load_class = other->AsLoadClass(); // TODO: To allow GVN for HLoadClass from different dex files, we should compare the type // names rather than type indexes. However, we shall also have to re-think the hash code. if (type_index_ != other_load_class->type_index_ ||
GetPackedFields() != other_load_class->GetPackedFields()) { returnfalse;
} switch (GetLoadKind()) { case LoadKind::kBootImageRelRo: case LoadKind::kJitBootImageAddress: case LoadKind::kJitTableAddress: {
ScopedObjectAccess soa(Thread::Current()); return GetClass().Get() == other_load_class->GetClass().Get();
} default:
DCHECK(HasTypeReference(GetLoadKind())); return IsSameDexFile(GetDexFile(), other_load_class->GetDexFile());
}
}
bool HLoadString::InstructionDataEquals(const HInstruction* other) const { const HLoadString* other_load_string = other->AsLoadString(); // TODO: To allow GVN for HLoadString from different dex files, we should compare the strings // rather than their indexes. However, we shall also have to re-think the hash code. if (string_index_ != other_load_string->string_index_ ||
GetPackedFields() != other_load_string->GetPackedFields()) { returnfalse;
} switch (GetLoadKind()) { case LoadKind::kBootImageRelRo: case LoadKind::kJitBootImageAddress: case LoadKind::kJitTableAddress: {
ScopedObjectAccess soa(Thread::Current()); return GetString().Get() == other_load_string->GetString().Get();
} default: return IsSameDexFile(GetDexFile(), other_load_string->GetDexFile());
}
}
void HInstruction::RemoveEnvironmentUsers() { for (const HUseListNode<HEnvironment*>& use : GetEnvUses()) {
HEnvironment* user = use.GetUser();
user->SetRawEnvAt(use.GetIndex(), nullptr);
}
env_uses_.clear();
}
std::ostream& operator<<(std::ostream& os, TypeCheckKind rhs) { switch (rhs) { case TypeCheckKind::kUnresolvedCheck: return os << "unresolved_check"; case TypeCheckKind::kExactCheck: return os << "exact_check"; case TypeCheckKind::kClassHierarchyCheck: return os << "class_hierarchy_check"; case TypeCheckKind::kAbstractClassCheck: return os << "abstract_class_check"; case TypeCheckKind::kInterfaceCheck: return os << "interface_check"; case TypeCheckKind::kArrayObjectCheck: return os << "array_object_check"; case TypeCheckKind::kArrayCheck: return os << "array_check"; case TypeCheckKind::kBitstringCheck: return os << "bitstring_check";
}
}
// Check that intrinsic enum values fit within space set aside in ArtMethod modifier flags. #define CHECK_INTRINSICS_ENUM_VALUES(Name, InvokeType, _, SideEffects, Exceptions, ...) \
static_assert( \ static_cast<uint32_t>(Intrinsics::k ## Name) <= (kAccIntrinsicBits >> CTZ(kAccIntrinsicBits)), \ "Intrinsics enumeration space overflow.");
ART_INTRINSICS_LIST(CHECK_INTRINSICS_ENUM_VALUES) #undef CHECK_INTRINSICS_ENUM_VALUES
// Function that returns whether an intrinsic needs an environment or not. staticinline IntrinsicNeedsEnvironment NeedsEnvironmentIntrinsic(Intrinsics i) { switch (i) { case Intrinsics::kNone: return kNeedsEnvironment; // Non-sensical for intrinsic. #define OPTIMIZING_INTRINSICS(Name, InvokeType, NeedsEnv, SideEffects, Exceptions, ...) \ case Intrinsics::k ## Name: \ return NeedsEnv;
ART_INTRINSICS_LIST(OPTIMIZING_INTRINSICS) #undef OPTIMIZING_INTRINSICS
} return kNeedsEnvironment;
}
// Function that returns whether an intrinsic has side effects. staticinline IntrinsicSideEffects GetSideEffectsIntrinsic(Intrinsics i) { switch (i) { case Intrinsics::kNone: return kAllSideEffects; #define OPTIMIZING_INTRINSICS(Name, InvokeType, NeedsEnv, SideEffects, Exceptions, ...) \ case Intrinsics::k ## Name: \ return SideEffects;
ART_INTRINSICS_LIST(OPTIMIZING_INTRINSICS) #undef OPTIMIZING_INTRINSICS
} return kAllSideEffects;
}
// Function that returns whether an intrinsic can throw exceptions. staticinline IntrinsicExceptions GetExceptionsIntrinsic(Intrinsics i) { switch (i) { case Intrinsics::kNone: return kCanThrow; #define OPTIMIZING_INTRINSICS(Name, InvokeType, NeedsEnv, SideEffects, Exceptions, ...) \ case Intrinsics::k ## Name: \ return Exceptions;
ART_INTRINSICS_LIST(OPTIMIZING_INTRINSICS) #undef OPTIMIZING_INTRINSICS
} return kCanThrow;
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
