ssa_transformation.cc revision fa57c47f1b72916371a9c2d5c1389219bce655b4
167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Copyright (C) 2011 The Android Open Source Project 367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * 467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * you may not use this file except in compliance with the License. 667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * You may obtain a copy of the License at 767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * 867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * http://www.apache.org/licenses/LICENSE-2.0 967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * 1067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Unless required by applicable law or agreed to in writing, software 1167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * distributed under the License is distributed on an "AS IS" BASIS, 1267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * See the License for the specific language governing permissions and 1467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * limitations under the License. 1567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 1667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 17eaf09bc65f9a10d12befcdb239156938c9bceef2buzbee#include "compiler_internals.h" 18efc6369224b036a1fb77849f7ae65b3492c832c0buzbee#include "dataflow.h" 1967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 2011d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughesnamespace art { 2111d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughes 22e5f01223ae03b89767dc7881d75dca061121ee36buzbee// Make sure iterative dfs recording matches old recursive version 23e5f01223ae03b89767dc7881d75dca061121ee36buzbee//#define TEST_DFS 24e5f01223ae03b89767dc7881d75dca061121ee36buzbee 25aad94383fc41e8f8770f0b2144f766a2ffa772e7buzbeestatic BasicBlock* NeedsVisit(BasicBlock* bb) { 26e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (bb != NULL) { 27e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (bb->visited || bb->hidden) { 28e5f01223ae03b89767dc7881d75dca061121ee36buzbee bb = NULL; 29e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 30e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 31e5f01223ae03b89767dc7881d75dca061121ee36buzbee return bb; 32e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 33e5f01223ae03b89767dc7881d75dca061121ee36buzbee 3452a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbeestatic BasicBlock* NextUnvisitedSuccessor(BasicBlock* bb) 35e5f01223ae03b89767dc7881d75dca061121ee36buzbee{ 36fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* res = NeedsVisit(bb->fall_through); 37e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (res == NULL) { 3852a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee res = NeedsVisit(bb->taken); 39e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (res == NULL) { 40fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->successor_block_list.block_list_type != kNotUsed) { 41e5f01223ae03b89767dc7881d75dca061121ee36buzbee GrowableListIterator iterator; 42fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableListIteratorInit(&bb->successor_block_list.blocks, 43e5f01223ae03b89767dc7881d75dca061121ee36buzbee &iterator); 44e5f01223ae03b89767dc7881d75dca061121ee36buzbee while (true) { 45cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee SuccessorBlockInfo *sbi = reinterpret_cast<SuccessorBlockInfo*> 4652a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee (GrowableListIteratorNext(&iterator)); 47e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (sbi == NULL) break; 4852a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee res = NeedsVisit(sbi->block); 49e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (res != NULL) break; 50e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 51e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 52e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 53e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 54e5f01223ae03b89767dc7881d75dca061121ee36buzbee return res; 55e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 56e5f01223ae03b89767dc7881d75dca061121ee36buzbee 57fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic void MarkPreOrder(CompilationUnit* cu, BasicBlock* block) 58e5f01223ae03b89767dc7881d75dca061121ee36buzbee{ 59e5f01223ae03b89767dc7881d75dca061121ee36buzbee block->visited = true; 60fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Enqueue the pre_order block id */ 61fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee InsertGrowableList(cu, &cu->dfs_order, block->id); 62e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 63e5f01223ae03b89767dc7881d75dca061121ee36buzbee 64fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic void RecordDFSOrders(CompilationUnit* cu, BasicBlock* block) 6567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 66e5f01223ae03b89767dc7881d75dca061121ee36buzbee std::vector<BasicBlock*> succ; 67fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee MarkPreOrder(cu, block); 68e5f01223ae03b89767dc7881d75dca061121ee36buzbee succ.push_back(block); 69e5f01223ae03b89767dc7881d75dca061121ee36buzbee while (!succ.empty()) { 70e5f01223ae03b89767dc7881d75dca061121ee36buzbee BasicBlock* curr = succ.back(); 71fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* next_successor = NextUnvisitedSuccessor(curr); 72fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (next_successor != NULL) { 73fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee MarkPreOrder(cu, next_successor); 74fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee succ.push_back(next_successor); 75e5f01223ae03b89767dc7881d75dca061121ee36buzbee continue; 76e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 77fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee curr->dfs_id = cu->dfs_post_order.num_used; 78fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee InsertGrowableList(cu, &cu->dfs_post_order, curr->id); 79e5f01223ae03b89767dc7881d75dca061121ee36buzbee succ.pop_back(); 80e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 81e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 82e5f01223ae03b89767dc7881d75dca061121ee36buzbee 83e5f01223ae03b89767dc7881d75dca061121ee36buzbee#if defined(TEST_DFS) 84fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee/* Enter the node to the dfs_order list then visit its successors */ 85fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic void RecursiveRecordDFSOrders(CompilationUnit* cu, BasicBlock* block) 86e5f01223ae03b89767dc7881d75dca061121ee36buzbee{ 8767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 88a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee if (block->visited || block->hidden) return; 89a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee block->visited = true; 90a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 91a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee // Can this block be reached only via previous block fallthrough? 92fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if ((block->block_type == kDalvikByteCode) && 93fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee (block->predecessors->num_used == 1)) { 94fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_GE(cu->dfs_order.num_used, 1U); 95fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int prev_idx = cu->dfs_order.num_used - 1; 96fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int prev_id = cu->dfs_order.elem_list[prev_idx]; 97fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* pred_bb = (BasicBlock*)block->predecessors->elem_list[0]; 98a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 99a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 100fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Enqueue the pre_order block id */ 101fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee InsertGrowableList(cu, &cu->dfs_order, block->id); 102a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 103fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (block->fall_through) { 104fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee RecursiveRecordDFSOrders(cu, block->fall_through); 105a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 106fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (block->taken) RecursiveRecordDFSOrders(cu, block->taken); 107fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (block->successor_block_list.block_list_type != kNotUsed) { 108a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee GrowableListIterator iterator; 109fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableListIteratorInit(&block->successor_block_list.blocks, 110a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee &iterator); 111a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 112fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SuccessorBlockInfo *successor_block_info = 11352a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee (SuccessorBlockInfo *) GrowableListIteratorNext(&iterator); 114fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (successor_block_info == NULL) break; 115fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* succ_bb = successor_block_info->block; 116fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee RecursiveRecordDFSOrders(cu, succ_bb); 117a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 118a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 119a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 120fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Record postorder in basic block and enqueue normal id in dfs_post_order */ 121fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee block->dfs_id = cu->dfs_post_order.num_used; 122fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee InsertGrowableList(cu, &cu->dfs_post_order, block->id); 123a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return; 12467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 125e5f01223ae03b89767dc7881d75dca061121ee36buzbee#endif 12667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 1275b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* Sort the blocks by the Depth-First-Search */ 128fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic void ComputeDFSOrders(CompilationUnit* cu) 12967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 130fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initialize or reset the DFS pre_order list */ 131fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (cu->dfs_order.elem_list == NULL) { 132fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CompilerInitGrowableList(cu, &cu->dfs_order, cu->num_blocks, 133a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kListDfsOrder); 134a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 135a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Just reset the used length on the counter */ 136fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->dfs_order.num_used = 0; 137a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 138a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 139fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initialize or reset the DFS post_order list */ 140fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (cu->dfs_post_order.elem_list == NULL) { 141fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CompilerInitGrowableList(cu, &cu->dfs_post_order, cu->num_blocks, 142a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kListDfsPostOrder); 143a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 144a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Just reset the used length on the counter */ 145fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->dfs_post_order.num_used = 0; 146a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 147a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 148e5f01223ae03b89767dc7881d75dca061121ee36buzbee#if defined(TEST_DFS) 149e5f01223ae03b89767dc7881d75dca061121ee36buzbee // Reset visited flags 150fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, ClearVisitedFlag, 151fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee kAllNodes, false /* is_iterative */); 152e5f01223ae03b89767dc7881d75dca061121ee36buzbee // Record pre and post order dfs 153fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee RecursiveRecordDFSOrders(cu, cu->entry_block); 154e5f01223ae03b89767dc7881d75dca061121ee36buzbee // Copy the results for later comparison and reset the lists 155fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableList recursive_dfs_order; 156fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableList recursive_dfs_post_order; 157fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CompilerInitGrowableList(cu, &recursive_dfs_order, cu->dfs_order.num_used, 158e5f01223ae03b89767dc7881d75dca061121ee36buzbee kListDfsOrder); 159fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (unsigned int i = 0; i < cu->dfs_order.num_used; i++) { 160fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee InsertGrowableList(cu, &recursive_dfs_order, 161fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->dfs_order.elem_list[i]); 162fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee } 163fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->dfs_order.num_used = 0; 164fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CompilerInitGrowableList(cu, &recursive_dfs_post_order, 165fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->dfs_post_order.num_used, kListDfsOrder); 166fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (unsigned int i = 0; i < cu->dfs_post_order.num_used; i++) { 167fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee InsertGrowableList(cu, &recursive_dfs_post_order, 168fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->dfs_post_order.elem_list[i]); 169fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee } 170fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->dfs_post_order.num_used = 0; 171e5f01223ae03b89767dc7881d75dca061121ee36buzbee#endif 172a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 173e5f01223ae03b89767dc7881d75dca061121ee36buzbee // Reset visited flags from all nodes 174fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, ClearVisitedFlag, 175fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee kAllNodes, false /* is_iterative */); 176e5f01223ae03b89767dc7881d75dca061121ee36buzbee // Record dfs orders 177fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee RecordDFSOrders(cu, cu->entry_block); 178e5f01223ae03b89767dc7881d75dca061121ee36buzbee 179e5f01223ae03b89767dc7881d75dca061121ee36buzbee#if defined(TEST_DFS) 180e5f01223ae03b89767dc7881d75dca061121ee36buzbee bool mismatch = false; 181fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee mismatch |= (cu->dfs_order.num_used != recursive_dfs_order.num_used); 182fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (unsigned int i = 0; i < cu->dfs_order.num_used; i++) { 183fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee mismatch |= (cu->dfs_order.elem_list[i] != 184fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee recursive_dfs_order.elem_list[i]); 185e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 186fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee mismatch |= (cu->dfs_post_order.num_used != recursive_dfs_post_order.num_used); 187fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (unsigned int i = 0; i < cu->dfs_post_order.num_used; i++) { 188fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee mismatch |= (cu->dfs_post_order.elem_list[i] != 189fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee recursive_dfs_post_order.elem_list[i]); 190e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 191e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (mismatch) { 192e5f01223ae03b89767dc7881d75dca061121ee36buzbee LOG(INFO) << "Mismatch for " 193fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee << PrettyMethod(cu->method_idx, *cu->dex_file); 194e5f01223ae03b89767dc7881d75dca061121ee36buzbee LOG(INFO) << "New dfs"; 195fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (unsigned int i = 0; i < cu->dfs_order.num_used; i++) { 196fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee LOG(INFO) << i << " - " << cu->dfs_order.elem_list[i]; 197e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 198e5f01223ae03b89767dc7881d75dca061121ee36buzbee LOG(INFO) << "Recursive dfs"; 199fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (unsigned int i = 0; i < recursive_dfs_order.num_used; i++) { 200fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee LOG(INFO) << i << " - " << recursive_dfs_order.elem_list[i]; 201e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 202e5f01223ae03b89767dc7881d75dca061121ee36buzbee LOG(INFO) << "New post dfs"; 203fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (unsigned int i = 0; i < cu->dfs_post_order.num_used; i++) { 204fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee LOG(INFO) << i << " - " << cu->dfs_post_order.elem_list[i]; 205e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 206e5f01223ae03b89767dc7881d75dca061121ee36buzbee LOG(INFO) << "Recursive post dfs"; 207fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (unsigned int i = 0; i < recursive_dfs_post_order.num_used; i++) { 208fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee LOG(INFO) << i << " - " << recursive_dfs_post_order.elem_list[i]; 209e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 210e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 211fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CHECK_EQ(cu->dfs_order.num_used, recursive_dfs_order.num_used); 212fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (unsigned int i = 0; i < cu->dfs_order.num_used; i++) { 213fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CHECK_EQ(cu->dfs_order.elem_list[i], recursive_dfs_order.elem_list[i]); 214e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 215fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CHECK_EQ(cu->dfs_post_order.num_used, recursive_dfs_post_order.num_used); 216fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (unsigned int i = 0; i < cu->dfs_post_order.num_used; i++) { 217fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CHECK_EQ(cu->dfs_post_order.elem_list[i], 218fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee recursive_dfs_post_order.elem_list[i]); 219e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 220e5f01223ae03b89767dc7881d75dca061121ee36buzbee#endif 221e5f01223ae03b89767dc7881d75dca061121ee36buzbee 222fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->num_reachable_blocks = cu->dfs_order.num_used; 22367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 22467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 22567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 22667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Mark block bit on the per-Dalvik register vector to denote that Dalvik 22767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * register idx is defined in BasicBlock bb. 22867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 229fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic bool FillDefBlockMatrix(CompilationUnit* cu, BasicBlock* bb) 23067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 231fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->data_flow_info == NULL) return false; 232a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 233a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee ArenaBitVectorIterator iterator; 234a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 235fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BitVectorIteratorInit(bb->data_flow_info->def_v, &iterator); 236a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 23752a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee int idx = BitVectorIteratorNext(&iterator); 238a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee if (idx == -1) break; 239a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Block bb defines register idx */ 240fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SetBit(cu, cu->def_block_matrix[idx], bb->id); 241a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 242a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 24367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 24467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 245fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic void ComputeDefBlockMatrix(CompilationUnit* cu) 24667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 247fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int num_registers = cu->num_dalvik_registers; 248fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Allocate num_dalvik_registers bit vector pointers */ 249fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->def_block_matrix = static_cast<ArenaBitVector**> 250fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee (NewMem(cu, sizeof(ArenaBitVector *) * num_registers, true, kAllocDFInfo)); 251a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee int i; 252a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 253fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initialize num_register vectors with num_blocks bits each */ 254fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (i = 0; i < num_registers; i++) { 255fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->def_block_matrix[i] = AllocBitVector(cu, cu->num_blocks, 256a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee false, kBitMapBMatrix); 257a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 258fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, FindLocalLiveIn, 259fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee kAllNodes, false /* is_iterative */); 260fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, FillDefBlockMatrix, 261fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee kAllNodes, false /* is_iterative */); 262a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 263a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 264a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * Also set the incoming parameters as defs in the entry block. 265a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * Only need to handle the parameters for the outer method. 266a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 267fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int num_regs = cu->num_dalvik_registers; 268fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int in_reg = num_regs - cu->num_ins; 269fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (; in_reg < num_regs; in_reg++) { 270fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SetBit(cu, cu->def_block_matrix[in_reg], cu->entry_block->id); 271a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 27267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 27367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 27467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Compute the post-order traversal of the CFG */ 275fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic void ComputeDomPostOrderTraversal(CompilationUnit* cu, BasicBlock* bb) 27667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 277fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ArenaBitVectorIterator bv_iterator; 278fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BitVectorIteratorInit(bb->i_dominated, &bv_iterator); 279fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableList* block_list = &cu->block_list; 280a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 281a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through the dominated blocks first */ 282a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 28352a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee //TUNING: hot call to BitVectorIteratorNext 284fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int bb_idx = BitVectorIteratorNext(&bv_iterator); 285fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb_idx == -1) break; 286fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* dominated_bb = 287fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee reinterpret_cast<BasicBlock*>(GrowableListGetElement(block_list, bb_idx)); 288fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ComputeDomPostOrderTraversal(cu, dominated_bb); 289a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 290a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 291a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Enter the current block id */ 292fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee InsertGrowableList(cu, &cu->dom_post_order_traversal, bb->id); 293a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 294a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* hacky loop detection */ 29552a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee if (bb->taken && IsBitSet(bb->dominators, bb->taken->id)) { 296fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->has_loop = true; 297a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 29867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 29967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 300fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic void CheckForDominanceFrontier(CompilationUnit* cu, BasicBlock* dom_bb, 301fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee const BasicBlock* succ_bb) 30267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 303a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 304a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * TODO - evaluate whether phi will ever need to be inserted into exit 305a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * blocks. 306a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 307fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (succ_bb->i_dom != dom_bb && 308fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee succ_bb->block_type == kDalvikByteCode && 309fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee succ_bb->hidden == false) { 310fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SetBit(cu, dom_bb->dom_frontier, succ_bb->id); 311a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 31267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 31367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 31467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Worker function to compute the dominance frontier */ 315fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic bool ComputeDominanceFrontier(CompilationUnit* cu, BasicBlock* bb) 31667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 317fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableList* block_list = &cu->block_list; 318a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 319a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Calculate DF_local */ 320a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee if (bb->taken) { 321fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CheckForDominanceFrontier(cu, bb, bb->taken); 322a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 323fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->fall_through) { 324fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CheckForDominanceFrontier(cu, bb, bb->fall_through); 325a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 326fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->successor_block_list.block_list_type != kNotUsed) { 327a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee GrowableListIterator iterator; 328fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableListIteratorInit(&bb->successor_block_list.blocks, 329a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee &iterator); 330a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 331fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SuccessorBlockInfo *successor_block_info = 33252a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee reinterpret_cast<SuccessorBlockInfo*>(GrowableListIteratorNext(&iterator)); 333fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (successor_block_info == NULL) break; 334fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* succ_bb = successor_block_info->block; 335fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CheckForDominanceFrontier(cu, bb, succ_bb); 336a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 337a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 338a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 339a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Calculate DF_up */ 340fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ArenaBitVectorIterator bv_iterator; 341fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BitVectorIteratorInit(bb->i_dominated, &bv_iterator); 342a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 34352a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee //TUNING: hot call to BitVectorIteratorNext 344fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int dominated_idx = BitVectorIteratorNext(&bv_iterator); 345fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (dominated_idx == -1) break; 346fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* dominated_bb = 347fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee reinterpret_cast<BasicBlock*>(GrowableListGetElement(block_list, dominated_idx)); 348fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ArenaBitVectorIterator df_iterator; 349fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BitVectorIteratorInit(dominated_bb->dom_frontier, &df_iterator); 35067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 35152a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee //TUNING: hot call to BitVectorIteratorNext 352fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int df_up_idx = BitVectorIteratorNext(&df_iterator); 353fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (df_up_idx == -1) break; 354fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* df_up_block = 355fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee reinterpret_cast<BasicBlock*>( GrowableListGetElement(block_list, df_up_idx)); 356fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CheckForDominanceFrontier(cu, bb, df_up_block); 35767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 358a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 35967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 360a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 36167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 36267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 36367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Worker function for initializing domination-related data structures */ 364fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic bool InitializeDominationInfo(CompilationUnit* cu, BasicBlock* bb) 36567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 366fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int num_total_blocks = cu->block_list.num_used; 367a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 368a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee if (bb->dominators == NULL ) { 369fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->dominators = AllocBitVector(cu, num_total_blocks, 370a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee false /* expandable */, 371a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kBitMapDominators); 372fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->i_dominated = AllocBitVector(cu, num_total_blocks, 373a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee false /* expandable */, 374a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kBitMapIDominated); 375fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->dom_frontier = AllocBitVector(cu, num_total_blocks, 376a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee false /* expandable */, 377a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kBitMapDomFrontier); 378a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 37952a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee ClearAllBits(bb->dominators); 380fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ClearAllBits(bb->i_dominated); 381fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ClearAllBits(bb->dom_frontier); 382a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 383a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Set all bits in the dominator vector */ 384fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SetInitialBits(bb->dominators, num_total_blocks); 385a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 386a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 38767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 38867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 3895b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* 3905b53710b4abcf8f35c91a963a475b72cb34757e6buzbee * Worker function to compute each block's dominators. This implementation 3915b53710b4abcf8f35c91a963a475b72cb34757e6buzbee * is only used when kDebugVerifyDataflow is active and should compute 39252a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee * the same dominator sets as ComputeBlockDominiators. 3935b53710b4abcf8f35c91a963a475b72cb34757e6buzbee */ 394fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic bool SlowComputeBlockDominators(CompilationUnit* cu, BasicBlock* bb) 39567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 396fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableList* block_list = &cu->block_list; 397fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int num_total_blocks = block_list->num_used; 398fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ArenaBitVector* temp_block_v = cu->temp_block_v; 399a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee GrowableListIterator iter; 400a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 401a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 402a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * The dominator of the entry block has been preset to itself and we need 403a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * to skip the calculation here. 404a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 405fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb == cu->entry_block) return false; 406a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 407fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SetInitialBits(temp_block_v, num_total_blocks); 408a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 409a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through the predecessors */ 41052a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee GrowableListIteratorInit(bb->predecessors, &iter); 411a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 412fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* pred_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter)); 413fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (!pred_bb) break; 414fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* temp_block_v = temp_block_v ^ dominators */ 415fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (pred_bb->dominators != NULL) { 416fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee IntersectBitVectors(temp_block_v, temp_block_v, pred_bb->dominators); 417a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 418a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 419fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SetBit(cu, temp_block_v, bb->id); 420fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (CompareBitVectors(temp_block_v, bb->dominators)) { 421fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CopyBitVector(bb->dominators, temp_block_v); 422a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 423a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 424a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 42567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 42667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 4275b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* 4285b53710b4abcf8f35c91a963a475b72cb34757e6buzbee * Worker function to compute the idom. This implementation is only 4295b53710b4abcf8f35c91a963a475b72cb34757e6buzbee * used when kDebugVerifyDataflow is active and should compute the 430fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * same i_dom as ComputeblockIDom. 4315b53710b4abcf8f35c91a963a475b72cb34757e6buzbee */ 432fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic bool SlowComputeBlockIDom(CompilationUnit* cu, BasicBlock* bb) 43367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 434fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableList* block_list = &cu->block_list; 435fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ArenaBitVector* temp_block_v = cu->temp_block_v; 436fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ArenaBitVectorIterator bv_iterator; 437fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* i_dom; 438a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 439fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb == cu->entry_block) return false; 440a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 441fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CopyBitVector(temp_block_v, bb->dominators); 442fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ClearBit(temp_block_v, bb->id); 443fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BitVectorIteratorInit(temp_block_v, &bv_iterator); 444a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 445a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Should not see any dead block */ 446fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_NE(CountSetBits(temp_block_v), 0); 447fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (CountSetBits(temp_block_v) == 1) { 448fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee i_dom = reinterpret_cast<BasicBlock*> 449fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee (GrowableListGetElement(block_list, BitVectorIteratorNext(&bv_iterator))); 450fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->i_dom = i_dom; 451a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 452fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int i_dom_idx = BitVectorIteratorNext(&bv_iterator); 453fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_NE(i_dom_idx, -1); 454a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 455fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int next_dom = BitVectorIteratorNext(&bv_iterator); 456fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (next_dom == -1) break; 457fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* next_dom_bb = 458fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee reinterpret_cast<BasicBlock*>(GrowableListGetElement(block_list, next_dom)); 459fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* i_dom dominates next_dom - set new i_dom */ 460fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (IsBitSet(next_dom_bb->dominators, i_dom_idx)) { 461fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee i_dom_idx = next_dom; 462a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 463a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 464a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 465fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee i_dom = reinterpret_cast<BasicBlock*>(GrowableListGetElement(block_list, i_dom_idx)); 466a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Set the immediate dominator block for bb */ 467fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->i_dom = i_dom; 468a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 469fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Add bb to the i_dominated set of the immediate dominator block */ 470fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SetBit(cu, i_dom->i_dominated, bb->id); 471a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 47267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 47367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 4745b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* 475fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * Walk through the ordered i_dom list until we reach common parent. 476fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * Given the ordering of i_dom_list, this common parent represents the 4775b53710b4abcf8f35c91a963a475b72cb34757e6buzbee * last element of the intersection of block1 and block2 dominators. 4785b53710b4abcf8f35c91a963a475b72cb34757e6buzbee */ 479fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic int FindCommonParent(CompilationUnit *cu, int block1, int block2) 4805b53710b4abcf8f35c91a963a475b72cb34757e6buzbee{ 481a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (block1 != block2) { 482a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (block1 < block2) { 483fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee block1 = cu->i_dom_list[block1]; 484a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee DCHECK_NE(block1, NOTVISITED); 485a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 486a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (block2 < block1) { 487fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee block2 = cu->i_dom_list[block2]; 488a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee DCHECK_NE(block2, NOTVISITED); 4895b53710b4abcf8f35c91a963a475b72cb34757e6buzbee } 490a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 491a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return block1; 4925b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 4935b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 4945b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* Worker function to compute each block's immediate dominator */ 495fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic bool ComputeblockIDom(CompilationUnit* cu, BasicBlock* bb) 4965b53710b4abcf8f35c91a963a475b72cb34757e6buzbee{ 497a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee GrowableListIterator iter; 498a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee int idom = -1; 4995b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 500a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Special-case entry block */ 501fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb == cu->entry_block) { 5025b53710b4abcf8f35c91a963a475b72cb34757e6buzbee return false; 503a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 504a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 505a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through the predecessors */ 50652a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee GrowableListIteratorInit(bb->predecessors, &iter); 507a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 508a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Find the first processed predecessor */ 509a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 510fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* pred_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter)); 511fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CHECK(pred_bb != NULL); 512fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (cu->i_dom_list[pred_bb->dfs_id] != NOTVISITED) { 513fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee idom = pred_bb->dfs_id; 514a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee break; 515a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 516a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 517a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 518a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Scan the rest of the predecessors */ 519a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 520fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* pred_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter)); 521fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (!pred_bb) break; 522fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (cu->i_dom_list[pred_bb->dfs_id] == NOTVISITED) { 523a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee continue; 524a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 525fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee idom = FindCommonParent(cu, pred_bb->dfs_id, idom); 526a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 527a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 528a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 529a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee DCHECK_NE(idom, NOTVISITED); 530a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 531a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Did something change? */ 532fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (cu->i_dom_list[bb->dfs_id] != idom) { 533fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->i_dom_list[bb->dfs_id] = idom; 534a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 535a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 536a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 5375b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 5385b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 5395b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* Worker function to compute each block's domintors */ 540fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic bool ComputeBlockDominiators(CompilationUnit* cu, BasicBlock* bb) 5415b53710b4abcf8f35c91a963a475b72cb34757e6buzbee{ 542fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb == cu->entry_block) { 54352a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee ClearAllBits(bb->dominators); 544a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 545fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CopyBitVector(bb->dominators, bb->i_dom->dominators); 546a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 547fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SetBit(cu, bb->dominators, bb->id); 548a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 5495b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 5505b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 551fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic bool SetDominators(CompilationUnit* cu, BasicBlock* bb) 5525b53710b4abcf8f35c91a963a475b72cb34757e6buzbee{ 553fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb != cu->entry_block) { 554fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int idom_dfs_idx = cu->i_dom_list[bb->dfs_id]; 555fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_NE(idom_dfs_idx, NOTVISITED); 556fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int i_dom_idx = cu->dfs_post_order.elem_list[idom_dfs_idx]; 557fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* i_dom = 558fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee reinterpret_cast<BasicBlock*>(GrowableListGetElement(&cu->block_list, i_dom_idx)); 559fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (cu->enable_debug & (1 << kDebugVerifyDataflow)) { 560fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_EQ(bb->i_dom->id, i_dom->id); 5615b53710b4abcf8f35c91a963a475b72cb34757e6buzbee } 562fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->i_dom = i_dom; 563fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Add bb to the i_dominated set of the immediate dominator block */ 564fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SetBit(cu, i_dom->i_dominated, bb->id); 565a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 566a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 5675b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 5685b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 56967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Compute dominators, immediate dominator, and dominance fronter */ 570fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic void ComputeDominators(CompilationUnit* cu) 57167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 572fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int num_reachable_blocks = cu->num_reachable_blocks; 573fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int num_total_blocks = cu->block_list.num_used; 574a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 575a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Initialize domination-related data structures */ 576fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, InitializeDominationInfo, 577fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee kReachableNodes, false /* is_iterative */); 578a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 579fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initalize & Clear i_dom_list */ 580fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (cu->i_dom_list == NULL) { 581fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->i_dom_list = static_cast<int*>(NewMem(cu, sizeof(int) * num_reachable_blocks, 582cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee false, kAllocDFInfo)); 583a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 584fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (int i = 0; i < num_reachable_blocks; i++) { 585fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->i_dom_list[i] = NOTVISITED; 586a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 587a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 588fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* For post-order, last block is entry block. Set its i_dom to istelf */ 589fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_EQ(cu->entry_block->dfs_id, num_reachable_blocks-1); 590fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->i_dom_list[cu->entry_block->dfs_id] = cu->entry_block->dfs_id; 591a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 592a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Compute the immediate dominators */ 593fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, ComputeblockIDom, 594a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kReversePostOrderTraversal, 595fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee true /* is_iterative */); 596a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 597a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Set the dominator for the root node */ 598fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ClearAllBits(cu->entry_block->dominators); 599fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SetBit(cu, cu->entry_block->dominators, cu->entry_block->id); 600a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 601fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (cu->temp_block_v == NULL) { 602fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->temp_block_v = AllocBitVector(cu, num_total_blocks, 603a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee false /* expandable */, 604a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kBitMapTmpBlockV); 605a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 606fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ClearAllBits(cu->temp_block_v); 607a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 608fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->entry_block->i_dom = NULL; 609a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 610a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* For testing, compute sets using alternate mechanism */ 611fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (cu->enable_debug & (1 << kDebugVerifyDataflow)) { 612a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee // Use alternate mechanism to compute dominators for comparison 613fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, SlowComputeBlockDominators, 614a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kPreOrderDFSTraversal, 615fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee true /* is_iterative */); 6165b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 617fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, SlowComputeBlockIDom, 618a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kReachableNodes, 619fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee false /* is_iterative */); 620a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 621a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 622fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, SetDominators, 623a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kReachableNodes, 624fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee false /* is_iterative */); 625a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 626fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, ComputeBlockDominiators, 627a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kReversePostOrderTraversal, 628fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee false /* is_iterative */); 629a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 630a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 631a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * Now go ahead and compute the post order traversal based on the 632fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * i_dominated sets. 633a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 634fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (cu->dom_post_order_traversal.elem_list == NULL) { 635fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CompilerInitGrowableList(cu, &cu->dom_post_order_traversal, 636fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee num_reachable_blocks, kListDomPostOrderTraversal); 637a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 638fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->dom_post_order_traversal.num_used = 0; 639a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 640a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 641fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ComputeDomPostOrderTraversal(cu, cu->entry_block); 642fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_EQ(cu->dom_post_order_traversal.num_used, static_cast<unsigned>(cu->num_reachable_blocks)); 643a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 644a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Now compute the dominance frontier for each block */ 645fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, ComputeDominanceFrontier, 646a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kPostOrderDOMTraversal, 647fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee false /* is_iterative */); 64867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 64967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 65067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 65167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Perform dest U= src1 ^ ~src2 65267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * This is probably not general enough to be placed in BitVector.[ch]. 65367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 65452a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbeestatic void ComputeSuccLineIn(ArenaBitVector* dest, const ArenaBitVector* src1, 65552a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee const ArenaBitVector* src2) 65667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 657fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (dest->storage_size != src1->storage_size || 658fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee dest->storage_size != src2->storage_size || 659a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee dest->expandable != src1->expandable || 660a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee dest->expandable != src2->expandable) { 661a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee LOG(FATAL) << "Incompatible set properties"; 662a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 663a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 664a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee unsigned int idx; 665fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (idx = 0; idx < dest->storage_size; idx++) { 666a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee dest->storage[idx] |= src1->storage[idx] & ~src2->storage[idx]; 667a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 66867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 66967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 67067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 67167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Iterate through all successor blocks and propagate up the live-in sets. 67267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * The calculated result is used for phi-node pruning - where we only need to 67367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * insert a phi node if the variable is live-in to the block. 67467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 675fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic bool ComputeBlockLiveIns(CompilationUnit* cu, BasicBlock* bb) 67667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 677fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ArenaBitVector* temp_dalvik_register_v = cu->temp_dalvik_register_v; 678fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee 679fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->data_flow_info == NULL) return false; 680fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CopyBitVector(temp_dalvik_register_v, bb->data_flow_info->live_in_v); 681fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->taken && bb->taken->data_flow_info) 682fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ComputeSuccLineIn(temp_dalvik_register_v, bb->taken->data_flow_info->live_in_v, 683fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->data_flow_info->def_v); 684fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->fall_through && bb->fall_through->data_flow_info) 685fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ComputeSuccLineIn(temp_dalvik_register_v, 686fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->fall_through->data_flow_info->live_in_v, 687fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->data_flow_info->def_v); 688fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->successor_block_list.block_list_type != kNotUsed) { 689a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee GrowableListIterator iterator; 690fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableListIteratorInit(&bb->successor_block_list.blocks, 691a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee &iterator); 692a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 693fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SuccessorBlockInfo *successor_block_info = 69452a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee reinterpret_cast<SuccessorBlockInfo*>(GrowableListIteratorNext(&iterator)); 695fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (successor_block_info == NULL) break; 696fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* succ_bb = successor_block_info->block; 697fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (succ_bb->data_flow_info) { 698fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ComputeSuccLineIn(temp_dalvik_register_v, 699fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee succ_bb->data_flow_info->live_in_v, 700fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->data_flow_info->def_v); 701a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 70267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 703a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 704fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (CompareBitVectors(temp_dalvik_register_v, bb->data_flow_info->live_in_v)) { 705fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CopyBitVector(bb->data_flow_info->live_in_v, temp_dalvik_register_v); 706a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 707a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 708a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 70967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 71067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 71167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Insert phi nodes to for each variable to the dominance frontiers */ 712fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic void InsertPhiNodes(CompilationUnit* cu) 71367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 714fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int dalvik_reg; 715fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee const GrowableList* block_list = &cu->block_list; 716fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ArenaBitVector* phi_blocks = 717fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee AllocBitVector(cu, cu->num_blocks, false, kBitMapPhi); 718fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ArenaBitVector* tmp_blocks = 719fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee AllocBitVector(cu, cu->num_blocks, false, kBitMapTmpBlocks); 720fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ArenaBitVector* input_blocks = 721fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee AllocBitVector(cu, cu->num_blocks, false, kBitMapInputBlocks); 722fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee 723fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->temp_dalvik_register_v = 724fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee AllocBitVector(cu, cu->num_dalvik_registers, false, 725a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee kBitMapRegisterV); 726a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 727fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, ComputeBlockLiveIns, 728fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee kPostOrderDFSTraversal, true /* is_iterative */); 729a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 730a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through each Dalvik register */ 731fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (dalvik_reg = cu->num_dalvik_registers - 1; dalvik_reg >= 0; dalvik_reg--) { 732a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee bool change; 733a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee ArenaBitVectorIterator iterator; 734a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 735fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CopyBitVector(input_blocks, cu->def_block_matrix[dalvik_reg]); 736fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ClearAllBits(phi_blocks); 737a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 738a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Calculate the phi blocks for each Dalvik register */ 739a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee do { 740a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee change = false; 741fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ClearAllBits(tmp_blocks); 742fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BitVectorIteratorInit(input_blocks, &iterator); 743a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 744a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 74552a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee int idx = BitVectorIteratorNext(&iterator); 746a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee if (idx == -1) break; 747fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* def_bb = 748fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee reinterpret_cast<BasicBlock*>(GrowableListGetElement(block_list, idx)); 749a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 750fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Merge the dominance frontier to tmp_blocks */ 75152a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee //TUNING: hot call to UnifyBitVetors 752fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (def_bb->dom_frontier != NULL) { 753fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee UnifyBitVetors(tmp_blocks, tmp_blocks, def_bb->dom_frontier); 754a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 75567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 756fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (CompareBitVectors(phi_blocks, tmp_blocks)) { 757a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee change = true; 758fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CopyBitVector(phi_blocks, tmp_blocks); 759a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 760a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 761a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * Iterate through the original blocks plus the new ones in 762a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * the dominance frontier. 763a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 764fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CopyBitVector(input_blocks, phi_blocks); 765fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee UnifyBitVetors(input_blocks, input_blocks, 766fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->def_block_matrix[dalvik_reg]); 767a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 768a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } while (change); 769a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 770a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 771fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * Insert a phi node for dalvik_reg in the phi_blocks if the Dalvik 772a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * register is in the live-in set. 773a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 774fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BitVectorIteratorInit(phi_blocks, &iterator); 775a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 77652a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee int idx = BitVectorIteratorNext(&iterator); 777a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee if (idx == -1) break; 778fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* phi_bb = 779fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee reinterpret_cast<BasicBlock*>(GrowableListGetElement(block_list, idx)); 780a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Variable will be clobbered before being used - no need for phi */ 781fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (!IsBitSet(phi_bb->data_flow_info->live_in_v, dalvik_reg)) continue; 782fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee MIR *phi = static_cast<MIR*>(NewMem(cu, sizeof(MIR), true, kAllocDFInfo)); 783cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpPhi); 784fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee phi->dalvikInsn.vA = dalvik_reg; 785fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee phi->offset = phi_bb->start_offset; 786fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee phi->meta.phi_next = cu->phi_list; 787fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->phi_list = phi; 788fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee PrependMIR(phi_bb, phi); 789a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 790a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 79167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 79267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 79367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 79467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Worker function to insert phi-operands with latest SSA names from 79567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * predecessor blocks 79667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 797fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic bool InsertPhiNodeOperands(CompilationUnit* cu, BasicBlock* bb) 79867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 799a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee GrowableListIterator iter; 800a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee MIR *mir; 8016969d50c820bd63043940b0e0f0ddc6e6ac763b0buzbee std::vector<int> uses; 802fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee std::vector<int> incoming_arc; 803a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 804a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Phi nodes are at the beginning of each block */ 805fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (mir = bb->first_mir_insn; mir; mir = mir->next) { 806cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee if (mir->dalvikInsn.opcode != static_cast<Instruction::Code>(kMirOpPhi)) 807a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 808fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int ssa_reg = mir->ssa_rep->defs[0]; 809fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_GE(ssa_reg, 0); // Shouldn't see compiler temps here 810fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int v_reg = SRegToVReg(cu, ssa_reg); 81167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 8126969d50c820bd63043940b0e0f0ddc6e6ac763b0buzbee uses.clear(); 813fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee incoming_arc.clear(); 81467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 815a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through the predecessors */ 81652a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee GrowableListIteratorInit(bb->predecessors, &iter); 817a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 818fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* pred_bb = 81952a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter)); 820fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (!pred_bb) break; 821fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int ssa_reg = pred_bb->data_flow_info->vreg_to_ssa_map[v_reg]; 822fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee uses.push_back(ssa_reg); 823fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee incoming_arc.push_back(pred_bb->id); 824a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 82567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 826a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Count the number of SSA registers for a Dalvik register */ 827fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int num_uses = uses.size(); 828fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee mir->ssa_rep->num_uses = num_uses; 829fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee mir->ssa_rep->uses = 830fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee static_cast<int*>(NewMem(cu, sizeof(int) * num_uses, false, kAllocDFInfo)); 831fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee mir->ssa_rep->fp_use = 832fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee static_cast<bool*>(NewMem(cu, sizeof(bool) * num_uses, true, kAllocDFInfo)); 8332cfc639fc803bf67e3d2a961f2b637220c86d5f7buzbee int* incoming = 834fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee static_cast<int*>(NewMem(cu, sizeof(int) * num_uses, false, kAllocDFInfo)); 8352cfc639fc803bf67e3d2a961f2b637220c86d5f7buzbee // TODO: Ugly, rework (but don't burden each MIR/LIR for Phi-only needs) 836cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee mir->dalvikInsn.vB = reinterpret_cast<uintptr_t>(incoming); 83767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 838a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Set the uses array for the phi node */ 839fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int *use_ptr = mir->ssa_rep->uses; 840fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (int i = 0; i < num_uses; i++) { 841fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee *use_ptr++ = uses[i]; 842fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee *incoming++ = incoming_arc[i]; 84367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 844a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 84567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 846a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 84767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 84867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 849fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeestatic void DoDFSPreOrderSSARename(CompilationUnit* cu, BasicBlock* block) 850f0cde549bed96e16401a347a4511b59130c61e84buzbee{ 851f0cde549bed96e16401a347a4511b59130c61e84buzbee 852a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee if (block->visited || block->hidden) return; 853a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee block->visited = true; 854a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 855a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Process this block */ 856fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DoSSAConversion(cu, block); 857fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int map_size = sizeof(int) * cu->num_dalvik_registers; 858a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 859a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Save SSA map snapshot */ 860fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int* saved_ssa_map = static_cast<int*>(NewMem(cu, map_size, false, kAllocDalvikToSSAMap)); 861fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee memcpy(saved_ssa_map, cu->vreg_to_ssa_map, map_size); 862a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 863fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (block->fall_through) { 864fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DoDFSPreOrderSSARename(cu, block->fall_through); 865a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Restore SSA map snapshot */ 866fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee memcpy(cu->vreg_to_ssa_map, saved_ssa_map, map_size); 867a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 868a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee if (block->taken) { 869fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DoDFSPreOrderSSARename(cu, block->taken); 870a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Restore SSA map snapshot */ 871fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee memcpy(cu->vreg_to_ssa_map, saved_ssa_map, map_size); 872a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 873fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (block->successor_block_list.block_list_type != kNotUsed) { 874a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee GrowableListIterator iterator; 875fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee GrowableListIteratorInit(&block->successor_block_list.blocks, &iterator); 876a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 877fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee SuccessorBlockInfo *successor_block_info = 87852a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee reinterpret_cast<SuccessorBlockInfo*>(GrowableListIteratorNext(&iterator)); 879fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (successor_block_info == NULL) break; 880fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* succ_bb = successor_block_info->block; 881fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DoDFSPreOrderSSARename(cu, succ_bb); 882a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Restore SSA map snapshot */ 883fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee memcpy(cu->vreg_to_ssa_map, saved_ssa_map, map_size); 884a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 885a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 886fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->vreg_to_ssa_map = saved_ssa_map; 887a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return; 888f0cde549bed96e16401a347a4511b59130c61e84buzbee} 889f0cde549bed96e16401a347a4511b59130c61e84buzbee 89067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Perform SSA transformation for the whole method */ 891fa57c47f1b72916371a9c2d5c1389219bce655b4buzbeevoid SSATransformation(CompilationUnit* cu) 89267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 893a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Compute the DFS order */ 894fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ComputeDFSOrders(cu); 89567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 896fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (!cu->disable_dataflow) { 897a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Compute the dominator info */ 898fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ComputeDominators(cu); 899a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 90067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 901a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Allocate data structures in preparation for SSA conversion */ 902fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CompilerInitializeSSAConversion(cu); 90367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 904fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (!cu->disable_dataflow) { 905a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Find out the "Dalvik reg def x block" relation */ 906fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ComputeDefBlockMatrix(cu); 90767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 908a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Insert phi nodes to dominance frontiers for all variables */ 909fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee InsertPhiNodes(cu); 910a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 91167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 912a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Rename register names by local defs and phi nodes */ 913fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, ClearVisitedFlag, 914fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee kAllNodes, false /* is_iterative */); 915fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DoDFSPreOrderSSARename(cu, cu->entry_block); 916a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 917fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (!cu->disable_dataflow) { 918a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 919a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * Shared temp bit vector used by each block to count the number of defs 920a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * from all the predecessor blocks. 921a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 922fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->temp_ssa_register_v = AllocBitVector(cu, cu->num_ssa_regs, 923a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee false, kBitMapTempSSARegisterV); 924a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 925fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee cu->temp_ssa_block_id_v = 926fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee static_cast<int*>(NewMem(cu, sizeof(int) * cu->num_ssa_regs, false, kAllocDFInfo)); 9272cfc639fc803bf67e3d2a961f2b637220c86d5f7buzbee 928a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Insert phi-operands with latest SSA names from predecessor blocks */ 929fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DataFlowAnalysisDispatcher(cu, InsertPhiNodeOperands, 930fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee kReachableNodes, false /* is_iterative */); 931a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 93267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 93311d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughes 93411d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughes} // namespace art 935