Partial Load Store Elimination

Add partial load-store elimination to the LSE pass. Partial LSE will
move object allocations which only escape along certain execution
paths closer to the escape point and allow more values to be
eliminated. It does this by creating new predicated load and store
instructions that are used when an object has only escaped some of the
time. In cases where the object has not escaped a default value will
be used.

Test: ./test.py --host
Test: ./test.py --target
Bug: 67037140

Change-Id: Idde67eb59ec90de79747cde17b552eec05b58497

1 files changed, 284 insertions, 12 deletions

diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 73db7e541f..9e0f515ba9 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -72,6 +72,7 @@ class HParameterValue;
 class HPhi;
 class HSuspendCheck;
 class HTryBoundary;
+class FieldInfo;
 class LiveInterval;
 class LocationSummary;
 class SlowPathCode;
@@ -1097,6 +1098,10 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> {
     return predecessors_;
   }
 
+  size_t GetNumberOfPredecessors() const {
+    return GetPredecessors().size();
+  }
+
   const ArenaVector<HBasicBlock*>& GetSuccessors() const {
     return successors_;
   }
@@ -1439,6 +1444,8 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> {
 
   friend class HGraph;
   friend class HInstruction;
+  // Allow manual control of the ordering of predecessors/successors
+  friend class OptimizingUnitTestHelper;
 
   DISALLOW_COPY_AND_ASSIGN(HBasicBlock);
 };
