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/macros.h"
#include "compiler_internals.h"
#include "utils/scoped_arena_containers.h"

namespace art {

class LocalValueNumbering;
class MirFieldInfo;

class GlobalValueNumbering {
 public:
  enum Mode {
    kModeGvn,
    kModeGvnPostProcessing,
    kModeLvn
  };

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

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

  // 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() {
    DCHECK(Good());
    DCHECK_EQ(mode_, kModeGvn);
    mode_ = kModeGvnPostProcessing;
  }

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

  // GlobalValueNumbering should be allocated on the ArenaStack (or the native stack).
  static void* operator new(size_t size, ScopedArenaAllocator* allocator) {
    return allocator->Alloc(sizeof(GlobalValueNumbering), kArenaAllocMisc);
  }

  // Allow delete-expression to destroy a GlobalValueNumbering object without deallocation.
  static void operator delete(void* ptr) { UNUSED(ptr); }

 private:
  static constexpr uint16_t kNoValue = 0xffffu;

  // Allocate a new value name.
  uint16_t NewValueName() {
    DCHECK_NE(mode_, kModeGvnPostProcessing);
    ++last_value_;
    return last_value_;
  }

  // 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);
    ValueMap::iterator 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) {
    uint16_t res;
    uint64_t key = BuildKey(op, operand1, operand2, modifier);
    ValueMap::iterator lb = global_value_map_.lower_bound(key);
    if (lb != global_value_map_.end() && lb->first == key) {
      res = lb->second;
    } else {
      res = kNoValue;
    }
    return res;
  }

  // Check if the exact value is stored in the global value map.
  bool HasValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier,
                uint16_t value) const {
    DCHECK(value != 0u || !Good());
    DCHECK_LE(value, last_value_);
    // This is equivalent to value == LookupValue(op, operand1, operand2, modifier)
    // except that it doesn't add an entry to the global value map if it's not there.
    uint64_t key = BuildKey(op, operand1, operand2, modifier);
    ValueMap::const_iterator it = global_value_map_.find(key);
    return (it != global_value_map_.end() && it->second == value);
  }

  // FieldReference represents a unique resolved field.
  struct FieldReference {
    const DexFile* dex_file;
    uint16_t field_idx;
    uint16_t type;  // See comments for LocalValueNumbering::kFieldTypeCount.
  };

  struct FieldReferenceComparator {
    bool operator()(const FieldReference& lhs, const FieldReference& rhs) const {
      if (lhs.field_idx != rhs.field_idx) {
        return lhs.field_idx < rhs.field_idx;
      }
      // If the field_idx and dex_file match, the type must also match.
      DCHECK(lhs.dex_file != rhs.dex_file || lhs.type == rhs.type);
      return lhs.dex_file < rhs.dex_file;
    }
  };

  // Maps field key to field id for resolved fields.
  typedef ScopedArenaSafeMap<FieldReference, uint32_t, FieldReferenceComparator> FieldIndexMap;

  // Get a field id.
  uint16_t GetFieldId(const MirFieldInfo& field_info, uint16_t type);

  // Get a field type based on field id.
  uint16_t GetFieldType(uint16_t field_id) {
    DCHECK_LT(field_id, field_index_reverse_map_.size());
    return field_index_reverse_map_[field_id]->first.type;
  }

  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;

  CompilationUnit* GetCompilationUnit() const {
    return cu_;
  }

  MIRGraph* GetMirGraph() const {
    return mir_graph_;
  }

  ScopedArenaAllocator* Allocator() const {
    return allocator_;
  }

  CompilationUnit* const cu_;
  MIRGraph* 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_;
  FieldIndexMap field_index_map_;
  ScopedArenaVector<const FieldIndexMap::value_type*> field_index_reverse_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);
};

}  // namespace art

#endif  // ART_COMPILER_DEX_GLOBAL_VALUE_NUMBERING_H_