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