1 /** 2 * Copyright (c) 2023-2024 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 26 namespace ark::compiler { 27 28 /** 29 * 1. Removes unnecessary String Builder instances 30 * 2. Replaces String Builder usage with string concatenation whenever optimal 31 * 3. Optimizes String Builder concatenation loops 32 * 33 * See compiler/docs/simplify_sb_doc.md for complete documentation 34 */ 35 36 constexpr size_t ARGS_NUM_2 = 2; 37 constexpr size_t ARGS_NUM_3 = 3; 38 constexpr size_t ARGS_NUM_4 = 4; 39 40 class SimplifyStringBuilder : public Optimization { 41 public: 42 explicit SimplifyStringBuilder(Graph *graph); 43 44 NO_MOVE_SEMANTIC(SimplifyStringBuilder); 45 NO_COPY_SEMANTIC(SimplifyStringBuilder); 46 ~SimplifyStringBuilder() override = default; 47 48 bool RunImpl() override; 49 IsEnable()50 bool IsEnable() const override 51 { 52 return g_options.IsCompilerSimplifyStringBuilder(); 53 } 54 GetPassName()55 const char *GetPassName() const override 56 { 57 return "SimplifyStringBuilder"; 58 } 59 void InvalidateAnalyses() override; 60 61 private: 62 // 1. Removes unnecessary String Builder instances 63 InstIter SkipToStringBuilderConstructorWithStringArg(InstIter begin, InstIter end); 64 void OptimizeStringBuilderToString(BasicBlock *block); 65 66 // 2. Replaces String Builder usage with string concatenation whenever optimal 67 struct ConcatenationMatch { 68 Inst *instance {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 69 Inst *ctorCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 70 Inst *toStringCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 71 size_t appendCount {0}; // NOLINT(misc-non-private-member-variables-in-classes) 72 std::array<IntrinsicInst *, ARGS_NUM_4> 73 appendIntrinsics {}; // NOLINT(misc-non-private-member-variables-in-classes) 74 }; 75 76 InstIter SkipToStringBuilderDefaultConstructor(InstIter begin, InstIter end); 77 IntrinsicInst *CreateConcatIntrinsic(const std::array<IntrinsicInst *, ARGS_NUM_4> &appendIntrinsics, 78 size_t appendCount, DataType::Type type, SaveStateInst *saveState); 79 bool IsIntrinsicStringBuilderAppendString(Inst *inst) const; 80 bool MatchConcatenation(InstIter &begin, const InstIter &end, ConcatenationMatch &match); 81 void FixBrokenSaveStates(Inst *source, Inst *target); 82 void Check(const ConcatenationMatch &match); 83 void InsertIntrinsicAndFixSaveStates(IntrinsicInst *concatIntrinsic, 84 const std::array<IntrinsicInst *, ARGS_NUM_4> &appendIntrinsics, 85 size_t appendCount, Inst *before); 86 void ReplaceWithIntrinsic(const ConcatenationMatch &match); 87 void RemoveStringBuilderInstance(Inst *instance); 88 void Cleanup(const ConcatenationMatch &match); 89 void OptimizeStringConcatenation(BasicBlock *block); 90 91 // 3. Optimizes String Builder concatenation loops 92 struct ConcatenationLoopMatch { 93 /* 94 This structure reflects the following string concatenation pattern: 95 96 preheader: 97 let initialValue: String = ... 98 header: 99 let accValue: String = preheader:initialValue | loop:accValue; 100 loop: 101 let preheaderInstance: StringBuilder; // preheader.instance 102 preheaderInstance = new StringBuilder(); // preheader.ctorCall 103 preheaderInstance.append(accValue); // preheader.appendAccValue 104 preheaderInstance.append(someArg0); // loop.appendInstructions[0] 105 ... Zero or more append non-accValue-arg calls 106 let tempAccum0 = preheaderInstance.toString(); // temp[0].toStringCall 107 108 ... The total number of temporary instances maybe zero 109 110 let tempInstanceN: StringBuilder // temp[N].instance 111 tempInstanceN = new StringBuilder(); // temp[N].ctorCall 112 tempInstanceN.append(tempAccumN); // temp[N].appendAccValue 113 tempInstanceN.append(someArgN); // loop.appendInstructions[N] 114 ... Zero or more append non-accValue-arg calls 115 accValue = tempInstanceN.toString(); // exit.toStringCall 116 117 The pattern above is then transformed into: 118 119 preheader: 120 let preheaderInstance: StringBuilder; 121 preheaderInstance = new StringBuilder(); 122 preheaderInstance.append(initialValue); 123 loop: 124 preheaderInstance.append(someArg0); 125 ... 126 preheaderInstance.append(someArgN); 127 exit: 128 let accValue: String = preheaderInstance.toString(); 129 130 To accomplish such transformation, we 131 1. Move all instructions collected in 'struct preheader' into loop preheader 132 2. Relink all append intrinsics collected in 'struct loop' to an instance moved to preheader 133 3. Move toString()-call instruction collected in 'struct exit' into loop post exit block 134 and relink it to an instance moved to preheader 135 4. Delete all temporary instructions 136 137 Multiple independent patterns maybe in a loop. 138 */ 139 ConcatenationLoopMatchConcatenationLoopMatch140 explicit ConcatenationLoopMatch(ArenaAllocator *allocator) : loop {allocator}, temp {allocator->Adapter()} {} 141 142 BasicBlock *block {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 143 PhiInst *accValue {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 144 Inst *initialValue {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 145 146 struct { 147 Inst *instance {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 148 Inst *ctorCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 149 Inst *appendAccValue {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 150 } preheader; // NOLINT(misc-non-private-member-variables-in-classes) 151 152 struct Loop { LoopConcatenationLoopMatch::Loop153 explicit Loop(ArenaAllocator *allocator) : appendInstructions {allocator->Adapter()} {} 154 ArenaVector<Inst *> appendInstructions; // NOLINT(misc-non-private-member-variables-in-classes) 155 } loop; // NOLINT(misc-non-private-member-variables-in-classes) 156 157 struct TemporaryInstructions { 158 Inst *intermediateValue {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 159 Inst *toStringCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 160 Inst *instance {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 161 Inst *ctorCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 162 Inst *appendAccValue {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 163 164 void Clear(); 165 bool IsEmpty() const; 166 }; 167 168 ArenaVector<TemporaryInstructions> temp; // NOLINT(misc-non-private-member-variables-in-classes) 169 170 struct { 171 Inst *toStringCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 172 } exit; // NOLINT(misc-non-private-member-variables-in-classes) 173 174 void Clear(); 175 bool IsInstanceHoistable() const; 176 }; 177 178 struct StringBuilderUsage { StringBuilderUsageStringBuilderUsage179 StringBuilderUsage(Inst *pInstance, CallInst *pCtorCall, ArenaAllocator *allocator) 180 : instance {pInstance}, 181 ctorCall {pCtorCall}, 182 appendInstructions {allocator->Adapter()}, 183 toStringCalls {allocator->Adapter()} 184 { 185 } 186 Inst *instance {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 187 Inst *ctorCall {nullptr}; // NOLINT(misc-non-private-member-variables-in-classes) 188 ArenaVector<Inst *> appendInstructions; // NOLINT(misc-non-private-member-variables-in-classes) 189 ArenaVector<Inst *> toStringCalls; // NOLINT(misc-non-private-member-variables-in-classes) 190 }; 191 192 IntrinsicInst *CreateIntrinsicStringBuilderAppendString(Inst *instance, Inst *arg, SaveStateInst *saveState); 193 void NormalizeStringBuilderAppendInstructionUsers(Inst *instance, SaveStateInst *saveState); 194 ArenaVector<Inst *> FindStringBuilderAppendInstructions(Inst *instance); 195 196 void RemoveFromSaveStateInputs(Inst *inst); 197 void RemoveFromAllExceptPhiInputs(Inst *inst); 198 void ReconnectStringBuilderCascade(Inst *instance, Inst *inputInst, Inst *appendInstruction, 199 SaveStateInst *saveState); 200 void ReconnectStringBuilderCascades(const ConcatenationLoopMatch &match); 201 void ReconnectInstructions(const ConcatenationLoopMatch &match); 202 203 Inst *HoistInstructionToPreHeaderRecursively(BasicBlock *preHeader, Inst *lastInst, Inst *inst, 204 SaveStateInst *saveState); 205 Inst *HoistInstructionToPreHeader(BasicBlock *preHeader, Inst *lastInst, Inst *inst, SaveStateInst *saveState); 206 void HoistInstructionsToPreHeader(const ConcatenationLoopMatch &match, SaveStateInst *initSaveState); 207 void HoistCheckCastInstructionUsers(Inst *inst, BasicBlock *loopBlock, BasicBlock *postExit); 208 void HoistInstructionsToPostExit(const ConcatenationLoopMatch &match, SaveStateInst *saveState); 209 210 void Cleanup(const ConcatenationLoopMatch &match); 211 bool NeedRemoveInputFromSaveStateInstruction(Inst *inputInst); 212 void CollectSaveStateInputsForRemoval(Inst *inst); 213 void CleanupSaveStateInstructionInputs(Loop *loop); 214 bool NeedRemoveInputFromPhiInstruction(Inst *inputInst); 215 void CleanupPhiInstructionInputs(Inst *phi); 216 void CleanupPhiInstructionInputs(Loop *loop); 217 bool HasNotHoistedUser(PhiInst *phi); 218 void RemoveUnusedPhiInstructions(Loop *loop); 219 void FixBrokenSaveStates(Loop *loop); 220 void Cleanup(Loop *loop); 221 222 bool AllUsersAreVisitedAppendInstructions(Inst *inst, Marker visited); 223 Inst *UpdateIntermediateValue(const StringBuilderUsage &usage, Inst *intermediateValue, 224 Marker appendInstructionVisited); 225 void MatchTemporaryInstructions(const StringBuilderUsage &usage, ConcatenationLoopMatch &match, Inst *accValue, 226 Inst *intermediateValue, Marker appendInstructionVisited); 227 Inst *MatchHoistableInstructions(const StringBuilderUsage &usage, ConcatenationLoopMatch &match, 228 Marker appendInstructionVisited); 229 void MatchStringBuilderUsage(Inst *instance, StringBuilderUsage &usage); 230 const ArenaVector<ConcatenationLoopMatch> &MatchLoopConcatenation(Loop *loop); 231 232 bool HasInputFromPreHeader(PhiInst *phi) const; 233 bool HasToStringCallInput(PhiInst *phi) const; 234 bool HasAppendInstructionUser(Inst *inst) const; 235 bool HasPhiOrAppendUsersOnly(Inst *inst, Marker visited) const; 236 bool HasAppendUsersOnly(Inst *inst) const; 237 bool HasInputInst(Inst *inputInst, Inst *inst) const; 238 239 bool IsInstanceHoistable(const ConcatenationLoopMatch &match) const; 240 bool IsToStringHoistable(const ConcatenationLoopMatch &match, Marker appendInstructionVisited) const; 241 242 bool IsPhiAccumulatedValue(PhiInst *phi) const; 243 ArenaVector<Inst *> GetPhiAccumulatedValues(Loop *loop); 244 void StringBuilderUsagesDFS(Inst *inst, Loop *loop, Marker visited); 245 const ArenaVector<StringBuilderUsage> &GetStringBuilderUsagesPO(Inst *accValue); 246 247 void OptimizeStringConcatenation(Loop *loop); 248 249 private: 250 bool isApplied_ {false}; 251 SaveStateBridgesBuilder ssb_ {}; 252 ArenaStack<Inst *> instructionsStack_; 253 ArenaVector<Inst *> instructionsVector_; 254 ArenaVector<std::pair<Inst *, size_t>> inputDescriptors_; 255 ArenaVector<StringBuilderUsage> usages_; 256 ArenaVector<ConcatenationLoopMatch> matches_; 257 }; 258 259 } // namespace ark::compiler 260 261 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_SIMPLIFY_STRING_BUILDER_H 262