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 #include "base/scoped_arena_allocator.h"
20 #include "optimizing/escape.h"
21 
22 namespace art HIDDEN {
23 
24 // A cap for the number of heap locations to prevent pathological time/space consumption.
25 // The number of heap locations for most of the methods stays below this threshold.
26 constexpr size_t kMaxNumberOfHeapLocations = 32;
27 
28 // Test if two integer ranges [l1,h1] and [l2,h2] overlap.
29 // Note that the ranges are inclusive on both ends.
30 //       l1|------|h1
31 //  l2|------|h2
CanIntegerRangesOverlap(int64_t l1,int64_t h1,int64_t l2,int64_t h2)32 static bool CanIntegerRangesOverlap(int64_t l1, int64_t h1, int64_t l2, int64_t h2) {
33   return std::max(l1, l2) <= std::min(h1, h2);
34 }
35 
CanBinaryOpAndIndexAlias(const HBinaryOperation * idx1,const size_t vector_length1,const HInstruction * idx2,const size_t vector_length2)36 static bool CanBinaryOpAndIndexAlias(const HBinaryOperation* idx1,
37                                      const size_t vector_length1,
38                                      const HInstruction* idx2,
39                                      const size_t vector_length2) {
40   if (!IsAddOrSub(idx1)) {
41     // We currently only support Add and Sub operations.
42     return true;
43   }
44   if (idx1->GetLeastConstantLeft() != idx2) {
45     // Cannot analyze [i+CONST1] and [j].
46     return true;
47   }
48   if (!idx1->GetConstantRight()->IsIntConstant()) {
49     return true;
50   }
51 
52   // Since 'i' are the same in [i+CONST] and [i],
53   // further compare [CONST] and [0].
54   int64_t l1 = idx1->IsAdd()
55       ? idx1->GetConstantRight()->AsIntConstant()->GetValue()
56       : -idx1->GetConstantRight()->AsIntConstant()->GetValue();
57   int64_t l2 = 0;
58   int64_t h1 = l1 + (vector_length1 - 1);
59   int64_t h2 = l2 + (vector_length2 - 1);
60   return CanIntegerRangesOverlap(l1, h1, l2, h2);
61 }
62 
CanBinaryOpsAlias(const HBinaryOperation * idx1,const size_t vector_length1,const HBinaryOperation * idx2,const size_t vector_length2)63 static bool CanBinaryOpsAlias(const HBinaryOperation* idx1,
64                               const size_t vector_length1,
65                               const HBinaryOperation* idx2,
66                               const size_t vector_length2) {
67   if (!IsAddOrSub(idx1) || !IsAddOrSub(idx2)) {
68     // We currently only support Add and Sub operations.
69     return true;
70   }
71   if (idx1->GetLeastConstantLeft() != idx2->GetLeastConstantLeft()) {
72     // Cannot analyze [i+CONST1] and [j+CONST2].
73     return true;
74   }
75   if (!idx1->GetConstantRight()->IsIntConstant() ||
76       !idx2->GetConstantRight()->IsIntConstant()) {
77     return true;
78   }
79 
80   // Since 'i' are the same in [i+CONST1] and [i+CONST2],
81   // further compare [CONST1] and [CONST2].
82   int64_t l1 = idx1->IsAdd()
83       ? idx1->GetConstantRight()->AsIntConstant()->GetValue()
84       : -idx1->GetConstantRight()->AsIntConstant()->GetValue();
85   int64_t l2 = idx2->IsAdd()
86       ? idx2->GetConstantRight()->AsIntConstant()->GetValue()
87       : -idx2->GetConstantRight()->AsIntConstant()->GetValue();
88   int64_t h1 = l1 + (vector_length1 - 1);
89   int64_t h2 = l2 + (vector_length2 - 1);
90   return CanIntegerRangesOverlap(l1, h1, l2, h2);
91 }
92 
InstructionEligibleForLSERemoval(HInstruction * inst) const93 bool HeapLocationCollector::InstructionEligibleForLSERemoval(HInstruction* inst) const {
94   if (inst->IsNewInstance()) {
95     return !inst->AsNewInstance()->NeedsChecks();
96   } else if (inst->IsNewArray()) {
97     HInstruction* array_length = inst->AsNewArray()->GetLength();
98     bool known_array_length =
99         array_length->IsIntConstant() && array_length->AsIntConstant()->GetValue() >= 0;
100     return known_array_length &&
101            std::all_of(inst->GetUses().cbegin(),
102                        inst->GetUses().cend(),
103                        [&](const HUseListNode<HInstruction*>& user) {
104                          if (user.GetUser()->IsArrayGet() || user.GetUser()->IsArraySet()) {
105                            return user.GetUser()->InputAt(1)->IsIntConstant();
106                          }
107                          return true;
108                        });
109   } else {
110     return false;
111   }
112 }
113 
DumpReferenceStats(OptimizingCompilerStats * stats)114 void HeapLocationCollector::DumpReferenceStats(OptimizingCompilerStats* stats) {
115   if (stats == nullptr) {
116     return;
117   }
118   std::vector<bool> seen_instructions(GetGraph()->GetCurrentInstructionId(), false);
119   for (auto hl : heap_locations_) {
120     auto ri = hl->GetReferenceInfo();
121     if (ri == nullptr || seen_instructions[ri->GetReference()->GetId()]) {
122       continue;
123     }
124     auto instruction = ri->GetReference();
125     seen_instructions[instruction->GetId()] = true;
126     if (ri->IsSingletonAndRemovable()) {
127       if (InstructionEligibleForLSERemoval(instruction)) {
128         MaybeRecordStat(stats, MethodCompilationStat::kFullLSEPossible);
129       }
130     }
131   }
132 }
133 
CanArrayElementsAlias(const HInstruction * idx1,const size_t vector_length1,const HInstruction * idx2,const size_t vector_length2) const134 bool HeapLocationCollector::CanArrayElementsAlias(const HInstruction* idx1,
135                                                   const size_t vector_length1,
136                                                   const HInstruction* idx2,
137                                                   const size_t vector_length2) const {
138   DCHECK(idx1 != nullptr);
139   DCHECK(idx2 != nullptr);
140   DCHECK_GE(vector_length1, HeapLocation::kScalar);
141   DCHECK_GE(vector_length2, HeapLocation::kScalar);
142 
143   // [i] and [i].
144   if (idx1 == idx2) {
145     return true;
146   }
147 
148   // [CONST1] and [CONST2].
149   if (idx1->IsIntConstant() && idx2->IsIntConstant()) {
150     int64_t l1 = idx1->AsIntConstant()->GetValue();
151     int64_t l2 = idx2->AsIntConstant()->GetValue();
152     // To avoid any overflow in following CONST+vector_length calculation,
153     // use int64_t instead of int32_t.
154     int64_t h1 = l1 + (vector_length1 - 1);
155     int64_t h2 = l2 + (vector_length2 - 1);
156     return CanIntegerRangesOverlap(l1, h1, l2, h2);
157   }
158 
159   // [i+CONST] and [i].
160   if (idx1->IsBinaryOperation() &&
161       idx1->AsBinaryOperation()->GetConstantRight() != nullptr &&
162       idx1->AsBinaryOperation()->GetLeastConstantLeft() == idx2) {
163     return CanBinaryOpAndIndexAlias(idx1->AsBinaryOperation(),
164                                     vector_length1,
165                                     idx2,
166                                     vector_length2);
167   }
168 
169   // [i] and [i+CONST].
170   if (idx2->IsBinaryOperation() &&
171       idx2->AsBinaryOperation()->GetConstantRight() != nullptr &&
172       idx2->AsBinaryOperation()->GetLeastConstantLeft() == idx1) {
173     return CanBinaryOpAndIndexAlias(idx2->AsBinaryOperation(),
174                                     vector_length2,
175                                     idx1,
176                                     vector_length1);
177   }
178 
179   // [i+CONST1] and [i+CONST2].
180   if (idx1->IsBinaryOperation() &&
181       idx1->AsBinaryOperation()->GetConstantRight() != nullptr &&
182       idx2->IsBinaryOperation() &&
183       idx2->AsBinaryOperation()->GetConstantRight() != nullptr) {
184     return CanBinaryOpsAlias(idx1->AsBinaryOperation(),
185                              vector_length1,
186                              idx2->AsBinaryOperation(),
187                              vector_length2);
188   }
189 
190   // By default, MAY alias.
191   return true;
192 }
193 
Run()194 bool LoadStoreAnalysis::Run() {
195   // Currently load_store analysis can't handle predicated load/stores; specifically pairs of
196   // memory operations with different predicates.
197   // TODO: support predicated SIMD.
198   if (graph_->HasPredicatedSIMD()) {
199     return false;
200   }
201 
202   for (HBasicBlock* block : graph_->GetReversePostOrder()) {
203     heap_location_collector_.VisitBasicBlock(block);
204   }
205 
206   if (heap_location_collector_.GetNumberOfHeapLocations() > kMaxNumberOfHeapLocations) {
207     // Bail out if there are too many heap locations to deal with.
208     heap_location_collector_.CleanUp();
209     return false;
210   }
211   if (!heap_location_collector_.HasHeapStores()) {
212     // Without heap stores, this pass would act mostly as GVN on heap accesses.
213     heap_location_collector_.CleanUp();
214     return false;
215   }
216   heap_location_collector_.BuildAliasingMatrix();
217   heap_location_collector_.DumpReferenceStats(stats_);
218   return true;
219 }
220 
221 }  // namespace art
222