buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2011 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 | |
buzbee | efc6369 | 2012-11-14 16:31:52 -0800 | [diff] [blame] | 17 | #include "compiler_internals.h" |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 18 | |
Elliott Hughes | 11d1b0c | 2012-01-23 16:57:47 -0800 | [diff] [blame] | 19 | namespace art { |
| 20 | |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 21 | const char* extendedMIROpNames[kMirOpLast - kMirOpFirst] = { |
| 22 | "kMirOpPhi", |
| 23 | "kMirOpCopy", |
| 24 | "kMirFusedCmplFloat", |
| 25 | "kMirFusedCmpgFloat", |
| 26 | "kMirFusedCmplDouble", |
| 27 | "kMirFusedCmpgDouble", |
| 28 | "kMirFusedCmpLong", |
| 29 | "kMirNop", |
| 30 | "kMirOpNullCheck", |
| 31 | "kMirOpRangeCheck", |
| 32 | "kMirOpDivZeroCheck", |
| 33 | "kMirOpCheck", |
| 34 | }; |
| 35 | |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 36 | #ifdef WITH_MEMSTATS |
Elliott Hughes | 719ace4 | 2012-03-09 18:06:03 -0800 | [diff] [blame] | 37 | struct Memstats { |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 38 | uint32_t allocStats[kNumAllocKinds]; |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 39 | int listSizes[kNumListKinds]; |
| 40 | int listWasted[kNumListKinds]; |
| 41 | int listGrows[kNumListKinds]; |
| 42 | int listMaxElems[kNumListKinds]; |
| 43 | int bitMapSizes[kNumBitMapKinds]; |
| 44 | int bitMapWasted[kNumBitMapKinds]; |
| 45 | int bitMapGrows[kNumBitMapKinds]; |
Elliott Hughes | 719ace4 | 2012-03-09 18:06:03 -0800 | [diff] [blame] | 46 | }; |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 47 | |
| 48 | const char* allocNames[kNumAllocKinds] = { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 49 | "Misc ", |
| 50 | "BasicBlock ", |
| 51 | "LIR ", |
| 52 | "MIR ", |
| 53 | "DataFlow ", |
| 54 | "GrowList ", |
| 55 | "GrowBitMap ", |
| 56 | "Dalvik2SSA ", |
| 57 | "DebugInfo ", |
| 58 | "Successor ", |
| 59 | "RegAlloc ", |
| 60 | "Data ", |
| 61 | "Preds ", |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 62 | }; |
| 63 | |
| 64 | const char* listNames[kNumListKinds] = { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 65 | "Misc ", |
| 66 | "blockList ", |
| 67 | "SSAtoDalvik ", |
| 68 | "dfsOrder ", |
| 69 | "dfsPostOrder ", |
| 70 | "domPostOrderTraversal ", |
| 71 | "throwLaunchPads ", |
| 72 | "suspendLaunchPads ", |
| 73 | "switchTables ", |
| 74 | "fillArrayData ", |
| 75 | "SuccessorBlocks ", |
| 76 | "Predecessors ", |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 77 | }; |
| 78 | |
| 79 | const char* bitMapNames[kNumBitMapKinds] = { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 80 | "Misc ", |
| 81 | "Use ", |
| 82 | "Def ", |
| 83 | "LiveIn ", |
| 84 | "BlockMatrix ", |
| 85 | "Dominators ", |
| 86 | "IDominated ", |
| 87 | "DomFrontier ", |
| 88 | "Phi ", |
| 89 | "TmpBlocks ", |
| 90 | "InputBlocks ", |
| 91 | "RegisterV ", |
| 92 | "TempSSARegisterV ", |
| 93 | "Null Check ", |
| 94 | "TmpBlockV ", |
| 95 | "Predecessors ", |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 96 | }; |
| 97 | #endif |
| 98 | |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 99 | #define kArenaBitVectorGrowth 4 /* increase by 4 uint32_ts when limit hit */ |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 100 | |
| 101 | /* Allocate the initial memory block for arena-based allocation */ |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 102 | bool oatHeapInit(CompilationUnit* cUnit) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 103 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 104 | DCHECK(cUnit->arenaHead == NULL); |
| 105 | cUnit->arenaHead = |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 106 | static_cast<ArenaMemBlock*>(malloc(sizeof(ArenaMemBlock) + ARENA_DEFAULT_SIZE)); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 107 | if (cUnit->arenaHead == NULL) { |
| 108 | LOG(FATAL) << "No memory left to create compiler heap memory"; |
| 109 | } |
| 110 | cUnit->arenaHead->blockSize = ARENA_DEFAULT_SIZE; |
| 111 | cUnit->currentArena = cUnit->arenaHead; |
| 112 | cUnit->currentArena->bytesAllocated = 0; |
| 113 | cUnit->currentArena->next = NULL; |
| 114 | cUnit->numArenaBlocks = 1; |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 115 | #ifdef WITH_MEMSTATS |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 116 | cUnit->mstats = (Memstats*) oatNew(cUnit, sizeof(Memstats), true, |
| 117 | kAllocDebugInfo); |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 118 | #endif |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 119 | return true; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 120 | } |
| 121 | |
| 122 | /* Arena-based malloc for compilation tasks */ |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 123 | void* oatNew(CompilationUnit* cUnit, size_t size, bool zero, oatAllocKind kind) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 124 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 125 | size = (size + 3) & ~3; |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 126 | #ifdef WITH_MEMSTATS |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 127 | if (cUnit->mstats != NULL) { |
| 128 | cUnit->mstats->allocStats[kind] += size; |
| 129 | } |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 130 | #endif |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 131 | retry: |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 132 | /* Normal case - space is available in the current page */ |
| 133 | if (size + cUnit->currentArena->bytesAllocated <= |
| 134 | cUnit->currentArena->blockSize) { |
| 135 | void *ptr; |
| 136 | ptr = &cUnit->currentArena->ptr[cUnit->currentArena->bytesAllocated]; |
| 137 | cUnit->currentArena->bytesAllocated += size; |
| 138 | if (zero) { |
| 139 | memset(ptr, 0, size); |
| 140 | } |
| 141 | return ptr; |
| 142 | } else { |
| 143 | /* |
| 144 | * See if there are previously allocated arena blocks before the last |
| 145 | * reset |
| 146 | */ |
| 147 | if (cUnit->currentArena->next) { |
| 148 | cUnit->currentArena = cUnit->currentArena->next; |
| 149 | cUnit->currentArena->bytesAllocated = 0; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 150 | goto retry; |
| 151 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 152 | |
| 153 | size_t blockSize = (size < ARENA_DEFAULT_SIZE) ? ARENA_DEFAULT_SIZE : size; |
| 154 | /* Time to allocate a new arena */ |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 155 | ArenaMemBlock *newArena = |
| 156 | static_cast<ArenaMemBlock*>(malloc(sizeof(ArenaMemBlock) + blockSize)); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 157 | if (newArena == NULL) { |
| 158 | LOG(FATAL) << "Arena allocation failure"; |
| 159 | } |
| 160 | newArena->blockSize = blockSize; |
| 161 | newArena->bytesAllocated = 0; |
| 162 | newArena->next = NULL; |
| 163 | cUnit->currentArena->next = newArena; |
| 164 | cUnit->currentArena = newArena; |
| 165 | cUnit->numArenaBlocks++; |
| 166 | if (cUnit->numArenaBlocks > 20000) { |
| 167 | LOG(INFO) << "Total arena pages: " << cUnit->numArenaBlocks; |
| 168 | } |
| 169 | goto retry; |
| 170 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 171 | } |
| 172 | |
| 173 | /* Reclaim all the arena blocks allocated so far */ |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 174 | void oatArenaReset(CompilationUnit* cUnit) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 175 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 176 | ArenaMemBlock* head = cUnit->arenaHead; |
| 177 | while (head != NULL) { |
| 178 | ArenaMemBlock* p = head; |
| 179 | head = head->next; |
| 180 | free(p); |
| 181 | } |
| 182 | cUnit->arenaHead = NULL; |
| 183 | cUnit->currentArena = NULL; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 184 | } |
| 185 | |
| 186 | /* Growable List initialization */ |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 187 | void oatInitGrowableList(CompilationUnit* cUnit, GrowableList* gList, |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 188 | size_t initLength, oatListKind kind) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 189 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 190 | gList->numAllocated = initLength; |
| 191 | gList->numUsed = 0; |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 192 | gList->elemList = static_cast<uintptr_t *>(oatNew(cUnit, sizeof(intptr_t) * initLength, |
| 193 | true, kAllocGrowableList)); |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 194 | #ifdef WITH_MEMSTATS |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 195 | cUnit->mstats->listSizes[kind] += sizeof(uintptr_t) * initLength; |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 196 | gList->kind = kind; |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 197 | if (static_cast<int>(initLength) > cUnit->mstats->listMaxElems[kind]) { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 198 | cUnit->mstats->listMaxElems[kind] = initLength; |
| 199 | } |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 200 | #endif |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 201 | } |
| 202 | |
| 203 | /* Expand the capacity of a growable list */ |
buzbee | 31a4a6f | 2012-02-28 15:36:15 -0800 | [diff] [blame] | 204 | void expandGrowableList(CompilationUnit* cUnit, GrowableList* gList) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 205 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 206 | int newLength = gList->numAllocated; |
| 207 | if (newLength < 128) { |
| 208 | newLength <<= 1; |
| 209 | } else { |
| 210 | newLength += 128; |
| 211 | } |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 212 | uintptr_t *newArray = |
| 213 | static_cast<uintptr_t*>(oatNew(cUnit, sizeof(uintptr_t) * newLength, true, |
| 214 | kAllocGrowableList)); |
| 215 | memcpy(newArray, gList->elemList, sizeof(uintptr_t) * gList->numAllocated); |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 216 | #ifdef WITH_MEMSTATS |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 217 | cUnit->mstats->listSizes[gList->kind] += sizeof(uintptr_t) * newLength; |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 218 | cUnit->mstats->listWasted[gList->kind] += |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 219 | sizeof(uintptr_t) * gList->numAllocated; |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 220 | cUnit->mstats->listGrows[gList->kind]++; |
| 221 | if (newLength > cUnit->mstats->listMaxElems[gList->kind]) { |
| 222 | cUnit->mstats->listMaxElems[gList->kind] = newLength; |
| 223 | } |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 224 | #endif |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 225 | gList->numAllocated = newLength; |
| 226 | gList->elemList = newArray; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 227 | } |
| 228 | |
| 229 | /* Insert a new element into the growable list */ |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 230 | void oatInsertGrowableList(CompilationUnit* cUnit, GrowableList* gList, |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 231 | uintptr_t elem) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 232 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 233 | DCHECK_NE(gList->numAllocated, 0U); |
| 234 | if (gList->numUsed == gList->numAllocated) { |
| 235 | expandGrowableList(cUnit, gList); |
| 236 | } |
| 237 | gList->elemList[gList->numUsed++] = elem; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 238 | } |
| 239 | |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 240 | /* Delete an element from a growable list. Element must be present */ |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 241 | void oatDeleteGrowableList(GrowableList* gList, uintptr_t elem) |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 242 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 243 | bool found = false; |
| 244 | for (unsigned int i = 0; i < gList->numUsed; i++) { |
| 245 | if (!found && gList->elemList[i] == elem) { |
| 246 | found = true; |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 247 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 248 | if (found) { |
| 249 | gList->elemList[i] = gList->elemList[i+1]; |
| 250 | } |
| 251 | } |
| 252 | DCHECK_EQ(found, true); |
| 253 | gList->numUsed--; |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 254 | } |
| 255 | |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 256 | void oatGrowableListIteratorInit(GrowableList* gList, |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 257 | GrowableListIterator* iterator) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 258 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 259 | iterator->list = gList; |
| 260 | iterator->idx = 0; |
| 261 | iterator->size = gList->numUsed; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 262 | } |
| 263 | |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 264 | uintptr_t oatGrowableListIteratorNext(GrowableListIterator* iterator) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 265 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 266 | DCHECK_EQ(iterator->size, iterator->list->numUsed); |
| 267 | if (iterator->idx == iterator->size) return 0; |
| 268 | return iterator->list->elemList[iterator->idx++]; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 269 | } |
| 270 | |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 271 | uintptr_t oatGrowableListGetElement(const GrowableList* gList, size_t idx) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 272 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 273 | DCHECK_LT(idx, gList->numUsed); |
| 274 | return gList->elemList[idx]; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 275 | } |
| 276 | |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 277 | #ifdef WITH_MEMSTATS |
| 278 | /* Dump memory usage stats */ |
| 279 | void oatDumpMemStats(CompilationUnit* cUnit) |
| 280 | { |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 281 | uint32_t total = 0; |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 282 | for (int i = 0; i < kNumAllocKinds; i++) { |
| 283 | total += cUnit->mstats->allocStats[i]; |
| 284 | } |
| 285 | if (total > (10 * 1024 * 1024)) { |
| 286 | LOG(INFO) << "MEMUSAGE: " << total << " : " |
| 287 | << PrettyMethod(cUnit->method_idx, *cUnit->dex_file); |
| 288 | LOG(INFO) << "insnsSize: " << cUnit->insnsSize; |
| 289 | if (cUnit->disableDataflow) { |
| 290 | LOG(INFO) << " ** Dataflow disabled ** "; |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 291 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 292 | LOG(INFO) << "===== Overall allocations"; |
| 293 | for (int i = 0; i < kNumAllocKinds; i++) { |
| 294 | LOG(INFO) << allocNames[i] << std::setw(10) << |
| 295 | cUnit->mstats->allocStats[i]; |
| 296 | } |
| 297 | LOG(INFO) << "===== GrowableList allocations"; |
| 298 | for (int i = 0; i < kNumListKinds; i++) { |
| 299 | LOG(INFO) << listNames[i] |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 300 | << " S:" << cUnit->mstats->listSizes[i] |
| 301 | << ", W:" << cUnit->mstats->listWasted[i] |
| 302 | << ", G:" << cUnit->mstats->listGrows[i] |
| 303 | << ", E:" << cUnit->mstats->listMaxElems[i]; |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 304 | } |
| 305 | LOG(INFO) << "===== GrowableBitMap allocations"; |
| 306 | for (int i = 0; i < kNumBitMapKinds; i++) { |
| 307 | LOG(INFO) << bitMapNames[i] |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 308 | << " S:" << cUnit->mstats->bitMapSizes[i] |
| 309 | << ", W:" << cUnit->mstats->bitMapWasted[i] |
| 310 | << ", G:" << cUnit->mstats->bitMapGrows[i]; |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 311 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 312 | } |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 313 | } |
| 314 | #endif |
| 315 | |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 316 | /* Debug Utility - dump a compilation unit */ |
| 317 | void oatDumpCompilationUnit(CompilationUnit* cUnit) |
| 318 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 319 | BasicBlock* bb; |
| 320 | const char* blockTypeNames[] = { |
| 321 | "Entry Block", |
| 322 | "Code Block", |
| 323 | "Exit Block", |
| 324 | "Exception Handling", |
| 325 | "Catch Block" |
| 326 | }; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 327 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 328 | LOG(INFO) << "Compiling " << PrettyMethod(cUnit->method_idx, *cUnit->dex_file); |
| 329 | LOG(INFO) << cUnit->insns << " insns"; |
| 330 | LOG(INFO) << cUnit->numBlocks << " blocks in total"; |
| 331 | GrowableListIterator iterator; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 332 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 333 | oatGrowableListIteratorInit(&cUnit->blockList, &iterator); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 334 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 335 | while (true) { |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 336 | bb = reinterpret_cast<BasicBlock*>(oatGrowableListIteratorNext(&iterator)); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 337 | if (bb == NULL) break; |
| 338 | LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", |
| 339 | bb->id, |
| 340 | blockTypeNames[bb->blockType], |
| 341 | bb->startOffset, |
| 342 | bb->lastMIRInsn ? bb->lastMIRInsn->offset : bb->startOffset, |
| 343 | bb->lastMIRInsn ? "" : " empty"); |
| 344 | if (bb->taken) { |
| 345 | LOG(INFO) << " Taken branch: block " << bb->taken->id |
| 346 | << "(0x" << std::hex << bb->taken->startOffset << ")"; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 347 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 348 | if (bb->fallThrough) { |
| 349 | LOG(INFO) << " Fallthrough : block " << bb->fallThrough->id |
| 350 | << " (0x" << std::hex << bb->fallThrough->startOffset << ")"; |
| 351 | } |
| 352 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 353 | } |
| 354 | |
buzbee | 67bc236 | 2011-10-11 18:08:40 -0700 | [diff] [blame] | 355 | static uint32_t checkMasks[32] = { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 356 | 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, |
| 357 | 0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200, |
| 358 | 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, |
| 359 | 0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, |
| 360 | 0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000, |
| 361 | 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, |
| 362 | 0x40000000, 0x80000000 }; |
buzbee | 67bc236 | 2011-10-11 18:08:40 -0700 | [diff] [blame] | 363 | |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 364 | /* |
| 365 | * Allocate a bit vector with enough space to hold at least the specified |
| 366 | * number of bits. |
| 367 | * |
| 368 | * NOTE: memory is allocated from the compiler arena. |
| 369 | */ |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 370 | ArenaBitVector* oatAllocBitVector(CompilationUnit* cUnit, |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 371 | unsigned int startBits, bool expandable, |
| 372 | oatBitMapKind kind) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 373 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 374 | ArenaBitVector* bv; |
| 375 | unsigned int count; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 376 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 377 | DCHECK_EQ(sizeof(bv->storage[0]), 4U); /* assuming 32-bit units */ |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 378 | |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 379 | bv = static_cast<ArenaBitVector*>(oatNew(cUnit, sizeof(ArenaBitVector), false, |
| 380 | kAllocGrowableBitMap)); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 381 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 382 | count = (startBits + 31) >> 5; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 383 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 384 | bv->storageSize = count; |
| 385 | bv->expandable = expandable; |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 386 | bv->storage = static_cast<uint32_t*>(oatNew(cUnit, count * sizeof(uint32_t), true, |
| 387 | kAllocGrowableBitMap)); |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 388 | #ifdef WITH_MEMSTATS |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 389 | bv->kind = kind; |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 390 | cUnit->mstats->bitMapSizes[kind] += count * sizeof(uint32_t); |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 391 | #endif |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 392 | return bv; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 393 | } |
| 394 | |
| 395 | /* |
| 396 | * Determine whether or not the specified bit is set. |
| 397 | */ |
| 398 | bool oatIsBitSet(const ArenaBitVector* pBits, unsigned int num) |
| 399 | { |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 400 | DCHECK_LT(num, pBits->storageSize * sizeof(uint32_t) * 8); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 401 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 402 | unsigned int val = pBits->storage[num >> 5] & checkMasks[num & 0x1f]; |
| 403 | return (val != 0); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 404 | } |
| 405 | |
| 406 | /* |
| 407 | * Mark all bits bit as "clear". |
| 408 | */ |
| 409 | void oatClearAllBits(ArenaBitVector* pBits) |
| 410 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 411 | unsigned int count = pBits->storageSize; |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 412 | memset(pBits->storage, 0, count * sizeof(uint32_t)); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 413 | } |
| 414 | |
| 415 | /* |
| 416 | * Mark the specified bit as "set". |
| 417 | * |
| 418 | * Returns "false" if the bit is outside the range of the vector and we're |
| 419 | * not allowed to expand. |
| 420 | * |
| 421 | * NOTE: memory is allocated from the compiler arena. |
| 422 | */ |
buzbee | ba938cb | 2012-02-03 14:47:55 -0800 | [diff] [blame] | 423 | bool oatSetBit(CompilationUnit* cUnit, ArenaBitVector* pBits, unsigned int num) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 424 | { |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 425 | if (num >= pBits->storageSize * sizeof(uint32_t) * 8) { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 426 | if (!pBits->expandable) { |
| 427 | LOG(FATAL) << "Can't expand"; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 428 | } |
| 429 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 430 | /* Round up to word boundaries for "num+1" bits */ |
| 431 | unsigned int newSize = (num + 1 + 31) >> 5; |
| 432 | DCHECK_GT(newSize, pBits->storageSize); |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 433 | uint32_t *newStorage = static_cast<uint32_t*>(oatNew(cUnit, newSize * sizeof(uint32_t), false, |
| 434 | kAllocGrowableBitMap)); |
| 435 | memcpy(newStorage, pBits->storage, pBits->storageSize * sizeof(uint32_t)); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 436 | memset(&newStorage[pBits->storageSize], 0, |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 437 | (newSize - pBits->storageSize) * sizeof(uint32_t)); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 438 | #ifdef WITH_MEMSTATS |
| 439 | cUnit->mstats->bitMapWasted[pBits->kind] += |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 440 | pBits->storageSize * sizeof(uint32_t); |
| 441 | cUnit->mstats->bitMapSizes[pBits->kind] += newSize * sizeof(uint32_t); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 442 | cUnit->mstats->bitMapGrows[pBits->kind]++; |
| 443 | #endif |
| 444 | pBits->storage = newStorage; |
| 445 | pBits->storageSize = newSize; |
| 446 | } |
| 447 | |
| 448 | pBits->storage[num >> 5] |= checkMasks[num & 0x1f]; |
| 449 | return true; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 450 | } |
| 451 | |
| 452 | /* |
| 453 | * Mark the specified bit as "unset". |
| 454 | * |
| 455 | * Returns "false" if the bit is outside the range of the vector and we're |
| 456 | * not allowed to expand. |
| 457 | * |
| 458 | * NOTE: memory is allocated from the compiler arena. |
| 459 | */ |
| 460 | bool oatClearBit(ArenaBitVector* pBits, unsigned int num) |
| 461 | { |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 462 | if (num >= pBits->storageSize * sizeof(uint32_t) * 8) { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 463 | LOG(FATAL) << "Attempt to clear a bit not set in the vector yet";; |
| 464 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 465 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 466 | pBits->storage[num >> 5] &= ~checkMasks[num & 0x1f]; |
| 467 | return true; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 468 | } |
| 469 | |
| 470 | /* |
| 471 | * If set is true, mark all bits as 1. Otherwise mark all bits as 0. |
| 472 | */ |
| 473 | void oatMarkAllBits(ArenaBitVector* pBits, bool set) |
| 474 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 475 | int value = set ? -1 : 0; |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 476 | memset(pBits->storage, value, pBits->storageSize * static_cast<int>(sizeof(uint32_t))); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 477 | } |
| 478 | |
| 479 | void oatDebugBitVector(char* msg, const ArenaBitVector* bv, int length) |
| 480 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 481 | int i; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 482 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 483 | LOG(INFO) << msg; |
| 484 | for (i = 0; i < length; i++) { |
| 485 | if (oatIsBitSet(bv, i)) { |
| 486 | LOG(INFO) << " Bit " << i << " is set"; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 487 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 488 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 489 | } |
| 490 | |
| 491 | void oatAbort(CompilationUnit* cUnit) |
| 492 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 493 | LOG(FATAL) << "Compiler aborting"; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 494 | } |
| 495 | |
| 496 | void oatDumpBlockBitVector(const GrowableList* blocks, char* msg, |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 497 | const ArenaBitVector* bv, int length) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 498 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 499 | int i; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 500 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 501 | LOG(INFO) << msg; |
| 502 | for (i = 0; i < length; i++) { |
| 503 | if (oatIsBitSet(bv, i)) { |
buzbee | cbd6d44 | 2012-11-17 14:11:25 -0800 | [diff] [blame^] | 504 | BasicBlock *bb = reinterpret_cast<BasicBlock*>(oatGrowableListGetElement(blocks, i)); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 505 | char blockName[BLOCK_NAME_LEN]; |
| 506 | oatGetBlockName(bb, blockName); |
| 507 | LOG(INFO) << "Bit " << i << " / " << blockName << " is set"; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 508 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 509 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 510 | } |
| 511 | /* Initialize the iterator structure */ |
| 512 | void oatBitVectorIteratorInit(ArenaBitVector* pBits, |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 513 | ArenaBitVectorIterator* iterator) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 514 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 515 | iterator->pBits = pBits; |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 516 | iterator->bitSize = pBits->storageSize * sizeof(uint32_t) * 8; |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 517 | iterator->idx = 0; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 518 | } |
| 519 | |
| 520 | /* |
| 521 | * If the vector sizes don't match, log an error and abort. |
| 522 | */ |
buzbee | 31a4a6f | 2012-02-28 15:36:15 -0800 | [diff] [blame] | 523 | void checkSizes(const ArenaBitVector* bv1, const ArenaBitVector* bv2) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 524 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 525 | if (bv1->storageSize != bv2->storageSize) { |
| 526 | LOG(FATAL) << "Mismatched vector sizes (" << bv1->storageSize |
| 527 | << ", " << bv2->storageSize << ")"; |
| 528 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 529 | } |
| 530 | |
| 531 | /* |
| 532 | * Copy a whole vector to the other. Only do that when the both vectors have |
| 533 | * the same size. |
| 534 | */ |
| 535 | void oatCopyBitVector(ArenaBitVector* dest, const ArenaBitVector* src) |
| 536 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 537 | /* if dest is expandable and < src, we could expand dest to match */ |
| 538 | checkSizes(dest, src); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 539 | |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 540 | memcpy(dest->storage, src->storage, sizeof(uint32_t) * dest->storageSize); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 541 | } |
| 542 | |
| 543 | /* |
| 544 | * Intersect two bit vectors and store the result to the dest vector. |
| 545 | */ |
| 546 | |
| 547 | bool oatIntersectBitVectors(ArenaBitVector* dest, const ArenaBitVector* src1, |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 548 | const ArenaBitVector* src2) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 549 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 550 | DCHECK(src1 != NULL); |
| 551 | DCHECK(src2 != NULL); |
| 552 | if (dest->storageSize != src1->storageSize || |
| 553 | dest->storageSize != src2->storageSize || |
| 554 | dest->expandable != src1->expandable || |
| 555 | dest->expandable != src2->expandable) |
| 556 | return false; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 557 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 558 | unsigned int idx; |
| 559 | for (idx = 0; idx < dest->storageSize; idx++) { |
| 560 | dest->storage[idx] = src1->storage[idx] & src2->storage[idx]; |
| 561 | } |
| 562 | return true; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 563 | } |
| 564 | |
| 565 | /* |
| 566 | * Unify two bit vectors and store the result to the dest vector. |
| 567 | */ |
| 568 | bool oatUnifyBitVectors(ArenaBitVector* dest, const ArenaBitVector* src1, |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 569 | const ArenaBitVector* src2) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 570 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 571 | DCHECK(src1 != NULL); |
| 572 | DCHECK(src2 != NULL); |
| 573 | if (dest->storageSize != src1->storageSize || |
| 574 | dest->storageSize != src2->storageSize || |
| 575 | dest->expandable != src1->expandable || |
| 576 | dest->expandable != src2->expandable) |
| 577 | return false; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 578 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 579 | unsigned int idx; |
| 580 | for (idx = 0; idx < dest->storageSize; idx++) { |
| 581 | dest->storage[idx] = src1->storage[idx] | src2->storage[idx]; |
| 582 | } |
| 583 | return true; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 584 | } |
| 585 | |
| 586 | /* |
buzbee | e196567 | 2012-03-11 18:39:19 -0700 | [diff] [blame] | 587 | * Return true if any bits collide. Vectors must be same size. |
| 588 | */ |
| 589 | bool oatTestBitVectors(const ArenaBitVector* src1, |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 590 | const ArenaBitVector* src2) |
buzbee | e196567 | 2012-03-11 18:39:19 -0700 | [diff] [blame] | 591 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 592 | DCHECK_EQ(src1->storageSize, src2->storageSize); |
| 593 | for (uint32_t idx = 0; idx < src1->storageSize; idx++) { |
| 594 | if (src1->storage[idx] & src2->storage[idx]) return true; |
| 595 | } |
| 596 | return false; |
buzbee | e196567 | 2012-03-11 18:39:19 -0700 | [diff] [blame] | 597 | } |
| 598 | |
| 599 | /* |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 600 | * Compare two bit vectors and return true if difference is seen. |
| 601 | */ |
| 602 | bool oatCompareBitVectors(const ArenaBitVector* src1, |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 603 | const ArenaBitVector* src2) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 604 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 605 | if (src1->storageSize != src2->storageSize || |
| 606 | src1->expandable != src2->expandable) |
| 607 | return true; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 608 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 609 | unsigned int idx; |
| 610 | for (idx = 0; idx < src1->storageSize; idx++) { |
| 611 | if (src1->storage[idx] != src2->storage[idx]) return true; |
| 612 | } |
| 613 | return false; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 614 | } |
| 615 | |
| 616 | /* |
| 617 | * Count the number of bits that are set. |
| 618 | */ |
| 619 | int oatCountSetBits(const ArenaBitVector* pBits) |
| 620 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 621 | unsigned int word; |
| 622 | unsigned int count = 0; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 623 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 624 | for (word = 0; word < pBits->storageSize; word++) { |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 625 | uint32_t val = pBits->storage[word]; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 626 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 627 | if (val != 0) { |
| 628 | if (val == 0xffffffff) { |
| 629 | count += 32; |
| 630 | } else { |
| 631 | /* count the number of '1' bits */ |
| 632 | while (val != 0) { |
| 633 | val &= val - 1; |
| 634 | count++; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 635 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 636 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 637 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 638 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 639 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 640 | return count; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 641 | } |
| 642 | |
| 643 | /* Return the next position set to 1. -1 means end-of-element reached */ |
| 644 | int oatBitVectorIteratorNext(ArenaBitVectorIterator* iterator) |
| 645 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 646 | ArenaBitVector* pBits = iterator->pBits; |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 647 | uint32_t bitIndex = iterator->idx; |
| 648 | uint32_t bitSize = iterator->bitSize; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 649 | |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 650 | DCHECK_EQ(bitSize, pBits->storageSize * sizeof(uint32_t) * 8); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 651 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 652 | if (bitIndex >= bitSize) return -1; |
buzbee | 5b53710 | 2012-01-17 17:33:47 -0800 | [diff] [blame] | 653 | |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 654 | uint32_t wordIndex = bitIndex >> 5; |
| 655 | uint32_t endWordIndex = bitSize >> 5; |
| 656 | uint32_t* storage = pBits->storage; |
| 657 | uint32_t word = storage[wordIndex++]; |
buzbee | 5b53710 | 2012-01-17 17:33:47 -0800 | [diff] [blame] | 658 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 659 | // Mask out any bits in the first word we've already considered |
| 660 | word &= ~((1 << (bitIndex & 0x1f))-1); |
buzbee | 5abfa3e | 2012-01-31 17:01:43 -0800 | [diff] [blame] | 661 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 662 | for (; wordIndex <= endWordIndex;) { |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame] | 663 | uint32_t bitPos = bitIndex & 0x1f; |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 664 | if (word == 0) { |
| 665 | bitIndex += (32 - bitPos); |
| 666 | word = storage[wordIndex++]; |
| 667 | continue; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 668 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 669 | for (; bitPos < 32; bitPos++) { |
| 670 | if (word & (1 << bitPos)) { |
| 671 | iterator->idx = bitIndex + 1; |
| 672 | return bitIndex; |
| 673 | } |
| 674 | bitIndex++; |
| 675 | } |
| 676 | word = storage[wordIndex++]; |
| 677 | } |
| 678 | iterator->idx = iterator->bitSize; |
| 679 | return -1; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 680 | } |
| 681 | |
| 682 | /* |
| 683 | * Mark specified number of bits as "set". Cannot set all bits like ClearAll |
| 684 | * since there might be unused bits - setting those to one will confuse the |
| 685 | * iterator. |
| 686 | */ |
| 687 | void oatSetInitialBits(ArenaBitVector* pBits, unsigned int numBits) |
| 688 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 689 | unsigned int idx; |
| 690 | DCHECK_LE(((numBits + 31) >> 5), pBits->storageSize); |
| 691 | for (idx = 0; idx < (numBits >> 5); idx++) { |
| 692 | pBits->storage[idx] = -1; |
| 693 | } |
| 694 | unsigned int remNumBits = numBits & 0x1f; |
| 695 | if (remNumBits) { |
| 696 | pBits->storage[idx] = (1 << remNumBits) - 1; |
| 697 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 698 | } |
| 699 | |
| 700 | void oatGetBlockName(BasicBlock* bb, char* name) |
| 701 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 702 | switch (bb->blockType) { |
| 703 | case kEntryBlock: |
Bill Buzbee | c9f40dd | 2012-08-15 11:35:25 -0700 | [diff] [blame] | 704 | snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 705 | break; |
| 706 | case kExitBlock: |
Bill Buzbee | c9f40dd | 2012-08-15 11:35:25 -0700 | [diff] [blame] | 707 | snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 708 | break; |
| 709 | case kDalvikByteCode: |
Bill Buzbee | c9f40dd | 2012-08-15 11:35:25 -0700 | [diff] [blame] | 710 | snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->startOffset, bb->id); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 711 | break; |
| 712 | case kExceptionHandling: |
Bill Buzbee | c9f40dd | 2012-08-15 11:35:25 -0700 | [diff] [blame] | 713 | snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->startOffset, |
| 714 | bb->id); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 715 | break; |
| 716 | default: |
Bill Buzbee | c9f40dd | 2012-08-15 11:35:25 -0700 | [diff] [blame] | 717 | snprintf(name, BLOCK_NAME_LEN, "??_%d", bb->id); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 718 | break; |
| 719 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 720 | } |
buzbee | ed3e930 | 2011-09-23 17:34:19 -0700 | [diff] [blame] | 721 | |
| 722 | const char* oatGetShortyFromTargetIdx(CompilationUnit *cUnit, int targetIdx) |
| 723 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 724 | const DexFile::MethodId& methodId = cUnit->dex_file->GetMethodId(targetIdx); |
| 725 | return cUnit->dex_file->GetShorty(methodId.proto_idx_); |
buzbee | ed3e930 | 2011-09-23 17:34:19 -0700 | [diff] [blame] | 726 | } |
Elliott Hughes | 11d1b0c | 2012-01-23 16:57:47 -0800 | [diff] [blame] | 727 | |
| 728 | } // namespace art |