1/*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "load_store_analysis.h"
18
19namespace art {
20
21// A cap for the number of heap locations to prevent pathological time/space consumption.
22// The number of heap locations for most of the methods stays below this threshold.
23constexpr size_t kMaxNumberOfHeapLocations = 32;
24
25// Test if two integer ranges [l1,h1] and [l2,h2] overlap.
26// Note that the ranges are inclusive on both ends.
27//       l1|------|h1
28//  l2|------|h2
29static bool CanIntegerRangesOverlap(int64_t l1, int64_t h1, int64_t l2, int64_t h2) {
30  return std::max(l1, l2) <= std::min(h1, h2);
31}
32
33static bool IsAddOrSub(const HInstruction* instruction) {
34  return instruction->IsAdd() || instruction->IsSub();
35}
36
37static bool CanBinaryOpAndIndexAlias(const HBinaryOperation* idx1,
38                                     const size_t vector_length1,
39                                     const HInstruction* idx2,
40                                     const size_t vector_length2) {
41  if (!IsAddOrSub(idx1)) {
42    // We currently only support Add and Sub operations.
43    return true;
44  }
45  if (idx1->AsBinaryOperation()->GetLeastConstantLeft() != idx2) {
46    // Cannot analyze [i+CONST1] and [j].
47    return true;
48  }
49  if (!idx1->GetConstantRight()->IsIntConstant()) {
50    return true;
51  }
52
53  // Since 'i' are the same in [i+CONST] and [i],
54  // further compare [CONST] and [0].
55  int64_t l1 = idx1->IsAdd() ?
56               idx1->GetConstantRight()->AsIntConstant()->GetValue() :
57               -idx1->GetConstantRight()->AsIntConstant()->GetValue();
58  int64_t l2 = 0;
59  int64_t h1 = l1 + (vector_length1 - 1);
60  int64_t h2 = l2 + (vector_length2 - 1);
61  return CanIntegerRangesOverlap(l1, h1, l2, h2);
62}
63
64static bool CanBinaryOpsAlias(const HBinaryOperation* idx1,
65                              const size_t vector_length1,
66                              const HBinaryOperation* idx2,
67                              const size_t vector_length2) {
68  if (!IsAddOrSub(idx1) || !IsAddOrSub(idx2)) {
69    // We currently only support Add and Sub operations.
70    return true;
71  }
72  if (idx1->AsBinaryOperation()->GetLeastConstantLeft() !=
73      idx2->AsBinaryOperation()->GetLeastConstantLeft()) {
74    // Cannot analyze [i+CONST1] and [j+CONST2].
75    return true;
76  }
77  if (!idx1->GetConstantRight()->IsIntConstant() ||
78      !idx2->GetConstantRight()->IsIntConstant()) {
79    return true;
80  }
81
82  // Since 'i' are the same in [i+CONST1] and [i+CONST2],
83  // further compare [CONST1] and [CONST2].
84  int64_t l1 = idx1->IsAdd() ?
85               idx1->GetConstantRight()->AsIntConstant()->GetValue() :
86               -idx1->GetConstantRight()->AsIntConstant()->GetValue();
87  int64_t l2 = idx2->IsAdd() ?
88               idx2->GetConstantRight()->AsIntConstant()->GetValue() :
89               -idx2->GetConstantRight()->AsIntConstant()->GetValue();
90  int64_t h1 = l1 + (vector_length1 - 1);
91  int64_t h2 = l2 + (vector_length2 - 1);
92  return CanIntegerRangesOverlap(l1, h1, l2, h2);
93}
94
95bool HeapLocationCollector::CanArrayElementsAlias(const HInstruction* idx1,
96                                                  const size_t vector_length1,
97                                                  const HInstruction* idx2,
98                                                  const size_t vector_length2) const {
99  DCHECK(idx1 != nullptr);
100  DCHECK(idx2 != nullptr);
101  DCHECK_GE(vector_length1, HeapLocation::kScalar);
102  DCHECK_GE(vector_length2, HeapLocation::kScalar);
103
104  // [i] and [i].
105  if (idx1 == idx2) {
106    return true;
107  }
108
109  // [CONST1] and [CONST2].
110  if (idx1->IsIntConstant() && idx2->IsIntConstant()) {
111    int64_t l1 = idx1->AsIntConstant()->GetValue();
112    int64_t l2 = idx2->AsIntConstant()->GetValue();
113    // To avoid any overflow in following CONST+vector_length calculation,
114    // use int64_t instead of int32_t.
115    int64_t h1 = l1 + (vector_length1 - 1);
116    int64_t h2 = l2 + (vector_length2 - 1);
117    return CanIntegerRangesOverlap(l1, h1, l2, h2);
118  }
119
120  // [i+CONST] and [i].
121  if (idx1->IsBinaryOperation() &&
122      idx1->AsBinaryOperation()->GetConstantRight() != nullptr &&
123      idx1->AsBinaryOperation()->GetLeastConstantLeft() == idx2) {
124    return CanBinaryOpAndIndexAlias(idx1->AsBinaryOperation(),
125                                    vector_length1,
126                                    idx2,
127                                    vector_length2);
128  }
129
130  // [i] and [i+CONST].
131  if (idx2->IsBinaryOperation() &&
132      idx2->AsBinaryOperation()->GetConstantRight() != nullptr &&
133      idx2->AsBinaryOperation()->GetLeastConstantLeft() == idx1) {
134    return CanBinaryOpAndIndexAlias(idx2->AsBinaryOperation(),
135                                    vector_length2,
136                                    idx1,
137                                    vector_length1);
138  }
139
140  // [i+CONST1] and [i+CONST2].
141  if (idx1->IsBinaryOperation() &&
142      idx1->AsBinaryOperation()->GetConstantRight() != nullptr &&
143      idx2->IsBinaryOperation() &&
144      idx2->AsBinaryOperation()->GetConstantRight() != nullptr) {
145    return CanBinaryOpsAlias(idx1->AsBinaryOperation(),
146                             vector_length1,
147                             idx2->AsBinaryOperation(),
148                             vector_length2);
149  }
150
151  // By default, MAY alias.
152  return true;
153}
154
155void LoadStoreAnalysis::Run() {
156  for (HBasicBlock* block : graph_->GetReversePostOrder()) {
157    heap_location_collector_.VisitBasicBlock(block);
158  }
159
160  if (heap_location_collector_.GetNumberOfHeapLocations() > kMaxNumberOfHeapLocations) {
161    // Bail out if there are too many heap locations to deal with.
162    heap_location_collector_.CleanUp();
163    return;
164  }
165  if (!heap_location_collector_.HasHeapStores()) {
166    // Without heap stores, this pass would act mostly as GVN on heap accesses.
167    heap_location_collector_.CleanUp();
168    return;
169  }
170  if (heap_location_collector_.HasVolatile() || heap_location_collector_.HasMonitorOps()) {
171    // Don't do load/store elimination if the method has volatile field accesses or
172    // monitor operations, for now.
173    // TODO: do it right.
174    heap_location_collector_.CleanUp();
175    return;
176  }
177
178  heap_location_collector_.BuildAliasingMatrix();
179}
180
181}  // namespace art
182