1 // Copyright 2022 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_BRANCH_CONDITION_DUPLICATOR_H_ 6 #define V8_COMPILER_BRANCH_CONDITION_DUPLICATOR_H_ 7 8 #include "src/base/macros.h" 9 #include "src/compiler/node-marker.h" 10 #include "src/compiler/node.h" 11 #include "src/zone/zone.h" 12 13 namespace v8 { 14 namespace internal { 15 namespace compiler { 16 17 // Forward declare. 18 class Graph; 19 20 // BranchConditionDuplicator makes sure that the condition nodes of branches are 21 // used only once. When it finds a branch node whose condition has multiples 22 // uses, this condition is duplicated. 23 // 24 // Doing this enables the InstructionSelector to generate more efficient code 25 // for branches. For instance, consider this code: 26 // 27 // if (a + b == 0) { /* some code */ } 28 // if (a + b == 0) { /* more code */ } 29 // 30 // Then the generated code will be something like (using registers "ra" for "a" 31 // and "rb" for "b", and "rt" a temporary register): 32 // 33 // add ra, rb ; a + b 34 // cmp ra, 0 ; (a + b) == 0 35 // sete rt ; rt = (a + b) == 0 36 // cmp rt, 0 ; rt == 0 37 // jz 38 // ... 39 // cmp rt, 0 ; rt == 0 40 // jz 41 // 42 // As you can see, TurboFan materialized the == bit into a temporary register. 43 // However, since the "add" instruction sets the ZF flag (on x64), it can be 44 // used to determine wether the jump should be taken or not. The code we'd like 45 // to generate instead if thus: 46 // 47 // add ra, rb 48 // jnz 49 // ... 50 // add ra, rb 51 // jnz 52 // 53 // However, this requires to generate twice the instruction "add ra, rb". Due to 54 // how virtual registers are assigned in TurboFan (there is a map from node ID 55 // to virtual registers), both "add" instructions will use the same virtual 56 // register as output, which will break SSA. 57 // 58 // In order to overcome this issue, BranchConditionDuplicator duplicates branch 59 // conditions that are used more than once, so that they can be generated right 60 // before each branch without worrying about breaking SSA. 61 62 class V8_EXPORT_PRIVATE BranchConditionDuplicator final { 63 public: 64 BranchConditionDuplicator(Zone* zone, Graph* graph); 65 ~BranchConditionDuplicator() = default; 66 67 void Reduce(); 68 69 Node* DuplicateNode(Node* node); 70 void DuplicateConditionIfNeeded(Node* node); 71 void Enqueue(Node* node); 72 void VisitNode(Node* node); 73 void ProcessGraph(); 74 75 private: 76 Graph* const graph_; 77 ZoneQueue<Node*> to_visit_; 78 NodeMarker<bool> seen_; 79 }; 80 81 } // namespace compiler 82 } // namespace internal 83 } // namespace v8 84 85 #endif // V8_COMPILER_BRANCH_CONDITION_DUPLICATOR_H_ 86