string-builder-optimizer.h | Explore in Territory

// Copyright 2022 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_COMPILER_STRING_BUILDER_OPTIMIZER_H_
#define V8_COMPILER_STRING_BUILDER_OPTIMIZER_H_

#include <cstdint>
#include <optional>
#include <unordered_map>
#include <vector>

#include "src/base/macros.h"
#include "src/compiler/graph-assembler.h"
#include "src/compiler/graph-reducer.h"
#include "src/compiler/js-graph.h"
#include "src/compiler/machine-operator.h"
#include "src/compiler/node-marker.h"
#include "src/compiler/node.h"
#include "src/compiler/schedule.h"
#include "src/zone/zone-containers.h"

namespace v8 {
namespace internal {

class Zone;

namespace compiler {

class JSGraphAssembler;
class NodeOriginTable;
class Schedule;
class SourcePositionTable;
class JSHeapBroker;

// StringBuilderOptimizer aims at avoid ConsString for some loops that build
// strings, and instead update a mutable over-allocated backing store, while
// keeping a (mutable) SlicedString to the valid part of the backing store.
//
// StringBuilderOptimizer only does the analysis: it finds out which nodes could
// benefit from this optimization. Then, EffectControlLinearizer actually
// applies the optimization to the graph.
//
// A typical example of what the StringBuilderOptimizer can optimize is:
//
//    let s = "";
//    for (...) {
//        s += "...";
//    }
//
// In general, for a series of concatenations to be optimized, they need:
//   - To start on a single initial concatenation
//   - All the concatenations in the string builder must have constant strings
//     or String.FromCharCode on their right-hand side.
//   - At least one of the concatenation must be in a loop.
//
// Because everything is nicer with a picture, here is one of what kind of
// patterns the StringBuilderOptimizer tries to optimize:
//
//            +--------+
//            |kLiteral|
//            +--------+
//                |
//                |
//                v
//         +-------------+          +--------+
//         |kStringConcat| <------- |kLiteral|
//         +-------------+          +--------+
//                |
//                |
//                v
//           optionally,
//        more kStringConcat
//                |
//                |
//                v
//             +----+
//    -------->|kPhi|------------------------------------------
//    |        +----+                                         |
//    |           |                                           |
//    |           |                                           |
//    |           |                                           |
//    |           |                                           |
//    |           |                                           |
//    |           |                                           |
//    |           |                                           |
//    |           v                                           |
//    |    +-------------+          +--------+                |
//    |    |kStringConcat| <------- |kLiteral|                |
//    |    +-------------+          +--------+                |
//    |           |                                           |
//    |           |                                           |
//    |           v                                           |
//    |      optionally,                                      v
//    |   more kStringConcat                            optionally,
//    |           |                                   more kStringConcat
//    |           |                                   or more kPhi/loops
//    |           |                                           |
//    ------------|                                           |
//                                                            |
//                                                            |
//                                                            v
//
// Where "kLiteral" actually means "either a string literal (HeapConstant) or a
// StringFromSingleCharCode". And kStringConcat can also be kNewConsString (when
// the size of the concatenation is known to be more than 13 bytes, Turbofan's
// front-end generates kNewConsString opcodes rather than kStringConcat).
// The StringBuilder also supports merge phis. For instance:
//
//                                  +--------+
//                                  |kLiteral|
//                                  +--------+
//                                      |
//                                      |
//                                      v
//                               +-------------+          +--------+
//                               |kStringConcat| <------- |kLiteral|
//                               +-------------+          +--------+
//                                  |       |
//                                  |       |
//                                  |       |
//                  +---------------+       +---------------+
//                  |                                       |
//                  |                                       |
//                  v                                       v
//           +-------------+                         +-------------+
//           |kStringConcat|                         |kStringConcat|
//           +-------------+                         +-------------+
//                  |                                       |
//                  |                                       |
//                  |                                       |
//                  +---------------+       +---------------+
//                                  |       |
//                                  |       |
//                                  v       v
//                               +-------------+
//                               |    kPhi     |
//                               |   (merge)   |
//                               +-------------+
//                                      |
//                                      |
//                                      v
//
// (and, of course, loops and merge can be mixed).

class OneOrTwoByteAnalysis final { … };

class V8_EXPORT_PRIVATE StringBuilderOptimizer final { … };

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_STRING_BUILDER_OPTIMIZER_H_
chromium/v8/src/compiler/string-builder-optimizer.h
