Semi-pruned SSA support for sea-ir.
Added the following:
Per file:
sea_ir/sea.*: IDominator pass, dominance frontiers, global variables for ssa
transformation, phi-function insertion pass, SSA renaming pass.
sea_ir/instruction_tools.*: These tools provide info needed by dataflow analysis
that is dependent on dex format.
compiler/utils/scoped_hashtable.h: Scoped hashtable implementation that
allows fast SSA renaming.
src/compiler/utils/scoped_hashtable_test.cc: Test for scoped_hashtable.h.
dex_instruction.cc: Changed semantics of the VRegA,B,C function
to return NO_REGISTER instead
of aborting if the instruction does not
have register operands.
Android.common.mk: Added support for scoped_hashtable test.
Change-Id: I990fe4c213d241a033e43a04a67c6083fca4b347
diff --git a/src/compiler/utils/scoped_hashtable.h b/src/compiler/utils/scoped_hashtable.h
new file mode 100644
index 0000000..5e6c64b
--- /dev/null
+++ b/src/compiler/utils/scoped_hashtable.h
@@ -0,0 +1,71 @@
+/*
+ * 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.
+ */
+
+#include <stddef.h>
+#include <map>
+#include <list>
+
+#ifndef SCOPED_HASHTABLE_
+#define SCOPED_HASHTABLE_
+
+namespace utils {
+template <typename K, typename V>
+class ScopedHashtable {
+ public:
+ explicit ScopedHashtable():scopes() {
+ }
+
+ void OpenScope() {
+ scopes.push_front(std::map<K, V>());
+ }
+
+ // Lookups entry K starting from the current (topmost) scope
+ // and returns its value if found or NULL.
+ V Lookup(K k) const {
+ for (typename std::list<std::map<K, V> >::const_iterator scopes_it = scopes.begin();
+ scopes_it != scopes.end(); scopes_it++) {
+ typename std::map<K, V>::const_iterator result_it = (*scopes_it).find(k);
+ if (result_it != (*scopes_it).end()) {
+ return (*result_it).second;
+ }
+ }
+ return NULL;
+ }
+
+ // Adds a new entry in the current (topmost) scope.
+ void Add(K k, V v) {
+ scopes.front().erase(k);
+ scopes.front().insert(std::pair< K, V >(k, v));
+ }
+
+ // Removes the topmost scope.
+ bool CloseScope() {
+ // Added check to uniformly handle undefined behavior
+ // when removing scope and the list of scopes is empty.
+ if (scopes.size() > 0) {
+ scopes.pop_front();
+ return true;
+ }
+ return false;
+ }
+
+ private:
+ std::list<std::map<K, V> > scopes;
+};
+} // end namespace utils
+
+#endif
diff --git a/src/compiler/utils/scoped_hashtable_test.cc b/src/compiler/utils/scoped_hashtable_test.cc
new file mode 100644
index 0000000..072da8c
--- /dev/null
+++ b/src/compiler/utils/scoped_hashtable_test.cc
@@ -0,0 +1,68 @@
+/*
+ * 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.
+ */
+
+#include "common_test.h"
+#include "scoped_hashtable.h"
+
+using utils::ScopedHashtable;
+
+namespace art {
+
+class Value {
+ public:
+ explicit Value(int v):value_(v) {}
+ int value_;
+};
+
+class ScopedHashtableTest : public CommonTest {
+};
+
+TEST_F(ScopedHashtableTest, Basics) {
+ ScopedHashtable<int, Value*> sht;
+ // Check table is empty when no scope is open.
+ EXPECT_TRUE(NULL == sht.Lookup(1));
+
+ // Check table is empty when scope open.
+ sht.OpenScope();
+ EXPECT_TRUE(NULL == sht.Lookup(1));
+ // Check table is empty after closing scope.
+ EXPECT_EQ(sht.CloseScope(), true);
+ // Check closing scope on empty table is no-op.
+ EXPECT_EQ(sht.CloseScope(), false);
+ // Check that find in current scope works.
+ sht.OpenScope();
+ sht.Add(1, new Value(1));
+ EXPECT_EQ(sht.Lookup(1)->value_, 1);
+ // Check that updating values in current scope works.
+ sht.Add(1, new Value(2));
+ EXPECT_EQ(sht.Lookup(1)->value_, 2);
+ // Check that find works in previous scope.
+ sht.OpenScope();
+ EXPECT_EQ(sht.Lookup(1)->value_, 2);
+ // Check that shadowing scopes works.
+ sht.Add(1, new Value(3));
+ EXPECT_EQ(sht.Lookup(1)->value_, 3);
+ // Check that having multiple keys work correctly.
+ sht.Add(2, new Value(4));
+ EXPECT_EQ(sht.Lookup(1)->value_, 3);
+ EXPECT_EQ(sht.Lookup(2)->value_, 4);
+ // Check that scope removal works corectly.
+ sht.CloseScope();
+ EXPECT_EQ(sht.Lookup(1)->value_, 2);
+ EXPECT_TRUE(NULL == sht.Lookup(2));
+}
+
+} // end namespace art