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 
19 namespace 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.
23 constexpr 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
CanIntegerRangesOverlap(int64_t l1,int64_t h1,int64_t l2,int64_t h2)29 static 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 
CanBinaryOpAndIndexAlias(const HBinaryOperation * idx1,const size_t vector_length1,const HInstruction * idx2,const size_t vector_length2)33 static bool CanBinaryOpAndIndexAlias(const HBinaryOperation* idx1,
34                                      const size_t vector_length1,
35                                      const HInstruction* idx2,
36                                      const size_t vector_length2) {
37   if (!IsAddOrSub(idx1)) {
38     // We currently only support Add and Sub operations.
39     return true;
40   }
41   if (idx1->AsBinaryOperation()->GetLeastConstantLeft() != idx2) {
42     // Cannot analyze [i+CONST1] and [j].
43     return true;
44   }
45   if (!idx1->GetConstantRight()->IsIntConstant()) {
46     return true;
47   }
48 
49   // Since 'i' are the same in [i+CONST] and [i],
50   // further compare [CONST] and [0].
51   int64_t l1 = idx1->IsAdd() ?
52                idx1->GetConstantRight()->AsIntConstant()->GetValue() :
53                -idx1->GetConstantRight()->AsIntConstant()->GetValue();
54   int64_t l2 = 0;
55   int64_t h1 = l1 + (vector_length1 - 1);
56   int64_t h2 = l2 + (vector_length2 - 1);
57   return CanIntegerRangesOverlap(l1, h1, l2, h2);
58 }
59 
CanBinaryOpsAlias(const HBinaryOperation * idx1,const size_t vector_length1,const HBinaryOperation * idx2,const size_t vector_length2)60 static bool CanBinaryOpsAlias(const HBinaryOperation* idx1,
61                               const size_t vector_length1,
62                               const HBinaryOperation* idx2,
63                               const size_t vector_length2) {
64   if (!IsAddOrSub(idx1) || !IsAddOrSub(idx2)) {
65     // We currently only support Add and Sub operations.
66     return true;
67   }
68   if (idx1->AsBinaryOperation()->GetLeastConstantLeft() !=
69       idx2->AsBinaryOperation()->GetLeastConstantLeft()) {
70     // Cannot analyze [i+CONST1] and [j+CONST2].
71     return true;
72   }
73   if (!idx1->GetConstantRight()->IsIntConstant() ||
74       !idx2->GetConstantRight()->IsIntConstant()) {
75     return true;
76   }
77 
78   // Since 'i' are the same in [i+CONST1] and [i+CONST2],
79   // further compare [CONST1] and [CONST2].
80   int64_t l1 = idx1->IsAdd() ?
81                idx1->GetConstantRight()->AsIntConstant()->GetValue() :
82                -idx1->GetConstantRight()->AsIntConstant()->GetValue();
83   int64_t l2 = idx2->IsAdd() ?
84                idx2->GetConstantRight()->AsIntConstant()->GetValue() :
85                -idx2->GetConstantRight()->AsIntConstant()->GetValue();
86   int64_t h1 = l1 + (vector_length1 - 1);
87   int64_t h2 = l2 + (vector_length2 - 1);
88   return CanIntegerRangesOverlap(l1, h1, l2, h2);
89 }
90 
CanArrayElementsAlias(const HInstruction * idx1,const size_t vector_length1,const HInstruction * idx2,const size_t vector_length2) const91 bool HeapLocationCollector::CanArrayElementsAlias(const HInstruction* idx1,
92                                                   const size_t vector_length1,
93                                                   const HInstruction* idx2,
94                                                   const size_t vector_length2) const {
95   DCHECK(idx1 != nullptr);
96   DCHECK(idx2 != nullptr);
97   DCHECK_GE(vector_length1, HeapLocation::kScalar);
98   DCHECK_GE(vector_length2, HeapLocation::kScalar);
99 
100   // [i] and [i].
101   if (idx1 == idx2) {
102     return true;
103   }
104 
105   // [CONST1] and [CONST2].
106   if (idx1->IsIntConstant() && idx2->IsIntConstant()) {
107     int64_t l1 = idx1->AsIntConstant()->GetValue();
108     int64_t l2 = idx2->AsIntConstant()->GetValue();
109     // To avoid any overflow in following CONST+vector_length calculation,
110     // use int64_t instead of int32_t.
111     int64_t h1 = l1 + (vector_length1 - 1);
112     int64_t h2 = l2 + (vector_length2 - 1);
113     return CanIntegerRangesOverlap(l1, h1, l2, h2);
114   }
115 
116   // [i+CONST] and [i].
117   if (idx1->IsBinaryOperation() &&
118       idx1->AsBinaryOperation()->GetConstantRight() != nullptr &&
119       idx1->AsBinaryOperation()->GetLeastConstantLeft() == idx2) {
120     return CanBinaryOpAndIndexAlias(idx1->AsBinaryOperation(),
121                                     vector_length1,
122                                     idx2,
123                                     vector_length2);
124   }
125 
126   // [i] and [i+CONST].
127   if (idx2->IsBinaryOperation() &&
128       idx2->AsBinaryOperation()->GetConstantRight() != nullptr &&
129       idx2->AsBinaryOperation()->GetLeastConstantLeft() == idx1) {
130     return CanBinaryOpAndIndexAlias(idx2->AsBinaryOperation(),
131                                     vector_length2,
132                                     idx1,
133                                     vector_length1);
134   }
135 
136   // [i+CONST1] and [i+CONST2].
137   if (idx1->IsBinaryOperation() &&
138       idx1->AsBinaryOperation()->GetConstantRight() != nullptr &&
139       idx2->IsBinaryOperation() &&
140       idx2->AsBinaryOperation()->GetConstantRight() != nullptr) {
141     return CanBinaryOpsAlias(idx1->AsBinaryOperation(),
142                              vector_length1,
143                              idx2->AsBinaryOperation(),
144                              vector_length2);
145   }
146 
147   // By default, MAY alias.
148   return true;
149 }
150 
Run()151 bool LoadStoreAnalysis::Run() {
152   for (HBasicBlock* block : graph_->GetReversePostOrder()) {
153     heap_location_collector_.VisitBasicBlock(block);
154   }
155 
156   if (heap_location_collector_.GetNumberOfHeapLocations() > kMaxNumberOfHeapLocations) {
157     // Bail out if there are too many heap locations to deal with.
158     heap_location_collector_.CleanUp();
159     return false;
160   }
161   if (!heap_location_collector_.HasHeapStores()) {
162     // Without heap stores, this pass would act mostly as GVN on heap accesses.
163     heap_location_collector_.CleanUp();
164     return false;
165   }
166   if (heap_location_collector_.HasVolatile() || heap_location_collector_.HasMonitorOps()) {
167     // Don't do load/store elimination if the method has volatile field accesses or
168     // monitor operations, for now.
169     // TODO: do it right.
170     heap_location_collector_.CleanUp();
171     return false;
172   }
173 
174   heap_location_collector_.BuildAliasingMatrix();
175   return true;
176 }
177 
178 }  // namespace art
179