compiler/dex/global_value_numbering.h - LeafOS-Project/android_art - Gitiles

 /*
  * Copyright (C) 2014 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.
  */

 #ifndef ART_COMPILER_DEX_GLOBAL_VALUE_NUMBERING_H_
 #define ART_COMPILER_DEX_GLOBAL_VALUE_NUMBERING_H_

 #include "base/arena_object.h"
 #include "base/logging.h"
 #include "base/macros.h"
 #include "mir_graph.h"
 #include "compiler_ir.h"
 #include "dex_flags.h"

 namespace art {

 class LocalValueNumbering;
 class MirFieldInfo;

 class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
  public:
   static constexpr uint16_t kNoValue = 0xffffu;
   static constexpr uint16_t kNullValue = 1u;

   enum Mode {
     kModeGvn,
     kModeGvnPostProcessing,
     kModeLvn
   };

   static bool Skip(CompilationUnit* cu) {
     return (cu->disable_opt & (1u << kGlobalValueNumbering)) != 0u ||
         cu->mir_graph->GetMaxNestedLoops() > kMaxAllowedNestedLoops;
   }

   // Instance and static field id map is held by MIRGraph to avoid multiple recalculations
   // when doing LVN.
   template <typename Container>  // Container of MirIFieldLoweringInfo or MirSFieldLoweringInfo.
   static uint16_t* PrepareGvnFieldIds(ScopedArenaAllocator* allocator,
                                       const Container& field_infos);

   GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator, Mode mode);
   ~GlobalValueNumbering();

   CompilationUnit* GetCompilationUnit() const {
     return cu_;
   }

   MIRGraph* GetMirGraph() const {
     return mir_graph_;
   }

   // Prepare LVN for the basic block.
   LocalValueNumbering* PrepareBasicBlock(BasicBlock* bb,
                                          ScopedArenaAllocator* allocator = nullptr);

   // Finish processing the basic block.
   bool FinishBasicBlock(BasicBlock* bb);

   // Checks that the value names didn't overflow.
   bool Good() const {
     return last_value_ < kNoValue;
   }

   // Allow modifications.
   void StartPostProcessing();

   bool CanModify() const {
     return modifications_allowed_ && Good();
   }

   // Retrieve the LVN with GVN results for a given BasicBlock.
   const LocalValueNumbering* GetLvn(BasicBlockId bb_id) const;

  private:
   // Allocate a new value name.
   uint16_t NewValueName();

   // Key is concatenation of opcode, operand1, operand2 and modifier, value is value name.
   typedef ScopedArenaSafeMap<uint64_t, uint16_t> ValueMap;

   static uint64_t BuildKey(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
     return (static_cast<uint64_t>(op) << 48 | static_cast<uint64_t>(operand1) << 32 |
             static_cast<uint64_t>(operand2) << 16 | static_cast<uint64_t>(modifier));
   }

   // Look up a value in the global value map, adding a new entry if there was none before.
   uint16_t LookupValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
     uint16_t res;
     uint64_t key = BuildKey(op, operand1, operand2, modifier);
     auto lb = global_value_map_.lower_bound(key);
     if (lb != global_value_map_.end() && lb->first == key) {
       res = lb->second;
     } else {
       res = NewValueName();
       global_value_map_.PutBefore(lb, key, res);
     }
     return res;
   }

   // Look up a value in the global value map, don't add a new entry if there was none before.
   uint16_t FindValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) const {
     uint16_t res;
     uint64_t key = BuildKey(op, operand1, operand2, modifier);
     auto lb = global_value_map_.lower_bound(key);
     if (lb != global_value_map_.end() && lb->first == key) {
       res = lb->second;
     } else {
       res = kNoValue;
     }
     return res;
   }

   // Get an instance field id.
   uint16_t GetIFieldId(MIR* mir) {
     return GetMirGraph()->GetGvnIFieldId(mir);
   }

   // Get a static field id.
   uint16_t GetSFieldId(MIR* mir) {
     return GetMirGraph()->GetGvnSFieldId(mir);
   }

   // Get an instance field type based on field id.
   uint16_t GetIFieldType(uint16_t field_id) {
     return static_cast<uint16_t>(GetMirGraph()->GetIFieldLoweringInfo(field_id).MemAccessType());
   }

   // Get a static field type based on field id.
   uint16_t GetSFieldType(uint16_t field_id) {
     return static_cast<uint16_t>(GetMirGraph()->GetSFieldLoweringInfo(field_id).MemAccessType());
   }

   struct ArrayLocation {
     uint16_t base;
     uint16_t index;
   };

   struct ArrayLocationComparator {
     bool operator()(const ArrayLocation& lhs, const ArrayLocation& rhs) const {
       if (lhs.base != rhs.base) {
         return lhs.base < rhs.base;
       }
       return lhs.index < rhs.index;
     }
   };

   typedef ScopedArenaSafeMap<ArrayLocation, uint16_t, ArrayLocationComparator> ArrayLocationMap;

   // Get an array location.
   uint16_t GetArrayLocation(uint16_t base, uint16_t index);

   // Get the array base from an array location.
   uint16_t GetArrayLocationBase(uint16_t location) const {
     return array_location_reverse_map_[location]->first.base;
   }

   // Get the array index from an array location.
   uint16_t GetArrayLocationIndex(uint16_t location) const {
     return array_location_reverse_map_[location]->first.index;
   }

   // A set of value names.
   typedef ScopedArenaSet<uint16_t> ValueNameSet;

   // A map from a set of references to the set id.
   typedef ScopedArenaSafeMap<ValueNameSet, uint16_t> RefSetIdMap;

   uint16_t GetRefSetId(const ValueNameSet& ref_set) {
     uint16_t res = kNoValue;
     auto lb = ref_set_map_.lower_bound(ref_set);
     if (lb != ref_set_map_.end() && !ref_set_map_.key_comp()(ref_set, lb->first)) {
       res = lb->second;
     } else {
       res = NewValueName();
       ref_set_map_.PutBefore(lb, ref_set, res);
     }
     return res;
   }

   const BasicBlock* GetBasicBlock(uint16_t bb_id) const {
     return mir_graph_->GetBasicBlock(bb_id);
   }

   static bool HasNullCheckLastInsn(const BasicBlock* pred_bb, BasicBlockId succ_id);

   bool NullCheckedInAllPredecessors(const ScopedArenaVector<uint16_t>& merge_names) const;

   bool DivZeroCheckedInAllPredecessors(const ScopedArenaVector<uint16_t>& merge_names) const;

   ScopedArenaAllocator* Allocator() const {
     return allocator_;
   }

   CompilationUnit* const cu_;
   MIRGraph* const mir_graph_;
   ScopedArenaAllocator* const allocator_;

   // The maximum number of nested loops that we accept for GVN.
   static constexpr size_t kMaxAllowedNestedLoops = 6u;

   // The number of BBs that we need to process grows exponentially with the number
   // of nested loops. Don't allow excessive processing for too many nested loops or
   // otherwise expensive methods.
   static constexpr uint32_t kMaxBbsToProcessMultiplyFactor = 20u;

   uint32_t bbs_processed_;
   uint32_t max_bbs_to_process_;  // Doesn't apply after the main GVN has converged.

   // We have 32-bit last_value_ so that we can detect when we run out of value names, see Good().
   // We usually don't check Good() until the end of LVN unless we're about to modify code.
   uint32_t last_value_;

   // Marks whether code modifications are allowed. The initial GVN is done without code
   // modifications to settle the value names. Afterwards, we allow modifications and rerun
   // LVN once for each BasicBlock.
   bool modifications_allowed_;

   // Specifies the mode of operation.
   Mode mode_;

   ValueMap global_value_map_;
   ArrayLocationMap array_location_map_;
   ScopedArenaVector<const ArrayLocationMap::value_type*> array_location_reverse_map_;
   RefSetIdMap ref_set_map_;

   ScopedArenaVector<const LocalValueNumbering*> lvns_;        // Owning.
   std::unique_ptr<LocalValueNumbering> work_lvn_;
   ScopedArenaVector<const LocalValueNumbering*> merge_lvns_;  // Not owning.

   friend class LocalValueNumbering;
   friend class GlobalValueNumberingTest;

   DISALLOW_COPY_AND_ASSIGN(GlobalValueNumbering);
 };
 std::ostream& operator<<(std::ostream& os, const GlobalValueNumbering::Mode& rhs);

 inline const LocalValueNumbering* GlobalValueNumbering::GetLvn(BasicBlockId bb_id) const {
   DCHECK_EQ(mode_, kModeGvnPostProcessing);
   DCHECK_LT(bb_id, lvns_.size());
   DCHECK(lvns_[bb_id] != nullptr);
   return lvns_[bb_id];
 }

 inline void GlobalValueNumbering::StartPostProcessing() {
   DCHECK(Good());
   DCHECK_EQ(mode_, kModeGvn);
   mode_ = kModeGvnPostProcessing;
 }

 inline uint16_t GlobalValueNumbering::NewValueName() {
   DCHECK_NE(mode_, kModeGvnPostProcessing);
   ++last_value_;
   return last_value_;
 }

 template <typename Container>  // Container of MirIFieldLoweringInfo or MirSFieldLoweringInfo.
 uint16_t* GlobalValueNumbering::PrepareGvnFieldIds(ScopedArenaAllocator* allocator,
                                                    const Container& field_infos) {
   size_t size = field_infos.size();
   uint16_t* field_ids = allocator->AllocArray<uint16_t>(size, kArenaAllocMisc);
   for (size_t i = 0u; i != size; ++i) {
     size_t idx = i;
     const MirFieldInfo& cur_info = field_infos[i];
     if (cur_info.IsResolved()) {
       for (size_t j = 0; j != i; ++j) {
         const MirFieldInfo& prev_info = field_infos[j];
         if (prev_info.IsResolved() &&
             prev_info.DeclaringDexFile() == cur_info.DeclaringDexFile() &&
             prev_info.DeclaringFieldIndex() == cur_info.DeclaringFieldIndex()) {
           DCHECK_EQ(cur_info.MemAccessType(), prev_info.MemAccessType());
           idx = j;
           break;
         }
       }
     }
     field_ids[i] = idx;
   }
   return field_ids;
 }

 }  // namespace art

 #endif  // ART_COMPILER_DEX_GLOBAL_VALUE_NUMBERING_H_
	/*
	* Copyright (C) 2014 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.
	*/

	#ifndef ART_COMPILER_DEX_GLOBAL_VALUE_NUMBERING_H_
	#define ART_COMPILER_DEX_GLOBAL_VALUE_NUMBERING_H_

	#include "base/arena_object.h"
	#include "base/logging.h"
	#include "base/macros.h"
	#include "mir_graph.h"
	#include "compiler_ir.h"
	#include "dex_flags.h"

	namespace art {

	class LocalValueNumbering;
	class MirFieldInfo;

	class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
	public:
	static constexpr uint16_t kNoValue = 0xffffu;
	static constexpr uint16_t kNullValue = 1u;

	enum Mode {
	kModeGvn,
	kModeGvnPostProcessing,
	kModeLvn
	};

	static bool Skip(CompilationUnit* cu) {
	return (cu->disable_opt & (1u << kGlobalValueNumbering)) != 0u \|\|
	cu->mir_graph->GetMaxNestedLoops() > kMaxAllowedNestedLoops;
	}

	// Instance and static field id map is held by MIRGraph to avoid multiple recalculations
	// when doing LVN.
	template <typename Container> // Container of MirIFieldLoweringInfo or MirSFieldLoweringInfo.
	static uint16_t* PrepareGvnFieldIds(ScopedArenaAllocator* allocator,
	const Container& field_infos);

	GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator, Mode mode);
	~GlobalValueNumbering();

	CompilationUnit* GetCompilationUnit() const {
	return cu_;
	}

	MIRGraph* GetMirGraph() const {
	return mir_graph_;
	}

	// Prepare LVN for the basic block.
	LocalValueNumbering* PrepareBasicBlock(BasicBlock* bb,
	ScopedArenaAllocator* allocator = nullptr);

	// Finish processing the basic block.
	bool FinishBasicBlock(BasicBlock* bb);

	// Checks that the value names didn't overflow.
	bool Good() const {
	return last_value_ < kNoValue;
	}

	// Allow modifications.
	void StartPostProcessing();

	bool CanModify() const {
	return modifications_allowed_ && Good();
	}

	// Retrieve the LVN with GVN results for a given BasicBlock.
	const LocalValueNumbering* GetLvn(BasicBlockId bb_id) const;

	private:
	// Allocate a new value name.
	uint16_t NewValueName();

	// Key is concatenation of opcode, operand1, operand2 and modifier, value is value name.
	typedef ScopedArenaSafeMap<uint64_t, uint16_t> ValueMap;

	static uint64_t BuildKey(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
	return (static_cast<uint64_t>(op) << 48 \| static_cast<uint64_t>(operand1) << 32 \|
	static_cast<uint64_t>(operand2) << 16 \| static_cast<uint64_t>(modifier));
	}

	// Look up a value in the global value map, adding a new entry if there was none before.
	uint16_t LookupValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
	uint16_t res;
	uint64_t key = BuildKey(op, operand1, operand2, modifier);
	auto lb = global_value_map_.lower_bound(key);
	if (lb != global_value_map_.end() && lb->first == key) {
	res = lb->second;
	} else {
	res = NewValueName();
	global_value_map_.PutBefore(lb, key, res);
	}
	return res;
	}

	// Look up a value in the global value map, don't add a new entry if there was none before.
	uint16_t FindValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) const {
	uint16_t res;
	uint64_t key = BuildKey(op, operand1, operand2, modifier);
	auto lb = global_value_map_.lower_bound(key);
	if (lb != global_value_map_.end() && lb->first == key) {
	res = lb->second;
	} else {
	res = kNoValue;
	}
	return res;
	}

	// Get an instance field id.
	uint16_t GetIFieldId(MIR* mir) {
	return GetMirGraph()->GetGvnIFieldId(mir);
	}

	// Get a static field id.
	uint16_t GetSFieldId(MIR* mir) {
	return GetMirGraph()->GetGvnSFieldId(mir);
	}

	// Get an instance field type based on field id.
	uint16_t GetIFieldType(uint16_t field_id) {
	return static_cast<uint16_t>(GetMirGraph()->GetIFieldLoweringInfo(field_id).MemAccessType());
	}

	// Get a static field type based on field id.
	uint16_t GetSFieldType(uint16_t field_id) {
	return static_cast<uint16_t>(GetMirGraph()->GetSFieldLoweringInfo(field_id).MemAccessType());
	}

	struct ArrayLocation {
	uint16_t base;
	uint16_t index;
	};

	struct ArrayLocationComparator {
	bool operator()(const ArrayLocation& lhs, const ArrayLocation& rhs) const {
	if (lhs.base != rhs.base) {
	return lhs.base < rhs.base;
	}
	return lhs.index < rhs.index;
	}
	};

	typedef ScopedArenaSafeMap<ArrayLocation, uint16_t, ArrayLocationComparator> ArrayLocationMap;

	// Get an array location.
	uint16_t GetArrayLocation(uint16_t base, uint16_t index);

	// Get the array base from an array location.
	uint16_t GetArrayLocationBase(uint16_t location) const {
	return array_location_reverse_map_[location]->first.base;
	}

	// Get the array index from an array location.
	uint16_t GetArrayLocationIndex(uint16_t location) const {
	return array_location_reverse_map_[location]->first.index;
	}

	// A set of value names.
	typedef ScopedArenaSet<uint16_t> ValueNameSet;

	// A map from a set of references to the set id.
	typedef ScopedArenaSafeMap<ValueNameSet, uint16_t> RefSetIdMap;

	uint16_t GetRefSetId(const ValueNameSet& ref_set) {
	uint16_t res = kNoValue;
	auto lb = ref_set_map_.lower_bound(ref_set);
	if (lb != ref_set_map_.end() && !ref_set_map_.key_comp()(ref_set, lb->first)) {
	res = lb->second;
	} else {
	res = NewValueName();
	ref_set_map_.PutBefore(lb, ref_set, res);
	}
	return res;
	}

	const BasicBlock* GetBasicBlock(uint16_t bb_id) const {
	return mir_graph_->GetBasicBlock(bb_id);
	}

	static bool HasNullCheckLastInsn(const BasicBlock* pred_bb, BasicBlockId succ_id);

	bool NullCheckedInAllPredecessors(const ScopedArenaVector<uint16_t>& merge_names) const;

	bool DivZeroCheckedInAllPredecessors(const ScopedArenaVector<uint16_t>& merge_names) const;

	ScopedArenaAllocator* Allocator() const {
	return allocator_;
	}

	CompilationUnit* const cu_;
	MIRGraph* const mir_graph_;
	ScopedArenaAllocator* const allocator_;

	// The maximum number of nested loops that we accept for GVN.
	static constexpr size_t kMaxAllowedNestedLoops = 6u;

	// The number of BBs that we need to process grows exponentially with the number
	// of nested loops. Don't allow excessive processing for too many nested loops or
	// otherwise expensive methods.
	static constexpr uint32_t kMaxBbsToProcessMultiplyFactor = 20u;

	uint32_t bbs_processed_;
	uint32_t max_bbs_to_process_; // Doesn't apply after the main GVN has converged.

	// We have 32-bit last_value_ so that we can detect when we run out of value names, see Good().
	// We usually don't check Good() until the end of LVN unless we're about to modify code.
	uint32_t last_value_;

	// Marks whether code modifications are allowed. The initial GVN is done without code
	// modifications to settle the value names. Afterwards, we allow modifications and rerun
	// LVN once for each BasicBlock.
	bool modifications_allowed_;

	// Specifies the mode of operation.
	Mode mode_;

	ValueMap global_value_map_;
	ArrayLocationMap array_location_map_;
	ScopedArenaVector<const ArrayLocationMap::value_type*> array_location_reverse_map_;
	RefSetIdMap ref_set_map_;

	ScopedArenaVector<const LocalValueNumbering*> lvns_; // Owning.
	std::unique_ptr<LocalValueNumbering> work_lvn_;
	ScopedArenaVector<const LocalValueNumbering*> merge_lvns_; // Not owning.

	friend class LocalValueNumbering;
	friend class GlobalValueNumberingTest;

	DISALLOW_COPY_AND_ASSIGN(GlobalValueNumbering);
	};
	std::ostream& operator<<(std::ostream& os, const GlobalValueNumbering::Mode& rhs);

	inline const LocalValueNumbering* GlobalValueNumbering::GetLvn(BasicBlockId bb_id) const {
	DCHECK_EQ(mode_, kModeGvnPostProcessing);
	DCHECK_LT(bb_id, lvns_.size());
	DCHECK(lvns_[bb_id] != nullptr);
	return lvns_[bb_id];
	}

	inline void GlobalValueNumbering::StartPostProcessing() {
	DCHECK(Good());
	DCHECK_EQ(mode_, kModeGvn);
	mode_ = kModeGvnPostProcessing;
	}

	inline uint16_t GlobalValueNumbering::NewValueName() {
	DCHECK_NE(mode_, kModeGvnPostProcessing);
	++last_value_;
	return last_value_;
	}

	template <typename Container> // Container of MirIFieldLoweringInfo or MirSFieldLoweringInfo.
	uint16_t* GlobalValueNumbering::PrepareGvnFieldIds(ScopedArenaAllocator* allocator,
	const Container& field_infos) {
	size_t size = field_infos.size();
	uint16_t* field_ids = allocator->AllocArray<uint16_t>(size, kArenaAllocMisc);
	for (size_t i = 0u; i != size; ++i) {
	size_t idx = i;
	const MirFieldInfo& cur_info = field_infos[i];
	if (cur_info.IsResolved()) {
	for (size_t j = 0; j != i; ++j) {
	const MirFieldInfo& prev_info = field_infos[j];
	if (prev_info.IsResolved() &&
	prev_info.DeclaringDexFile() == cur_info.DeclaringDexFile() &&
	prev_info.DeclaringFieldIndex() == cur_info.DeclaringFieldIndex()) {
	DCHECK_EQ(cur_info.MemAccessType(), prev_info.MemAccessType());
	idx = j;
	break;
	}
	}
	}
	field_ids[i] = idx;
	}
	return field_ids;
	}

	} // namespace art

	#endif // ART_COMPILER_DEX_GLOBAL_VALUE_NUMBERING_H_