ART: Clean up arm64 kNumberOfXRegisters usage.

Avoid undefined behavior for arm64 stemming from 1u << 32 in
loops with upper bound kNumberOfXRegisters.

Create iterators for enumerating bits in an integer either
from high to low or from low to high and use them for
<arch>Context::FillCalleeSaves() on all architectures.

Refactor runtime/utils.{h,cc} by moving all bit-fiddling
functions to runtime/base/bit_utils.{h,cc} (together with
the new bit iterators) and all time-related functions to
runtime/base/time_utils.{h,cc}. Improve test coverage and
fix some corner cases for the bit-fiddling functions.

Bug: 13925192

(cherry picked from commit 80afd02024d20e60b197d3adfbb43cc303cf29e0)

Change-Id: I905257a21de90b5860ebe1e39563758f721eab82

22 files changed, 25 insertions, 8 deletions

diff --git a/runtime/gc/accounting/atomic_stack.h b/runtime/gc/accounting/atomic_stack.h
index 399832a..ac716ea 100644
--- a/runtime/gc/accounting/atomic_stack.h
+++ b/runtime/gc/accounting/atomic_stack.h
@@ -22,11 +22,11 @@
 #include <string>
 
 #include "atomic.h"
+#include "base/bit_utils.h"
 #include "base/logging.h"
 #include "base/macros.h"
 #include "mem_map.h"
 #include "stack.h"
