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 class Block { 25 public: Block(ControlFlowGraph * cfg,size_t id,base::Optional<Stack<const Type * >> input_types,bool is_deferred)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 is_deferred_(is_deferred) {} Add(Instruction instruction)33 void Add(Instruction instruction) { 34 DCHECK(!IsComplete()); 35 instructions_.push_back(std::move(instruction)); 36 } 37 HasInputTypes()38 bool HasInputTypes() const { return input_types_ != base::nullopt; } InputTypes()39 const Stack<const Type*>& InputTypes() const { return *input_types_; } 40 void SetInputTypes(const Stack<const Type*>& input_types); Retype()41 void Retype() { 42 Stack<const Type*> current_stack = InputTypes(); 43 for (const Instruction& instruction : instructions()) { 44 instruction.TypeInstruction(¤t_stack, cfg_); 45 } 46 } 47 instructions()48 std::vector<Instruction>& instructions() { return instructions_; } instructions()49 const std::vector<Instruction>& instructions() const { return instructions_; } IsComplete()50 bool IsComplete() const { 51 return !instructions_.empty() && instructions_.back()->IsBlockTerminator(); 52 } id()53 size_t id() const { return id_; } IsDeferred()54 bool IsDeferred() const { return is_deferred_; } 55 MergeInputDefinitions(const Stack<DefinitionLocation> & input_definitions,Worklist<Block * > * worklist)56 void MergeInputDefinitions(const Stack<DefinitionLocation>& input_definitions, 57 Worklist<Block*>* worklist) { 58 if (!input_definitions_) { 59 input_definitions_ = input_definitions; 60 if (worklist) worklist->Enqueue(this); 61 return; 62 } 63 64 DCHECK_EQ(input_definitions_->Size(), input_definitions.Size()); 65 bool changed = false; 66 for (BottomOffset i = {0}; i < input_definitions.AboveTop(); ++i) { 67 auto& current = input_definitions_->Peek(i); 68 auto& input = input_definitions.Peek(i); 69 if (current == input) continue; 70 if (current == DefinitionLocation::Phi(this, i.offset)) continue; 71 input_definitions_->Poke(i, DefinitionLocation::Phi(this, i.offset)); 72 changed = true; 73 } 74 75 if (changed && worklist) worklist->Enqueue(this); 76 } HasInputDefinitions()77 bool HasInputDefinitions() const { 78 return input_definitions_ != base::nullopt; 79 } InputDefinitions()80 const Stack<DefinitionLocation>& InputDefinitions() const { 81 DCHECK(HasInputDefinitions()); 82 return *input_definitions_; 83 } 84 IsDead()85 bool IsDead() const { return !HasInputDefinitions(); } 86 87 private: 88 ControlFlowGraph* cfg_; 89 std::vector<Instruction> instructions_; 90 base::Optional<Stack<const Type*>> input_types_; 91 base::Optional<Stack<DefinitionLocation>> input_definitions_; 92 const size_t id_; 93 bool is_deferred_; 94 }; 95 96 class ControlFlowGraph { 97 public: ControlFlowGraph(Stack<const Type * > input_types)98 explicit ControlFlowGraph(Stack<const Type*> input_types) { 99 start_ = NewBlock(std::move(input_types), false); 100 PlaceBlock(start_); 101 } 102 NewBlock(base::Optional<Stack<const Type * >> input_types,bool is_deferred)103 Block* NewBlock(base::Optional<Stack<const Type*>> input_types, 104 bool is_deferred) { 105 blocks_.emplace_back(this, next_block_id_++, std::move(input_types), 106 is_deferred); 107 return &blocks_.back(); 108 } PlaceBlock(Block * block)109 void PlaceBlock(Block* block) { placed_blocks_.push_back(block); } 110 template <typename UnaryPredicate> UnplaceBlockIf(UnaryPredicate && predicate)111 void UnplaceBlockIf(UnaryPredicate&& predicate) { 112 auto newEnd = std::remove_if(placed_blocks_.begin(), placed_blocks_.end(), 113 std::forward<UnaryPredicate>(predicate)); 114 placed_blocks_.erase(newEnd, placed_blocks_.end()); 115 } start()116 Block* start() const { return start_; } end()117 base::Optional<Block*> end() const { return end_; } set_end(Block * end)118 void set_end(Block* end) { end_ = end; } SetReturnType(const Type * t)119 void SetReturnType(const Type* t) { 120 if (!return_type_) { 121 return_type_ = t; 122 return; 123 } 124 if (t != *return_type_) { 125 ReportError("expected return type ", **return_type_, " instead of ", *t); 126 } 127 } blocks()128 const std::vector<Block*>& blocks() const { return placed_blocks_; } NumberOfBlockIds()129 size_t NumberOfBlockIds() const { return next_block_id_; } ParameterCount()130 std::size_t ParameterCount() const { 131 return start_ ? start_->InputTypes().Size() : 0; 132 } 133 134 private: 135 std::list<Block> blocks_; 136 Block* start_; 137 std::vector<Block*> placed_blocks_; 138 base::Optional<Block*> end_; 139 base::Optional<const Type*> return_type_; 140 size_t next_block_id_ = 0; 141 }; 142 143 class CfgAssembler { 144 public: CfgAssembler(Stack<const Type * > input_types)145 explicit CfgAssembler(Stack<const Type*> input_types) 146 : current_stack_(std::move(input_types)), cfg_(current_stack_) {} 147 Result()148 const ControlFlowGraph& Result() { 149 if (!CurrentBlockIsComplete()) { 150 cfg_.set_end(current_block_); 151 } 152 OptimizeCfg(); 153 DCHECK(CfgIsComplete()); 154 ComputeInputDefinitions(); 155 return cfg_; 156 } 157 158 Block* NewBlock( 159 base::Optional<Stack<const Type*>> input_types = base::nullopt, 160 bool is_deferred = false) { 161 return cfg_.NewBlock(std::move(input_types), is_deferred); 162 } 163 CurrentBlockIsComplete()164 bool CurrentBlockIsComplete() const { return current_block_->IsComplete(); } CfgIsComplete()165 bool CfgIsComplete() const { 166 return std::all_of( 167 cfg_.blocks().begin(), cfg_.blocks().end(), [this](Block* block) { 168 return (cfg_.end() && *cfg_.end() == block) || block->IsComplete(); 169 }); 170 } 171 Emit(Instruction instruction)172 void Emit(Instruction instruction) { 173 instruction.TypeInstruction(¤t_stack_, &cfg_); 174 current_block_->Add(std::move(instruction)); 175 } 176 CurrentStack()177 const Stack<const Type*>& CurrentStack() const { return current_stack_; } 178 TopRange(size_t slot_count)179 StackRange TopRange(size_t slot_count) const { 180 return CurrentStack().TopRange(slot_count); 181 } 182 183 void Bind(Block* block); 184 void Goto(Block* block); 185 // Goto block while keeping {preserved_slots} many slots on the top and 186 // deleting additional the slots below these to match the input type of the 187 // target block. 188 // Returns the StackRange of the preserved slots in the target block. 189 StackRange Goto(Block* block, size_t preserved_slots); 190 // The condition must be of type bool and on the top of stack. It is removed 191 // from the stack before branching. 192 void Branch(Block* if_true, Block* if_false); 193 // Delete the specified range of slots, moving upper slots to fill the gap. 194 void DeleteRange(StackRange range); 195 void DropTo(BottomOffset new_level); 196 StackRange Peek(StackRange range, base::Optional<const Type*> type); 197 void Poke(StackRange destination, StackRange origin, 198 base::Optional<const Type*> type); 199 void Print(std::string s); 200 void AssertionFailure(std::string message); 201 void Unreachable(); 202 void DebugBreak(); 203 PrintCurrentStack(std::ostream & s)204 void PrintCurrentStack(std::ostream& s) { s << "stack: " << current_stack_; } 205 void OptimizeCfg(); 206 void ComputeInputDefinitions(); 207 208 private: 209 friend class CfgAssemblerScopedTemporaryBlock; 210 Stack<const Type*> current_stack_; 211 ControlFlowGraph cfg_; 212 Block* current_block_ = cfg_.start(); 213 }; 214 215 class CfgAssemblerScopedTemporaryBlock { 216 public: CfgAssemblerScopedTemporaryBlock(CfgAssembler * assembler,Block * block)217 CfgAssemblerScopedTemporaryBlock(CfgAssembler* assembler, Block* block) 218 : assembler_(assembler), saved_block_(block) { 219 saved_stack_ = block->InputTypes(); 220 DCHECK(!assembler->CurrentBlockIsComplete()); 221 std::swap(saved_block_, assembler->current_block_); 222 std::swap(saved_stack_, assembler->current_stack_); 223 assembler->cfg_.PlaceBlock(block); 224 } 225 ~CfgAssemblerScopedTemporaryBlock()226 ~CfgAssemblerScopedTemporaryBlock() { 227 DCHECK(assembler_->CurrentBlockIsComplete()); 228 std::swap(saved_block_, assembler_->current_block_); 229 std::swap(saved_stack_, assembler_->current_stack_); 230 } 231 232 private: 233 CfgAssembler* assembler_; 234 Stack<const Type*> saved_stack_; 235 Block* saved_block_; 236 }; 237 238 } // namespace torque 239 } // namespace internal 240 } // namespace v8 241 242 #endif // V8_TORQUE_CFG_H_ 243