1 /** 2 * Copyright (c) 2023-2025 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef COMPILER_OPTIMIZER_OPTIMIZATIONS_SIMPLIFY_STRING_BUILDER_H 17 #define COMPILER_OPTIMIZER_OPTIMIZATIONS_SIMPLIFY_STRING_BUILDER_H 18 19 #include "optimizer/analysis/loop_analyzer.h" 20 #include "optimizer/ir/analysis.h" 21 #include "optimizer/ir/basicblock.h" 22 #include "optimizer/ir/graph.h" 23 #include "optimizer/ir/inst.h" 24 #include "optimizer/pass.h" 25 #include "optimizer/optimizations/string_builder_utils.h" 26 27 namespace ark::compiler { 28 29 /** 30 * 1. Removes unnecessary String Builder instances 31 * 2. Replaces String Builder usage with string concatenation whenever optimal 32 * 3. Optimizes String Builder concatenation loops 33 * 4. Merges consecutive String Builder append string calls into one appendN call 34 * 5. Merges consecutive String Builders into one String Builder if possible 35 * 36 * See compiler/docs/simplify_sb_doc.md for complete documentation 37 */ 38 39 constexpr size_t ARGS_NUM_2 = 2; 40 constexpr size_t ARGS_NUM_3 = 3; 41 constexpr size_t ARGS_NUM_4 = 4; 42 constexpr size_t SB_APPEND_STRING_MAX_ARGS = ARGS_NUM_4; 43 44 class SimplifyStringBuilder : public Optimization { 45 public: 46 explicit SimplifyStringBuilder(Graph *graph); 47 48 NO_MOVE_SEMANTIC(SimplifyStringBuilder); 49 NO_COPY_SEMANTIC(SimplifyStringBuilder); 50 ~SimplifyStringBuilder() override = default; 51 52 bool RunImpl() override; 53 IsEnable()54 bool IsEnable() const override 55 { 56 return g_options.IsCompilerSimplifyStringBuilder(); 57 } 58 GetPassName()59 const char *GetPassName() const override 60 { 61 return "SimplifyStringBuilder"; 62 } 63 void InvalidateAnalyses() override; 64 65 private: 66 // 1. Removes unnecessary String Builder instances 67 InstIter SkipToStringBuilderConstructorWithStringArg(InstIter begin, InstIter end); 68 void OptimizeStringBuilderToString(BasicBlock *block); 69 70 // 2. Replaces String Builder usage with string concatenation whenever optimal 71 struct ConcatenationMatch { 72 Inst *instance {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 73 Inst *ctorCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 74 Inst *toStringCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 75 size_t appendCount {0}; // NOLINT(misc-non-private-member-variables-in-classes) 76 std::array<IntrinsicInst *, ARGS_NUM_4> 77 appendIntrinsics {}; // NOLINT(misc-non-private-member-variables-in-classes) 78 }; 79 80 InstIter SkipToStringBuilderDefaultConstructor(InstIter begin, InstIter end); 81 IntrinsicInst *CreateConcatIntrinsic(const std::array<IntrinsicInst *, ARGS_NUM_4> &appendIntrinsics, 82 size_t appendCount, DataType::Type type, SaveStateInst *saveState); 83 bool MatchConcatenation(InstIter &begin, const InstIter &end, ConcatenationMatch &match); 84 void FixBrokenSaveStates(Inst *source, Inst *target); 85 void Check(const ConcatenationMatch &match); 86 void InsertIntrinsicAndFixSaveStates(IntrinsicInst *concatIntrinsic, 87 const std::array<IntrinsicInst *, ARGS_NUM_4> &appendIntrinsics, 88 size_t appendCount, Inst *before); 89 void ReplaceWithConcatIntrinsic(const ConcatenationMatch &match); 90 void RemoveStringBuilderInstance(Inst *instance); 91 void Cleanup(const ConcatenationMatch &match); 92 void OptimizeStringConcatenation(BasicBlock *block); 93 94 // 3. Optimizes String Builder concatenation loops 95 struct ConcatenationLoopMatch { 96 /* 97 This structure reflects the following string concatenation pattern: 98 99 preheader: 100 let initialValue: String = ... 101 header: 102 let accValue: String = preheader:initialValue | loop:accValue; 103 loop: 104 let preheaderInstance: StringBuilder; // preheader.instance 105 preheaderInstance = new StringBuilder(); // preheader.ctorCall 106 preheaderInstance.append(accValue); // preheader.appendAccValue 107 preheaderInstance.append(someArg0); // loop.appendInstructions[0] 108 ... Zero or more append non-accValue-arg calls 109 let tempAccum0 = preheaderInstance.toString(); // temp[0].toStringCall 110 111 ... The total number of temporary instances maybe zero 112 113 let tempInstanceN: StringBuilder // temp[N].instance 114 tempInstanceN = new StringBuilder(); // temp[N].ctorCall 115 tempInstanceN.append(tempAccumN); // temp[N].appendAccValue 116 tempInstanceN.append(someArgN); // loop.appendInstructions[N] 117 ... Zero or more append non-accValue-arg calls 118 accValue = tempInstanceN.toString(); // exit.toStringCall 119 120 The pattern above is then transformed into: 121 122 preheader: 123 let preheaderInstance: StringBuilder; 124 preheaderInstance = new StringBuilder(); 125 preheaderInstance.append(initialValue); 126 loop: 127 preheaderInstance.append(someArg0); 128 ... 129 preheaderInstance.append(someArgN); 130 exit: 131 let accValue: String = preheaderInstance.toString(); 132 133 To accomplish such transformation, we 134 1. Move all instructions collected in 'struct preheader' into loop preheader 135 2. Relink all append intrinsics collected in 'struct loop' to an instance moved to preheader 136 3. Move toString()-call instruction collected in 'struct exit' into loop post exit block 137 and relink it to an instance moved to preheader 138 4. Delete all temporary instructions 139 140 Multiple independent patterns maybe in a loop. 141 */ 142 ConcatenationLoopMatchConcatenationLoopMatch143 explicit ConcatenationLoopMatch(ArenaAllocator *allocator) : loop {allocator}, temp {allocator->Adapter()} {} 144 145 BasicBlock *block {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 146 PhiInst *accValue {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 147 Inst *initialValue {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 148 149 struct { 150 Inst *instance {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 151 Inst *ctorCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 152 Inst *appendAccValue {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 153 } preheader; // NOLINT(misc-non-private-member-variables-in-classes) 154 155 struct Loop { LoopConcatenationLoopMatch::Loop156 explicit Loop(ArenaAllocator *allocator) : appendInstructions {allocator->Adapter()} {} 157 ArenaVector<Inst *> appendInstructions; // NOLINT(misc-non-private-member-variables-in-classes) 158 } loop; // NOLINT(misc-non-private-member-variables-in-classes) 159 160 struct TemporaryInstructions { 161 Inst *intermediateValue {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 162 Inst *toStringCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 163 Inst *instance {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 164 Inst *ctorCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 165 Inst *appendAccValue {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 166 167 void Clear(); 168 bool IsEmpty() const; 169 }; 170 171 ArenaVector<TemporaryInstructions> temp; // NOLINT(misc-non-private-member-variables-in-classes) 172 173 struct { 174 Inst *toStringCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 175 } exit; // NOLINT(misc-non-private-member-variables-in-classes) 176 177 void Clear(); 178 bool IsInstanceHoistable() const; 179 }; 180 181 struct StringBuilderUsage { StringBuilderUsageStringBuilderUsage182 StringBuilderUsage(Inst *pInstance, CallInst *pCtorCall, ArenaAllocator *allocator) 183 : instance {pInstance}, 184 ctorCall {pCtorCall}, 185 appendInstructions {allocator->Adapter()}, 186 toStringCalls {allocator->Adapter()} 187 { 188 } 189 Inst *instance {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 190 Inst *ctorCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 191 ArenaVector<Inst *> appendInstructions; // NOLINT(misc-non-private-member-variables-in-classes) 192 ArenaVector<Inst *> toStringCalls; // NOLINT(misc-non-private-member-variables-in-classes) 193 }; 194 195 IntrinsicInst *CreateIntrinsicStringBuilderAppendString(Inst *instance, Inst *arg, SaveStateInst *saveState); 196 void NormalizeStringBuilderAppendInstructionUsers(Inst *instance, SaveStateInst *saveState); 197 ArenaVector<Inst *> FindStringBuilderAppendInstructions(Inst *instance); 198 199 void RemoveFromSaveStateInputs(Inst *inst, bool doMark = false); 200 void RemoveFromAllExceptPhiInputs(Inst *inst); 201 void ReconnectStringBuilderCascade(Inst *instance, Inst *inputInst, Inst *appendInstruction, 202 SaveStateInst *saveState); 203 void ReconnectStringBuilderCascades(const ConcatenationLoopMatch &match); 204 void ReconnectInstructions(const ConcatenationLoopMatch &match); 205 206 Inst *HoistInstructionToPreHeaderRecursively(BasicBlock *preHeader, Inst *lastInst, Inst *inst, 207 SaveStateInst *saveState); 208 Inst *HoistInstructionToPreHeader(BasicBlock *preHeader, Inst *lastInst, Inst *inst, SaveStateInst *saveState); 209 void HoistInstructionsToPreHeader(const ConcatenationLoopMatch &match, SaveStateInst *initSaveState); 210 void HoistCheckCastInstructionUsers(Inst *inst, BasicBlock *loopBlock, BasicBlock *postExit); 211 void HoistInstructionsToPostExit(const ConcatenationLoopMatch &match, SaveStateInst *saveState); 212 213 void Cleanup(const ConcatenationLoopMatch &match); 214 bool NeedRemoveInputFromSaveStateInstruction(Inst *inputInst); 215 void CollectSaveStateInputsForRemoval(Inst *inst); 216 void CleanupSaveStateInstructionInputs(Loop *loop); 217 Inst *FindHoistedToStringCallInput(Inst *phi); 218 void CleanupPhiInstructionInputs(Inst *phi); 219 void CleanupPhiInstructionInputs(Loop *loop); 220 bool HasNotHoistedUser(PhiInst *phi); 221 void RemoveUnusedPhiInstructions(Loop *loop); 222 void FixBrokenSaveStates(Loop *loop); 223 void Cleanup(Loop *loop); 224 225 bool AllUsersAreVisitedAppendInstructions(Inst *inst, Marker visited); 226 Inst *UpdateIntermediateValue(const StringBuilderUsage &usage, Inst *intermediateValue, 227 Marker appendInstructionVisited); 228 bool MatchTemporaryInstruction(ConcatenationLoopMatch &match, ConcatenationLoopMatch::TemporaryInstructions &temp, 229 Inst *appendInstruction, const Inst *accValue, Marker appendInstructionVisited); 230 void MatchTemporaryInstructions(const StringBuilderUsage &usage, ConcatenationLoopMatch &match, Inst *accValue, 231 Inst *intermediateValue, Marker appendInstructionVisited); 232 Inst *MatchHoistableInstructions(const StringBuilderUsage &usage, ConcatenationLoopMatch &match, 233 Marker appendInstructionVisited); 234 void MatchStringBuilderUsage(Inst *instance, StringBuilderUsage &usage); 235 const ArenaVector<ConcatenationLoopMatch> &MatchLoopConcatenation(Loop *loop); 236 237 bool HasInputFromPreHeader(PhiInst *phi) const; 238 bool HasToStringCallInput(PhiInst *phi) const; 239 bool HasAppendInstructionUser(Inst *inst) const; 240 bool HasPhiOrAppendUsersOnly(Inst *inst, Marker visited) const; 241 bool HasAppendUsersOnly(Inst *inst) const; 242 bool HasInputInst(Inst *inputInst, Inst *inst) const; 243 244 bool IsInstanceHoistable(const ConcatenationLoopMatch &match) const; 245 bool IsToStringHoistable(const ConcatenationLoopMatch &match, Marker appendInstructionVisited) const; 246 247 bool IsPhiAccumulatedValue(PhiInst *phi) const; 248 ArenaVector<Inst *> GetPhiAccumulatedValues(Loop *loop); 249 void StringBuilderUsagesDFS(Inst *inst, Loop *loop, Marker visited); 250 const ArenaVector<StringBuilderUsage> &GetStringBuilderUsagesPO(Inst *accValue); 251 252 // 4. Merges consecutive String Builder append string calls into one appendN call 253 void OptimizeStringConcatenation(Loop *loop); 254 IntrinsicInst *CreateIntrinsicStringBuilderAppendStrings(const ConcatenationMatch &match, SaveStateInst *saveState); 255 void ReplaceWithAppendIntrinsic(const ConcatenationMatch &match); 256 using StringBuilderCallsMap = ArenaMap<Inst *, InstVector>; 257 const StringBuilderCallsMap &CollectStringBuilderCalls(BasicBlock *block); 258 void ReplaceWithAppendIntrinsic(Inst *instance, const InstVector &calls, size_t from, size_t to); 259 void OptimizeStringBuilderAppendChain(BasicBlock *block); 260 261 // 5. Merges consecutive String Builders into one String Builder if possible 262 using InstPair = std::pair<Inst *, Inst *>; 263 using StringBuilderFirstLastCallsMap = ArenaMap<Inst *, InstPair>; 264 void CollectStringBuilderFirstCalls(BasicBlock *block); 265 void CollectStringBuilderLastCalls(BasicBlock *block); 266 void CollectStringBuilderFirstLastCalls(); 267 void CollectStringBuilderChainCalls(Inst *instance, Inst *inputInstance); 268 StringBuilderCallsMap &CollectStringBuilderChainCalls(); 269 bool CanMergeStringBuilders(Inst *instance, const InstPair &instanceCalls, Inst *inputInstance); 270 void Cleanup(Inst *instance, Inst *instanceFirstAppendCall, Inst *inputInstanceToStringCall); 271 void FixBrokenSaveStatesForStringBuilderCalls(Inst *instance); 272 void OptimizeStringBuilderChain(); 273 274 private: 275 bool isApplied_ {false}; 276 SaveStateBridgesBuilder ssb_ {}; 277 ArenaStack<Inst *> instructionsStack_; 278 ArenaVector<Inst *> instructionsVector_; 279 ArenaVector<InputDesc> inputDescriptors_; 280 ArenaVector<StringBuilderUsage> usages_; 281 ArenaVector<ConcatenationLoopMatch> matches_; 282 StringBuilderCallsMap stringBuilderCalls_; 283 StringBuilderFirstLastCallsMap stringBuilderFirstLastCalls_; 284 }; 285 286 } // namespace ark::compiler 287 288 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_SIMPLIFY_STRING_BUILDER_H 289