// Copyright 2018 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef V8_TORQUE_CFG_H_ #define V8_TORQUE_CFG_H_ #include <list> #include <memory> #include <unordered_map> #include <vector> #include "src/torque/ast.h" #include "src/torque/instructions.h" #include "src/torque/source-positions.h" #include "src/torque/types.h" namespace v8 { namespace internal { namespace torque { class ControlFlowGraph; class Block { public: explicit Block(ControlFlowGraph* cfg, size_t id, base::Optional<Stack<const Type*>> input_types, bool is_deferred) : cfg_(cfg), input_types_(std::move(input_types)), id_(id), is_deferred_(is_deferred) {} void Add(Instruction instruction) { DCHECK(!IsComplete()); instructions_.push_back(std::move(instruction)); } bool HasInputTypes() const { return input_types_ != base::nullopt; } const Stack<const Type*>& InputTypes() const { return *input_types_; } void SetInputTypes(const Stack<const Type*>& input_types); void Retype() { Stack<const Type*> current_stack = InputTypes(); for (const Instruction& instruction : instructions()) { instruction.TypeInstruction(¤t_stack, cfg_); } } std::vector<Instruction>& instructions() { return instructions_; } const std::vector<Instruction>& instructions() const { return instructions_; } bool IsComplete() const { return !instructions_.empty() && instructions_.back()->IsBlockTerminator(); } size_t id() const { return id_; } bool IsDeferred() const { return is_deferred_; } void MergeInputDefinitions(const Stack<DefinitionLocation>& input_definitions, Worklist<Block*>* worklist) { if (!input_definitions_) { input_definitions_ = input_definitions; if (worklist) worklist->Enqueue(this); return; } DCHECK_EQ(input_definitions_->Size(), input_definitions.Size()); bool changed = false; for (BottomOffset i = {0}; i < input_definitions.AboveTop(); ++i) { auto& current = input_definitions_->Peek(i); auto& input = input_definitions.Peek(i); if (current == input) continue; if (current == DefinitionLocation::Phi(this, i.offset)) continue; input_definitions_->Poke(i, DefinitionLocation::Phi(this, i.offset)); changed = true; } if (changed && worklist) worklist->Enqueue(this); } bool HasInputDefinitions() const { return input_definitions_ != base::nullopt; } const Stack<DefinitionLocation>& InputDefinitions() const { DCHECK(HasInputDefinitions()); return *input_definitions_; } bool IsDead() const { return !HasInputDefinitions(); } private: ControlFlowGraph* cfg_; std::vector<Instruction> instructions_; base::Optional<Stack<const Type*>> input_types_; base::Optional<Stack<DefinitionLocation>> input_definitions_; const size_t id_; bool is_deferred_; }; class ControlFlowGraph { public: explicit ControlFlowGraph(Stack<const Type*> input_types) { start_ = NewBlock(std::move(input_types), false); PlaceBlock(start_); } Block* NewBlock(base::Optional<Stack<const Type*>> input_types, bool is_deferred) { blocks_.emplace_back(this, next_block_id_++, std::move(input_types), is_deferred); return &blocks_.back(); } void PlaceBlock(Block* block) { placed_blocks_.push_back(block); } template <typename UnaryPredicate> void UnplaceBlockIf(UnaryPredicate&& predicate) { auto newEnd = std::remove_if(placed_blocks_.begin(), placed_blocks_.end(), std::forward<UnaryPredicate>(predicate)); placed_blocks_.erase(newEnd, placed_blocks_.end()); } Block* start() const { return start_; } base::Optional<Block*> end() const { return end_; } void set_end(Block* end) { end_ = end; } void SetReturnType(TypeVector t) { if (!return_type_) { return_type_ = t; return; } if (t != *return_type_) { std::stringstream message; message << "expected return type "; PrintCommaSeparatedList(message, *return_type_); message << " instead of "; PrintCommaSeparatedList(message, t); ReportError(message.str()); } } const std::vector<Block*>& blocks() const { return placed_blocks_; } size_t NumberOfBlockIds() const { return next_block_id_; } std::size_t ParameterCount() const { return start_ ? start_->InputTypes().Size() : 0; } private: std::list<Block> blocks_; Block* start_; std::vector<Block*> placed_blocks_; base::Optional<Block*> end_; base::Optional<TypeVector> return_type_; size_t next_block_id_ = 0; }; class CfgAssembler { public: explicit CfgAssembler(Stack<const Type*> input_types) : current_stack_(std::move(input_types)), cfg_(current_stack_) {} const ControlFlowGraph& Result() { if (!CurrentBlockIsComplete()) { cfg_.set_end(current_block_); } OptimizeCfg(); DCHECK(CfgIsComplete()); ComputeInputDefinitions(); return cfg_; } Block* NewBlock( base::Optional<Stack<const Type*>> input_types = base::nullopt, bool is_deferred = false) { return cfg_.NewBlock(std::move(input_types), is_deferred); } bool CurrentBlockIsComplete() const { return current_block_->IsComplete(); } bool CfgIsComplete() const { return std::all_of( cfg_.blocks().begin(), cfg_.blocks().end(), [this](Block* block) { return (cfg_.end() && *cfg_.end() == block) || block->IsComplete(); }); } void Emit(Instruction instruction) { instruction.TypeInstruction(¤t_stack_, &cfg_); current_block_->Add(std::move(instruction)); } const Stack<const Type*>& CurrentStack() const { return current_stack_; } StackRange TopRange(size_t slot_count) const { return CurrentStack().TopRange(slot_count); } void Bind(Block* block); void Goto(Block* block); // Goto block while keeping {preserved_slots} many slots on the top and // deleting additional the slots below these to match the input type of the // target block. // Returns the StackRange of the preserved slots in the target block. StackRange Goto(Block* block, size_t preserved_slots); // The condition must be of type bool and on the top of stack. It is removed // from the stack before branching. void Branch(Block* if_true, Block* if_false); // Delete the specified range of slots, moving upper slots to fill the gap. void DeleteRange(StackRange range); void DropTo(BottomOffset new_level); StackRange Peek(StackRange range, base::Optional<const Type*> type); void Poke(StackRange destination, StackRange origin, base::Optional<const Type*> type); void Print(std::string s); void AssertionFailure(std::string message); void Unreachable(); void DebugBreak(); void PrintCurrentStack(std::ostream& s) { s << "stack: " << current_stack_; } void OptimizeCfg(); void ComputeInputDefinitions(); private: friend class CfgAssemblerScopedTemporaryBlock; Stack<const Type*> current_stack_; ControlFlowGraph cfg_; Block* current_block_ = cfg_.start(); }; class V8_NODISCARD CfgAssemblerScopedTemporaryBlock { public: CfgAssemblerScopedTemporaryBlock(CfgAssembler* assembler, Block* block) : assembler_(assembler), saved_block_(block) { saved_stack_ = block->InputTypes(); DCHECK(!assembler->CurrentBlockIsComplete()); std::swap(saved_block_, assembler->current_block_); std::swap(saved_stack_, assembler->current_stack_); assembler->cfg_.PlaceBlock(block); } ~CfgAssemblerScopedTemporaryBlock() { DCHECK(assembler_->CurrentBlockIsComplete()); std::swap(saved_block_, assembler_->current_block_); std::swap(saved_stack_, assembler_->current_stack_); } private: CfgAssembler* assembler_; Stack<const Type*> saved_stack_; Block* saved_block_; }; } // namespace torque } // namespace internal } // namespace v8 #endif // V8_TORQUE_CFG_H_