Coverage Report

Created: 2025-06-13 06:37

/src/spirv-tools/source/val/construct.cpp
Line
Count
Source (jump to first uncovered line)
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/construct.h"
16
17
#include <cassert>
18
#include <cstddef>
19
20
#include "source/val/function.h"
21
#include "source/val/validation_state.h"
22
23
namespace spvtools {
24
namespace val {
25
26
Construct::Construct(ConstructType construct_type, BasicBlock* entry,
27
                     BasicBlock* exit, std::vector<Construct*> constructs)
28
68.7k
    : type_(construct_type),
29
68.7k
      corresponding_constructs_(constructs),
30
68.7k
      entry_block_(entry),
31
68.7k
      exit_block_(exit) {}
32
33
483k
ConstructType Construct::type() const { return type_; }
34
35
3.82k
const std::vector<Construct*>& Construct::corresponding_constructs() const {
36
3.82k
  return corresponding_constructs_;
37
3.82k
}
38
17.3k
std::vector<Construct*>& Construct::corresponding_constructs() {
39
17.3k
  return corresponding_constructs_;
40
17.3k
}
41
42
52.0k
bool ValidateConstructSize(ConstructType type, size_t size) {
43
52.0k
  switch (type) {
44
0
    case ConstructType::kSelection:
45
0
      return size == 0;
46
26.0k
    case ConstructType::kContinue:
47
26.0k
      return size == 1;
48
26.0k
    case ConstructType::kLoop:
49
26.0k
      return size == 1;
50
0
    case ConstructType::kCase:
51
0
      return size >= 1;
52
0
    default:
53
0
      assert(1 == 0 && "Type not defined");
54
52.0k
  }
55
0
  return false;
56
52.0k
}
57
58
void Construct::set_corresponding_constructs(
59
52.0k
    std::vector<Construct*> constructs) {
60
52.0k
  assert(ValidateConstructSize(type_, constructs.size()));
61
52.0k
  corresponding_constructs_ = constructs;
62
52.0k
}
63
64
97.5k
const BasicBlock* Construct::entry_block() const { return entry_block_; }
65
87.6k
BasicBlock* Construct::entry_block() { return entry_block_; }
66
67
29.9k
const BasicBlock* Construct::exit_block() const { return exit_block_; }
68
0
BasicBlock* Construct::exit_block() { return exit_block_; }
69
70
5.98k
void Construct::set_exit(BasicBlock* block) { exit_block_ = block; }
71
72
8.18k
Construct::ConstructBlockSet Construct::blocks(Function* /*function*/) const {
73
8.18k
  const auto header = entry_block();
74
8.18k
  const auto exit = exit_block();
75
8.18k
  const bool is_continue = type() == ConstructType::kContinue;
76
8.18k
  const bool is_loop = type() == ConstructType::kLoop;
77
8.18k
  const BasicBlock* continue_header = nullptr;
78
8.18k
  if (is_loop) {
79
    // The only corresponding construct for a loop is the continue.
80
1.98k
    continue_header = (*corresponding_constructs().begin())->entry_block();
81
1.98k
  }
82
8.18k
  std::vector<BasicBlock*> stack;
83
8.18k
  stack.push_back(const_cast<BasicBlock*>(header));
84
8.18k
  ConstructBlockSet construct_blocks;
85
107k
  while (!stack.empty()) {
86
99.7k
    auto* block = stack.back();
87
99.7k
    stack.pop_back();
88
89
99.7k
    if (header->structurally_dominates(*block)) {
90
92.9k
      bool include = false;
91
92.9k
      if (is_continue && exit->structurally_postdominates(*block)) {
92
        // Continue construct include blocks dominated by the continue target
93
        // and post-dominated by the back-edge block.
94
3.48k
        include = true;
95
89.4k
      } else if (!exit->structurally_dominates(*block)) {
96
        // Selection and loop constructs include blocks dominated by the header
97
        // and not dominated by the merge.
98
74.8k
        include = true;
99
74.8k
        if (is_loop && continue_header->structurally_dominates(*block)) {
100
          // Loop constructs have an additional constraint that they do not
101
          // include blocks dominated by the continue construct. Since all
102
          // blocks in the continue construct are dominated by the continue
103
          // target, we just test for dominance by continue target.
104
4.57k
          include = false;
105
4.57k
        }
106
74.8k
      }
107
92.9k
      if (include) {
108
73.7k
        if (!construct_blocks.insert(block).second) continue;
109
110
91.5k
        for (auto succ : *block->structural_successors()) {
111
91.5k
          stack.push_back(succ);
112
91.5k
        }
113
48.1k
      }
114
92.9k
    }
115
99.7k
  }
116
117
8.18k
  return construct_blocks;
118
8.18k
}
119
120
17.5k
bool Construct::IsStructuredExit(ValidationState_t& _, BasicBlock* dest) const {
121
  // Structured Exits:
122
  // - Selection:
123
  //  - branch to its merge
124
  //  - branch to nearest enclosing loop merge or continue
125
  //  - branch to nearest enclosing switch selection merge
126
  // - Loop:
127
  //  - branch to its merge
128
  //  - branch to its continue
129
  // - Continue:
130
  //  - branch to loop header
131
  //  - branch to loop merge
132
  //
133
  // Note: we will never see a case construct here.
134
17.5k
  assert(type() != ConstructType::kCase);
135
17.5k
  if (type() == ConstructType::kLoop) {
136
5.42k
    auto header = entry_block();
137
5.42k
    auto terminator = header->terminator();
138
5.42k
    auto index = terminator - &_.ordered_instructions()[0];
139
5.42k
    auto merge_inst = &_.ordered_instructions()[index - 1];
140
5.42k
    auto merge_block_id = merge_inst->GetOperandAs<uint32_t>(0u);
141
5.42k
    auto continue_block_id = merge_inst->GetOperandAs<uint32_t>(1u);
142
5.42k
    if (dest->id() == merge_block_id || dest->id() == continue_block_id) {
143
5.41k
      return true;
144
5.41k
    }
145
12.1k
  } else if (type() == ConstructType::kContinue) {
146
1.84k
    auto loop_construct = corresponding_constructs()[0];
147
1.84k
    auto header = loop_construct->entry_block();
148
1.84k
    auto terminator = header->terminator();
149
1.84k
    auto index = terminator - &_.ordered_instructions()[0];
150
1.84k
    auto merge_inst = &_.ordered_instructions()[index - 1];
151
1.84k
    auto merge_block_id = merge_inst->GetOperandAs<uint32_t>(0u);
152
1.84k
    if (dest == header || dest->id() == merge_block_id) {
153
1.83k
      return true;
154
1.83k
    }
155
10.2k
  } else {
156
10.2k
    assert(type() == ConstructType::kSelection);
157
10.2k
    if (dest == exit_block()) {
158
5.45k
      return true;
159
5.45k
    }
160
161
    // The next block in the traversal is either:
162
    //  i.  The header block that declares |block| as its merge block.
163
    //  ii. The immediate dominator of |block|.
164
9.52k
    auto NextBlock = [](const BasicBlock* block) -> const BasicBlock* {
165
12.9k
      for (auto& use : block->label()->uses()) {
166
12.9k
        if ((use.first->opcode() == spv::Op::OpLoopMerge ||
167
12.9k
             use.first->opcode() == spv::Op::OpSelectionMerge) &&
168
12.9k
            use.second == 1 &&
169
12.9k
            use.first->block()->structurally_dominates(*block) &&
170
            // A header likely declared itself as its merge.
171
12.9k
            use.first->block() != block) {
172
1.62k
          return use.first->block();
173
1.62k
        }
174
12.9k
      }
175
7.89k
      return block->immediate_structural_dominator();
176
9.52k
    };
177
178
4.82k
    bool seen_switch = false;
179
4.82k
    auto header = entry_block();
180
4.82k
    auto block = NextBlock(header);
181
9.52k
    while (block) {
182
9.48k
      auto terminator = block->terminator();
183
9.48k
      auto index = terminator - &_.ordered_instructions()[0];
184
9.48k
      auto merge_inst = &_.ordered_instructions()[index - 1];
185
9.48k
      if (merge_inst->opcode() == spv::Op::OpLoopMerge ||
186
9.48k
          (header->terminator()->opcode() != spv::Op::OpSwitch &&
187
4.90k
           merge_inst->opcode() == spv::Op::OpSelectionMerge &&
188
5.84k
           terminator->opcode() == spv::Op::OpSwitch)) {
189
5.84k
        auto merge_target = merge_inst->GetOperandAs<uint32_t>(0u);
190
5.84k
        auto merge_block = merge_inst->function()->GetBlock(merge_target).first;
191
5.84k
        if (merge_block->structurally_dominates(*header)) {
192
1.04k
          block = NextBlock(block);
193
1.04k
          continue;
194
1.04k
        }
195
196
4.80k
        if ((!seen_switch || merge_inst->opcode() == spv::Op::OpLoopMerge) &&
197
4.80k
            dest->id() == merge_target) {
198
2.96k
          return true;
199
2.96k
        } else if (merge_inst->opcode() == spv::Op::OpLoopMerge) {
200
1.82k
          auto continue_target = merge_inst->GetOperandAs<uint32_t>(1u);
201
1.82k
          if (dest->id() == continue_target) {
202
1.80k
            return true;
203
1.80k
          }
204
1.82k
        }
205
206
42
        if (terminator->opcode() == spv::Op::OpSwitch) {
207
19
          seen_switch = true;
208
19
        }
209
210
        // Hit an enclosing loop and didn't break or continue.
211
42
        if (merge_inst->opcode() == spv::Op::OpLoopMerge) return false;
212
42
      }
213
214
3.65k
      block = NextBlock(block);
215
3.65k
    }
216
4.82k
  }
217
218
53
  return false;
219
17.5k
}
220
221
}  // namespace val
222
}  // namespace spvtools