Re-apply: Initial check-in of an optimizing compiler.
The classes and the names are very much inspired by V8/Dart.
It currently only supports the RETURN_VOID dex instruction,
and there is a pretty printer to check if the building of the
graph is correct.
Change-Id: I28e125dfee86ae6ec9b3fec6aa1859523b92a893
diff --git a/compiler/utils/growable_array.h b/compiler/utils/growable_array.h
new file mode 100644
index 0000000..b591870
--- /dev/null
+++ b/compiler/utils/growable_array.h
@@ -0,0 +1,186 @@
+/*
+ * Copyright (C) 2013 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_UTILS_GROWABLE_ARRAY_H_
+#define ART_COMPILER_UTILS_GROWABLE_ARRAY_H_
+
+#include <stdint.h>
+#include <stddef.h>
+#include "arena_allocator.h"
+
+namespace art {
+
+// Type of growable list for memory tuning.
+enum OatListKind {
+ kGrowableArrayMisc = 0,
+ kGrowableArrayBlockList,
+ kGrowableArraySSAtoDalvikMap,
+ kGrowableArrayDfsOrder,
+ kGrowableArrayDfsPostOrder,
+ kGrowableArrayDomPostOrderTraversal,
+ kGrowableArrayThrowLaunchPads,
+ kGrowableArraySuspendLaunchPads,
+ kGrowableArraySwitchTables,
+ kGrowableArrayFillArrayData,
+ kGrowableArraySuccessorBlocks,
+ kGrowableArrayPredecessors,
+ kGrowableArraySlowPaths,
+ kGNumListKinds
+};
+
+template<typename T>
+class GrowableArray {
+ public:
+ class Iterator {
+ public:
+ explicit Iterator(GrowableArray* g_list)
+ : idx_(0),
+ g_list_(g_list) {}
+
+ // NOTE: returns 0/NULL when no next.
+ // TODO: redo to make usage consistent with other iterators.
+ T Next() {
+ if (idx_ >= g_list_->Size()) {
+ return 0;
+ } else {
+ return g_list_->Get(idx_++);
+ }
+ }
+
+ void Reset() {
+ idx_ = 0;
+ }
+
+ private:
+ size_t idx_;
+ GrowableArray* const g_list_;
+ };
+
+ GrowableArray(ArenaAllocator* arena, size_t init_length, OatListKind kind = kGrowableArrayMisc)
+ : arena_(arena),
+ num_allocated_(init_length),
+ num_used_(0),
+ kind_(kind) {
+ elem_list_ = static_cast<T*>(arena_->Alloc(sizeof(T) * init_length,
+ ArenaAllocator::kAllocGrowableArray));
+ };
+
+
+ // Expand the list size to at least new length.
+ void Resize(size_t new_length) {
+ if (new_length <= num_allocated_) return;
+ // If it's a small list double the size, else grow 1.5x.
+ size_t target_length =
+ (num_allocated_ < 128) ? num_allocated_ << 1 : num_allocated_ + (num_allocated_ >> 1);
+ if (new_length > target_length) {
+ target_length = new_length;
+ }
+ T* new_array = static_cast<T*>(arena_->Alloc(sizeof(T) * target_length,
+ ArenaAllocator::kAllocGrowableArray));
+ memcpy(new_array, elem_list_, sizeof(T) * num_allocated_);
+ num_allocated_ = target_length;
+ elem_list_ = new_array;
+ };
+
+ // NOTE: does not return storage, just resets use count.
+ void Reset() {
+ num_used_ = 0;
+ }
+
+ // Insert an element to the end of a list, resizing if necessary.
+ void Insert(T elem) {
+ if (num_used_ == num_allocated_) {
+ Resize(num_used_ + 1);
+ }
+ elem_list_[num_used_++] = elem;
+ }
+
+ void InsertAt(size_t index, T elem) {
+ DCHECK(index <= Size());
+ Insert(elem);
+ for (size_t i = Size() - 1; i > index; --i) {
+ elem_list_[i] = elem_list_[i - 1];
+ }
+ elem_list_[index] = elem;
+ }
+
+ void Add(T elem) {
+ Insert(elem);
+ }
+
+ T Get(size_t index) const {
+ DCHECK_LT(index, num_used_);
+ return elem_list_[index];
+ };
+
+ // Overwrite existing element at position index. List must be large enough.
+ void Put(size_t index, T elem) {
+ DCHECK_LT(index, num_used_);
+ elem_list_[index] = elem;
+ }
+
+ void Increment(size_t index) {
+ DCHECK_LT(index, num_used_);
+ elem_list_[index]++;
+ }
+
+ /*
+ * Remove an existing element from list. If there are more than one copy
+ * of the element, only the first one encountered will be deleted.
+ */
+ // TODO: consider renaming this.
+ void Delete(T element) {
+ bool found = false;
+ for (size_t i = 0; i < num_used_ - 1; i++) {
+ if (!found && elem_list_[i] == element) {
+ found = true;
+ }
+ if (found) {
+ elem_list_[i] = elem_list_[i+1];
+ }
+ }
+ // We should either have found the element, or it was the last (unscanned) element.
+ DCHECK(found || (element == elem_list_[num_used_ - 1]));
+ num_used_--;
+ };
+
+ size_t GetNumAllocated() const { return num_allocated_; }
+
+ size_t Size() const { return num_used_; }
+
+ void SetSize(size_t new_size) {
+ Resize(new_size);
+ num_used_ = new_size;
+ }
+
+ T* GetRawStorage() const { return elem_list_; }
+
+ static void* operator new(size_t size, ArenaAllocator* arena) {
+ return arena->Alloc(sizeof(GrowableArray<T>), ArenaAllocator::kAllocGrowableArray);
+ };
+ static void operator delete(void* p) {} // Nop.
+
+ private:
+ ArenaAllocator* const arena_;
+ size_t num_allocated_;
+ size_t num_used_;
+ OatListKind kind_;
+ T* elem_list_;
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_UTILS_GROWABLE_ARRAY_H_