1 /* 2 * Copyright (c) 2023 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 MAPLEBE_CG_INCLUDE_CGSSUPRE_H 17 #define MAPLEBE_CG_INCLUDE_CGSSUPRE_H 18 #include <vector> 19 #include "mempool.h" 20 #include "mempool_allocator.h" 21 #include "cg_dominance.h" 22 #include "cg_ssa_pre.h" 23 24 // Use SSUPRE to determine where to insert restores for callee-saved registers. 25 // The external interface is DoRestorePlacementOpt(). Class SPreWorkCand is used 26 // as input/output interface. 27 28 namespace maplebe { 29 30 // This must have been constructed by the caller of DoRestorePlacementOpt() and 31 // passed to it as parameter. The caller of DoRestorePlacementOpt() describes 32 // the problem via occBBs and saveBBs. DoRestorePlacementOpt()'s outputs are 33 // returned to the caller by setting restoreAtEntryBBs and restoreAtExitBBs. 34 class SPreWorkCand { 35 public: SPreWorkCand(MapleAllocator * alloc)36 explicit SPreWorkCand(MapleAllocator *alloc) 37 : occBBs(alloc->Adapter()), 38 saveBBs(alloc->Adapter()), 39 restoreAtEntryBBs(alloc->Adapter()), 40 restoreAtExitBBs(alloc->Adapter()) 41 { 42 } 43 // inputs 44 MapleSet<BBId> occBBs; // Id's of BBs with appearances of the callee-saved reg 45 MapleSet<BBId> saveBBs; // Id's of BBs with saves of the callee-saved reg 46 // outputs 47 MapleSet<BBId> restoreAtEntryBBs; // Id's of BBs to insert restores of the register at BB entry 48 MapleSet<BBId> restoreAtExitBBs; // Id's of BBs to insert restores of the register at BB exit 49 bool restoreAtEpilog = false; // if true, no shrinkwrapping can be done and 50 // the other outputs can be ignored 51 }; 52 53 extern void DoRestorePlacementOpt(CGFunc *f, PostDomAnalysis *pdom, SPreWorkCand *workCand); 54 55 enum SOccType { 56 kSOccUndef, 57 kSOccReal, 58 kSOccLambda, 59 kSOccLambdaRes, 60 kSOccEntry, 61 kSOccKill, 62 }; 63 64 class SOcc { 65 public: SOcc(SOccType ty,BB * bb)66 SOcc(SOccType ty, BB *bb) : occTy(ty), cgbb(bb) {} 67 virtual ~SOcc() = default; 68 69 virtual void Dump() const = 0; IsPostDominate(PostDomAnalysis * pdom,const SOcc * occ)70 bool IsPostDominate(PostDomAnalysis *pdom, const SOcc *occ) const 71 { 72 return pdom->PostDominate(*cgbb, *occ->cgbb); 73 } 74 75 SOccType occTy; 76 uint32 classId = 0; 77 BB *cgbb; // the BB it occurs in 78 SOcc *use = nullptr; // points to its single use 79 }; 80 81 class SRealOcc : public SOcc { 82 public: SRealOcc(BB * bb)83 explicit SRealOcc(BB *bb) : SOcc(kSOccReal, bb) {} 84 virtual ~SRealOcc() = default; 85 Dump()86 void Dump() const override 87 { 88 LogInfo::MapleLogger() << "RealOcc at bb" << cgbb->GetId(); 89 LogInfo::MapleLogger() << " classId" << classId; 90 } 91 92 bool redundant = true; 93 }; 94 95 class SLambdaOcc; 96 97 class SLambdaResOcc : public SOcc { 98 public: SLambdaResOcc(BB * bb)99 explicit SLambdaResOcc(BB *bb) : SOcc(kSOccLambdaRes, bb) {} 100 virtual ~SLambdaResOcc() = default; 101 Dump()102 void Dump() const override 103 { 104 LogInfo::MapleLogger() << "LambdaResOcc at bb" << cgbb->GetId() << " classId" << classId; 105 } 106 107 SLambdaOcc *useLambdaOcc = nullptr; // its rhs use 108 bool hasRealUse = false; 109 bool insertHere = false; 110 }; 111 112 class SLambdaOcc : public SOcc { 113 public: SLambdaOcc(BB * bb,MapleAllocator & alloc)114 SLambdaOcc(BB *bb, MapleAllocator &alloc) : SOcc(kSOccLambda, bb), lambdaRes(alloc.Adapter()) {} 115 virtual ~SLambdaOcc() = default; 116 WillBeAnt()117 bool WillBeAnt() const 118 { 119 return isCanBeAnt && !isEarlier; 120 } 121 Dump()122 void Dump() const override 123 { 124 LogInfo::MapleLogger() << "LambdaOcc at bb" << cgbb->GetId() << " classId" << classId << " Lambda["; 125 for (size_t i = 0; i < lambdaRes.size(); i++) { 126 lambdaRes[i]->Dump(); 127 DEBUG_ASSERT(lambdaRes.size() >= 1, "lambdaRes.size() -1 should be uint"); 128 if (i != lambdaRes.size() - 1) { 129 LogInfo::MapleLogger() << ", "; 130 } 131 } 132 LogInfo::MapleLogger() << "]"; 133 } 134 135 bool isUpsafe = true; 136 bool isCanBeAnt = true; 137 bool isEarlier = true; 138 MapleVector<SLambdaResOcc *> lambdaRes; 139 }; 140 141 class SEntryOcc : public SOcc { 142 public: SEntryOcc(BB * bb)143 explicit SEntryOcc(BB *bb) : SOcc(kSOccEntry, bb) {} 144 virtual ~SEntryOcc() = default; 145 Dump()146 void Dump() const 147 { 148 LogInfo::MapleLogger() << "EntryOcc at bb" << cgbb->GetId(); 149 } 150 }; 151 152 class SKillOcc : public SOcc { 153 public: SKillOcc(BB * bb)154 explicit SKillOcc(BB *bb) : SOcc(kSOccKill, bb) {} 155 virtual ~SKillOcc() = default; 156 Dump()157 void Dump() const override 158 { 159 LogInfo::MapleLogger() << "KillOcc at bb" << cgbb->GetId(); 160 } 161 }; 162 163 class SSUPre { 164 public: SSUPre(CGFunc * cgfunc,PostDomAnalysis * pd,MemPool * memPool,SPreWorkCand * wkcand,bool alap,bool enDebug)165 SSUPre(CGFunc *cgfunc, PostDomAnalysis *pd, MemPool *memPool, SPreWorkCand *wkcand, bool alap, bool enDebug) 166 : cgFunc(cgfunc), 167 pdom(pd), 168 spreMp(memPool), 169 spreAllocator(memPool), 170 workCand(wkcand), 171 fullyAvailBBs(cgfunc->GetAllBBs().size(), true, spreAllocator.Adapter()), 172 lambdaDfns(std::less<uint32>(), spreAllocator.Adapter()), 173 classCount(0), 174 realOccs(spreAllocator.Adapter()), 175 allOccs(spreAllocator.Adapter()), 176 lambdaOccs(spreAllocator.Adapter()), 177 entryOccs(spreAllocator.Adapter()), 178 asLateAsPossible(alap), 179 enabledDebug(enDebug) 180 { 181 CreateEntryOcc(cgfunc->GetFirstBB()); 182 } 183 ~SSUPre() = default; 184 185 void ApplySSUPre(); 186 187 private: 188 // step 6 methods 189 void CodeMotion(); 190 // step 5 methods 191 void Finalize(); 192 // step 4 methods 193 void ResetCanBeAnt(SLambdaOcc *lambda) const; 194 void ComputeCanBeAnt() const; 195 void ResetEarlier(SLambdaOcc *lambda) const; 196 void ComputeEarlier() const; 197 // step 3 methods 198 void ResetUpsafe(const SLambdaResOcc *lambdaRes) const; 199 void ComputeUpsafe() const; 200 // step 2 methods 201 void Rename(); 202 // step 1 methods GetIterPdomFrontier(const BB * bb,MapleSet<uint32> * pdfset)203 void GetIterPdomFrontier(const BB *bb, MapleSet<uint32> *pdfset) const 204 { 205 for (BBId bbid : pdom->GetIpdomFrontier(bb->GetId())) { 206 (void)pdfset->insert(pdom->GetPdtDfnItem(bbid)); 207 } 208 } 209 void FormLambdas(); 210 void CreateSortedOccs(); 211 // step 0 methods CreateEntryOcc(BB * bb)212 void CreateEntryOcc(BB *bb) 213 { 214 SEntryOcc *entryOcc = spreMp->New<SEntryOcc>(bb); 215 entryOccs.push_back(entryOcc); 216 } 217 void PropagateNotAvail(BB *bb, std::set<BB *, BBIdCmp> *visitedBBs); 218 void FormReals(); 219 220 CGFunc *cgFunc; 221 PostDomAnalysis *pdom; 222 MemPool *spreMp; 223 MapleAllocator spreAllocator; 224 SPreWorkCand *workCand; 225 // step 0 226 MapleVector<bool> fullyAvailBBs; // index is BBid; true if occ is fully available at BB exit 227 // step 1 lambda insertion data structures: 228 MapleSet<uint32> lambdaDfns; // set by FormLambdas(); set of BBs in terms of 229 // their dfn's; index into 230 // dominance->pdt_preorder to get their bbid's 231 // step 2 renaming 232 uint32 classCount; // for assigning new class id 233 // the following 4 lists are all maintained in order of pdt_preorder 234 MapleVector<SOcc *> realOccs; // both real and kill occurrences 235 MapleVector<SOcc *> allOccs; 236 MapleVector<SLambdaOcc *> lambdaOccs; 237 MapleVector<SEntryOcc *> entryOccs; 238 bool asLateAsPossible; 239 bool enabledDebug; 240 }; 241 242 }; // namespace maplebe 243 #endif // MAPLEBE_CG_INCLUDE_CGSSUPRE_H 244