graph_checker.cc revision 9ee66183d8e046ea661f642ba884626f16b46e06
1/* 2 * Copyright (C) 2014 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 "graph_checker.h" 18 19#include <map> 20#include <sstream> 21#include <string> 22 23#include "base/bit_vector-inl.h" 24 25namespace art { 26 27void GraphChecker::VisitBasicBlock(HBasicBlock* block) { 28 current_block_ = block; 29 30 // Check consistency with respect to predecessors of `block`. 31 const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors(); 32 std::map<HBasicBlock*, size_t> predecessors_count; 33 for (size_t i = 0, e = predecessors.Size(); i < e; ++i) { 34 HBasicBlock* p = predecessors.Get(i); 35 ++predecessors_count[p]; 36 } 37 for (auto& pc : predecessors_count) { 38 HBasicBlock* p = pc.first; 39 size_t p_count_in_block_predecessors = pc.second; 40 const GrowableArray<HBasicBlock*>& p_successors = p->GetSuccessors(); 41 size_t block_count_in_p_successors = 0; 42 for (size_t j = 0, f = p_successors.Size(); j < f; ++j) { 43 if (p_successors.Get(j) == block) { 44 ++block_count_in_p_successors; 45 } 46 } 47 if (p_count_in_block_predecessors != block_count_in_p_successors) { 48 std::stringstream error; 49 error << "Block " << block->GetBlockId() 50 << " lists " << p_count_in_block_predecessors 51 << " occurrences of block " << p->GetBlockId() 52 << " in its predecessors, whereas block " << p->GetBlockId() 53 << " lists " << block_count_in_p_successors 54 << " occurrences of block " << block->GetBlockId() 55 << " in its successors."; 56 errors_.push_back(error.str()); 57 } 58 } 59 60 // Check consistency with respect to successors of `block`. 61 const GrowableArray<HBasicBlock*>& successors = block->GetSuccessors(); 62 std::map<HBasicBlock*, size_t> successors_count; 63 for (size_t i = 0, e = successors.Size(); i < e; ++i) { 64 HBasicBlock* s = successors.Get(i); 65 ++successors_count[s]; 66 } 67 for (auto& sc : successors_count) { 68 HBasicBlock* s = sc.first; 69 size_t s_count_in_block_successors = sc.second; 70 const GrowableArray<HBasicBlock*>& s_predecessors = s->GetPredecessors(); 71 size_t block_count_in_s_predecessors = 0; 72 for (size_t j = 0, f = s_predecessors.Size(); j < f; ++j) { 73 if (s_predecessors.Get(j) == block) { 74 ++block_count_in_s_predecessors; 75 } 76 } 77 if (s_count_in_block_successors != block_count_in_s_predecessors) { 78 std::stringstream error; 79 error << "Block " << block->GetBlockId() 80 << " lists " << s_count_in_block_successors 81 << " occurrences of block " << s->GetBlockId() 82 << " in its successors, whereas block " << s->GetBlockId() 83 << " lists " << block_count_in_s_predecessors 84 << " occurrences of block " << block->GetBlockId() 85 << " in its predecessors."; 86 errors_.push_back(error.str()); 87 } 88 } 89 90 // Ensure `block` ends with a branch instruction. 91 HInstruction* last_inst = block->GetLastInstruction(); 92 if (last_inst == nullptr || !last_inst->IsControlFlow()) { 93 std::stringstream error; 94 error << "Block " << block->GetBlockId() 95 << " does not end with a branch instruction."; 96 errors_.push_back(error.str()); 97 } 98 99 // Visit this block's list of phis. 100 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 101 // Ensure this block's list of phis contains only phis. 102 if (!it.Current()->IsPhi()) { 103 std::stringstream error; 104 error << "Block " << current_block_->GetBlockId() 105 << " has a non-phi in its phi list."; 106 errors_.push_back(error.str()); 107 } 108 it.Current()->Accept(this); 109 } 110 111 // Visit this block's list of instructions. 112 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); 113 it.Advance()) { 114 // Ensure this block's list of instructions does not contains phis. 115 if (it.Current()->IsPhi()) { 116 std::stringstream error; 117 error << "Block " << current_block_->GetBlockId() 118 << " has a phi in its non-phi list."; 119 errors_.push_back(error.str()); 120 } 121 it.Current()->Accept(this); 122 } 123} 124 125void GraphChecker::VisitInstruction(HInstruction* instruction) { 126 if (seen_ids_.IsBitSet(instruction->GetId())) { 127 std::stringstream error; 128 error << "Duplicate id in graph " << instruction->GetId() << "."; 129 errors_.push_back(error.str()); 130 } else { 131 seen_ids_.SetBit(instruction->GetId()); 132 } 133 134 // Ensure `instruction` is associated with `current_block_`. 135 if (instruction->GetBlock() != current_block_) { 136 std::stringstream error; 137 if (instruction->IsPhi()) { 138 error << "Phi "; 139 } else { 140 error << "Instruction "; 141 } 142 error << instruction->GetId() << " in block " 143 << current_block_->GetBlockId(); 144 if (instruction->GetBlock() != nullptr) { 145 error << " associated with block " 146 << instruction->GetBlock()->GetBlockId() << "."; 147 } else { 148 error << " not associated with any block."; 149 } 150 errors_.push_back(error.str()); 151 } 152 153 // Ensure the inputs of `instruction` are defined in a block of the graph. 154 for (HInputIterator input_it(instruction); !input_it.Done(); 155 input_it.Advance()) { 156 HInstruction* input = input_it.Current(); 157 const HInstructionList& list = input->IsPhi() 158 ? input->GetBlock()->GetPhis() 159 : input->GetBlock()->GetInstructions(); 160 if (!list.Contains(input)) { 161 std::stringstream error; 162 error << "Input " << input->GetId() 163 << " of instruction " << instruction->GetId() 164 << " is not defined in a basic block of the control-flow graph."; 165 errors_.push_back(error.str()); 166 } 167 } 168 169 // Ensure the uses of `instruction` are defined in a block of the graph. 170 for (HUseIterator<HInstruction> use_it(instruction->GetUses()); 171 !use_it.Done(); use_it.Advance()) { 172 HInstruction* use = use_it.Current()->GetUser(); 173 const HInstructionList& list = use->IsPhi() 174 ? use->GetBlock()->GetPhis() 175 : use->GetBlock()->GetInstructions(); 176 if (!list.Contains(use)) { 177 std::stringstream error; 178 error << "User " << use->GetId() 179 << " of instruction " << instruction->GetId() 180 << " is not defined in a basic block of the control-flow graph."; 181 errors_.push_back(error.str()); 182 } 183 } 184} 185 186void SSAChecker::VisitBasicBlock(HBasicBlock* block) { 187 super_type::VisitBasicBlock(block); 188 189 // Ensure there is no critical edge (i.e., an edge connecting a 190 // block with multiple successors to a block with multiple 191 // predecessors). 192 if (block->GetSuccessors().Size() > 1) { 193 for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { 194 HBasicBlock* successor = block->GetSuccessors().Get(j); 195 if (successor->GetPredecessors().Size() > 1) { 196 std::stringstream error; 197 error << "Critical edge between blocks " << block->GetBlockId() 198 << " and " << successor->GetBlockId() << "."; 199 errors_.push_back(error.str()); 200 } 201 } 202 } 203 204 if (block->IsLoopHeader()) { 205 CheckLoop(block); 206 } 207} 208 209void SSAChecker::CheckLoop(HBasicBlock* loop_header) { 210 int id = loop_header->GetBlockId(); 211 212 // Ensure the pre-header block is first in the list of 213 // predecessors of a loop header. 214 if (!loop_header->IsLoopPreHeaderFirstPredecessor()) { 215 std::stringstream error; 216 error << "Loop pre-header is not the first predecessor of the loop header " 217 << id << "."; 218 errors_.push_back(error.str()); 219 } 220 221 // Ensure the loop header has only two predecessors and that only the 222 // second one is a back edge. 223 if (loop_header->GetPredecessors().Size() < 2) { 224 std::stringstream error; 225 error << "Loop header " << id << " has less than two predecessors."; 226 errors_.push_back(error.str()); 227 } else if (loop_header->GetPredecessors().Size() > 2) { 228 std::stringstream error; 229 error << "Loop header " << id << " has more than two predecessors."; 230 errors_.push_back(error.str()); 231 } else { 232 HLoopInformation* loop_information = loop_header->GetLoopInformation(); 233 HBasicBlock* first_predecessor = loop_header->GetPredecessors().Get(0); 234 if (loop_information->IsBackEdge(first_predecessor)) { 235 std::stringstream error; 236 error << "First predecessor of loop header " << id << " is a back edge."; 237 errors_.push_back(error.str()); 238 } 239 HBasicBlock* second_predecessor = loop_header->GetPredecessors().Get(1); 240 if (!loop_information->IsBackEdge(second_predecessor)) { 241 std::stringstream error; 242 error << "Second predecessor of loop header " << id 243 << " is not a back edge."; 244 errors_.push_back(error.str()); 245 } 246 } 247 248 // Ensure there is only one back edge per loop. 249 size_t num_back_edges = 250 loop_header->GetLoopInformation()->GetBackEdges().Size(); 251 if (num_back_edges != 1) { 252 std::stringstream error; 253 error << "Loop defined by header " << id << " has " 254 << num_back_edges << " back edge(s)."; 255 errors_.push_back(error.str()); 256 } 257 258 // Ensure all blocks in the loop are dominated by the loop header. 259 const ArenaBitVector& loop_blocks = 260 loop_header->GetLoopInformation()->GetBlocks(); 261 for (uint32_t i : loop_blocks.Indexes()) { 262 HBasicBlock* loop_block = GetGraph()->GetBlocks().Get(i); 263 if (!loop_header->Dominates(loop_block)) { 264 std::stringstream error; 265 error << "Loop block " << loop_block->GetBlockId() 266 << " not dominated by loop header " << id; 267 errors_.push_back(error.str()); 268 } 269 } 270} 271 272void SSAChecker::VisitInstruction(HInstruction* instruction) { 273 super_type::VisitInstruction(instruction); 274 275 // Ensure an instruction dominates all its uses. 276 for (HUseIterator<HInstruction> use_it(instruction->GetUses()); 277 !use_it.Done(); use_it.Advance()) { 278 HInstruction* use = use_it.Current()->GetUser(); 279 if (!use->IsPhi() && !instruction->StrictlyDominates(use)) { 280 std::stringstream error; 281 error << "Instruction " << instruction->GetId() 282 << " in block " << current_block_->GetBlockId() 283 << " does not dominate use " << use->GetId() 284 << " in block " << use->GetBlock()->GetBlockId() << "."; 285 errors_.push_back(error.str()); 286 } 287 } 288 289 // Ensure an instruction having an environment is dominated by the 290 // instructions contained in the environment. 291 HEnvironment* environment = instruction->GetEnvironment(); 292 if (environment != nullptr) { 293 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 294 HInstruction* env_instruction = environment->GetInstructionAt(i); 295 if (env_instruction != nullptr 296 && !env_instruction->StrictlyDominates(instruction)) { 297 std::stringstream error; 298 error << "Instruction " << env_instruction->GetId() 299 << " in environment of instruction " << instruction->GetId() 300 << " from block " << current_block_->GetBlockId() 301 << " does not dominate instruction " << instruction->GetId() 302 << "."; 303 errors_.push_back(error.str()); 304 } 305 } 306 } 307} 308 309void SSAChecker::VisitPhi(HPhi* phi) { 310 VisitInstruction(phi); 311 312 // Ensure the first input of a phi is not itself. 313 if (phi->InputAt(0) == phi) { 314 std::stringstream error; 315 error << "Loop phi " << phi->GetId() 316 << " in block " << phi->GetBlock()->GetBlockId() 317 << " is its own first input."; 318 errors_.push_back(error.str()); 319 } 320 321 // Ensure the number of phi inputs is the same as the number of 322 // its predecessors. 323 const GrowableArray<HBasicBlock*>& predecessors = 324 phi->GetBlock()->GetPredecessors(); 325 if (phi->InputCount() != predecessors.Size()) { 326 std::stringstream error; 327 error << "Phi " << phi->GetId() 328 << " in block " << phi->GetBlock()->GetBlockId() 329 << " has " << phi->InputCount() << " inputs, but block " 330 << phi->GetBlock()->GetBlockId() << " has " 331 << predecessors.Size() << " predecessors."; 332 errors_.push_back(error.str()); 333 } else { 334 // Ensure phi input at index I either comes from the Ith 335 // predecessor or from a block that dominates this predecessor. 336 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 337 HInstruction* input = phi->InputAt(i); 338 HBasicBlock* predecessor = predecessors.Get(i); 339 if (!(input->GetBlock() == predecessor 340 || input->GetBlock()->Dominates(predecessor))) { 341 std::stringstream error; 342 error << "Input " << input->GetId() << " at index " << i 343 << " of phi " << phi->GetId() 344 << " from block " << phi->GetBlock()->GetBlockId() 345 << " is not defined in predecessor number " << i 346 << " nor in a block dominating it."; 347 errors_.push_back(error.str()); 348 } 349 } 350 } 351} 352 353static Primitive::Type PrimitiveKind(Primitive::Type type) { 354 switch (type) { 355 case Primitive::kPrimBoolean: 356 case Primitive::kPrimByte: 357 case Primitive::kPrimShort: 358 case Primitive::kPrimChar: 359 case Primitive::kPrimInt: 360 return Primitive::kPrimInt; 361 default: 362 return type; 363 } 364} 365 366void SSAChecker::VisitIf(HIf* instruction) { 367 VisitInstruction(instruction); 368 HInstruction* input = instruction->InputAt(0); 369 if (input->IsIntConstant()) { 370 int value = input->AsIntConstant()->GetValue(); 371 if (value != 0 && value != 1) { 372 std::stringstream error; 373 error << "If instruction " << instruction->GetId() 374 << " has a non-boolean constant input whose value is: " 375 << value << "."; 376 errors_.push_back(error.str()); 377 } 378 } else if (instruction->InputAt(0)->GetType() != Primitive::kPrimBoolean) { 379 std::stringstream error; 380 error << "If instruction " << instruction->GetId() 381 << " has a non-boolean input type: " 382 << instruction->InputAt(0)->GetType() << "."; 383 errors_.push_back(error.str()); 384 } 385} 386 387void SSAChecker::VisitCondition(HCondition* op) { 388 VisitInstruction(op); 389 if (op->GetType() != Primitive::kPrimBoolean) { 390 std::stringstream error; 391 error << "Condition " << op->DebugName() << " " << op->GetId() 392 << " has a non-boolean result type: " 393 << op->GetType() << "."; 394 errors_.push_back(error.str()); 395 } 396 HInstruction* lhs = op->InputAt(0); 397 HInstruction* rhs = op->InputAt(1); 398 if (lhs->GetType() == Primitive::kPrimNot && rhs->IsIntConstant()) { 399 if (rhs->AsIntConstant()->GetValue() != 0) { 400 std::stringstream error; 401 error << "Condition " << op->DebugName() << " " << op->GetId() 402 << " compares an object with a non-0 integer: " 403 << rhs->AsIntConstant()->GetValue() 404 << "."; 405 errors_.push_back(error.str()); 406 } 407 } else if (rhs->GetType() == Primitive::kPrimNot && lhs->IsIntConstant()) { 408 if (lhs->AsIntConstant()->GetValue() != 0) { 409 std::stringstream error; 410 error << "Condition " << op->DebugName() << " " << op->GetId() 411 << " compares a non-0 integer with an object: " 412 << lhs->AsIntConstant()->GetValue() 413 << "."; 414 errors_.push_back(error.str()); 415 } 416 } else if (PrimitiveKind(lhs->GetType()) != PrimitiveKind(rhs->GetType())) { 417 std::stringstream error; 418 error << "Condition " << op->DebugName() << " " << op->GetId() 419 << " has inputs of different type: " 420 << lhs->GetType() << ", and " << rhs->GetType() 421 << "."; 422 errors_.push_back(error.str()); 423 } 424} 425 426void SSAChecker::VisitBinaryOperation(HBinaryOperation* op) { 427 VisitInstruction(op); 428 if (op->IsUShr() || op->IsShr() || op->IsShl()) { 429 if (PrimitiveKind(op->InputAt(1)->GetType()) != Primitive::kPrimInt) { 430 std::stringstream error; 431 error << "Shift operation " << op->DebugName() << " " << op->GetId() 432 << " has a non-int kind second input: " 433 << op->InputAt(1)->DebugName() << " of type " << op->InputAt(1)->GetType() 434 << "."; 435 errors_.push_back(error.str()); 436 } 437 } else { 438 if (PrimitiveKind(op->InputAt(1)->GetType()) != PrimitiveKind(op->InputAt(0)->GetType())) { 439 std::stringstream error; 440 error << "Binary operation " << op->DebugName() << " " << op->GetId() 441 << " has inputs of different type: " 442 << op->InputAt(0)->GetType() << ", and " << op->InputAt(1)->GetType() 443 << "."; 444 errors_.push_back(error.str()); 445 } 446 } 447 448 if (op->IsCompare()) { 449 if (op->GetType() != Primitive::kPrimInt) { 450 std::stringstream error; 451 error << "Compare operation " << op->GetId() 452 << " has a non-int result type: " 453 << op->GetType() << "."; 454 errors_.push_back(error.str()); 455 } 456 } else { 457 // Use the first input, so that we can also make this check for shift operations. 458 if (PrimitiveKind(op->GetType()) != PrimitiveKind(op->InputAt(0)->GetType())) { 459 std::stringstream error; 460 error << "Binary operation " << op->DebugName() << " " << op->GetId() 461 << " has a result type different than its input type: " 462 << op->GetType() << ", and " << op->InputAt(1)->GetType() 463 << "."; 464 errors_.push_back(error.str()); 465 } 466 } 467} 468 469} // namespace art 470