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 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 33 static bool IsAddOrSub(const HInstruction* instruction) { 34 return instruction->IsAdd() || instruction->IsSub(); 35 } 36 37 static 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 64 static 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 95 bool 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 155 void 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
