compiler/optimizing/cha_guard_optimization.cc - platform/art - Git at Google

 /*
  * Copyright (C) 2016 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "cha_guard_optimization.h"

 namespace art {

 // Note we can only do CHA guard elimination/motion in a single pass, since
 // if a guard is not removed, another guard might be removed due to
 // the existence of the first guard. The first guard should not be further
 // removed in another pass. For example, due to further optimizations,
 // a receiver of a guard might turn out to be a parameter value, or defined at
 // a different site, which makes the guard removable as a result. However
 // it's not safe to remove the guard in another pass since another guard might
 // have been removed due to the existence of this guard.
 //
 // As a consequence, we decided not to rely on other passes to remove them
 // (such as GVN or instruction simplifier).

 class CHAGuardVisitor : HGraphVisitor {
  public:
   explicit CHAGuardVisitor(HGraph* graph)
       : HGraphVisitor(graph),
         block_has_cha_guard_(GetGraph()->GetBlocks().size(),
                              0,
                              graph->GetAllocator()->Adapter(kArenaAllocCHA)),
         instruction_iterator_(nullptr) {
     number_of_guards_to_visit_ = GetGraph()->GetNumberOfCHAGuards();
     DCHECK_NE(number_of_guards_to_visit_, 0u);
     // Will recount number of guards during guard optimization.
     GetGraph()->SetNumberOfCHAGuards(0);
   }

   void VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) override;

   void VisitBasicBlock(HBasicBlock* block) override;

  private:
   void RemoveGuard(HShouldDeoptimizeFlag* flag);
   // Return true if `flag` is removed.
   bool OptimizeForParameter(HShouldDeoptimizeFlag* flag, HInstruction* receiver);
   // Return true if `flag` is removed.
   bool OptimizeWithDominatingGuard(HShouldDeoptimizeFlag* flag, HInstruction* receiver);
   // Return true if `flag` is hoisted.
   bool HoistGuard(HShouldDeoptimizeFlag* flag, HInstruction* receiver);

   // Record if each block has any CHA guard. It's updated during the
   // reverse post order visit. Use int instead of bool since ArenaVector
   // does not support bool.
   ArenaVector<int> block_has_cha_guard_;

   // The iterator that's being used for this visitor. Need it to manually
   // advance the iterator due to removing/moving more than one instruction.
   HInstructionIterator* instruction_iterator_;

   // Used to short-circuit the pass when there is no more guards left to visit.
   uint32_t number_of_guards_to_visit_;

   DISALLOW_COPY_AND_ASSIGN(CHAGuardVisitor);
 };

 void CHAGuardVisitor::VisitBasicBlock(HBasicBlock* block) {
   if (number_of_guards_to_visit_ == 0) {
     return;
   }
   // Skip phis, just iterate through instructions.
   HInstructionIterator it(block->GetInstructions());
   instruction_iterator_ = &it;
   for (; !it.Done(); it.Advance()) {
     DCHECK(it.Current()->IsInBlock());
     it.Current()->Accept(this);
   }
 }

 void CHAGuardVisitor::RemoveGuard(HShouldDeoptimizeFlag* flag) {
   HBasicBlock* block = flag->GetBlock();
   HInstruction* compare = flag->GetNext();
   DCHECK(compare->IsNotEqual());
   HInstruction* deopt = compare->GetNext();
   DCHECK(deopt->IsDeoptimize());

   // Advance instruction iterator first before we remove the guard.
   // We need to do it twice since we remove three instructions and the
   // visitor is responsible for advancing it once.
   instruction_iterator_->Advance();
   instruction_iterator_->Advance();
   block->RemoveInstruction(deopt);
   block->RemoveInstruction(compare);
   block->RemoveInstruction(flag);
 }

 bool CHAGuardVisitor::OptimizeForParameter(HShouldDeoptimizeFlag* flag,
                                            HInstruction* receiver) {
   // If some compiled code is invalidated by CHA due to class loading, the
   // compiled code will not be entered anymore. So the very fact that the
   // compiled code is invoked guarantees that a parameter receiver conforms
   // to all the CHA devirtualization assumptions made by the compiled code,
   // since all parameter receivers pre-exist any (potential) invalidation of
   // the compiled code.
   //
   // TODO: allow more cases such as a phi whose inputs are all parameters.
   if (receiver->IsParameterValue()) {
     RemoveGuard(flag);
     return true;
   }
   return false;
 }

 bool CHAGuardVisitor::OptimizeWithDominatingGuard(HShouldDeoptimizeFlag* flag,
                                                   HInstruction* receiver) {
   // If there is another guard that dominates the current guard, and
   // that guard is dominated by receiver's definition, then the current
   // guard can be eliminated, since receiver must pre-exist that other
   // guard, and passing that guard guarantees that receiver conforms to
   // all the CHA devirtualization assumptions.
   HBasicBlock* dominator = flag->GetBlock();
   HBasicBlock* receiver_def_block = receiver->GetBlock();

   // Complexity of the following algorithm:
   // We potentially need to traverse the full dominator chain to receiver_def_block,
   // plus a (partial) linear search within one block for each guard.
   // So the worst case for each guard is bounded by the size of the
   // biggest block plus the depth of the dominating tree.

   while (dominator != receiver_def_block) {
     if (block_has_cha_guard_[dominator->GetBlockId()] == 1) {
       RemoveGuard(flag);
       return true;
     }
     dominator = dominator->GetDominator();
   }

   // At this point dominator is the block where receiver is defined.
   // We do a linear search within dominator to see if there is a guard after
   // receiver's definition.
   HInstruction* instruction;
   if (dominator == flag->GetBlock()) {
     // Flag and receiver are defined in the same block. Search backward from
     // the current guard.
     instruction = flag->GetPrevious();
   } else {
     // Search backward from the last instruction of that dominator.
     instruction = dominator->GetLastInstruction();
   }
   while (instruction != receiver) {
     if (instruction == nullptr) {
       // receiver must be defined in this block, we didn't find it
       // in the instruction list, so it must be a Phi.
       DCHECK(receiver->IsPhi());
       break;
     }
     if (instruction->IsShouldDeoptimizeFlag()) {
       RemoveGuard(flag);
       return true;
     }
     instruction = instruction->GetPrevious();
   }
   return false;
 }

 bool CHAGuardVisitor::HoistGuard(HShouldDeoptimizeFlag* flag,
                                  HInstruction* receiver) {
   // If receiver is loop invariant, we can hoist the guard out of the
   // loop since passing a guard before entering the loop guarantees that
   // receiver conforms to all the CHA devirtualization assumptions.
   // We only hoist guards out of the inner loop since that offers most of the
   // benefit and it might help remove other guards in the inner loop.
   HBasicBlock* block = flag->GetBlock();
   HLoopInformation* loop_info = block->GetLoopInformation();
   if (loop_info != nullptr &&
       !loop_info->IsIrreducible() &&
       loop_info->IsDefinedOutOfTheLoop(receiver)) {
     HInstruction* compare = flag->GetNext();
     DCHECK(compare->IsNotEqual());
     HInstruction* deopt = compare->GetNext();
     DCHECK(deopt->IsDeoptimize());

     // Advance instruction iterator first before we move the guard.
     // We need to do it twice since we move three instructions and the
     // visitor is responsible for advancing it once.
     instruction_iterator_->Advance();
     instruction_iterator_->Advance();

     HBasicBlock* pre_header = loop_info->GetPreHeader();
     flag->MoveBefore(pre_header->GetLastInstruction());
     compare->MoveBefore(pre_header->GetLastInstruction());

     block->RemoveInstruction(deopt);
     HInstruction* suspend = loop_info->GetSuspendCheck();
     // Need a new deoptimize instruction that copies the environment
     // of the suspend instruction for the loop.
     HDeoptimize* deoptimize = new (GetGraph()->GetAllocator()) HDeoptimize(
         GetGraph()->GetAllocator(), compare, DeoptimizationKind::kCHA, suspend->GetDexPc());
     pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction());
     deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
         suspend->GetEnvironment(), loop_info->GetHeader());
     block_has_cha_guard_[pre_header->GetBlockId()] = 1;
     GetGraph()->IncrementNumberOfCHAGuards();
     return true;
   }
   return false;
 }

 void CHAGuardVisitor::VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) {
   number_of_guards_to_visit_--;
   HInstruction* receiver = flag->InputAt(0);
   // Don't need the receiver anymore.
   flag->RemoveInputAt(0);
   if (receiver->IsNullCheck()) {
     receiver = receiver->InputAt(0);
   }

   if (OptimizeForParameter(flag, receiver)) {
     DCHECK(!flag->IsInBlock());
     return;
   }
   if (OptimizeWithDominatingGuard(flag, receiver)) {
     DCHECK(!flag->IsInBlock());
     return;
   }
   if (HoistGuard(flag, receiver)) {
     DCHECK(flag->IsInBlock());
     return;
   }

   // Need to keep the CHA guard in place.
   block_has_cha_guard_[flag->GetBlock()->GetBlockId()] = 1;
   GetGraph()->IncrementNumberOfCHAGuards();
 }

 bool CHAGuardOptimization::Run() {
   if (graph_->GetNumberOfCHAGuards() == 0) {
     return false;
   }
   CHAGuardVisitor visitor(graph_);
   for (HBasicBlock* block : graph_->GetReversePostOrder()) {
     visitor.VisitBasicBlock(block);
   }
   return true;
 }

 }  // namespace art
	/*
	* Copyright (C) 2016 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "cha_guard_optimization.h"

	namespace art {

	// Note we can only do CHA guard elimination/motion in a single pass, since
	// if a guard is not removed, another guard might be removed due to
	// the existence of the first guard. The first guard should not be further
	// removed in another pass. For example, due to further optimizations,
	// a receiver of a guard might turn out to be a parameter value, or defined at
	// a different site, which makes the guard removable as a result. However
	// it's not safe to remove the guard in another pass since another guard might
	// have been removed due to the existence of this guard.
	//
	// As a consequence, we decided not to rely on other passes to remove them
	// (such as GVN or instruction simplifier).

	class CHAGuardVisitor : HGraphVisitor {
	public:
	explicit CHAGuardVisitor(HGraph* graph)
	: HGraphVisitor(graph),
	block_has_cha_guard_(GetGraph()->GetBlocks().size(),
	0,
	graph->GetAllocator()->Adapter(kArenaAllocCHA)),
	instruction_iterator_(nullptr) {
	number_of_guards_to_visit_ = GetGraph()->GetNumberOfCHAGuards();
	DCHECK_NE(number_of_guards_to_visit_, 0u);
	// Will recount number of guards during guard optimization.
	GetGraph()->SetNumberOfCHAGuards(0);
	}

	void VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) override;

	void VisitBasicBlock(HBasicBlock* block) override;

	private:
	void RemoveGuard(HShouldDeoptimizeFlag* flag);
	// Return true if `flag` is removed.
	bool OptimizeForParameter(HShouldDeoptimizeFlag* flag, HInstruction* receiver);
	// Return true if `flag` is removed.
	bool OptimizeWithDominatingGuard(HShouldDeoptimizeFlag* flag, HInstruction* receiver);
	// Return true if `flag` is hoisted.
	bool HoistGuard(HShouldDeoptimizeFlag* flag, HInstruction* receiver);

	// Record if each block has any CHA guard. It's updated during the
	// reverse post order visit. Use int instead of bool since ArenaVector
	// does not support bool.
	ArenaVector<int> block_has_cha_guard_;

	// The iterator that's being used for this visitor. Need it to manually
	// advance the iterator due to removing/moving more than one instruction.
	HInstructionIterator* instruction_iterator_;

	// Used to short-circuit the pass when there is no more guards left to visit.
	uint32_t number_of_guards_to_visit_;

	DISALLOW_COPY_AND_ASSIGN(CHAGuardVisitor);
	};

	void CHAGuardVisitor::VisitBasicBlock(HBasicBlock* block) {
	if (number_of_guards_to_visit_ == 0) {
	return;
	}
	// Skip phis, just iterate through instructions.
	HInstructionIterator it(block->GetInstructions());
	instruction_iterator_ = ⁢
	for (; !it.Done(); it.Advance()) {
	DCHECK(it.Current()->IsInBlock());
	it.Current()->Accept(this);
	}
	}

	void CHAGuardVisitor::RemoveGuard(HShouldDeoptimizeFlag* flag) {
	HBasicBlock* block = flag->GetBlock();
	HInstruction* compare = flag->GetNext();
	DCHECK(compare->IsNotEqual());
	HInstruction* deopt = compare->GetNext();
	DCHECK(deopt->IsDeoptimize());

	// Advance instruction iterator first before we remove the guard.
	// We need to do it twice since we remove three instructions and the
	// visitor is responsible for advancing it once.
	instruction_iterator_->Advance();
	instruction_iterator_->Advance();
	block->RemoveInstruction(deopt);
	block->RemoveInstruction(compare);
	block->RemoveInstruction(flag);
	}

	bool CHAGuardVisitor::OptimizeForParameter(HShouldDeoptimizeFlag* flag,
	HInstruction* receiver) {
	// If some compiled code is invalidated by CHA due to class loading, the
	// compiled code will not be entered anymore. So the very fact that the
	// compiled code is invoked guarantees that a parameter receiver conforms
	// to all the CHA devirtualization assumptions made by the compiled code,
	// since all parameter receivers pre-exist any (potential) invalidation of
	// the compiled code.
	//
	// TODO: allow more cases such as a phi whose inputs are all parameters.
	if (receiver->IsParameterValue()) {
	RemoveGuard(flag);
	return true;
	}
	return false;
	}

	bool CHAGuardVisitor::OptimizeWithDominatingGuard(HShouldDeoptimizeFlag* flag,
	HInstruction* receiver) {
	// If there is another guard that dominates the current guard, and
	// that guard is dominated by receiver's definition, then the current
	// guard can be eliminated, since receiver must pre-exist that other
	// guard, and passing that guard guarantees that receiver conforms to
	// all the CHA devirtualization assumptions.
	HBasicBlock* dominator = flag->GetBlock();
	HBasicBlock* receiver_def_block = receiver->GetBlock();

	// Complexity of the following algorithm:
	// We potentially need to traverse the full dominator chain to receiver_def_block,
	// plus a (partial) linear search within one block for each guard.
	// So the worst case for each guard is bounded by the size of the
	// biggest block plus the depth of the dominating tree.

	while (dominator != receiver_def_block) {
	if (block_has_cha_guard_[dominator->GetBlockId()] == 1) {
	RemoveGuard(flag);
	return true;
	}
	dominator = dominator->GetDominator();
	}

	// At this point dominator is the block where receiver is defined.
	// We do a linear search within dominator to see if there is a guard after
	// receiver's definition.
	HInstruction* instruction;
	if (dominator == flag->GetBlock()) {
	// Flag and receiver are defined in the same block. Search backward from
	// the current guard.
	instruction = flag->GetPrevious();
	} else {
	// Search backward from the last instruction of that dominator.
	instruction = dominator->GetLastInstruction();
	}
	while (instruction != receiver) {
	if (instruction == nullptr) {
	// receiver must be defined in this block, we didn't find it
	// in the instruction list, so it must be a Phi.
	DCHECK(receiver->IsPhi());
	break;
	}
	if (instruction->IsShouldDeoptimizeFlag()) {
	RemoveGuard(flag);
	return true;
	}
	instruction = instruction->GetPrevious();
	}
	return false;
	}

	bool CHAGuardVisitor::HoistGuard(HShouldDeoptimizeFlag* flag,
	HInstruction* receiver) {
	// If receiver is loop invariant, we can hoist the guard out of the
	// loop since passing a guard before entering the loop guarantees that
	// receiver conforms to all the CHA devirtualization assumptions.
	// We only hoist guards out of the inner loop since that offers most of the
	// benefit and it might help remove other guards in the inner loop.
	HBasicBlock* block = flag->GetBlock();
	HLoopInformation* loop_info = block->GetLoopInformation();
	if (loop_info != nullptr &&
	!loop_info->IsIrreducible() &&
	loop_info->IsDefinedOutOfTheLoop(receiver)) {
	HInstruction* compare = flag->GetNext();
	DCHECK(compare->IsNotEqual());
	HInstruction* deopt = compare->GetNext();
	DCHECK(deopt->IsDeoptimize());

	// Advance instruction iterator first before we move the guard.
	// We need to do it twice since we move three instructions and the
	// visitor is responsible for advancing it once.
	instruction_iterator_->Advance();
	instruction_iterator_->Advance();

	HBasicBlock* pre_header = loop_info->GetPreHeader();
	flag->MoveBefore(pre_header->GetLastInstruction());
	compare->MoveBefore(pre_header->GetLastInstruction());

	block->RemoveInstruction(deopt);
	HInstruction* suspend = loop_info->GetSuspendCheck();
	// Need a new deoptimize instruction that copies the environment
	// of the suspend instruction for the loop.
	HDeoptimize* deoptimize = new (GetGraph()->GetAllocator()) HDeoptimize(
	GetGraph()->GetAllocator(), compare, DeoptimizationKind::kCHA, suspend->GetDexPc());
	pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction());
	deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
	suspend->GetEnvironment(), loop_info->GetHeader());
	block_has_cha_guard_[pre_header->GetBlockId()] = 1;
	GetGraph()->IncrementNumberOfCHAGuards();
	return true;
	}
	return false;
	}

	void CHAGuardVisitor::VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) {
	number_of_guards_to_visit_--;
	HInstruction* receiver = flag->InputAt(0);
	// Don't need the receiver anymore.
	flag->RemoveInputAt(0);
	if (receiver->IsNullCheck()) {
	receiver = receiver->InputAt(0);
	}

	if (OptimizeForParameter(flag, receiver)) {
	DCHECK(!flag->IsInBlock());
	return;
	}
	if (OptimizeWithDominatingGuard(flag, receiver)) {
	DCHECK(!flag->IsInBlock());
	return;
	}
	if (HoistGuard(flag, receiver)) {
	DCHECK(flag->IsInBlock());
	return;
	}

	// Need to keep the CHA guard in place.
	block_has_cha_guard_[flag->GetBlock()->GetBlockId()] = 1;
	GetGraph()->IncrementNumberOfCHAGuards();
	}

	bool CHAGuardOptimization::Run() {
	if (graph_->GetNumberOfCHAGuards() == 0) {
	return false;
	}
	CHAGuardVisitor visitor(graph_);
	for (HBasicBlock* block : graph_->GetReversePostOrder()) {
	visitor.VisitBasicBlock(block);
	}
	return true;
	}

	} // namespace art