1// Copyright (c) 2017 Google 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#ifndef SOURCE_OPT_CCP_PASS_H_
16#define SOURCE_OPT_CCP_PASS_H_
17
18#include <memory>
19#include <unordered_map>
20
21#include "source/opt/constants.h"
22#include "source/opt/function.h"
23#include "source/opt/ir_context.h"
24#include "source/opt/mem_pass.h"
25#include "source/opt/module.h"
26#include "source/opt/propagator.h"
27
28namespace spvtools {
29namespace opt {
30
31class CCPPass : public MemPass {
32 public:
33 CCPPass() = default;
34
35 const char* name() const override { return "ccp"; }
36 Status Process() override;
37
38 IRContext::Analysis GetPreservedAnalyses() override {
39 return IRContext::kAnalysisDefUse |
40 IRContext::kAnalysisInstrToBlockMapping |
41 IRContext::kAnalysisDecorations | IRContext::kAnalysisCombinators |
42 IRContext::kAnalysisCFG | IRContext::kAnalysisDominatorAnalysis |
43 IRContext::kAnalysisNameMap | IRContext::kAnalysisConstants |
44 IRContext::kAnalysisTypes;
45 }
46
47 private:
48 // Initializes the pass.
49 void Initialize();
50
51 // Runs constant propagation on the given function |fp|. Returns true if any
52 // constants were propagated and the IR modified.
53 bool PropagateConstants(Function* fp);
54
55 // Visits a single instruction |instr|. If the instruction is a conditional
56 // branch that always jumps to the same basic block, it sets the destination
57 // block in |dest_bb|.
58 SSAPropagator::PropStatus VisitInstruction(Instruction* instr,
59 BasicBlock** dest_bb);
60
61 // Visits an OpPhi instruction |phi|. This applies the meet operator for the
62 // CCP lattice. Essentially, if all the operands in |phi| have the same
63 // constant value C, the result for |phi| gets assigned the value C.
64 SSAPropagator::PropStatus VisitPhi(Instruction* phi);
65
66 // Visits an SSA assignment instruction |instr|. If the RHS of |instr| folds
67 // into a constant value C, then the LHS of |instr| is assigned the value C in
68 // |values_|.
69 SSAPropagator::PropStatus VisitAssignment(Instruction* instr);
70
71 // Visits a branch instruction |instr|. If the branch is conditional
72 // (OpBranchConditional or OpSwitch), and the value of its selector is known,
73 // |dest_bb| will be set to the corresponding destination block. Unconditional
74 // branches always set |dest_bb| to the single destination block.
75 SSAPropagator::PropStatus VisitBranch(Instruction* instr,
76 BasicBlock** dest_bb) const;
77
78 // Replaces all operands used in |fp| with the corresponding constant values
79 // in |values_|. Returns true if any operands were replaced, and false
80 // otherwise.
81 bool ReplaceValues();
82
83 // Marks |instr| as varying by registering a varying value for its result
84 // into the |values_| table. Returns SSAPropagator::kVarying.
85 SSAPropagator::PropStatus MarkInstructionVarying(Instruction* instr);
86
87 // Returns true if |id| is the special SSA id that corresponds to a varying
88 // value.
89 bool IsVaryingValue(uint32_t id) const;
90
91 // Constant manager for the parent IR context. Used to record new constants
92 // generated during propagation.
93 analysis::ConstantManager* const_mgr_;
94
95 // Constant value table. Each entry <id, const_decl_id> in this map
96 // represents the compile-time constant value for |id| as declared by
97 // |const_decl_id|. Each |const_decl_id| in this table is an OpConstant
98 // declaration for the current module.
99 //
100 // Additionally, this table keeps track of SSA IDs with varying values. If an
101 // SSA ID is found to have a varying value, it will have an entry in this
102 // table that maps to the special SSA id kVaryingSSAId. These values are
103 // never replaced in the IR, they are used by CCP during propagation.
104 std::unordered_map<uint32_t, uint32_t> values_;
105
106 // Propagator engine used.
107 std::unique_ptr<SSAPropagator> propagator_;
108};
109
110} // namespace opt
111} // namespace spvtools
112
113#endif // SOURCE_OPT_CCP_PASS_H_
114