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/arena_object.h"

namespace art {

class LocalValueNumbering;
class MirFieldInfo;

class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
 public:
  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();

  // 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();
  }

 private:
  static constexpr uint16_t kNoValue = 0xffffu;

  // 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);
    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);
  }

  // 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;

  CompilationUnit* GetCompilationUnit() const {
    return cu_;
  }

  MIRGraph* GetMirGraph() const {
    return mir_graph_;
  }

  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  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 = reinterpret_cast<uint16_t*>(allocator->Alloc(size * sizeof(uint16_t),
                                                                     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_