@@ -1503,6 +1510,7 @@ class HLoopInformationOutwardIterator : public ValueObject {
   M(If, Instruction)                                                    \
   M(InstanceFieldGet, Instruction)                                      \
   M(InstanceFieldSet, Instruction)                                      \
+  M(PredicatedInstanceFieldGet, Instruction)                            \
   M(InstanceOf, Instruction)                                            \
   M(IntConstant, Constant)                                              \
   M(IntermediateAddress, Instruction)                                   \
@@ -1680,8 +1688,7 @@ FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
   H##type& operator=(const H##type&) = delete;                          \
   public:
 
-#define DEFAULT_COPY_CONSTRUCTOR(type)                                  \
-  explicit H##type(const H##type& other) = default;
+#define DEFAULT_COPY_CONSTRUCTOR(type) H##type(const H##type& other) = default;
 
 template <typename T>
 class HUseListNode : public ArenaObject<kArenaAllocUseListNode>,
@@ -2105,6 +2112,23 @@ class HEnvironment : public ArenaObject<kArenaAllocEnvironment> {
     return GetParent() != nullptr;
   }
 
+  class EnvInputSelector {
+   public:
+    explicit EnvInputSelector(const HEnvironment* e) : env_(e) {}
+    HInstruction* operator()(size_t s) const {
+      return env_->GetInstructionAt(s);
+    }
+   private:
+    const HEnvironment* env_;
+  };
+
+  using HConstEnvInputRef = TransformIterator<CountIter, EnvInputSelector>;
+  IterationRange<HConstEnvInputRef> GetEnvInputs() const {
+    IterationRange<CountIter> range(Range(Size()));
+    return MakeIterationRange(MakeTransformIterator(range.begin(), EnvInputSelector(this)),
+                              MakeTransformIterator(range.end(), EnvInputSelector(this)));
+  }
+
  private:
   ArenaVector<HUserRecord<HEnvironment*>> vregs_;
   ArenaVector<Location> locations_;
@@ -2122,6 +2146,40 @@ class HEnvironment : public ArenaObject<kArenaAllocEnvironment> {
 
 std::ostream& operator<<(std::ostream& os, const HInstruction& rhs);
 
+// Iterates over the Environments
+class HEnvironmentIterator : public ValueObject,
+                             public std::iterator<std::forward_iterator_tag, HEnvironment*> {
+ public:
+  explicit HEnvironmentIterator(HEnvironment* cur) : cur_(cur) {}
+
+  HEnvironment* operator*() const {
+    return cur_;
+  }
+
+  HEnvironmentIterator& operator++() {
+    DCHECK(cur_ != nullptr);
+    cur_ = cur_->GetParent();
+    return *this;
+  }
+
+  HEnvironmentIterator operator++(int) {
+    HEnvironmentIterator prev(*this);
+    ++(*this);
+    return prev;
+  }
+
+  bool operator==(const HEnvironmentIterator& other) const {
+    return other.cur_ == cur_;
+  }
+
+  bool operator!=(const HEnvironmentIterator& other) const {
+    return !(*this == other);
+  }
+
+ private:
+  HEnvironment* cur_;
+};
+
 class HInstruction : public ArenaObject<kArenaAllocInstruction> {
  public:
 #define DECLARE_KIND(type, super) k##type,
@@ -2240,6 +2298,10 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
 
   // Does the instruction always throw an exception unconditionally?
   virtual bool AlwaysThrows() const { return false; }
+  // Will this instruction only cause async exceptions if it causes any at all?
+  virtual bool OnlyThrowsAsyncExceptions() const {
+    return false;
+  }
 
   bool CanThrowIntoCatchBlock() const { return CanThrow() && block_->IsTryBlock(); }
 
@@ -2361,6 +2423,10 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
 
   bool HasEnvironment() const { return environment_ != nullptr; }
   HEnvironment* GetEnvironment() const { return environment_; }
+  IterationRange<HEnvironmentIterator> GetAllEnvironments() const {
+    return MakeIterationRange(HEnvironmentIterator(GetEnvironment()),
+                              HEnvironmentIterator(nullptr));
+  }
   // Set the `environment_` field. Raw because this method does not
   // update the uses lists.
   void SetRawEnvironment(HEnvironment* environment) {
@@ -2461,6 +2527,17 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
     UNREACHABLE();
   }
 
+  virtual bool IsFieldAccess() const {
+    return false;
+  }
+
+  virtual const FieldInfo& GetFieldInfo() const {
+    CHECK(IsFieldAccess()) << "Only callable on field accessors not " << DebugName() << " "
+                           << *this;
+    LOG(FATAL) << "Must be overridden by field accessors. Not implemented by " << *this;
+    UNREACHABLE();
+  }
+
   // Return whether instruction can be cloned (copied).
   virtual bool IsClonable() const { return false; }
 
@@ -2696,12 +2773,16 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
   friend class HGraph;
   friend class HInstructionList;
 };
+
 std::ostream& operator<<(std::ostream& os, HInstruction::InstructionKind rhs);
 std::ostream& operator<<(std::ostream& os, const HInstruction::NoArgsDump rhs);
 std::ostream& operator<<(std::ostream& os, const HInstruction::ArgsDump rhs);
 std::ostream& operator<<(std::ostream& os, const HUseList<HInstruction*>& lst);
 std::ostream& operator<<(std::ostream& os, const HUseList<HEnvironment*>& lst);
 
+// Forward declarations for friends
+template <typename InnerIter> struct HSTLInstructionIterator;
+
 // Iterates over the instructions, while preserving the next instruction
 // in case the current instruction gets removed from the list by the user
 // of this iterator.
@@ -2720,10 +2801,12 @@ class HInstructionIterator : public ValueObject {
   }
 
  private:
+  HInstructionIterator() : instruction_(nullptr), next_(nullptr) {}
+
   HInstruction* instruction_;
   HInstruction* next_;
 
-  DISALLOW_COPY_AND_ASSIGN(HInstructionIterator);
+  friend struct HSTLInstructionIterator<HInstructionIterator>;
 };
 
 // Iterates over the instructions without saving the next instruction,
@@ -2742,9 +2825,11 @@ class HInstructionIteratorHandleChanges : public ValueObject {
   }
 
  private:
+  HInstructionIteratorHandleChanges() : instruction_(nullptr) {}
+
   HInstruction* instruction_;
 
-  DISALLOW_COPY_AND_ASSIGN(HInstructionIteratorHandleChanges);
+  friend struct HSTLInstructionIterator<HInstructionIteratorHandleChanges>;
 };
 
 
@@ -2763,12 +2848,63 @@ class HBackwardInstructionIterator : public ValueObject {
   }
 
  private:
+  HBackwardInstructionIterator() : instruction_(nullptr), next_(nullptr) {}
+
   HInstruction* instruction_;
   HInstruction* next_;
 