-#include "utils.h"
 
 namespace art {
 namespace gc {
diff --git a/runtime/gc/accounting/bitmap-inl.h b/runtime/gc/accounting/bitmap-inl.h
index e87a0c0..cd3923a 100644
--- a/runtime/gc/accounting/bitmap-inl.h
+++ b/runtime/gc/accounting/bitmap-inl.h
@@ -22,8 +22,8 @@
 #include <memory>
 
 #include "atomic.h"
+#include "base/bit_utils.h"
 #include "base/logging.h"
-#include "utils.h"
 
 namespace art {
 namespace gc {
diff --git a/runtime/gc/accounting/bitmap.cc b/runtime/gc/accounting/bitmap.cc
index 13fcdb3..fdded02 100644
--- a/runtime/gc/accounting/bitmap.cc
+++ b/runtime/gc/accounting/bitmap.cc
@@ -16,6 +16,7 @@
 
 #include "bitmap-inl.h"
 
+#include "base/bit_utils.h"
 #include "card_table.h"
 #include "mem_map.h"
 
diff --git a/runtime/gc/accounting/card_table-inl.h b/runtime/gc/accounting/card_table-inl.h
index b936d93..f72f219 100644
--- a/runtime/gc/accounting/card_table-inl.h
+++ b/runtime/gc/accounting/card_table-inl.h
@@ -18,11 +18,11 @@
 #define ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_
 
 #include "atomic.h"
+#include "base/bit_utils.h"
 #include "base/logging.h"
 #include "card_table.h"
 #include "mem_map.h"
 #include "space_bitmap.h"
-#include "utils.h"
 
 namespace art {
 namespace gc {
diff --git a/runtime/gc/accounting/read_barrier_table.h b/runtime/gc/accounting/read_barrier_table.h
index bb9aae7..436df92 100644
--- a/runtime/gc/accounting/read_barrier_table.h
+++ b/runtime/gc/accounting/read_barrier_table.h
@@ -17,6 +17,7 @@
 #ifndef ART_RUNTIME_GC_ACCOUNTING_READ_BARRIER_TABLE_H_
 #define ART_RUNTIME_GC_ACCOUNTING_READ_BARRIER_TABLE_H_
 
+#include "base/bit_utils.h"
 #include "base/mutex.h"
 #include "gc/space/space.h"
 #include "globals.h"
diff --git a/runtime/gc/accounting/space_bitmap-inl.h b/runtime/gc/accounting/space_bitmap-inl.h
index ae91200..c16f5d3 100644
--- a/runtime/gc/accounting/space_bitmap-inl.h
+++ b/runtime/gc/accounting/space_bitmap-inl.h
@@ -22,8 +22,8 @@
 #include <memory>
 
 #include "atomic.h"
+#include "base/bit_utils.h"
 #include "base/logging.h"
-#include "utils.h"
 
 namespace art {
 namespace gc {
diff --git a/runtime/gc/allocator/dlmalloc.cc b/runtime/gc/allocator/dlmalloc.cc
index 8558f96..3d85395 100644
--- a/runtime/gc/allocator/dlmalloc.cc
+++ b/runtime/gc/allocator/dlmalloc.cc
@@ -16,6 +16,7 @@
 
 #include "dlmalloc.h"
 
+#include "base/bit_utils.h"
 #include "base/logging.h"
 
 // ART specific morecore implementation defined in space.cc.
diff --git a/runtime/gc/allocator/rosalloc.h b/runtime/gc/allocator/rosalloc.h
index a54edcc..0fcfe72 100644
--- a/runtime/gc/allocator/rosalloc.h
+++ b/runtime/gc/allocator/rosalloc.h
@@ -27,11 +27,11 @@
 #include <vector>
 
 #include "base/allocator.h"
+#include "base/bit_utils.h"
 #include "base/mutex.h"
 #include "base/logging.h"
 #include "globals.h"
 #include "thread.h"
-#include "utils.h"
 
 namespace art {
 
diff --git a/runtime/gc/collector/garbage_collector.cc b/runtime/gc/collector/garbage_collector.cc
index 47d6ada..afd0a30 100644
--- a/runtime/gc/collector/garbage_collector.cc
+++ b/runtime/gc/collector/garbage_collector.cc
@@ -25,11 +25,13 @@
 #include "base/histogram-inl.h"
 #include "base/logging.h"
 #include "base/mutex-inl.h"
+#include "base/time_utils.h"
 #include "gc/accounting/heap_bitmap.h"
 #include "gc/space/large_object_space.h"
 #include "gc/space/space-inl.h"
 #include "thread-inl.h"
 #include "thread_list.h"
+#include "utils.h"
 
 namespace art {
 namespace gc {
diff --git a/runtime/gc/collector/mark_sweep.cc b/runtime/gc/collector/mark_sweep.cc
index 2db5650..2a9c03d 100644
--- a/runtime/gc/collector/mark_sweep.cc
+++ b/runtime/gc/collector/mark_sweep.cc
@@ -29,6 +29,7 @@
 #include "base/logging.h"
 #include "base/macros.h"
 #include "base/mutex-inl.h"
+#include "base/time_utils.h"
 #include "base/timing_logger.h"
 #include "gc/accounting/card_table-inl.h"
 #include "gc/accounting/heap_bitmap-inl.h"
diff --git a/runtime/gc/heap-inl.h b/runtime/gc/heap-inl.h
index fbf36e8..eb0e9be 100644
--- a/runtime/gc/heap-inl.h
+++ b/runtime/gc/heap-inl.h
@@ -19,6 +19,7 @@
 
 #include "heap.h"
 
+#include "base/time_utils.h"
 #include "debugger.h"
 #include "gc/accounting/card_table-inl.h"
 #include "gc/collector/semi_space.h"
@@ -31,6 +32,7 @@
 #include "handle_scope-inl.h"
 #include "thread.h"
 #include "thread-inl.h"
+#include "utils.h"
 #include "verify_object-inl.h"
 
 namespace art {
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index 11a0e3c..fbde494 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -28,6 +28,7 @@
 #include "base/dumpable.h"
 #include "base/histogram-inl.h"
 #include "base/stl_util.h"
+#include "base/time_utils.h"
 #include "common_throws.h"
 #include "cutils/sched_policy.h"
 #include "debugger.h"
diff --git a/runtime/gc/heap.h b/runtime/gc/heap.h
index 90249f9..c72414a 100644
--- a/runtime/gc/heap.h
+++ b/runtime/gc/heap.h
@@ -24,6 +24,7 @@
 #include "allocator_type.h"
 #include "arch/instruction_set.h"
 #include "atomic.h"
+#include "base/time_utils.h"
 #include "base/timing_logger.h"
 #include "gc/accounting/atomic_stack.h"
 #include "gc/accounting/card_table.h"
diff --git a/runtime/gc/reference_processor.cc b/runtime/gc/reference_processor.cc
index 01e8795..5af2a53 100644
--- a/runtime/gc/reference_processor.cc
+++ b/runtime/gc/reference_processor.cc
@@ -16,6 +16,7 @@
 
 #include "reference_processor.h"
 
+#include "base/time_utils.h"
 #include "mirror/object-inl.h"
 #include "mirror/reference.h"
 #include "mirror/reference-inl.h"
@@ -24,6 +25,7 @@
 #include "ScopedLocalRef.h"
 #include "scoped_thread_state_change.h"
 #include "task_processor.h"
+#include "utils.h"
 #include "well_known_classes.h"
 
 namespace art {
diff --git a/runtime/gc/space/bump_pointer_space-inl.h b/runtime/gc/space/bump_pointer_space-inl.h
index 14a93d1..d9ad9a3 100644
--- a/runtime/gc/space/bump_pointer_space-inl.h
+++ b/runtime/gc/space/bump_pointer_space-inl.h
@@ -17,6 +17,7 @@
 #ifndef ART_RUNTIME_GC_SPACE_BUMP_POINTER_SPACE_INL_H_
 #define ART_RUNTIME_GC_SPACE_BUMP_POINTER_SPACE_INL_H_
 
+#include "base/bit_utils.h"
 #include "bump_pointer_space.h"
 
 namespace art {
diff --git a/runtime/gc/space/dlmalloc_space.cc b/runtime/gc/space/dlmalloc_space.cc
index 7b1a421..5237c7b 100644
--- a/runtime/gc/space/dlmalloc_space.cc
+++ b/runtime/gc/space/dlmalloc_space.cc
@@ -16,6 +16,7 @@
 
 #include "dlmalloc_space-inl.h"
 
+#include "base/time_utils.h"
 #include "gc/accounting/card_table.h"
 #include "gc/accounting/space_bitmap-inl.h"
 #include "gc/heap.h"
diff --git a/runtime/gc/space/image_space.cc b/runtime/gc/space/image_space.cc
index 99f5d45..ade9cec 100644
--- a/runtime/gc/space/image_space.cc
+++ b/runtime/gc/space/image_space.cc
@@ -25,8 +25,9 @@
 
 #include "base/macros.h"
 #include "base/stl_util.h"
-#include "base/unix_file/fd_file.h"
 #include "base/scoped_flock.h"
+#include "base/time_utils.h"
+#include "base/unix_file/fd_file.h"
 #include "gc/accounting/space_bitmap-inl.h"
 #include "mirror/art_method.h"
 #include "mirror/class-inl.h"
diff --git a/runtime/gc/space/large_object_space.cc b/runtime/gc/space/large_object_space.cc
index 4dfdaa5..da4a930 100644
--- a/runtime/gc/space/large_object_space.cc
+++ b/runtime/gc/space/large_object_space.cc
@@ -27,7 +27,6 @@
 #include "os.h"
 #include "space-inl.h"
 #include "thread-inl.h"
-#include "utils.h"
 
 namespace art {
 namespace gc {
diff --git a/runtime/gc/space/large_object_space_test.cc b/runtime/gc/space/large_object_space_test.cc
index a261663..f04a7ca 100644
--- a/runtime/gc/space/large_object_space_test.cc
+++ b/runtime/gc/space/large_object_space_test.cc
@@ -14,6 +14,7 @@
  * limitations under the License.
  */
 
+#include "base/time_utils.h"
 #include "space_test.h"
 #include "large_object_space.h"
 
diff --git a/runtime/gc/space/rosalloc_space.cc b/runtime/gc/space/rosalloc_space.cc
index 2c7d93e..bc4414d 100644
--- a/runtime/gc/space/rosalloc_space.cc
+++ b/runtime/gc/space/rosalloc_space.cc
@@ -20,6 +20,7 @@
 #define ATRACE_TAG ATRACE_TAG_DALVIK
 #include "cutils/trace.h"
 
+#include "base/time_utils.h"
 #include "gc/accounting/card_table.h"
 #include "gc/accounting/space_bitmap-inl.h"
 #include "gc/heap.h"
diff --git a/runtime/gc/task_processor.cc b/runtime/gc/task_processor.cc
index ef34c68..a49121b 100644
--- a/runtime/gc/task_processor.cc
+++ b/runtime/gc/task_processor.cc
@@ -16,6 +16,7 @@
 
 #include "task_processor.h"
 
+#include "base/time_utils.h"
 #include "scoped_thread_state_change.h"
 
 namespace art {
diff --git a/runtime/gc/task_processor_test.cc b/runtime/gc/task_processor_test.cc
index 5dd6d8f..f06f68d 100644
--- a/runtime/gc/task_processor_test.cc
+++ b/runtime/gc/task_processor_test.cc
@@ -14,11 +14,11 @@
  * limitations under the License.
  */
 
+#include "base/time_utils.h"
 #include "common_runtime_test.h"
 #include "task_processor.h"
 #include "thread_pool.h"
 #include "thread-inl.h"
-#include "utils.h"
 
 namespace art {
 namespace gc {