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_CG_SSU_PRE_H 17 #define MAPLEBE_CG_INCLUDE_CG_SSU_PRE_H 18 #include <vector> 19 #include "mempool.h" 20 #include "mempool_allocator.h" 21 #include "cg_dominance.h" 22 #include "loop.h" 23 24 // Use SSAPRE to determine where to insert saves for callee-saved registers. 25 // The external interface is DoSavePlacementOpt(). Class SsaPreWorkCand is used 26 // as input/output interface. 27 28 namespace maplebe { 29 30 using BBId = uint32; 31 32 // This must have been constructed by the caller of DoSavePlacementOpt() and 33 // passed to it as parameter. The caller of DoSavePlacementOpt() describes 34 // the problem via occBBs. DoSavePlacementOpt()'s outputs are returned to the 35 // caller by setting saveAtEntryBBs. 36 class SsaPreWorkCand { 37 public: SsaPreWorkCand(MapleAllocator * alloc)38 explicit SsaPreWorkCand(MapleAllocator *alloc) : occBBs(alloc->Adapter()), saveAtEntryBBs(alloc->Adapter()) {} 39 // inputs 40 MapleSet<BBId> occBBs; // Id's of BBs with appearances of the callee-saved reg 41 // outputs 42 MapleSet<BBId> saveAtEntryBBs; // Id's of BBs to insert saves of the register at BB entry 43 bool saveAtProlog = false; // if true, no shrinkwrapping can be done and 44 // the other outputs can be ignored 45 }; 46 47 extern void DoSavePlacementOpt(CGFunc *f, DomAnalysis *dom, LoopAnalysis *loop, SsaPreWorkCand *workCand); 48 49 enum AOccType { 50 kAOccUndef, 51 kAOccReal, 52 kAOccPhi, 53 kAOccPhiOpnd, 54 kAOccExit, 55 }; 56 57 class Occ { 58 public: Occ(AOccType ty,BB * bb)59 Occ(AOccType ty, BB *bb) : occTy(ty), cgbb(bb) {} 60 virtual ~Occ() = default; 61 62 virtual void Dump() const = 0; IsDominate(DomAnalysis * dom,const Occ * occ)63 bool IsDominate(DomAnalysis *dom, const Occ *occ) const 64 { 65 return dom->Dominate(*cgbb, *occ->cgbb); 66 } 67 68 AOccType occTy; 69 uint32 classId = 0; 70 BB *cgbb; // the BB it occurs in 71 Occ *def = nullptr; // points to its single def 72 }; 73 74 class RealOcc : public Occ { 75 public: RealOcc(BB * bb)76 explicit RealOcc(BB *bb) : Occ(kAOccReal, bb) {} 77 virtual ~RealOcc() = default; 78 Dump()79 void Dump() const override 80 { 81 LogInfo::MapleLogger() << "RealOcc at bb" << cgbb->GetId(); 82 LogInfo::MapleLogger() << " classId" << classId; 83 } 84 85 bool redundant = true; 86 }; 87 88 class PhiOcc; 89 90 class PhiOpndOcc : public Occ { 91 public: PhiOpndOcc(BB * bb)92 explicit PhiOpndOcc(BB *bb) : Occ(kAOccPhiOpnd, bb) {} 93 virtual ~PhiOpndOcc() = default; 94 Dump()95 void Dump() const override 96 { 97 LogInfo::MapleLogger() << "PhiOpndOcc at bb" << cgbb->GetId() << " classId" << classId; 98 } 99 100 PhiOcc *defPhiOcc = nullptr; // its lhs definition 101 bool hasRealUse = false; 102 bool insertHere = false; 103 }; 104 105 class PhiOcc : public Occ { 106 public: PhiOcc(BB * bb,MapleAllocator & alloc)107 PhiOcc(BB *bb, MapleAllocator &alloc) : Occ(kAOccPhi, bb), phiOpnds(alloc.Adapter()) {} 108 virtual ~PhiOcc() = default; 109 WillBeAvail()110 bool WillBeAvail() const 111 { 112 return isCanBeAvail && !isLater; 113 } 114 Dump()115 void Dump() const override 116 { 117 LogInfo::MapleLogger() << "PhiOcc at bb" << cgbb->GetId() << " classId" << classId << " Phi["; 118 for (size_t i = 0; i < phiOpnds.size(); i++) { 119 phiOpnds[i]->Dump(); 120 DEBUG_ASSERT(phiOpnds.size() >= 1, "phiopnds size -1 should be unit"); 121 if (i != phiOpnds.size() - 1) { 122 LogInfo::MapleLogger() << ", "; 123 } 124 } 125 LogInfo::MapleLogger() << "]"; 126 } 127 128 bool isDownsafe = true; 129 bool speculativeDownsafe = false; // true if set to downsafe via speculation 130 bool isCanBeAvail = true; 131 bool isLater = true; 132 MapleVector<PhiOpndOcc *> phiOpnds; 133 }; 134 135 class ExitOcc : public Occ { 136 public: ExitOcc(BB * bb)137 explicit ExitOcc(BB *bb) : Occ(kAOccExit, bb) {} 138 virtual ~ExitOcc() = default; 139 Dump()140 void Dump() const override 141 { 142 LogInfo::MapleLogger() << "ExitOcc at bb" << cgbb->GetId(); 143 } 144 }; 145 146 class SSAPre { 147 public: SSAPre(CGFunc * cgfunc,DomAnalysis * dm,LoopAnalysis * loop,MemPool * memPool,SsaPreWorkCand * wkcand,bool aeap,bool enDebug)148 SSAPre(CGFunc *cgfunc, DomAnalysis *dm, LoopAnalysis *loop, MemPool *memPool, SsaPreWorkCand *wkcand, 149 bool aeap, bool enDebug) 150 : cgFunc(cgfunc), 151 dom(dm), 152 loop(loop), 153 preMp(memPool), 154 preAllocator(memPool), 155 workCand(wkcand), 156 fullyAntBBs(cgfunc->GetAllBBs().size(), true, preAllocator.Adapter()), 157 phiDfns(std::less<uint32>(), preAllocator.Adapter()), 158 classCount(0), 159 realOccs(preAllocator.Adapter()), 160 allOccs(preAllocator.Adapter()), 161 phiOccs(preAllocator.Adapter()), 162 exitOccs(preAllocator.Adapter()), 163 asEarlyAsPossible(aeap), 164 enabledDebug(enDebug) 165 { 166 } 167 ~SSAPre() = default; 168 169 void ApplySSAPre(); 170 171 private: 172 // step 6 methods 173 void CodeMotion(); 174 // step 5 methods 175 void Finalize(); 176 // step 4 methods 177 void ResetCanBeAvail(PhiOcc *phi) const; 178 void ComputeCanBeAvail() const; 179 void ResetLater(PhiOcc *phi) const; 180 void ComputeLater() const; 181 // step 3 methods 182 void ResetDownsafe(const PhiOpndOcc *phiOpnd) const; 183 void ComputeDownsafe() const; 184 // step 2 methods 185 void Rename(); 186 // step 1 methods GetIterDomFrontier(const BB * bb,MapleSet<uint32> * dfset)187 void GetIterDomFrontier(const BB *bb, MapleSet<uint32> *dfset) const 188 { 189 for (BBId bbid : dom->GetIdomFrontier(bb->GetId())) { 190 (void)dfset->insert(dom->GetDtDfnItem(bbid)); 191 } 192 } 193 void FormPhis(); 194 void CreateSortedOccs(); 195 // step 0 methods 196 void PropagateNotAnt(BB *bb, std::set<BB *, BBIdCmp> *visitedBBs); 197 void FormRealsNExits(); 198 199 CGFunc *cgFunc; 200 DomAnalysis *dom; 201 LoopAnalysis *loop; 202 MemPool *preMp; 203 MapleAllocator preAllocator; 204 SsaPreWorkCand *workCand; 205 // step 0 206 MapleVector<bool> fullyAntBBs; // index is BBid; true if occ is fully anticipated at BB entry 207 // step 1 phi insertion data structures: 208 MapleSet<uint32> phiDfns; // set by FormPhis(); set of BBs in terms of their 209 // dfn's; index into dominance->dt_preorder to get 210 // their bbid's 211 // step 2 renaming 212 uint32 classCount; // for assigning new class id 213 // the following 4 lists are all maintained in order of dt_preorder 214 MapleVector<Occ *> realOccs; 215 MapleVector<Occ *> allOccs; 216 MapleVector<PhiOcc *> phiOccs; 217 MapleVector<ExitOcc *> exitOccs; 218 bool asEarlyAsPossible; 219 bool enabledDebug; 220 }; 221 222 }; // namespace maplebe 223 #endif // MAPLEBE_CG_INCLUDE_CG_SSA_PRE_H 224