Debian Codegraph @

third_party/spirv-tools/source/reduce/structured_loop_to_selection_reduction_opportunity.h

raw
1 // Copyright (c) 2018 Google LLC
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 #ifndef SOURCE_REDUCE_CUT_LOOP_REDUCTION_OPPORTUNITY_H_
16 #define SOURCE_REDUCE_CUT_LOOP_REDUCTION_OPPORTUNITY_H_
17
18 #include "source/opt/def_use_manager.h"
19 #include "source/opt/dominator_analysis.h"
20 #include "source/opt/function.h"
21 #include "source/reduce/reduction_opportunity.h"
22
23 namespace spvtools {
24 namespace reduce {
25
26 // An opportunity to replace a structured loop with a selection.
27 class StructuredLoopToSelectionReductionOpportunity
28 : public ReductionOpportunity {
29 public:
30 // Constructs an opportunity from a loop header block and the function that
31 // encloses it.
32 explicit StructuredLoopToSelectionReductionOpportunity(
33 opt::IRContext* context, opt::BasicBlock* loop_construct_header,
34 opt::Function* enclosing_function)
35 : context_(context),
36 loop_construct_header_(loop_construct_header),
37 enclosing_function_(enclosing_function) {}
38
39 // Returns true if the loop header is reachable. A structured loop might
40 // become unreachable as a result of turning another structured loop into
41 // a selection.
42 bool PreconditionHolds() override;
43
44 protected:
45 void Apply() override;
46
47 private:
48 // Parameter |original_target_id| is the id of the loop's merge block or
49 // continue target. This method considers each edge of the form
50 // b->original_target_id and transforms it into an edge of the form b->c,
51 // where c is the merge block of the structured control flow construct that
52 // most tightly contains b.
53 void RedirectToClosestMergeBlock(uint32_t original_target_id);
54
55 // |source_id|, |original_target_id| and |new_target_id| are required to all
56 // be distinct, with a CFG edge existing from |source_id| to
57 // |original_target_id|, and |original_target_id| being either the merge block
58 // or continue target for the loop being operated on.
59 // The method removes this edge and adds an edge from
60 // |source_id| to |new_target_id|. It takes care of fixing up any OpPhi
61 // instructions associated with |original_target_id| and |new_target_id|.
62 void RedirectEdge(uint32_t source_id, uint32_t original_target_id,
63 uint32_t new_target_id);
64
65 // Adds components to |to_block|'s phi instructions to account for a new
66 // incoming edge from |from_id|.
67 void AdaptPhiInstructionsForAddedEdge(uint32_t from_id,
68 opt::BasicBlock* to_block);
69
70 // Turns the OpLoopMerge for the loop into OpSelectionMerge, and adapts the
71 // following branch instruction accordingly.
72 void ChangeLoopToSelection();
73
74 // Fixes any scenarios where, due to CFG changes, ids have uses not dominated
75 // by their definitions, by changing such uses to uses of OpUndef or of
76 // placeholder variables.
77 void FixNonDominatedIdUses();
78
79 // Returns true if and only if at least one of the following holds:
80 // 1) |def| dominates |use|
81 // 2) |def| is an OpVariable
82 // 3) |use| is part of an OpPhi, with associated incoming block b, and |def|
83 // dominates b.
84 bool DefinitionSufficientlyDominatesUse(opt::Instruction* def,
85 opt::Instruction* use,
86 uint32_t use_index,
87 opt::BasicBlock& def_block);
88
89 opt::IRContext* context_;
90 opt::BasicBlock* loop_construct_header_;
91 opt::Function* enclosing_function_;
92 };
93
94 } // namespace reduce
95 } // namespace spvtools
96
97 #endif // SOURCE_REDUCE_CUT_LOOP_REDUCTION_OPPORTUNITY_H_