-  DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator);
+  friend struct HSTLInstructionIterator<HBackwardInstructionIterator>;
+};
+
+template <typename InnerIter>
+struct HSTLInstructionIterator : public ValueObject,
+                                 public std::iterator<std::forward_iterator_tag, HInstruction*> {
+ public:
+  static_assert(std::is_same_v<InnerIter, HBackwardInstructionIterator> ||
+                    std::is_same_v<InnerIter, HInstructionIterator> ||
+                    std::is_same_v<InnerIter, HInstructionIteratorHandleChanges>,
+                "Unknown wrapped iterator!");
+
+  explicit HSTLInstructionIterator(InnerIter inner) : inner_(inner) {}
+  HInstruction* operator*() const {
+    DCHECK(inner_.Current() != nullptr);
+    return inner_.Current();
+  }
+
+  HSTLInstructionIterator<InnerIter>& operator++() {
+    DCHECK(*this != HSTLInstructionIterator<InnerIter>::EndIter());
+    inner_.Advance();
+    return *this;
+  }
+
+  HSTLInstructionIterator<InnerIter> operator++(int) {
+    HSTLInstructionIterator<InnerIter> prev(*this);
+    ++(*this);
+    return prev;
+  }
+
+  bool operator==(const HSTLInstructionIterator<InnerIter>& other) const {
+    return inner_.Current() == other.inner_.Current();
+  }
+
+  bool operator!=(const HSTLInstructionIterator<InnerIter>& other) const {
+    return !(*this == other);
+  }
+
+  static HSTLInstructionIterator<InnerIter> EndIter() {
+    return HSTLInstructionIterator<InnerIter>(InnerIter());
+  }
+
+ private:
+  InnerIter inner_;
 };
 
