| 729 | } |
| 730 | |
| 731 | spv_result_t StructuredControlFlowChecks( |
| 732 | ValidationState_t& _, Function* function, |
| 733 | const std::vector<std::pair<uint32_t, uint32_t>>& back_edges, |
| 734 | const std::vector<const BasicBlock*>& postorder) { |
| 735 | /// Check all backedges target only loop headers and have exactly one |
| 736 | /// back-edge branching to it |
| 737 | |
| 738 | // Map a loop header to blocks with back-edges to the loop header. |
| 739 | std::map<uint32_t, std::unordered_set<uint32_t>> loop_latch_blocks; |
| 740 | for (auto back_edge : back_edges) { |
| 741 | uint32_t back_edge_block; |
| 742 | uint32_t header_block; |
| 743 | std::tie(back_edge_block, header_block) = back_edge; |
| 744 | if (!function->IsBlockType(header_block, kBlockTypeLoop)) { |
| 745 | return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(back_edge_block)) |
| 746 | << "Back-edges (" << _.getIdName(back_edge_block) << " -> " |
| 747 | << _.getIdName(header_block) |
| 748 | << ") can only be formed between a block and a loop header."; |
| 749 | } |
| 750 | loop_latch_blocks[header_block].insert(back_edge_block); |
| 751 | } |
| 752 | |
| 753 | // Check the loop headers have exactly one back-edge branching to it |
| 754 | for (BasicBlock* loop_header : function->ordered_blocks()) { |
| 755 | if (!loop_header->structurally_reachable()) continue; |
| 756 | if (!loop_header->is_type(kBlockTypeLoop)) continue; |
| 757 | auto loop_header_id = loop_header->id(); |
| 758 | auto num_latch_blocks = loop_latch_blocks[loop_header_id].size(); |
| 759 | if (num_latch_blocks != 1) { |
| 760 | return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(loop_header_id)) |
| 761 | << "Loop header " << _.getIdName(loop_header_id) |
| 762 | << " is targeted by " << num_latch_blocks |
| 763 | << " back-edge blocks but the standard requires exactly one"; |
| 764 | } |
| 765 | } |
| 766 | |
| 767 | // Check construct rules |
| 768 | for (const Construct& construct : function->constructs()) { |
| 769 | auto header = construct.entry_block(); |
| 770 | if (!header->structurally_reachable()) continue; |
| 771 | auto merge = construct.exit_block(); |
| 772 | |
| 773 | if (!merge) { |
| 774 | std::string construct_name, header_name, exit_name; |
| 775 | std::tie(construct_name, header_name, exit_name) = |
| 776 | ConstructNames(construct.type()); |
| 777 | return _.diag(SPV_ERROR_INTERNAL, _.FindDef(header->id())) |
| 778 | << "Construct " + construct_name + " with " + header_name + " " + |
| 779 | _.getIdName(header->id()) + " does not have a " + |
| 780 | exit_name + ". This may be a bug in the validator."; |
| 781 | } |
| 782 | |
| 783 | // If the header is reachable, the merge is guaranteed to be structurally |
| 784 | // reachable. |
| 785 | if (!header->structurally_dominates(*merge)) { |
| 786 | return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id())) |
| 787 | << ConstructErrorString(construct, _.getIdName(header->id()), |
| 788 | _.getIdName(merge->id()), |
no test coverage detected