1 // Copyright 2016 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_COMPILER_GRAPH_ASSEMBLER_H_ 6 #define V8_COMPILER_GRAPH_ASSEMBLER_H_ 7 8 #include "src/compiler/js-graph.h" 9 #include "src/compiler/node.h" 10 #include "src/compiler/simplified-operator.h" 11 12 namespace v8 { 13 namespace internal { 14 15 class JSGraph; 16 class Graph; 17 18 namespace compiler { 19 20 #define PURE_ASSEMBLER_MACH_UNOP_LIST(V) \ 21 V(ChangeInt32ToInt64) \ 22 V(ChangeInt32ToFloat64) \ 23 V(ChangeUint32ToFloat64) \ 24 V(ChangeUint32ToUint64) \ 25 V(ChangeFloat64ToInt32) \ 26 V(ChangeFloat64ToUint32) \ 27 V(TruncateInt64ToInt32) \ 28 V(RoundFloat64ToInt32) \ 29 V(TruncateFloat64ToWord32) \ 30 V(Float64ExtractHighWord32) \ 31 V(Float64Abs) \ 32 V(BitcastWordToTagged) 33 34 #define PURE_ASSEMBLER_MACH_BINOP_LIST(V) \ 35 V(WordShl) \ 36 V(WordSar) \ 37 V(WordAnd) \ 38 V(Word32Or) \ 39 V(Word32And) \ 40 V(Word32Shr) \ 41 V(Word32Shl) \ 42 V(IntAdd) \ 43 V(IntSub) \ 44 V(UintLessThan) \ 45 V(Int32Add) \ 46 V(Int32Sub) \ 47 V(Int32Mul) \ 48 V(Int32LessThanOrEqual) \ 49 V(Uint32LessThanOrEqual) \ 50 V(Uint32LessThan) \ 51 V(Int32LessThan) \ 52 V(Float64Add) \ 53 V(Float64Sub) \ 54 V(Float64Mod) \ 55 V(Float64Equal) \ 56 V(Float64LessThan) \ 57 V(Float64LessThanOrEqual) \ 58 V(Word32Equal) \ 59 V(WordEqual) 60 61 #define CHECKED_ASSEMBLER_MACH_BINOP_LIST(V) \ 62 V(Int32AddWithOverflow) \ 63 V(Int32SubWithOverflow) \ 64 V(Int32MulWithOverflow) \ 65 V(Int32Mod) \ 66 V(Int32Div) \ 67 V(Uint32Mod) \ 68 V(Uint32Div) 69 70 #define JSGRAPH_SINGLETON_CONSTANT_LIST(V) \ 71 V(TrueConstant) \ 72 V(FalseConstant) \ 73 V(HeapNumberMapConstant) \ 74 V(NoContextConstant) \ 75 V(EmptyStringConstant) \ 76 V(UndefinedConstant) \ 77 V(TheHoleConstant) \ 78 V(FixedArrayMapConstant) \ 79 V(ToNumberBuiltinConstant) \ 80 V(AllocateInNewSpaceStubConstant) \ 81 V(AllocateInOldSpaceStubConstant) 82 83 class GraphAssembler; 84 85 enum class GraphAssemblerLabelType { kDeferred, kNonDeferred }; 86 87 // Label with statically known count of incoming branches and phis. 88 template <size_t MergeCount, size_t VarCount = 0u> 89 class GraphAssemblerStaticLabel { 90 public: 91 Node* PhiAt(size_t index); 92 93 template <typename... Reps> 94 explicit GraphAssemblerStaticLabel(GraphAssemblerLabelType is_deferred, 95 Reps... reps) 96 : is_deferred_(is_deferred == GraphAssemblerLabelType::kDeferred) { 97 STATIC_ASSERT(VarCount == sizeof...(reps)); 98 MachineRepresentation reps_array[] = {MachineRepresentation::kNone, 99 reps...}; 100 for (size_t i = 0; i < VarCount; i++) { 101 representations_[i] = reps_array[i + 1]; 102 } 103 } 104 105 ~GraphAssemblerStaticLabel() { DCHECK(IsBound() || MergedCount() == 0); } 106 107 private: 108 friend class GraphAssembler; 109 110 void SetBound() { 111 DCHECK(!IsBound()); 112 DCHECK_EQ(merged_count_, MergeCount); 113 is_bound_ = true; 114 } 115 bool IsBound() const { return is_bound_; } 116 117 size_t PhiCount() const { return VarCount; } 118 size_t MaxMergeCount() const { return MergeCount; } 119 size_t MergedCount() const { return merged_count_; } 120 bool IsDeferred() const { return is_deferred_; } 121 122 // For each phi, the buffer must have at least MaxMergeCount() + 1 123 // node entries. 124 Node** GetBindingsPtrFor(size_t phi_index) { 125 DCHECK_LT(phi_index, PhiCount()); 126 return &bindings_[phi_index * (MergeCount + 1)]; 127 } 128 void SetBinding(size_t phi_index, size_t merge_index, Node* binding) { 129 DCHECK_LT(phi_index, PhiCount()); 130 DCHECK_LT(merge_index, MergeCount); 131 bindings_[phi_index * (MergeCount + 1) + merge_index] = binding; 132 } 133 MachineRepresentation GetRepresentationFor(size_t phi_index) { 134 DCHECK_LT(phi_index, PhiCount()); 135 return representations_[phi_index]; 136 } 137 // The controls buffer must have at least MaxMergeCount() entries. 138 Node** GetControlsPtr() { return controls_; } 139 // The effects buffer must have at least MaxMergeCount() + 1 entries. 140 Node** GetEffectsPtr() { return effects_; } 141 void IncrementMergedCount() { merged_count_++; } 142 143 bool is_bound_ = false; 144 bool is_deferred_; 145 size_t merged_count_ = 0; 146 Node* effects_[MergeCount + 1]; // Extra element for control edge, 147 // so that we can use the array to 148 // construct EffectPhi. 149 Node* controls_[MergeCount]; 150 Node* bindings_[(MergeCount + 1) * VarCount + 1]; 151 MachineRepresentation representations_[VarCount + 1]; 152 }; 153 154 // General label (with zone allocated buffers for incoming branches and phi 155 // inputs). 156 class GraphAssemblerLabel { 157 public: 158 Node* PhiAt(size_t index); 159 160 GraphAssemblerLabel(GraphAssemblerLabelType is_deferred, size_t merge_count, 161 size_t var_count, MachineRepresentation* representations, 162 Zone* zone); 163 164 ~GraphAssemblerLabel(); 165 166 private: 167 friend class GraphAssembler; 168 169 void SetBound() { 170 DCHECK(!is_bound_); 171 is_bound_ = true; 172 } 173 bool IsBound() const { return is_bound_; } 174 size_t PhiCount() const { return var_count_; } 175 size_t MaxMergeCount() const { return max_merge_count_; } 176 size_t MergedCount() const { return merged_count_; } 177 bool IsDeferred() const { return is_deferred_; } 178 179 // For each phi, the buffer must have at least MaxMergeCount() + 1 180 // node entries. 181 Node** GetBindingsPtrFor(size_t phi_index); 182 void SetBinding(size_t phi_index, size_t merge_index, Node* binding); 183 MachineRepresentation GetRepresentationFor(size_t phi_index); 184 // The controls buffer must have at least MaxMergeCount() entries. 185 Node** GetControlsPtr(); 186 // The effects buffer must have at least MaxMergeCount() + 1 entries. 187 Node** GetEffectsPtr(); 188 void IncrementMergedCount() { merged_count_++; } 189 190 bool is_bound_ = false; 191 bool is_deferred_; 192 size_t merged_count_ = 0; 193 size_t max_merge_count_; 194 size_t var_count_; 195 Node** effects_ = nullptr; 196 Node** controls_ = nullptr; 197 Node** bindings_ = nullptr; 198 MachineRepresentation* representations_ = nullptr; 199 }; 200 201 class GraphAssembler { 202 public: 203 GraphAssembler(JSGraph* jsgraph, Node* effect, Node* control, Zone* zone); 204 205 void Reset(Node* effect, Node* control); 206 207 // Create non-deferred label with statically known number of incoming 208 // gotos/branches. 209 template <size_t MergeCount, typename... Reps> 210 static GraphAssemblerStaticLabel<MergeCount, sizeof...(Reps)> MakeLabel( 211 Reps... reps) { 212 return GraphAssemblerStaticLabel<MergeCount, sizeof...(Reps)>( 213 GraphAssemblerLabelType::kNonDeferred, reps...); 214 } 215 216 // Create deferred label with statically known number of incoming 217 // gotos/branches. 218 template <size_t MergeCount, typename... Reps> 219 static GraphAssemblerStaticLabel<MergeCount, sizeof...(Reps)> 220 MakeDeferredLabel(Reps... reps) { 221 return GraphAssemblerStaticLabel<MergeCount, sizeof...(Reps)>( 222 GraphAssemblerLabelType::kDeferred, reps...); 223 } 224 225 // Create label with number of incoming branches supplied at runtime. 226 template <typename... Reps> 227 GraphAssemblerLabel MakeLabelFor(GraphAssemblerLabelType is_deferred, 228 size_t merge_count, Reps... reps) { 229 MachineRepresentation reps_array[] = {MachineRepresentation::kNone, 230 reps...}; 231 return GraphAssemblerLabel(is_deferred, merge_count, sizeof...(reps), 232 &(reps_array[1]), temp_zone()); 233 } 234 235 // Value creation. 236 Node* IntPtrConstant(intptr_t value); 237 Node* Uint32Constant(int32_t value); 238 Node* Int32Constant(int32_t value); 239 Node* UniqueInt32Constant(int32_t value); 240 Node* SmiConstant(int32_t value); 241 Node* Float64Constant(double value); 242 Node* Projection(int index, Node* value); 243 Node* HeapConstant(Handle<HeapObject> object); 244 Node* CEntryStubConstant(int result_size); 245 Node* ExternalConstant(ExternalReference ref); 246 247 #define SINGLETON_CONST_DECL(Name) Node* Name(); 248 JSGRAPH_SINGLETON_CONSTANT_LIST(SINGLETON_CONST_DECL) 249 #undef SINGLETON_CONST_DECL 250 251 #define PURE_UNOP_DECL(Name) Node* Name(Node* input); 252 PURE_ASSEMBLER_MACH_UNOP_LIST(PURE_UNOP_DECL) 253 #undef PURE_UNOP_DECL 254 255 #define BINOP_DECL(Name) Node* Name(Node* left, Node* right); 256 PURE_ASSEMBLER_MACH_BINOP_LIST(BINOP_DECL) 257 CHECKED_ASSEMBLER_MACH_BINOP_LIST(BINOP_DECL) 258 #undef BINOP_DECL 259 260 Node* Float64RoundDown(Node* value); 261 262 Node* ToNumber(Node* value); 263 Node* Allocate(PretenureFlag pretenure, Node* size); 264 Node* LoadField(FieldAccess const&, Node* object); 265 Node* LoadElement(ElementAccess const&, Node* object, Node* index); 266 Node* StoreField(FieldAccess const&, Node* object, Node* value); 267 Node* StoreElement(ElementAccess const&, Node* object, Node* index, 268 Node* value); 269 270 Node* Store(StoreRepresentation rep, Node* object, Node* offset, Node* value); 271 Node* Load(MachineType rep, Node* object, Node* offset); 272 273 Node* Retain(Node* buffer); 274 Node* UnsafePointerAdd(Node* base, Node* external); 275 276 Node* DeoptimizeIf(DeoptimizeReason reason, Node* condition, 277 Node* frame_state); 278 Node* DeoptimizeUnless(DeoptimizeKind kind, DeoptimizeReason reason, 279 Node* condition, Node* frame_state); 280 Node* DeoptimizeUnless(DeoptimizeReason reason, Node* condition, 281 Node* frame_state); 282 template <typename... Args> 283 Node* Call(const CallDescriptor* desc, Args... args); 284 template <typename... Args> 285 Node* Call(const Operator* op, Args... args); 286 287 // Basic control operations. 288 template <class LabelType> 289 void Bind(LabelType* label); 290 291 template <class LabelType, typename... vars> 292 void Goto(LabelType* label, vars...); 293 294 void Branch(Node* condition, GraphAssemblerStaticLabel<1>* if_true, 295 GraphAssemblerStaticLabel<1>* if_false); 296 297 // Control helpers. 298 // {GotoIf(c, l)} is equivalent to {Branch(c, l, templ);Bind(templ)}. 299 template <class LabelType, typename... vars> 300 void GotoIf(Node* condition, LabelType* label, vars...); 301 302 // {GotoUnless(c, l)} is equivalent to {Branch(c, templ, l);Bind(templ)}. 303 template <class LabelType, typename... vars> 304 void GotoUnless(Node* condition, LabelType* label, vars...); 305 306 // Extractors (should be only used when destructing/resetting the assembler). 307 Node* ExtractCurrentControl(); 308 Node* ExtractCurrentEffect(); 309 310 private: 311 template <class LabelType, typename... Vars> 312 void MergeState(LabelType label, Vars... vars); 313 314 Operator const* ToNumberOperator(); 315 316 JSGraph* jsgraph() const { return jsgraph_; } 317 Graph* graph() const { return jsgraph_->graph(); } 318 Zone* temp_zone() const { return temp_zone_; } 319 CommonOperatorBuilder* common() const { return jsgraph()->common(); } 320 MachineOperatorBuilder* machine() const { return jsgraph()->machine(); } 321 SimplifiedOperatorBuilder* simplified() const { 322 return jsgraph()->simplified(); 323 } 324 325 SetOncePointer<Operator const> to_number_operator_; 326 Zone* temp_zone_; 327 JSGraph* jsgraph_; 328 Node* current_effect_; 329 Node* current_control_; 330 }; 331 332 template <size_t MergeCount, size_t VarCount> 333 Node* GraphAssemblerStaticLabel<MergeCount, VarCount>::PhiAt(size_t index) { 334 DCHECK(IsBound()); 335 return GetBindingsPtrFor(index)[0]; 336 } 337 338 template <class LabelType, typename... Vars> 339 void GraphAssembler::MergeState(LabelType label, Vars... vars) { 340 DCHECK(!label->IsBound()); 341 size_t merged_count = label->MergedCount(); 342 DCHECK_LT(merged_count, label->MaxMergeCount()); 343 DCHECK_EQ(label->PhiCount(), sizeof...(vars)); 344 label->GetEffectsPtr()[merged_count] = current_effect_; 345 label->GetControlsPtr()[merged_count] = current_control_; 346 // We need to start with nullptr to avoid 0-length arrays. 347 Node* var_array[] = {nullptr, vars...}; 348 for (size_t i = 0; i < sizeof...(vars); i++) { 349 label->SetBinding(i, merged_count, var_array[i + 1]); 350 } 351 label->IncrementMergedCount(); 352 } 353 354 template <class LabelType> 355 void GraphAssembler::Bind(LabelType* label) { 356 DCHECK(current_control_ == nullptr); 357 DCHECK(current_effect_ == nullptr); 358 DCHECK(label->MaxMergeCount() > 0); 359 DCHECK_EQ(label->MaxMergeCount(), label->MergedCount()); 360 361 int merge_count = static_cast<int>(label->MaxMergeCount()); 362 if (merge_count == 1) { 363 current_control_ = label->GetControlsPtr()[0]; 364 current_effect_ = label->GetEffectsPtr()[0]; 365 label->SetBound(); 366 return; 367 } 368 369 current_control_ = graph()->NewNode(common()->Merge(merge_count), merge_count, 370 label->GetControlsPtr()); 371 372 Node** effects = label->GetEffectsPtr(); 373 current_effect_ = effects[0]; 374 for (size_t i = 1; i < label->MaxMergeCount(); i++) { 375 if (current_effect_ != effects[i]) { 376 effects[label->MaxMergeCount()] = current_control_; 377 current_effect_ = graph()->NewNode(common()->EffectPhi(merge_count), 378 merge_count + 1, effects); 379 break; 380 } 381 } 382 383 for (size_t var = 0; var < label->PhiCount(); var++) { 384 Node** bindings = label->GetBindingsPtrFor(var); 385 bindings[label->MaxMergeCount()] = current_control_; 386 bindings[0] = graph()->NewNode( 387 common()->Phi(label->GetRepresentationFor(var), merge_count), 388 merge_count + 1, bindings); 389 } 390 391 label->SetBound(); 392 } 393 394 template <class LabelType, typename... Vars> 395 void GraphAssembler::Goto(LabelType* label, Vars... vars) { 396 DCHECK_NOT_NULL(current_control_); 397 DCHECK_NOT_NULL(current_effect_); 398 MergeState(label, vars...); 399 current_control_ = nullptr; 400 current_effect_ = nullptr; 401 } 402 403 template <class LabelType, typename... Vars> 404 void GraphAssembler::GotoIf(Node* condition, LabelType* label, Vars... vars) { 405 BranchHint hint = 406 label->IsDeferred() ? BranchHint::kFalse : BranchHint::kNone; 407 Node* branch = 408 graph()->NewNode(common()->Branch(hint), condition, current_control_); 409 410 current_control_ = graph()->NewNode(common()->IfTrue(), branch); 411 MergeState(label, vars...); 412 413 current_control_ = graph()->NewNode(common()->IfFalse(), branch); 414 } 415 416 template <class LabelType, typename... Vars> 417 void GraphAssembler::GotoUnless(Node* condition, LabelType* label, 418 Vars... vars) { 419 BranchHint hint = label->IsDeferred() ? BranchHint::kTrue : BranchHint::kNone; 420 Node* branch = 421 graph()->NewNode(common()->Branch(hint), condition, current_control_); 422 423 current_control_ = graph()->NewNode(common()->IfFalse(), branch); 424 MergeState(label, vars...); 425 426 current_control_ = graph()->NewNode(common()->IfTrue(), branch); 427 } 428 429 template <typename... Args> 430 Node* GraphAssembler::Call(const CallDescriptor* desc, Args... args) { 431 const Operator* op = common()->Call(desc); 432 return Call(op, args...); 433 } 434 435 template <typename... Args> 436 Node* GraphAssembler::Call(const Operator* op, Args... args) { 437 DCHECK_EQ(IrOpcode::kCall, op->opcode()); 438 Node* args_array[] = {args..., current_effect_, current_control_}; 439 int size = static_cast<int>(sizeof...(args)) + op->EffectInputCount() + 440 op->ControlInputCount(); 441 Node* call = graph()->NewNode(op, size, args_array); 442 DCHECK_EQ(0, op->ControlOutputCount()); 443 current_effect_ = call; 444 return call; 445 } 446 447 } // namespace compiler 448 } // namespace internal 449 } // namespace v8 450 451 #endif // V8_COMPILER_GRAPH_ASSEMBLER_H_ 452