+template <typename InnerIter>
+IterationRange<HSTLInstructionIterator<InnerIter>> MakeSTLInstructionIteratorRange(InnerIter iter) {
+  return MakeIterationRange(HSTLInstructionIterator<InnerIter>(iter),
+                            HSTLInstructionIterator<InnerIter>::EndIter());
+}
+
 class HVariableInputSizeInstruction : public HInstruction {
  public:
   using HInstruction::GetInputRecords;  // Keep the const version visible.
@@ -4345,11 +4481,16 @@ class HNewInstance final : public HExpression<1> {
         dex_file_(dex_file),
         entrypoint_(entrypoint) {
     SetPackedFlag<kFlagFinalizable>(finalizable);
+    SetPackedFlag<kFlagPartialMaterialization>(false);
     SetRawInputAt(0, cls);
   }
 
   bool IsClonable() const override { return true; }
 
+  void SetPartialMaterialization() {
+    SetPackedFlag<kFlagPartialMaterialization>(true);
+  }
+
   dex::TypeIndex GetTypeIndex() const { return type_index_; }
   const DexFile& GetDexFile() const { return dex_file_; }
 
@@ -4358,6 +4499,9 @@ class HNewInstance final : public HExpression<1> {
 
   // Can throw errors when out-of-memory or if it's not instantiable/accessible.
   bool CanThrow() const override { return true; }
+  bool OnlyThrowsAsyncExceptions() const override {
+    return !IsFinalizable() && !NeedsChecks();
+  }
 
   bool NeedsChecks() const {
     return entrypoint_ == kQuickAllocObjectWithChecks;
@@ -4367,6 +4511,10 @@ class HNewInstance final : public HExpression<1> {
 
   bool CanBeNull() const override { return false; }
 
+  bool IsPartialMaterialization() const {
+    return GetPackedFlag<kFlagPartialMaterialization>();
+  }
+
   QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; }
 
   void SetEntrypoint(QuickEntrypointEnum entrypoint) {
@@ -4391,7 +4539,8 @@ class HNewInstance final : public HExpression<1> {
 
  private:
   static constexpr size_t kFlagFinalizable = kNumberOfGenericPackedBits;
-  static constexpr size_t kNumberOfNewInstancePackedBits = kFlagFinalizable + 1;
+  static constexpr size_t kFlagPartialMaterialization = kFlagFinalizable + 1;
+  static constexpr size_t kNumberOfNewInstancePackedBits = kFlagPartialMaterialization + 1;
   static_assert(kNumberOfNewInstancePackedBits <= kMaxNumberOfPackedBits,
                 "Too many packed fields.");
 
@@ -5965,6 +6114,23 @@ class FieldInfo : public ValueObject {
   const DexFile& GetDexFile() const { return dex_file_; }
   bool IsVolatile() const { return is_volatile_; }
 
+  bool Equals(const FieldInfo& other) const {
+    return field_ == other.field_ &&
+           field_offset_ == other.field_offset_ &&
+           field_type_ == other.field_type_ &&
+           is_volatile_ == other.is_volatile_ &&
+           index_ == other.index_ &&
+           declaring_class_def_index_ == other.declaring_class_def_index_ &&
+           &dex_file_ == &other.dex_file_;
+  }
+
+  std::ostream& Dump(std::ostream& os) const {
+    os << field_ << ", off: " << field_offset_ << ", type: " << field_type_
+       << ", volatile: " << std::boolalpha << is_volatile_ << ", index_: " << std::dec << index_
+       << ", declaring_class: " << declaring_class_def_index_ << ", dex: " << dex_file_;
+    return os;
+  }
+
  private:
   ArtField* const field_;
   const MemberOffset field_offset_;
@@ -5975,6 +6141,14 @@ class FieldInfo : public ValueObject {
   const DexFile& dex_file_;
 };
 
+inline bool operator==(const FieldInfo& a, const FieldInfo& b) {
+  return a.Equals(b);
+}
+
+inline std::ostream& operator<<(std::ostream& os, const FieldInfo& a) {
+  return a.Dump(os);
+}
+
 class HInstanceFieldGet final : public HExpression<1> {
  public:
   HInstanceFieldGet(HInstruction* value,
@@ -6016,7 +6190,8 @@ class HInstanceFieldGet final : public HExpression<1> {
     return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
   }
 
-  const FieldInfo& GetFieldInfo() const { return field_info_; }
+  bool IsFieldAccess() const override { return true; }
+  const FieldInfo& GetFieldInfo() const override { return field_info_; }
   MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
   DataType::Type GetFieldType() const { return field_info_.GetFieldType(); }
   bool IsVolatile() const { return field_info_.IsVolatile(); }
@@ -6037,6 +6212,96 @@ class HInstanceFieldGet final : public HExpression<1> {
   const FieldInfo field_info_;
 };
 
+class HPredicatedInstanceFieldGet final : public HExpression<2> {
+ public:
+  HPredicatedInstanceFieldGet(HInstanceFieldGet* orig,
+                              HInstruction* target,
+                              HInstruction* default_val)
+      : HExpression(kPredicatedInstanceFieldGet,
+                    orig->GetFieldType(),
+                    orig->GetSideEffects(),
+                    orig->GetDexPc()),
+        field_info_(orig->GetFieldInfo()) {
+    // NB Default-val is at 0 so we can avoid doing a move.
+    SetRawInputAt(1, target);
+    SetRawInputAt(0, default_val);
+  }
+
+  HPredicatedInstanceFieldGet(HInstruction* value,
+                              ArtField* field,
+                              HInstruction* default_value,
+                              DataType::Type field_type,
+                              MemberOffset field_offset,
+                              bool is_volatile,
+                              uint32_t field_idx,
+                              uint16_t declaring_class_def_index,
+                              const DexFile& dex_file,
+                              uint32_t dex_pc)
+      : HExpression(kPredicatedInstanceFieldGet,
+                    field_type,
+                    SideEffects::FieldReadOfType(field_type, is_volatile),
+                    dex_pc),
+        field_info_(field,
+                    field_offset,
+                    field_type,
+                    is_volatile,
+                    field_idx,
+                    declaring_class_def_index,
+                    dex_file) {
+    SetRawInputAt(0, value);
+    SetRawInputAt(1, default_value);
+  }
+
+  bool IsClonable() const override {
+    return true;
+  }
+  bool CanBeMoved() const override {
+    return !IsVolatile();
+  }
+
+  HInstruction* GetDefaultValue() const {
+    return InputAt(0);
+  }
+  HInstruction* GetTarget() const {
+    return InputAt(1);
+  }
+
+  bool InstructionDataEquals(const HInstruction* other) const override {
+    const HPredicatedInstanceFieldGet* other_get = other->AsPredicatedInstanceFieldGet();
+    return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue() &&
+           GetDefaultValue() == other_get->GetDefaultValue();
+  }
+
+  bool CanDoImplicitNullCheckOn(HInstruction* obj) const override {
+    return (obj == InputAt(0)) && art::CanDoImplicitNullCheckOn(GetFieldOffset().Uint32Value());
+  }
+
+  size_t ComputeHashCode() const override {
+    return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
+  }
+
+  bool IsFieldAccess() const override { return true; }
+  const FieldInfo& GetFieldInfo() const override { return field_info_; }
+  MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
+  DataType::Type GetFieldType() const { return field_info_.GetFieldType(); }
+  bool IsVolatile() const { return field_info_.IsVolatile(); }
+
+  void SetType(DataType::Type new_type) {
+    DCHECK(DataType::IsIntegralType(GetType()));
+    DCHECK(DataType::IsIntegralType(new_type));
+    DCHECK_EQ(DataType::Size(GetType()), DataType::Size(new_type));
+    SetPackedField<TypeField>(new_type);
+  }
+
+  DECLARE_INSTRUCTION(PredicatedInstanceFieldGet);
+
+ protected:
+  DEFAULT_COPY_CONSTRUCTOR(PredicatedInstanceFieldGet);
+
+ private:
+  const FieldInfo field_info_;
+};
+
 class HInstanceFieldSet final : public HExpression<2> {
  public:
   HInstanceFieldSet(HInstruction* object,
@@ -6060,6 +6325,7 @@ class HInstanceFieldSet final : public HExpression<2> {
                     declaring_class_def_index,
                     dex_file) {
     SetPackedFlag<kFlagValueCanBeNull>(true);
+    SetPackedFlag<kFlagIsPredicatedSet>(false);
     SetRawInputAt(0, object);
     SetRawInputAt(1, value);
   }
@@ -6070,13 +6336,16 @@ class HInstanceFieldSet final : public HExpression<2> {
     return (obj == InputAt(0)) && art::CanDoImplicitNullCheckOn(GetFieldOffset().Uint32Value());
   }
 
-  const FieldInfo& GetFieldInfo() const { return field_info_; }
+  bool IsFieldAccess() const override { return true; }
+  const FieldInfo& GetFieldInfo() const override { return field_info_; }
   MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
   DataType::Type GetFieldType() const { return field_info_.GetFieldType(); }
   bool IsVolatile() const { return field_info_.IsVolatile(); }
   HInstruction* GetValue() const { return InputAt(1); }
   bool GetValueCanBeNull() const { return GetPackedFlag<kFlagValueCanBeNull>(); }
   void ClearValueCanBeNull() { SetPackedFlag<kFlagValueCanBeNull>(false); }
+  bool GetIsPredicatedSet() const { return GetPackedFlag<kFlagIsPredicatedSet>(); }
+  void SetIsPredicatedSet(bool value = true) { SetPackedFlag<kFlagIsPredicatedSet>(value); }
 
   DECLARE_INSTRUCTION(InstanceFieldSet);
 
@@ -6085,7 +6354,8 @@ class HInstanceFieldSet final : public HExpression<2> {
 
  private:
   static constexpr size_t kFlagValueCanBeNull = kNumberOfGenericPackedBits;
-  static constexpr size_t kNumberOfInstanceFieldSetPackedBits = kFlagValueCanBeNull + 1;
+  static constexpr size_t kFlagIsPredicatedSet = kFlagValueCanBeNull + 1;
+  static constexpr size_t kNumberOfInstanceFieldSetPackedBits = kFlagIsPredicatedSet + 1;
   static_assert(kNumberOfInstanceFieldSetPackedBits <= kMaxNumberOfPackedBits,
                 "Too many packed fields.");
 
@@ -7016,7 +7286,8 @@ class HStaticFieldGet final : public HExpression<1> {
     return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
   }
 
-  const FieldInfo& GetFieldInfo() const { return field_info_; }
+  bool IsFieldAccess() const override { return true; }
+  const FieldInfo& GetFieldInfo() const override { return field_info_; }
   MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
   DataType::Type GetFieldType() const { return field_info_.GetFieldType(); }
   bool IsVolatile() const { return field_info_.IsVolatile(); }
@@ -7065,7 +7336,8 @@ class HStaticFieldSet final : public HExpression<2> {
   }
 
   bool IsClonable() const override { return true; }
-  const FieldInfo& GetFieldInfo() const { return field_info_; }
+  bool IsFieldAccess() const override { return true; }
+  const FieldInfo& GetFieldInfo() const override { return field_info_; }
   MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
   DataType::Type GetFieldType() const { return field_info_.GetFieldType(); }
   bool IsVolatile() const { return field_info_.IsVolatile(); }
@@ -7984,7 +8256,7 @@ class HParallelMove final : public HExpression<0> {
         DCHECK(!destination.OverlapsWith(move.GetDestination()))
             << "Overlapped destination for two moves in a parallel move: "
             << move.GetSource() << " ==> " << move.GetDestination() << " and "
-            << source << " ==> " << destination;
+            << source << " ==> " << destination << " for " << *instruction;
       }
     }
     moves_.emplace_back(source, destination, type, instruction);