1 // Copyright (c) 2015-2016 The Khronos Group Inc. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "source/val/validate.h" 16 17 #include <cassert> 18 19 #include <algorithm> 20 #include <iostream> 21 #include <iterator> 22 #include <stack> 23 #include <string> 24 #include <unordered_set> 25 #include <utility> 26 #include <vector> 27 28 #include "source/diagnostic.h" 29 #include "source/instruction.h" 30 #include "source/opcode.h" 31 #include "source/operand.h" 32 #include "source/spirv_validator_options.h" 33 #include "source/val/function.h" 34 #include "source/val/validation_state.h" 35 #include "spirv-tools/libspirv.h" 36 37 namespace spvtools { 38 namespace val { 39 40 spv_result_t UpdateIdUse(ValidationState_t& _, const Instruction* inst) { 41 for (auto& operand : inst->operands()) { 42 const spv_operand_type_t& type = operand.type; 43 const uint32_t operand_id = inst->word(operand.offset); 44 if (spvIsIdType(type) && type != SPV_OPERAND_TYPE_RESULT_ID) { 45 if (auto def = _.FindDef(operand_id)) 46 def->RegisterUse(inst, operand.offset); 47 } 48 } 49 50 return SPV_SUCCESS; 51 } 52 53 /// This function checks all ID definitions dominate their use in the CFG. 54 /// 55 /// This function will iterate over all ID definitions that are defined in the 56 /// functions of a module and make sure that the definitions appear in a 57 /// block that dominates their use. 58 /// 59 /// NOTE: This function does NOT check module scoped functions which are 60 /// checked during the initial binary parse in the IdPass below 61 spv_result_t CheckIdDefinitionDominateUse(ValidationState_t& _) { 62 std::vector<const Instruction*> phi_instructions; 63 std::unordered_set<uint32_t> phi_ids; 64 for (const auto& inst : _.ordered_instructions()) { 65 if (inst.id() == 0) continue; 66 if (const Function* func = inst.function()) { 67 if (const BasicBlock* block = inst.block()) { 68 // If the Id is defined within a block then make sure all references to 69 // that Id appear in a blocks that are dominated by the defining block 70 for (auto& use_index_pair : inst.uses()) { 71 const Instruction* use = use_index_pair.first; 72 if (const BasicBlock* use_block = use->block()) { 73 if (use_block->reachable() == false) continue; 74 if (use->opcode() == SpvOpPhi) { 75 if (phi_ids.insert(use->id()).second) { 76 phi_instructions.push_back(use); 77 } 78 } else if (!block->dominates(*use->block())) { 79 return _.diag(SPV_ERROR_INVALID_ID, use_block->label()) 80 << "ID " << _.getIdName(inst.id()) << " defined in block " 81 << _.getIdName(block->id()) 82 << " does not dominate its use in block " 83 << _.getIdName(use_block->id()); 84 } 85 } 86 } 87 } else { 88 // If the Ids defined within a function but not in a block(i.e. function 89 // parameters, block ids), then make sure all references to that Id 90 // appear within the same function 91 for (auto use : inst.uses()) { 92 const Instruction* user = use.first; 93 if (user->function() && user->function() != func) { 94 return _.diag(SPV_ERROR_INVALID_ID, _.FindDef(func->id())) 95 << "ID " << _.getIdName(inst.id()) << " used in function " 96 << _.getIdName(user->function()->id()) 97 << " is used outside of it's defining function " 98 << _.getIdName(func->id()); 99 } 100 } 101 } 102 } 103 // NOTE: Ids defined outside of functions must appear before they are used 104 // This check is being performed in the IdPass function 105 } 106 107 // Check all OpPhi parent blocks are dominated by the variable's defining 108 // blocks 109 for (const Instruction* phi : phi_instructions) { 110 if (phi->block()->reachable() == false) continue; 111 for (size_t i = 3; i < phi->operands().size(); i += 2) { 112 const Instruction* variable = _.FindDef(phi->word(i)); 113 const BasicBlock* parent = 114 phi->function()->GetBlock(phi->word(i + 1)).first; 115 if (variable->block() && parent->reachable() && 116 !variable->block()->dominates(*parent)) { 117 return _.diag(SPV_ERROR_INVALID_ID, phi) 118 << "In OpPhi instruction " << _.getIdName(phi->id()) << ", ID " 119 << _.getIdName(variable->id()) 120 << " definition does not dominate its parent " 121 << _.getIdName(parent->id()); 122 } 123 } 124 } 125 126 return SPV_SUCCESS; 127 } 128 129 // Performs SSA validation on the IDs of an instruction. The 130 // can_have_forward_declared_ids functor should return true if the 131 // instruction operand's ID can be forward referenced. 132 spv_result_t IdPass(ValidationState_t& _, Instruction* inst) { 133 auto can_have_forward_declared_ids = 134 spvOperandCanBeForwardDeclaredFunction(inst->opcode()); 135 136 // Keep track of a result id defined by this instruction. 0 means it 137 // does not define an id. 138 uint32_t result_id = 0; 139 140 for (unsigned i = 0; i < inst->operands().size(); i++) { 141 const spv_parsed_operand_t& operand = inst->operand(i); 142 const spv_operand_type_t& type = operand.type; 143 // We only care about Id operands, which are a single word. 144 const uint32_t operand_word = inst->word(operand.offset); 145 146 auto ret = SPV_ERROR_INTERNAL; 147 switch (type) { 148 case SPV_OPERAND_TYPE_RESULT_ID: 149 // NOTE: Multiple Id definitions are being checked by the binary parser. 150 // 151 // Defer undefined-forward-reference removal until after we've analyzed 152 // the remaining operands to this instruction. Deferral only matters 153 // for OpPhi since it's the only case where it defines its own forward 154 // reference. Other instructions that can have forward references 155 // either don't define a value or the forward reference is to a function 156 // Id (and hence defined outside of a function body). 157 result_id = operand_word; 158 // NOTE: The result Id is added (in RegisterInstruction) *after* all of 159 // the other Ids have been checked to avoid premature use in the same 160 // instruction. 161 ret = SPV_SUCCESS; 162 break; 163 case SPV_OPERAND_TYPE_ID: 164 case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID: 165 case SPV_OPERAND_TYPE_SCOPE_ID: 166 if (const auto def = _.FindDef(operand_word)) { 167 const auto opcode = inst->opcode(); 168 if (spvOpcodeGeneratesType(def->opcode()) && 169 !spvOpcodeGeneratesType(opcode) && !spvOpcodeIsDebug(opcode) && 170 !spvOpcodeIsDecoration(opcode) && opcode != SpvOpFunction) { 171 return _.diag(SPV_ERROR_INVALID_ID, inst) 172 << "Operand " << _.getIdName(operand_word) 173 << " cannot be a type"; 174 } else if (def->type_id() == 0 && !spvOpcodeGeneratesType(opcode) && 175 !spvOpcodeIsDebug(opcode) && 176 !spvOpcodeIsDecoration(opcode) && 177 !spvOpcodeIsBranch(opcode) && opcode != SpvOpPhi && 178 opcode != SpvOpExtInst && opcode != SpvOpExtInstImport && 179 opcode != SpvOpSelectionMerge && 180 opcode != SpvOpLoopMerge && opcode != SpvOpFunction) { 181 return _.diag(SPV_ERROR_INVALID_ID, inst) 182 << "Operand " << _.getIdName(operand_word) 183 << " requires a type"; 184 } else { 185 ret = SPV_SUCCESS; 186 } 187 } else if (can_have_forward_declared_ids(i)) { 188 ret = _.ForwardDeclareId(operand_word); 189 } else { 190 ret = _.diag(SPV_ERROR_INVALID_ID, inst) 191 << "ID " << _.getIdName(operand_word) 192 << " has not been defined"; 193 } 194 break; 195 case SPV_OPERAND_TYPE_TYPE_ID: 196 if (_.IsDefinedId(operand_word)) { 197 auto* def = _.FindDef(operand_word); 198 if (!spvOpcodeGeneratesType(def->opcode())) { 199 ret = _.diag(SPV_ERROR_INVALID_ID, inst) 200 << "ID " << _.getIdName(operand_word) << " is not a type id"; 201 } else { 202 ret = SPV_SUCCESS; 203 } 204 } else { 205 ret = _.diag(SPV_ERROR_INVALID_ID, inst) 206 << "ID " << _.getIdName(operand_word) 207 << " has not been defined"; 208 } 209 break; 210 default: 211 ret = SPV_SUCCESS; 212 break; 213 } 214 if (SPV_SUCCESS != ret) return ret; 215 } 216 if (result_id) _.RemoveIfForwardDeclared(result_id); 217 218 return SPV_SUCCESS; 219 } 220 221 } // namespace val 222 } // namespace spvtools 223
