Line data Source code
1 : // Copyright 2018 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_TORQUE_CFG_H_
6 : #define V8_TORQUE_CFG_H_
7 :
8 : #include <list>
9 : #include <memory>
10 : #include <unordered_map>
11 : #include <vector>
12 :
13 : #include "src/torque/ast.h"
14 : #include "src/torque/instructions.h"
15 : #include "src/torque/source-positions.h"
16 : #include "src/torque/types.h"
17 :
18 : namespace v8 {
19 : namespace internal {
20 : namespace torque {
21 :
22 : class ControlFlowGraph;
23 :
24 15954 : class Block {
25 : public:
26 : explicit Block(ControlFlowGraph* cfg, size_t id,
27 : base::Optional<Stack<const Type*>> input_types,
28 : bool is_deferred)
29 : : cfg_(cfg),
30 : input_types_(std::move(input_types)),
31 : id_(id),
32 15954 : is_deferred_(is_deferred) {}
33 : void Add(Instruction instruction) {
34 : DCHECK(!IsComplete());
35 44672 : instructions_.push_back(std::move(instruction));
36 : }
37 :
38 : bool HasInputTypes() const { return input_types_ != base::nullopt; }
39 : const Stack<const Type*>& InputTypes() const { return *input_types_; }
40 : void SetInputTypes(const Stack<const Type*>& input_types);
41 331 : void Retype() {
42 : Stack<const Type*> current_stack = InputTypes();
43 2023 : for (const Instruction& instruction : instructions()) {
44 1692 : instruction.TypeInstruction(¤t_stack, cfg_);
45 : }
46 331 : }
47 :
48 : const std::vector<Instruction>& instructions() const { return instructions_; }
49 : bool IsComplete() const {
50 18042 : return !instructions_.empty() && instructions_.back()->IsBlockTerminator();
51 : }
52 : size_t id() const { return id_; }
53 : bool IsDeferred() const { return is_deferred_; }
54 :
55 : private:
56 : ControlFlowGraph* cfg_;
57 : std::vector<Instruction> instructions_;
58 : base::Optional<Stack<const Type*>> input_types_;
59 : const size_t id_;
60 : bool is_deferred_;
61 : };
62 :
63 9359 : class ControlFlowGraph {
64 : public:
65 2674 : explicit ControlFlowGraph(Stack<const Type*> input_types) {
66 2674 : start_ = NewBlock(std::move(input_types), false);
67 1337 : PlaceBlock(start_);
68 1337 : }
69 :
70 7977 : Block* NewBlock(base::Optional<Stack<const Type*>> input_types,
71 : bool is_deferred) {
72 15954 : blocks_.emplace_back(this, next_block_id_++, std::move(input_types),
73 : is_deferred);
74 7977 : return &blocks_.back();
75 : }
76 7757 : void PlaceBlock(Block* block) { placed_blocks_.push_back(block); }
77 : Block* start() const { return start_; }
78 16227 : base::Optional<Block*> end() const { return end_; }
79 : void set_end(Block* end) { end_ = end; }
80 243 : void SetReturnType(const Type* t) {
81 243 : if (!return_type_) {
82 : return_type_ = t;
83 182 : return;
84 : }
85 61 : if (t != *return_type_) {
86 0 : ReportError("expected return type ", **return_type_, " instead of ", *t);
87 : }
88 : }
89 : const std::vector<Block*>& blocks() const { return placed_blocks_; }
90 :
91 : private:
92 : std::list<Block> blocks_;
93 : Block* start_;
94 : std::vector<Block*> placed_blocks_;
95 : base::Optional<Block*> end_;
96 : base::Optional<const Type*> return_type_;
97 : size_t next_block_id_ = 0;
98 : };
99 :
100 8022 : class CfgAssembler {
101 : public:
102 1337 : explicit CfgAssembler(Stack<const Type*> input_types)
103 2674 : : current_stack_(std::move(input_types)), cfg_(current_stack_) {}
104 :
105 1337 : const ControlFlowGraph& Result() {
106 1337 : if (!CurrentBlockIsComplete()) {
107 1130 : cfg_.set_end(current_block_);
108 : }
109 1337 : return cfg_;
110 : }
111 :
112 6640 : Block* NewBlock(
113 : base::Optional<Stack<const Type*>> input_types = base::nullopt,
114 : bool is_deferred = false) {
115 19920 : return cfg_.NewBlock(std::move(input_types), is_deferred);
116 : }
117 :
118 : bool CurrentBlockIsComplete() const { return current_block_->IsComplete(); }
119 :
120 44672 : void Emit(Instruction instruction) {
121 44672 : instruction.TypeInstruction(¤t_stack_, &cfg_);
122 89344 : current_block_->Add(std::move(instruction));
123 44672 : }
124 :
125 : const Stack<const Type*>& CurrentStack() const { return current_stack_; }
126 :
127 : StackRange TopRange(size_t slot_count) const {
128 : return CurrentStack().TopRange(slot_count);
129 : }
130 :
131 : void Bind(Block* block);
132 : void Goto(Block* block);
133 : // Goto block while keeping {preserved_slots} many slots on the top and
134 : // deleting additional the slots below these to match the input type of the
135 : // target block.
136 : // Returns the StackRange of the preserved slots in the target block.
137 : StackRange Goto(Block* block, size_t preserved_slots);
138 : // The condition must be of type bool and on the top of stack. It is removed
139 : // from the stack before branching.
140 : void Branch(Block* if_true, Block* if_false);
141 : // Delete the specified range of slots, moving upper slots to fill the gap.
142 : void DeleteRange(StackRange range);
143 : void DropTo(BottomOffset new_level);
144 : StackRange Peek(StackRange range, base::Optional<const Type*> type);
145 : void Poke(StackRange destination, StackRange origin,
146 : base::Optional<const Type*> type);
147 : void Print(std::string s);
148 : void AssertionFailure(std::string message);
149 : void Unreachable();
150 : void DebugBreak();
151 :
152 : void PrintCurrentStack(std::ostream& s) { s << "stack: " << current_stack_; }
153 :
154 : private:
155 : friend class CfgAssemblerScopedTemporaryBlock;
156 : Stack<const Type*> current_stack_;
157 : ControlFlowGraph cfg_;
158 : Block* current_block_ = cfg_.start();
159 : };
160 :
161 : class CfgAssemblerScopedTemporaryBlock {
162 : public:
163 9 : CfgAssemblerScopedTemporaryBlock(CfgAssembler* assembler, Block* block)
164 18 : : assembler_(assembler), saved_block_(block) {
165 : saved_stack_ = block->InputTypes();
166 : DCHECK(!assembler->CurrentBlockIsComplete());
167 : std::swap(saved_block_, assembler->current_block_);
168 9 : std::swap(saved_stack_, assembler->current_stack_);
169 : assembler->cfg_.PlaceBlock(block);
170 9 : }
171 :
172 18 : ~CfgAssemblerScopedTemporaryBlock() {
173 : DCHECK(assembler_->CurrentBlockIsComplete());
174 9 : std::swap(saved_block_, assembler_->current_block_);
175 9 : std::swap(saved_stack_, assembler_->current_stack_);
176 9 : }
177 :
178 : private:
179 : CfgAssembler* assembler_;
180 : Stack<const Type*> saved_stack_;
181 : Block* saved_block_;
182 : };
183 :
184 : } // namespace torque
185 : } // namespace internal
186 : } // namespace v8
187 :
188 : #endif // V8_TORQUE_CFG_H_
|