Refactor handling of input records.
Introduce HInstruction::GetInputRecords(), a new virtual
function that returns an ArrayRef<> to all input records.
Implement all other functions dealing with input records as
wrappers around GetInputRecords(). Rewrite functions that
previously used multiple virtual calls to deal with input
records, especially in loops, to prefetch the ArrayRef<>
only once for each instruction. Besides avoiding all the
extra calls, this also allows the compiler (clang++) to
perform additional optimizations.
This speeds up the Nexus 5 boot image compilation by ~0.5s
(4% of "Compile Dex File", 2% of dex2oat time) on AOSP ToT.
Change-Id: Id8ebe0fb9405e38d918972a11bd724146e4ca578
diff --git a/compiler/utils/transform_iterator.h b/compiler/utils/transform_iterator.h
new file mode 100644
index 0000000..f0769d4
--- /dev/null
+++ b/compiler/utils/transform_iterator.h
@@ -0,0 +1,182 @@
+/*
+ * Copyright (C) 2016 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_TRANSFORM_ITERATOR_H_
+#define ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_
+
+#include <iterator>
+#include <type_traits>
+
+#include "base/iteration_range.h"
+
+namespace art {
+
+// The transform iterator transforms values from the base iterator with a given
+// transformation function. It can serve as a replacement for std::transform(), i.e.
+// std::copy(MakeTransformIterator(begin, f), MakeTransformIterator(end, f), out)
+// is equivalent to
+// std::transform(begin, end, f)
+// If the function returns an l-value reference or a wrapper that supports assignment,
+// the TransformIterator can be used also as an output iterator, i.e.
+// std::copy(begin, end, MakeTransformIterator(out, f))
+// is equivalent to
+// for (auto it = begin; it != end; ++it) {
+// f(*out++) = *it;
+// }
+template <typename BaseIterator, typename Function>
+class TransformIterator {
+ private:
+ static_assert(std::is_base_of<
+ std::input_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "Transform iterator base must be an input iterator.");
+
+ using InputType =
+ typename std::conditional<
+ std::is_same<void, typename std::iterator_traits<BaseIterator>::reference>::value,
+ typename std::iterator_traits<BaseIterator>::value_type,
+ typename std::iterator_traits<BaseIterator>::reference>::type;
+ using ResultType = typename std::result_of<Function(InputType)>::type;
+
+ public:
+ using iterator_category = typename std::iterator_traits<BaseIterator>::iterator_category;
+ using value_type =
+ typename std::remove_const<typename std::remove_reference<ResultType>::type>::type;
+ using difference_type = typename std::iterator_traits<BaseIterator>::difference_type;
+ using pointer = typename std::conditional<
+ std::is_reference<ResultType>::value,
+ typename std::add_pointer<typename std::remove_reference<ResultType>::type>::type,
+ TransformIterator>::type;
+ using reference = ResultType;
+
+ TransformIterator(BaseIterator base, Function fn)
+ : data_(base, fn) { }
+
+ template <typename OtherBI>
+ TransformIterator(const TransformIterator<OtherBI, Function>& other)
+ : data_(other.base(), other.GetFunction()) {
+ }
+
+ TransformIterator& operator++() {
+ ++data_.base_;
+ return *this;
+ }
+
+ TransformIterator& operator++(int) {
+ TransformIterator tmp(*this);
+ ++*this;
+ return tmp;
+ }
+
+ TransformIterator& operator--() {
+ static_assert(
+ std::is_base_of<std::bidirectional_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "BaseIterator must be bidirectional iterator to use operator--()");
+ --data_.base_;
+ return *this;
+ }
+
+ TransformIterator& operator--(int) {
+ TransformIterator tmp(*this);
+ --*this;
+ return tmp;
+ }
+
+ reference operator*() const {
+ return GetFunction()(*base());
+ }
+
+ reference operator[](difference_type n) const {
+ static_assert(
+ std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "BaseIterator must be random access iterator to use operator[]");
+ return GetFunction()(base()[n]);
+ }
+
+ TransformIterator operator+(difference_type n) const {
+ static_assert(
+ std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "BaseIterator must be random access iterator to use operator+");
+ return TransformIterator(base() + n, GetFunction());
+ }
+
+ TransformIterator operator-(difference_type n) const {
+ static_assert(
+ std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "BaseIterator must be random access iterator to use operator-");
+ return TransformIterator(base() - n, GetFunction());
+ }
+
+ difference_type operator-(const TransformIterator& other) const {
+ static_assert(
+ std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "BaseIterator must be random access iterator to use operator-");
+ return base() - other.base();
+ }
+
+ // Retrieve the base iterator.
+ BaseIterator base() const {
+ return data_.base_;
+ }
+
+ // Retrieve the transformation function.
+ const Function& GetFunction() const {
+ return static_cast<const Function&>(data_);
+ }
+
+ private:
+ // Allow EBO for state-less Function.
+ struct Data : Function {
+ public:
+ Data(BaseIterator base, Function fn) : Function(fn), base_(base) { }
+
+ BaseIterator base_;
+ };
+
+ Data data_;
+};
+
+template <typename BaseIterator1, typename BaseIterator2, typename Function>
+bool operator==(const TransformIterator<BaseIterator1, Function>& lhs,
+ const TransformIterator<BaseIterator2, Function>& rhs) {
+ return lhs.base() == rhs.base();
+}
+
+template <typename BaseIterator1, typename BaseIterator2, typename Function>
+bool operator!=(const TransformIterator<BaseIterator1, Function>& lhs,
+ const TransformIterator<BaseIterator2, Function>& rhs) {
+ return !(lhs == rhs);
+}
+
+template <typename BaseIterator, typename Function>
+TransformIterator<BaseIterator, Function> MakeTransformIterator(BaseIterator base, Function f) {
+ return TransformIterator<BaseIterator, Function>(base, f);
+}
+
+template <typename BaseRange, typename Function>
+auto MakeTransformRange(BaseRange& range, Function f) {
+ return MakeIterationRange(MakeTransformIterator(range.begin(), f),
+ MakeTransformIterator(range.end(), f));
+}
+
+} // namespace art
+
+#endif // ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_