| File: | llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp |
| Warning: | line 285, column 18 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- HexagonEarlyIfConv.cpp ---------------------------------------------===// | ||||||
| 2 | // | ||||||
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | ||||||
| 4 | // See https://llvm.org/LICENSE.txt for license information. | ||||||
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | ||||||
| 6 | // | ||||||
| 7 | //===----------------------------------------------------------------------===// | ||||||
| 8 | // | ||||||
| 9 | // This implements a Hexagon-specific if-conversion pass that runs on the | ||||||
| 10 | // SSA form. | ||||||
| 11 | // In SSA it is not straightforward to represent instructions that condi- | ||||||
| 12 | // tionally define registers, since a conditionally-defined register may | ||||||
| 13 | // only be used under the same condition on which the definition was based. | ||||||
| 14 | // To avoid complications of this nature, this patch will only generate | ||||||
| 15 | // predicated stores, and speculate other instructions from the "if-conver- | ||||||
| 16 | // ted" block. | ||||||
| 17 | // The code will recognize CFG patterns where a block with a conditional | ||||||
| 18 | // branch "splits" into a "true block" and a "false block". Either of these | ||||||
| 19 | // could be omitted (in case of a triangle, for example). | ||||||
| 20 | // If after conversion of the side block(s) the CFG allows it, the resul- | ||||||
| 21 | // ting blocks may be merged. If the "join" block contained PHI nodes, they | ||||||
| 22 | // will be replaced with MUX (or MUX-like) instructions to maintain the | ||||||
| 23 | // semantics of the PHI. | ||||||
| 24 | // | ||||||
| 25 | // Example: | ||||||
| 26 | // | ||||||
| 27 | // %40 = L2_loadrub_io killed %39, 1 | ||||||
| 28 | // %41 = S2_tstbit_i killed %40, 0 | ||||||
| 29 | // J2_jumpt killed %41, <%bb.5>, implicit dead %pc | ||||||
| 30 | // J2_jump <%bb.4>, implicit dead %pc | ||||||
| 31 | // Successors according to CFG: %bb.4(62) %bb.5(62) | ||||||
| 32 | // | ||||||
| 33 | // %bb.4: derived from LLVM BB %if.then | ||||||
| 34 | // Predecessors according to CFG: %bb.3 | ||||||
| 35 | // %11 = A2_addp %6, %10 | ||||||
| 36 | // S2_storerd_io %32, 16, %11 | ||||||
| 37 | // Successors according to CFG: %bb.5 | ||||||
| 38 | // | ||||||
| 39 | // %bb.5: derived from LLVM BB %if.end | ||||||
| 40 | // Predecessors according to CFG: %bb.3 %bb.4 | ||||||
| 41 | // %12 = PHI %6, <%bb.3>, %11, <%bb.4> | ||||||
| 42 | // %13 = A2_addp %7, %12 | ||||||
| 43 | // %42 = C2_cmpeqi %9, 10 | ||||||
| 44 | // J2_jumpf killed %42, <%bb.3>, implicit dead %pc | ||||||
| 45 | // J2_jump <%bb.6>, implicit dead %pc | ||||||
| 46 | // Successors according to CFG: %bb.6(4) %bb.3(124) | ||||||
| 47 | // | ||||||
| 48 | // would become: | ||||||
| 49 | // | ||||||
| 50 | // %40 = L2_loadrub_io killed %39, 1 | ||||||
| 51 | // %41 = S2_tstbit_i killed %40, 0 | ||||||
| 52 | // spec-> %11 = A2_addp %6, %10 | ||||||
| 53 | // pred-> S2_pstorerdf_io %41, %32, 16, %11 | ||||||
| 54 | // %46 = PS_pselect %41, %6, %11 | ||||||
| 55 | // %13 = A2_addp %7, %46 | ||||||
| 56 | // %42 = C2_cmpeqi %9, 10 | ||||||
| 57 | // J2_jumpf killed %42, <%bb.3>, implicit dead %pc | ||||||
| 58 | // J2_jump <%bb.6>, implicit dead %pc | ||||||
| 59 | // Successors according to CFG: %bb.6 %bb.3 | ||||||
| 60 | |||||||
| 61 | #include "Hexagon.h" | ||||||
| 62 | #include "HexagonInstrInfo.h" | ||||||
| 63 | #include "HexagonSubtarget.h" | ||||||
| 64 | #include "llvm/ADT/DenseSet.h" | ||||||
| 65 | #include "llvm/ADT/SmallVector.h" | ||||||
| 66 | #include "llvm/ADT/StringRef.h" | ||||||
| 67 | #include "llvm/ADT/iterator_range.h" | ||||||
| 68 | #include "llvm/CodeGen/MachineBasicBlock.h" | ||||||
| 69 | #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" | ||||||
| 70 | #include "llvm/CodeGen/MachineDominators.h" | ||||||
| 71 | #include "llvm/CodeGen/MachineFunction.h" | ||||||
| 72 | #include "llvm/CodeGen/MachineFunctionPass.h" | ||||||
| 73 | #include "llvm/CodeGen/MachineInstr.h" | ||||||
| 74 | #include "llvm/CodeGen/MachineInstrBuilder.h" | ||||||
| 75 | #include "llvm/CodeGen/MachineLoopInfo.h" | ||||||
| 76 | #include "llvm/CodeGen/MachineOperand.h" | ||||||
| 77 | #include "llvm/CodeGen/MachineRegisterInfo.h" | ||||||
| 78 | #include "llvm/CodeGen/TargetRegisterInfo.h" | ||||||
| 79 | #include "llvm/IR/DebugLoc.h" | ||||||
| 80 | #include "llvm/Pass.h" | ||||||
| 81 | #include "llvm/Support/BranchProbability.h" | ||||||
| 82 | #include "llvm/Support/CommandLine.h" | ||||||
| 83 | #include "llvm/Support/Compiler.h" | ||||||
| 84 | #include "llvm/Support/Debug.h" | ||||||
| 85 | #include "llvm/Support/ErrorHandling.h" | ||||||
| 86 | #include "llvm/Support/raw_ostream.h" | ||||||
| 87 | #include <cassert> | ||||||
| 88 | #include <iterator> | ||||||
| 89 | |||||||
| 90 | #define DEBUG_TYPE"hexagon-eif" "hexagon-eif" | ||||||
| 91 | |||||||
| 92 | using namespace llvm; | ||||||
| 93 | |||||||
| 94 | namespace llvm { | ||||||
| 95 | |||||||
| 96 | FunctionPass *createHexagonEarlyIfConversion(); | ||||||
| 97 | void initializeHexagonEarlyIfConversionPass(PassRegistry& Registry); | ||||||
| 98 | |||||||
| 99 | } // end namespace llvm | ||||||
| 100 | |||||||
| 101 | static cl::opt<bool> EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden, | ||||||
| 102 | cl::init(true), cl::desc("Enable branch probability info")); | ||||||
| 103 | static cl::opt<unsigned> SizeLimit("eif-limit", cl::init(6), cl::Hidden, | ||||||
| 104 | cl::desc("Size limit in Hexagon early if-conversion")); | ||||||
| 105 | static cl::opt<bool> SkipExitBranches("eif-no-loop-exit", cl::init(false), | ||||||
| 106 | cl::Hidden, cl::desc("Do not convert branches that may exit the loop")); | ||||||
| 107 | |||||||
| 108 | namespace { | ||||||
| 109 | |||||||
| 110 | struct PrintMB { | ||||||
| 111 | PrintMB(const MachineBasicBlock *B) : MB(B) {} | ||||||
| 112 | |||||||
| 113 | const MachineBasicBlock *MB; | ||||||
| 114 | }; | ||||||
| 115 | raw_ostream &operator<< (raw_ostream &OS, const PrintMB &P) { | ||||||
| 116 | if (!P.MB) | ||||||
| 117 | return OS << "<none>"; | ||||||
| 118 | return OS << '#' << P.MB->getNumber(); | ||||||
| 119 | } | ||||||
| 120 | |||||||
| 121 | struct FlowPattern { | ||||||
| 122 | FlowPattern() = default; | ||||||
| 123 | FlowPattern(MachineBasicBlock *B, unsigned PR, MachineBasicBlock *TB, | ||||||
| 124 | MachineBasicBlock *FB, MachineBasicBlock *JB) | ||||||
| 125 | : SplitB(B), TrueB(TB), FalseB(FB), JoinB(JB), PredR(PR) {} | ||||||
| 126 | |||||||
| 127 | MachineBasicBlock *SplitB = nullptr; | ||||||
| 128 | MachineBasicBlock *TrueB = nullptr; | ||||||
| 129 | MachineBasicBlock *FalseB = nullptr; | ||||||
| 130 | MachineBasicBlock *JoinB = nullptr; | ||||||
| 131 | unsigned PredR = 0; | ||||||
| 132 | }; | ||||||
| 133 | |||||||
| 134 | struct PrintFP { | ||||||
| 135 | PrintFP(const FlowPattern &P, const TargetRegisterInfo &T) | ||||||
| 136 | : FP(P), TRI(T) {} | ||||||
| 137 | |||||||
| 138 | const FlowPattern &FP; | ||||||
| 139 | const TargetRegisterInfo &TRI; | ||||||
| 140 | friend raw_ostream &operator<< (raw_ostream &OS, const PrintFP &P); | ||||||
| 141 | }; | ||||||
| 142 | raw_ostream &operator<<(raw_ostream &OS, | ||||||
| 143 | const PrintFP &P) LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)); | ||||||
| 144 | raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) { | ||||||
| 145 | OS << "{ SplitB:" << PrintMB(P.FP.SplitB) | ||||||
| 146 | << ", PredR:" << printReg(P.FP.PredR, &P.TRI) | ||||||
| 147 | << ", TrueB:" << PrintMB(P.FP.TrueB) | ||||||
| 148 | << ", FalseB:" << PrintMB(P.FP.FalseB) | ||||||
| 149 | << ", JoinB:" << PrintMB(P.FP.JoinB) << " }"; | ||||||
| 150 | return OS; | ||||||
| 151 | } | ||||||
| 152 | |||||||
| 153 | class HexagonEarlyIfConversion : public MachineFunctionPass { | ||||||
| 154 | public: | ||||||
| 155 | static char ID; | ||||||
| 156 | |||||||
| 157 | HexagonEarlyIfConversion() : MachineFunctionPass(ID) {} | ||||||
| 158 | |||||||
| 159 | StringRef getPassName() const override { | ||||||
| 160 | return "Hexagon early if conversion"; | ||||||
| 161 | } | ||||||
| 162 | |||||||
| 163 | void getAnalysisUsage(AnalysisUsage &AU) const override { | ||||||
| 164 | AU.addRequired<MachineBranchProbabilityInfo>(); | ||||||
| 165 | AU.addRequired<MachineDominatorTree>(); | ||||||
| 166 | AU.addPreserved<MachineDominatorTree>(); | ||||||
| 167 | AU.addRequired<MachineLoopInfo>(); | ||||||
| 168 | MachineFunctionPass::getAnalysisUsage(AU); | ||||||
| 169 | } | ||||||
| 170 | |||||||
| 171 | bool runOnMachineFunction(MachineFunction &MF) override; | ||||||
| 172 | |||||||
| 173 | private: | ||||||
| 174 | using BlockSetType = DenseSet<MachineBasicBlock *>; | ||||||
| 175 | |||||||
| 176 | bool isPreheader(const MachineBasicBlock *B) const; | ||||||
| 177 | bool matchFlowPattern(MachineBasicBlock *B, MachineLoop *L, | ||||||
| 178 | FlowPattern &FP); | ||||||
| 179 | bool visitBlock(MachineBasicBlock *B, MachineLoop *L); | ||||||
| 180 | bool visitLoop(MachineLoop *L); | ||||||
| 181 | |||||||
| 182 | bool hasEHLabel(const MachineBasicBlock *B) const; | ||||||
| 183 | bool hasUncondBranch(const MachineBasicBlock *B) const; | ||||||
| 184 | bool isValidCandidate(const MachineBasicBlock *B) const; | ||||||
| 185 | bool usesUndefVReg(const MachineInstr *MI) const; | ||||||
| 186 | bool isValid(const FlowPattern &FP) const; | ||||||
| 187 | unsigned countPredicateDefs(const MachineBasicBlock *B) const; | ||||||
| 188 | unsigned computePhiCost(const MachineBasicBlock *B, | ||||||
| 189 | const FlowPattern &FP) const; | ||||||
| 190 | bool isProfitable(const FlowPattern &FP) const; | ||||||
| 191 | bool isPredicableStore(const MachineInstr *MI) const; | ||||||
| 192 | bool isSafeToSpeculate(const MachineInstr *MI) const; | ||||||
| 193 | bool isPredicate(unsigned R) const; | ||||||
| 194 | |||||||
| 195 | unsigned getCondStoreOpcode(unsigned Opc, bool IfTrue) const; | ||||||
| 196 | void predicateInstr(MachineBasicBlock *ToB, MachineBasicBlock::iterator At, | ||||||
| 197 | MachineInstr *MI, unsigned PredR, bool IfTrue); | ||||||
| 198 | void predicateBlockNB(MachineBasicBlock *ToB, | ||||||
| 199 | MachineBasicBlock::iterator At, MachineBasicBlock *FromB, | ||||||
| 200 | unsigned PredR, bool IfTrue); | ||||||
| 201 | |||||||
| 202 | unsigned buildMux(MachineBasicBlock *B, MachineBasicBlock::iterator At, | ||||||
| 203 | const TargetRegisterClass *DRC, unsigned PredR, unsigned TR, | ||||||
| 204 | unsigned TSR, unsigned FR, unsigned FSR); | ||||||
| 205 | void updatePhiNodes(MachineBasicBlock *WhereB, const FlowPattern &FP); | ||||||
| 206 | void convert(const FlowPattern &FP); | ||||||
| 207 | |||||||
| 208 | void removeBlock(MachineBasicBlock *B); | ||||||
| 209 | void eliminatePhis(MachineBasicBlock *B); | ||||||
| 210 | void mergeBlocks(MachineBasicBlock *PredB, MachineBasicBlock *SuccB); | ||||||
| 211 | void simplifyFlowGraph(const FlowPattern &FP); | ||||||
| 212 | |||||||
| 213 | const HexagonInstrInfo *HII = nullptr; | ||||||
| 214 | const TargetRegisterInfo *TRI = nullptr; | ||||||
| 215 | MachineFunction *MFN = nullptr; | ||||||
| 216 | MachineRegisterInfo *MRI = nullptr; | ||||||
| 217 | MachineDominatorTree *MDT = nullptr; | ||||||
| 218 | MachineLoopInfo *MLI = nullptr; | ||||||
| 219 | BlockSetType Deleted; | ||||||
| 220 | const MachineBranchProbabilityInfo *MBPI = nullptr; | ||||||
| 221 | }; | ||||||
| 222 | |||||||
| 223 | } // end anonymous namespace | ||||||
| 224 | |||||||
| 225 | char HexagonEarlyIfConversion::ID = 0; | ||||||
| 226 | |||||||
| 227 | INITIALIZE_PASS(HexagonEarlyIfConversion, "hexagon-early-if",static void *initializeHexagonEarlyIfConversionPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Hexagon early if conversion" , "hexagon-early-if", &HexagonEarlyIfConversion::ID, PassInfo ::NormalCtor_t(callDefaultCtor<HexagonEarlyIfConversion> ), false, false); Registry.registerPass(*PI, true); return PI ; } static llvm::once_flag InitializeHexagonEarlyIfConversionPassFlag ; void llvm::initializeHexagonEarlyIfConversionPass(PassRegistry &Registry) { llvm::call_once(InitializeHexagonEarlyIfConversionPassFlag , initializeHexagonEarlyIfConversionPassOnce, std::ref(Registry )); } | ||||||
| 228 | "Hexagon early if conversion", false, false)static void *initializeHexagonEarlyIfConversionPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Hexagon early if conversion" , "hexagon-early-if", &HexagonEarlyIfConversion::ID, PassInfo ::NormalCtor_t(callDefaultCtor<HexagonEarlyIfConversion> ), false, false); Registry.registerPass(*PI, true); return PI ; } static llvm::once_flag InitializeHexagonEarlyIfConversionPassFlag ; void llvm::initializeHexagonEarlyIfConversionPass(PassRegistry &Registry) { llvm::call_once(InitializeHexagonEarlyIfConversionPassFlag , initializeHexagonEarlyIfConversionPassOnce, std::ref(Registry )); } | ||||||
| 229 | |||||||
| 230 | bool HexagonEarlyIfConversion::isPreheader(const MachineBasicBlock *B) const { | ||||||
| 231 | if (B->succ_size() != 1) | ||||||
| 232 | return false; | ||||||
| 233 | MachineBasicBlock *SB = *B->succ_begin(); | ||||||
| 234 | MachineLoop *L = MLI->getLoopFor(SB); | ||||||
| 235 | return L && SB == L->getHeader() && MDT->dominates(B, SB); | ||||||
| 236 | } | ||||||
| 237 | |||||||
| 238 | bool HexagonEarlyIfConversion::matchFlowPattern(MachineBasicBlock *B, | ||||||
| 239 | MachineLoop *L, FlowPattern &FP) { | ||||||
| 240 | LLVM_DEBUG(dbgs() << "Checking flow pattern at " << printMBBReference(*B)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Checking flow pattern at " << printMBBReference(*B) << "\n"; } } while (false ) | ||||||
| 241 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Checking flow pattern at " << printMBBReference(*B) << "\n"; } } while (false ); | ||||||
| 242 | |||||||
| 243 | // Interested only in conditional branches, no .new, no new-value, etc. | ||||||
| 244 | // Check the terminators directly, it's easier than handling all responses | ||||||
| 245 | // from analyzeBranch. | ||||||
| 246 | MachineBasicBlock *TB = nullptr, *FB = nullptr; | ||||||
| 247 | MachineBasicBlock::const_iterator T1I = B->getFirstTerminator(); | ||||||
| 248 | if (T1I == B->end()) | ||||||
| 249 | return false; | ||||||
| 250 | unsigned Opc = T1I->getOpcode(); | ||||||
| 251 | if (Opc != Hexagon::J2_jumpt && Opc != Hexagon::J2_jumpf) | ||||||
| 252 | return false; | ||||||
| 253 | Register PredR = T1I->getOperand(0).getReg(); | ||||||
| 254 | |||||||
| 255 | // Get the layout successor, or 0 if B does not have one. | ||||||
| 256 | MachineFunction::iterator NextBI = std::next(MachineFunction::iterator(B)); | ||||||
| 257 | MachineBasicBlock *NextB = (NextBI != MFN->end()) ? &*NextBI : nullptr; | ||||||
| 258 | |||||||
| 259 | MachineBasicBlock *T1B = T1I->getOperand(1).getMBB(); | ||||||
| 260 | MachineBasicBlock::const_iterator T2I = std::next(T1I); | ||||||
| 261 | // The second terminator should be an unconditional branch. | ||||||
| 262 | assert(T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump)((T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump ) ? static_cast<void> (0) : __assert_fail ("T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 262, __PRETTY_FUNCTION__)); | ||||||
| 263 | MachineBasicBlock *T2B = (T2I == B->end()) ? NextB | ||||||
| 264 | : T2I->getOperand(0).getMBB(); | ||||||
| 265 | if (T1B == T2B) { | ||||||
| 266 | // XXX merge if T1B == NextB, or convert branch to unconditional. | ||||||
| 267 | // mark as diamond with both sides equal? | ||||||
| 268 | return false; | ||||||
| 269 | } | ||||||
| 270 | |||||||
| 271 | // Record the true/false blocks in such a way that "true" means "if (PredR)", | ||||||
| 272 | // and "false" means "if (!PredR)". | ||||||
| 273 | if (Opc
| ||||||
| 274 | TB = T1B, FB = T2B; | ||||||
| 275 | else | ||||||
| 276 | TB = T2B, FB = T1B; | ||||||
| 277 | |||||||
| 278 | if (!MDT->properlyDominates(B, TB) || !MDT->properlyDominates(B, FB)) | ||||||
| 279 | return false; | ||||||
| 280 | |||||||
| 281 | // Detect triangle first. In case of a triangle, one of the blocks TB/FB | ||||||
| 282 | // can fall through into the other, in other words, it will be executed | ||||||
| 283 | // in both cases. We only want to predicate the block that is executed | ||||||
| 284 | // conditionally. | ||||||
| 285 | unsigned TNP = TB->pred_size(), FNP = FB->pred_size(); | ||||||
| |||||||
| 286 | unsigned TNS = TB->succ_size(), FNS = FB->succ_size(); | ||||||
| 287 | |||||||
| 288 | // A block is predicable if it has one predecessor (it must be B), and | ||||||
| 289 | // it has a single successor. In fact, the block has to end either with | ||||||
| 290 | // an unconditional branch (which can be predicated), or with a fall- | ||||||
| 291 | // through. | ||||||
| 292 | // Also, skip blocks that do not belong to the same loop. | ||||||
| 293 | bool TOk = (TNP == 1 && TNS == 1 && MLI->getLoopFor(TB) == L); | ||||||
| 294 | bool FOk = (FNP == 1 && FNS == 1 && MLI->getLoopFor(FB) == L); | ||||||
| 295 | |||||||
| 296 | // If requested (via an option), do not consider branches where the | ||||||
| 297 | // true and false targets do not belong to the same loop. | ||||||
| 298 | if (SkipExitBranches && MLI->getLoopFor(TB) != MLI->getLoopFor(FB)) | ||||||
| 299 | return false; | ||||||
| 300 | |||||||
| 301 | // If neither is predicable, there is nothing interesting. | ||||||
| 302 | if (!TOk && !FOk) | ||||||
| 303 | return false; | ||||||
| 304 | |||||||
| 305 | MachineBasicBlock *TSB = (TNS > 0) ? *TB->succ_begin() : nullptr; | ||||||
| 306 | MachineBasicBlock *FSB = (FNS > 0) ? *FB->succ_begin() : nullptr; | ||||||
| 307 | MachineBasicBlock *JB = nullptr; | ||||||
| 308 | |||||||
| 309 | if (TOk) { | ||||||
| 310 | if (FOk) { | ||||||
| 311 | if (TSB == FSB) | ||||||
| 312 | JB = TSB; | ||||||
| 313 | // Diamond: "if (P) then TB; else FB;". | ||||||
| 314 | } else { | ||||||
| 315 | // TOk && !FOk | ||||||
| 316 | if (TSB == FB) | ||||||
| 317 | JB = FB; | ||||||
| 318 | FB = nullptr; | ||||||
| 319 | } | ||||||
| 320 | } else { | ||||||
| 321 | // !TOk && FOk (at least one must be true by now). | ||||||
| 322 | if (FSB == TB) | ||||||
| 323 | JB = TB; | ||||||
| 324 | TB = nullptr; | ||||||
| 325 | } | ||||||
| 326 | // Don't try to predicate loop preheaders. | ||||||
| 327 | if ((TB && isPreheader(TB)) || (FB && isPreheader(FB))) { | ||||||
| 328 | LLVM_DEBUG(dbgs() << "One of blocks " << PrintMB(TB) << ", " << PrintMB(FB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "One of blocks " << PrintMB (TB) << ", " << PrintMB(FB) << " is a loop preheader. Skipping.\n" ; } } while (false) | ||||||
| 329 | << " is a loop preheader. Skipping.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "One of blocks " << PrintMB (TB) << ", " << PrintMB(FB) << " is a loop preheader. Skipping.\n" ; } } while (false); | ||||||
| 330 | return false; | ||||||
| 331 | } | ||||||
| 332 | |||||||
| 333 | FP = FlowPattern(B, PredR, TB, FB, JB); | ||||||
| 334 | LLVM_DEBUG(dbgs() << "Detected " << PrintFP(FP, *TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Detected " << PrintFP (FP, *TRI) << "\n"; } } while (false); | ||||||
| 335 | return true; | ||||||
| 336 | } | ||||||
| 337 | |||||||
| 338 | // KLUDGE: HexagonInstrInfo::analyzeBranch won't work on a block that | ||||||
| 339 | // contains EH_LABEL. | ||||||
| 340 | bool HexagonEarlyIfConversion::hasEHLabel(const MachineBasicBlock *B) const { | ||||||
| 341 | for (auto &I : *B) | ||||||
| 342 | if (I.isEHLabel()) | ||||||
| 343 | return true; | ||||||
| 344 | return false; | ||||||
| 345 | } | ||||||
| 346 | |||||||
| 347 | // KLUDGE: HexagonInstrInfo::analyzeBranch may be unable to recognize | ||||||
| 348 | // that a block can never fall-through. | ||||||
| 349 | bool HexagonEarlyIfConversion::hasUncondBranch(const MachineBasicBlock *B) | ||||||
| 350 | const { | ||||||
| 351 | MachineBasicBlock::const_iterator I = B->getFirstTerminator(), E = B->end(); | ||||||
| 352 | while (I != E) { | ||||||
| 353 | if (I->isBarrier()) | ||||||
| 354 | return true; | ||||||
| 355 | ++I; | ||||||
| 356 | } | ||||||
| 357 | return false; | ||||||
| 358 | } | ||||||
| 359 | |||||||
| 360 | bool HexagonEarlyIfConversion::isValidCandidate(const MachineBasicBlock *B) | ||||||
| 361 | const { | ||||||
| 362 | if (!B) | ||||||
| 363 | return true; | ||||||
| 364 | if (B->isEHPad() || B->hasAddressTaken()) | ||||||
| 365 | return false; | ||||||
| 366 | if (B->succ_size() == 0) | ||||||
| 367 | return false; | ||||||
| 368 | |||||||
| 369 | for (auto &MI : *B) { | ||||||
| 370 | if (MI.isDebugInstr()) | ||||||
| 371 | continue; | ||||||
| 372 | if (MI.isConditionalBranch()) | ||||||
| 373 | return false; | ||||||
| 374 | unsigned Opc = MI.getOpcode(); | ||||||
| 375 | bool IsJMP = (Opc == Hexagon::J2_jump); | ||||||
| 376 | if (!isPredicableStore(&MI) && !IsJMP && !isSafeToSpeculate(&MI)) | ||||||
| 377 | return false; | ||||||
| 378 | // Look for predicate registers defined by this instruction. It's ok | ||||||
| 379 | // to speculate such an instruction, but the predicate register cannot | ||||||
| 380 | // be used outside of this block (or else it won't be possible to | ||||||
| 381 | // update the use of it after predication). PHI uses will be updated | ||||||
| 382 | // to use a result of a MUX, and a MUX cannot be created for predicate | ||||||
| 383 | // registers. | ||||||
| 384 | for (const MachineOperand &MO : MI.operands()) { | ||||||
| 385 | if (!MO.isReg() || !MO.isDef()) | ||||||
| 386 | continue; | ||||||
| 387 | Register R = MO.getReg(); | ||||||
| 388 | if (!Register::isVirtualRegister(R)) | ||||||
| 389 | continue; | ||||||
| 390 | if (!isPredicate(R)) | ||||||
| 391 | continue; | ||||||
| 392 | for (auto U = MRI->use_begin(R); U != MRI->use_end(); ++U) | ||||||
| 393 | if (U->getParent()->isPHI()) | ||||||
| 394 | return false; | ||||||
| 395 | } | ||||||
| 396 | } | ||||||
| 397 | return true; | ||||||
| 398 | } | ||||||
| 399 | |||||||
| 400 | bool HexagonEarlyIfConversion::usesUndefVReg(const MachineInstr *MI) const { | ||||||
| 401 | for (const MachineOperand &MO : MI->operands()) { | ||||||
| 402 | if (!MO.isReg() || !MO.isUse()) | ||||||
| 403 | continue; | ||||||
| 404 | Register R = MO.getReg(); | ||||||
| 405 | if (!Register::isVirtualRegister(R)) | ||||||
| 406 | continue; | ||||||
| 407 | const MachineInstr *DefI = MRI->getVRegDef(R); | ||||||
| 408 | // "Undefined" virtual registers are actually defined via IMPLICIT_DEF. | ||||||
| 409 | assert(DefI && "Expecting a reaching def in MRI")((DefI && "Expecting a reaching def in MRI") ? static_cast <void> (0) : __assert_fail ("DefI && \"Expecting a reaching def in MRI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 409, __PRETTY_FUNCTION__)); | ||||||
| 410 | if (DefI->isImplicitDef()) | ||||||
| 411 | return true; | ||||||
| 412 | } | ||||||
| 413 | return false; | ||||||
| 414 | } | ||||||
| 415 | |||||||
| 416 | bool HexagonEarlyIfConversion::isValid(const FlowPattern &FP) const { | ||||||
| 417 | if (hasEHLabel(FP.SplitB)) // KLUDGE: see function definition | ||||||
| 418 | return false; | ||||||
| 419 | if (FP.TrueB && !isValidCandidate(FP.TrueB)) | ||||||
| 420 | return false; | ||||||
| 421 | if (FP.FalseB && !isValidCandidate(FP.FalseB)) | ||||||
| 422 | return false; | ||||||
| 423 | // Check the PHIs in the join block. If any of them use a register | ||||||
| 424 | // that is defined as IMPLICIT_DEF, do not convert this. This can | ||||||
| 425 | // legitimately happen if one side of the split never executes, but | ||||||
| 426 | // the compiler is unable to prove it. That side may then seem to | ||||||
| 427 | // provide an "undef" value to the join block, however it will never | ||||||
| 428 | // execute at run-time. If we convert this case, the "undef" will | ||||||
| 429 | // be used in a MUX instruction, and that may seem like actually | ||||||
| 430 | // using an undefined value to other optimizations. This could lead | ||||||
| 431 | // to trouble further down the optimization stream, cause assertions | ||||||
| 432 | // to fail, etc. | ||||||
| 433 | if (FP.JoinB) { | ||||||
| 434 | const MachineBasicBlock &B = *FP.JoinB; | ||||||
| 435 | for (auto &MI : B) { | ||||||
| 436 | if (!MI.isPHI()) | ||||||
| 437 | break; | ||||||
| 438 | if (usesUndefVReg(&MI)) | ||||||
| 439 | return false; | ||||||
| 440 | Register DefR = MI.getOperand(0).getReg(); | ||||||
| 441 | if (isPredicate(DefR)) | ||||||
| 442 | return false; | ||||||
| 443 | } | ||||||
| 444 | } | ||||||
| 445 | return true; | ||||||
| 446 | } | ||||||
| 447 | |||||||
| 448 | unsigned HexagonEarlyIfConversion::computePhiCost(const MachineBasicBlock *B, | ||||||
| 449 | const FlowPattern &FP) const { | ||||||
| 450 | if (B->pred_size() < 2) | ||||||
| 451 | return 0; | ||||||
| 452 | |||||||
| 453 | unsigned Cost = 0; | ||||||
| 454 | for (const MachineInstr &MI : *B) { | ||||||
| 455 | if (!MI.isPHI()) | ||||||
| 456 | break; | ||||||
| 457 | // If both incoming blocks are one of the TrueB/FalseB/SplitB, then | ||||||
| 458 | // a MUX may be needed. Otherwise the PHI will need to be updated at | ||||||
| 459 | // no extra cost. | ||||||
| 460 | // Find the interesting PHI operands for further checks. | ||||||
| 461 | SmallVector<unsigned,2> Inc; | ||||||
| 462 | for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { | ||||||
| 463 | const MachineBasicBlock *BB = MI.getOperand(i+1).getMBB(); | ||||||
| 464 | if (BB == FP.SplitB || BB == FP.TrueB || BB == FP.FalseB) | ||||||
| 465 | Inc.push_back(i); | ||||||
| 466 | } | ||||||
| 467 | assert(Inc.size() <= 2)((Inc.size() <= 2) ? static_cast<void> (0) : __assert_fail ("Inc.size() <= 2", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 467, __PRETTY_FUNCTION__)); | ||||||
| 468 | if (Inc.size() < 2) | ||||||
| 469 | continue; | ||||||
| 470 | |||||||
| 471 | const MachineOperand &RA = MI.getOperand(1); | ||||||
| 472 | const MachineOperand &RB = MI.getOperand(3); | ||||||
| 473 | assert(RA.isReg() && RB.isReg())((RA.isReg() && RB.isReg()) ? static_cast<void> (0) : __assert_fail ("RA.isReg() && RB.isReg()", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 473, __PRETTY_FUNCTION__)); | ||||||
| 474 | // Must have a MUX if the phi uses a subregister. | ||||||
| 475 | if (RA.getSubReg() != 0 || RB.getSubReg() != 0) { | ||||||
| 476 | Cost++; | ||||||
| 477 | continue; | ||||||
| 478 | } | ||||||
| 479 | const MachineInstr *Def1 = MRI->getVRegDef(RA.getReg()); | ||||||
| 480 | const MachineInstr *Def3 = MRI->getVRegDef(RB.getReg()); | ||||||
| 481 | if (!HII->isPredicable(*Def1) || !HII->isPredicable(*Def3)) | ||||||
| 482 | Cost++; | ||||||
| 483 | } | ||||||
| 484 | return Cost; | ||||||
| 485 | } | ||||||
| 486 | |||||||
| 487 | unsigned HexagonEarlyIfConversion::countPredicateDefs( | ||||||
| 488 | const MachineBasicBlock *B) const { | ||||||
| 489 | unsigned PredDefs = 0; | ||||||
| 490 | for (auto &MI : *B) { | ||||||
| 491 | for (const MachineOperand &MO : MI.operands()) { | ||||||
| 492 | if (!MO.isReg() || !MO.isDef()) | ||||||
| 493 | continue; | ||||||
| 494 | Register R = MO.getReg(); | ||||||
| 495 | if (!Register::isVirtualRegister(R)) | ||||||
| 496 | continue; | ||||||
| 497 | if (isPredicate(R)) | ||||||
| 498 | PredDefs++; | ||||||
| 499 | } | ||||||
| 500 | } | ||||||
| 501 | return PredDefs; | ||||||
| 502 | } | ||||||
| 503 | |||||||
| 504 | bool HexagonEarlyIfConversion::isProfitable(const FlowPattern &FP) const { | ||||||
| 505 | BranchProbability JumpProb(1, 10); | ||||||
| 506 | BranchProbability Prob(9, 10); | ||||||
| 507 | if (MBPI && FP.TrueB && !FP.FalseB && | ||||||
| 508 | (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) < JumpProb || | ||||||
| 509 | MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob)) | ||||||
| 510 | return false; | ||||||
| 511 | |||||||
| 512 | if (MBPI && !FP.TrueB && FP.FalseB && | ||||||
| 513 | (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) < JumpProb || | ||||||
| 514 | MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob)) | ||||||
| 515 | return false; | ||||||
| 516 | |||||||
| 517 | if (FP.TrueB && FP.FalseB) { | ||||||
| 518 | // Do not IfCovert if the branch is one sided. | ||||||
| 519 | if (MBPI) { | ||||||
| 520 | if (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob) | ||||||
| 521 | return false; | ||||||
| 522 | if (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob) | ||||||
| 523 | return false; | ||||||
| 524 | } | ||||||
| 525 | |||||||
| 526 | // If both sides are predicable, convert them if they join, and the | ||||||
| 527 | // join block has no other predecessors. | ||||||
| 528 | MachineBasicBlock *TSB = *FP.TrueB->succ_begin(); | ||||||
| 529 | MachineBasicBlock *FSB = *FP.FalseB->succ_begin(); | ||||||
| 530 | if (TSB != FSB) | ||||||
| 531 | return false; | ||||||
| 532 | if (TSB->pred_size() != 2) | ||||||
| 533 | return false; | ||||||
| 534 | } | ||||||
| 535 | |||||||
| 536 | // Calculate the total size of the predicated blocks. | ||||||
| 537 | // Assume instruction counts without branches to be the approximation of | ||||||
| 538 | // the code size. If the predicated blocks are smaller than a packet size, | ||||||
| 539 | // approximate the spare room in the packet that could be filled with the | ||||||
| 540 | // predicated/speculated instructions. | ||||||
| 541 | auto TotalCount = [] (const MachineBasicBlock *B, unsigned &Spare) { | ||||||
| 542 | if (!B) | ||||||
| 543 | return 0u; | ||||||
| 544 | unsigned T = std::count_if(B->begin(), B->getFirstTerminator(), | ||||||
| 545 | [](const MachineInstr &MI) { | ||||||
| 546 | return !MI.isMetaInstruction(); | ||||||
| 547 | }); | ||||||
| 548 | if (T < HEXAGON_PACKET_SIZE4) | ||||||
| 549 | Spare += HEXAGON_PACKET_SIZE4-T; | ||||||
| 550 | return T; | ||||||
| 551 | }; | ||||||
| 552 | unsigned Spare = 0; | ||||||
| 553 | unsigned TotalIn = TotalCount(FP.TrueB, Spare) + TotalCount(FP.FalseB, Spare); | ||||||
| 554 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of instructions to be predicated/speculated: " << TotalIn << ", spare room: " << Spare << "\n"; } } while (false) | ||||||
| 555 | dbgs() << "Total number of instructions to be predicated/speculated: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of instructions to be predicated/speculated: " << TotalIn << ", spare room: " << Spare << "\n"; } } while (false) | ||||||
| 556 | << TotalIn << ", spare room: " << Spare << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of instructions to be predicated/speculated: " << TotalIn << ", spare room: " << Spare << "\n"; } } while (false); | ||||||
| 557 | if (TotalIn >= SizeLimit+Spare) | ||||||
| 558 | return false; | ||||||
| 559 | |||||||
| 560 | // Count the number of PHI nodes that will need to be updated (converted | ||||||
| 561 | // to MUX). Those can be later converted to predicated instructions, so | ||||||
| 562 | // they aren't always adding extra cost. | ||||||
| 563 | // KLUDGE: Also, count the number of predicate register definitions in | ||||||
| 564 | // each block. The scheduler may increase the pressure of these and cause | ||||||
| 565 | // expensive spills (e.g. bitmnp01). | ||||||
| 566 | unsigned TotalPh = 0; | ||||||
| 567 | unsigned PredDefs = countPredicateDefs(FP.SplitB); | ||||||
| 568 | if (FP.JoinB) { | ||||||
| 569 | TotalPh = computePhiCost(FP.JoinB, FP); | ||||||
| 570 | PredDefs += countPredicateDefs(FP.JoinB); | ||||||
| 571 | } else { | ||||||
| 572 | if (FP.TrueB && FP.TrueB->succ_size() > 0) { | ||||||
| 573 | MachineBasicBlock *SB = *FP.TrueB->succ_begin(); | ||||||
| 574 | TotalPh += computePhiCost(SB, FP); | ||||||
| 575 | PredDefs += countPredicateDefs(SB); | ||||||
| 576 | } | ||||||
| 577 | if (FP.FalseB && FP.FalseB->succ_size() > 0) { | ||||||
| 578 | MachineBasicBlock *SB = *FP.FalseB->succ_begin(); | ||||||
| 579 | TotalPh += computePhiCost(SB, FP); | ||||||
| 580 | PredDefs += countPredicateDefs(SB); | ||||||
| 581 | } | ||||||
| 582 | } | ||||||
| 583 | LLVM_DEBUG(dbgs() << "Total number of extra muxes from converted phis: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of extra muxes from converted phis: " << TotalPh << "\n"; } } while (false) | ||||||
| 584 | << TotalPh << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of extra muxes from converted phis: " << TotalPh << "\n"; } } while (false); | ||||||
| 585 | if (TotalIn+TotalPh >= SizeLimit+Spare) | ||||||
| 586 | return false; | ||||||
| 587 | |||||||
| 588 | LLVM_DEBUG(dbgs() << "Total number of predicate registers: " << PredDefsdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of predicate registers: " << PredDefs << "\n"; } } while (false) | ||||||
| 589 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Total number of predicate registers: " << PredDefs << "\n"; } } while (false); | ||||||
| 590 | if (PredDefs > 4) | ||||||
| 591 | return false; | ||||||
| 592 | |||||||
| 593 | return true; | ||||||
| 594 | } | ||||||
| 595 | |||||||
| 596 | bool HexagonEarlyIfConversion::visitBlock(MachineBasicBlock *B, | ||||||
| 597 | MachineLoop *L) { | ||||||
| 598 | bool Changed = false; | ||||||
| 599 | |||||||
| 600 | // Visit all dominated blocks from the same loop first, then process B. | ||||||
| 601 | MachineDomTreeNode *N = MDT->getNode(B); | ||||||
| 602 | |||||||
| 603 | using GTN = GraphTraits<MachineDomTreeNode *>; | ||||||
| 604 | |||||||
| 605 | // We will change CFG/DT during this traversal, so take precautions to | ||||||
| 606 | // avoid problems related to invalidated iterators. In fact, processing | ||||||
| 607 | // a child C of B cannot cause another child to be removed, but it can | ||||||
| 608 | // cause a new child to be added (which was a child of C before C itself | ||||||
| 609 | // was removed. This new child C, however, would have been processed | ||||||
| 610 | // prior to processing B, so there is no need to process it again. | ||||||
| 611 | // Simply keep a list of children of B, and traverse that list. | ||||||
| 612 | using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>; | ||||||
| 613 | DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N)); | ||||||
| 614 | for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) { | ||||||
| 615 | MachineBasicBlock *SB = (*I)->getBlock(); | ||||||
| 616 | if (!Deleted.count(SB)) | ||||||
| 617 | Changed |= visitBlock(SB, L); | ||||||
| 618 | } | ||||||
| 619 | // When walking down the dominator tree, we want to traverse through | ||||||
| 620 | // blocks from nested (other) loops, because they can dominate blocks | ||||||
| 621 | // that are in L. Skip the non-L blocks only after the tree traversal. | ||||||
| 622 | if (MLI->getLoopFor(B) != L) | ||||||
| 623 | return Changed; | ||||||
| 624 | |||||||
| 625 | FlowPattern FP; | ||||||
| 626 | if (!matchFlowPattern(B, L, FP)) | ||||||
| 627 | return Changed; | ||||||
| 628 | |||||||
| 629 | if (!isValid(FP)) { | ||||||
| 630 | LLVM_DEBUG(dbgs() << "Conversion is not valid\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Conversion is not valid\n" ; } } while (false); | ||||||
| 631 | return Changed; | ||||||
| 632 | } | ||||||
| 633 | if (!isProfitable(FP)) { | ||||||
| 634 | LLVM_DEBUG(dbgs() << "Conversion is not profitable\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Conversion is not profitable\n" ; } } while (false); | ||||||
| 635 | return Changed; | ||||||
| 636 | } | ||||||
| 637 | |||||||
| 638 | convert(FP); | ||||||
| 639 | simplifyFlowGraph(FP); | ||||||
| 640 | return true; | ||||||
| 641 | } | ||||||
| 642 | |||||||
| 643 | bool HexagonEarlyIfConversion::visitLoop(MachineLoop *L) { | ||||||
| 644 | MachineBasicBlock *HB = L
| ||||||
| 645 | LLVM_DEBUG((L ? dbgs() << "Visiting loop H:" << PrintMB(HB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { (L ? dbgs() << "Visiting loop H:" << PrintMB(HB) : dbgs() << "Visiting function") << "\n" ; } } while (false) | ||||||
| 646 | : dbgs() << "Visiting function")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { (L ? dbgs() << "Visiting loop H:" << PrintMB(HB) : dbgs() << "Visiting function") << "\n" ; } } while (false) | ||||||
| 647 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { (L ? dbgs() << "Visiting loop H:" << PrintMB(HB) : dbgs() << "Visiting function") << "\n" ; } } while (false); | ||||||
| 648 | bool Changed = false; | ||||||
| 649 | if (L
| ||||||
| 650 | for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) | ||||||
| 651 | Changed |= visitLoop(*I); | ||||||
| 652 | } | ||||||
| 653 | |||||||
| 654 | MachineBasicBlock *EntryB = GraphTraits<MachineFunction*>::getEntryNode(MFN); | ||||||
| 655 | Changed |= visitBlock(L
| ||||||
| 656 | return Changed; | ||||||
| 657 | } | ||||||
| 658 | |||||||
| 659 | bool HexagonEarlyIfConversion::isPredicableStore(const MachineInstr *MI) | ||||||
| 660 | const { | ||||||
| 661 | // HexagonInstrInfo::isPredicable will consider these stores are non- | ||||||
| 662 | // -predicable if the offset would become constant-extended after | ||||||
| 663 | // predication. | ||||||
| 664 | unsigned Opc = MI->getOpcode(); | ||||||
| 665 | switch (Opc) { | ||||||
| 666 | case Hexagon::S2_storerb_io: | ||||||
| 667 | case Hexagon::S2_storerbnew_io: | ||||||
| 668 | case Hexagon::S2_storerh_io: | ||||||
| 669 | case Hexagon::S2_storerhnew_io: | ||||||
| 670 | case Hexagon::S2_storeri_io: | ||||||
| 671 | case Hexagon::S2_storerinew_io: | ||||||
| 672 | case Hexagon::S2_storerd_io: | ||||||
| 673 | case Hexagon::S4_storeirb_io: | ||||||
| 674 | case Hexagon::S4_storeirh_io: | ||||||
| 675 | case Hexagon::S4_storeiri_io: | ||||||
| 676 | return true; | ||||||
| 677 | } | ||||||
| 678 | |||||||
| 679 | // TargetInstrInfo::isPredicable takes a non-const pointer. | ||||||
| 680 | return MI->mayStore() && HII->isPredicable(const_cast<MachineInstr&>(*MI)); | ||||||
| 681 | } | ||||||
| 682 | |||||||
| 683 | bool HexagonEarlyIfConversion::isSafeToSpeculate(const MachineInstr *MI) | ||||||
| 684 | const { | ||||||
| 685 | if (MI->mayLoadOrStore()) | ||||||
| 686 | return false; | ||||||
| 687 | if (MI->isCall() || MI->isBarrier() || MI->isBranch()) | ||||||
| 688 | return false; | ||||||
| 689 | if (MI->hasUnmodeledSideEffects()) | ||||||
| 690 | return false; | ||||||
| 691 | if (MI->getOpcode() == TargetOpcode::LIFETIME_END) | ||||||
| 692 | return false; | ||||||
| 693 | |||||||
| 694 | return true; | ||||||
| 695 | } | ||||||
| 696 | |||||||
| 697 | bool HexagonEarlyIfConversion::isPredicate(unsigned R) const { | ||||||
| 698 | const TargetRegisterClass *RC = MRI->getRegClass(R); | ||||||
| 699 | return RC == &Hexagon::PredRegsRegClass || | ||||||
| 700 | RC == &Hexagon::HvxQRRegClass; | ||||||
| 701 | } | ||||||
| 702 | |||||||
| 703 | unsigned HexagonEarlyIfConversion::getCondStoreOpcode(unsigned Opc, | ||||||
| 704 | bool IfTrue) const { | ||||||
| 705 | return HII->getCondOpcode(Opc, !IfTrue); | ||||||
| 706 | } | ||||||
| 707 | |||||||
| 708 | void HexagonEarlyIfConversion::predicateInstr(MachineBasicBlock *ToB, | ||||||
| 709 | MachineBasicBlock::iterator At, MachineInstr *MI, | ||||||
| 710 | unsigned PredR, bool IfTrue) { | ||||||
| 711 | DebugLoc DL; | ||||||
| 712 | if (At != ToB->end()) | ||||||
| 713 | DL = At->getDebugLoc(); | ||||||
| 714 | else if (!ToB->empty()) | ||||||
| 715 | DL = ToB->back().getDebugLoc(); | ||||||
| 716 | |||||||
| 717 | unsigned Opc = MI->getOpcode(); | ||||||
| 718 | |||||||
| 719 | if (isPredicableStore(MI)) { | ||||||
| 720 | unsigned COpc = getCondStoreOpcode(Opc, IfTrue); | ||||||
| 721 | assert(COpc)((COpc) ? static_cast<void> (0) : __assert_fail ("COpc" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 721, __PRETTY_FUNCTION__)); | ||||||
| 722 | MachineInstrBuilder MIB = BuildMI(*ToB, At, DL, HII->get(COpc)); | ||||||
| 723 | MachineInstr::mop_iterator MOI = MI->operands_begin(); | ||||||
| 724 | if (HII->isPostIncrement(*MI)) { | ||||||
| 725 | MIB.add(*MOI); | ||||||
| 726 | ++MOI; | ||||||
| 727 | } | ||||||
| 728 | MIB.addReg(PredR); | ||||||
| 729 | for (const MachineOperand &MO : make_range(MOI, MI->operands_end())) | ||||||
| 730 | MIB.add(MO); | ||||||
| 731 | |||||||
| 732 | // Set memory references. | ||||||
| 733 | MIB.cloneMemRefs(*MI); | ||||||
| 734 | |||||||
| 735 | MI->eraseFromParent(); | ||||||
| 736 | return; | ||||||
| 737 | } | ||||||
| 738 | |||||||
| 739 | if (Opc == Hexagon::J2_jump) { | ||||||
| 740 | MachineBasicBlock *TB = MI->getOperand(0).getMBB(); | ||||||
| 741 | const MCInstrDesc &D = HII->get(IfTrue ? Hexagon::J2_jumpt | ||||||
| 742 | : Hexagon::J2_jumpf); | ||||||
| 743 | BuildMI(*ToB, At, DL, D) | ||||||
| 744 | .addReg(PredR) | ||||||
| 745 | .addMBB(TB); | ||||||
| 746 | MI->eraseFromParent(); | ||||||
| 747 | return; | ||||||
| 748 | } | ||||||
| 749 | |||||||
| 750 | // Print the offending instruction unconditionally as we are about to | ||||||
| 751 | // abort. | ||||||
| 752 | dbgs() << *MI; | ||||||
| 753 | llvm_unreachable("Unexpected instruction")::llvm::llvm_unreachable_internal("Unexpected instruction", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 753); | ||||||
| 754 | } | ||||||
| 755 | |||||||
| 756 | // Predicate/speculate non-branch instructions from FromB into block ToB. | ||||||
| 757 | // Leave the branches alone, they will be handled later. Btw, at this point | ||||||
| 758 | // FromB should have at most one branch, and it should be unconditional. | ||||||
| 759 | void HexagonEarlyIfConversion::predicateBlockNB(MachineBasicBlock *ToB, | ||||||
| 760 | MachineBasicBlock::iterator At, MachineBasicBlock *FromB, | ||||||
| 761 | unsigned PredR, bool IfTrue) { | ||||||
| 762 | LLVM_DEBUG(dbgs() << "Predicating block " << PrintMB(FromB) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Predicating block " << PrintMB(FromB) << "\n"; } } while (false); | ||||||
| 763 | MachineBasicBlock::iterator End = FromB->getFirstTerminator(); | ||||||
| 764 | MachineBasicBlock::iterator I, NextI; | ||||||
| 765 | |||||||
| 766 | for (I = FromB->begin(); I != End; I = NextI) { | ||||||
| 767 | assert(!I->isPHI())((!I->isPHI()) ? static_cast<void> (0) : __assert_fail ("!I->isPHI()", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 767, __PRETTY_FUNCTION__)); | ||||||
| 768 | NextI = std::next(I); | ||||||
| 769 | if (isSafeToSpeculate(&*I)) | ||||||
| 770 | ToB->splice(At, FromB, I); | ||||||
| 771 | else | ||||||
| 772 | predicateInstr(ToB, At, &*I, PredR, IfTrue); | ||||||
| 773 | } | ||||||
| 774 | } | ||||||
| 775 | |||||||
| 776 | unsigned HexagonEarlyIfConversion::buildMux(MachineBasicBlock *B, | ||||||
| 777 | MachineBasicBlock::iterator At, const TargetRegisterClass *DRC, | ||||||
| 778 | unsigned PredR, unsigned TR, unsigned TSR, unsigned FR, unsigned FSR) { | ||||||
| 779 | unsigned Opc = 0; | ||||||
| 780 | switch (DRC->getID()) { | ||||||
| 781 | case Hexagon::IntRegsRegClassID: | ||||||
| 782 | case Hexagon::IntRegsLow8RegClassID: | ||||||
| 783 | Opc = Hexagon::C2_mux; | ||||||
| 784 | break; | ||||||
| 785 | case Hexagon::DoubleRegsRegClassID: | ||||||
| 786 | case Hexagon::GeneralDoubleLow8RegsRegClassID: | ||||||
| 787 | Opc = Hexagon::PS_pselect; | ||||||
| 788 | break; | ||||||
| 789 | case Hexagon::HvxVRRegClassID: | ||||||
| 790 | Opc = Hexagon::PS_vselect; | ||||||
| 791 | break; | ||||||
| 792 | case Hexagon::HvxWRRegClassID: | ||||||
| 793 | Opc = Hexagon::PS_wselect; | ||||||
| 794 | break; | ||||||
| 795 | default: | ||||||
| 796 | llvm_unreachable("unexpected register type")::llvm::llvm_unreachable_internal("unexpected register type", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 796); | ||||||
| 797 | } | ||||||
| 798 | const MCInstrDesc &D = HII->get(Opc); | ||||||
| 799 | |||||||
| 800 | DebugLoc DL = B->findBranchDebugLoc(); | ||||||
| 801 | Register MuxR = MRI->createVirtualRegister(DRC); | ||||||
| 802 | BuildMI(*B, At, DL, D, MuxR) | ||||||
| 803 | .addReg(PredR) | ||||||
| 804 | .addReg(TR, 0, TSR) | ||||||
| 805 | .addReg(FR, 0, FSR); | ||||||
| 806 | return MuxR; | ||||||
| 807 | } | ||||||
| 808 | |||||||
| 809 | void HexagonEarlyIfConversion::updatePhiNodes(MachineBasicBlock *WhereB, | ||||||
| 810 | const FlowPattern &FP) { | ||||||
| 811 | // Visit all PHI nodes in the WhereB block and generate MUX instructions | ||||||
| 812 | // in the split block. Update the PHI nodes with the values of the MUX. | ||||||
| 813 | auto NonPHI = WhereB->getFirstNonPHI(); | ||||||
| 814 | for (auto I = WhereB->begin(); I != NonPHI; ++I) { | ||||||
| 815 | MachineInstr *PN = &*I; | ||||||
| 816 | // Registers and subregisters corresponding to TrueB, FalseB and SplitB. | ||||||
| 817 | unsigned TR = 0, TSR = 0, FR = 0, FSR = 0, SR = 0, SSR = 0; | ||||||
| 818 | for (int i = PN->getNumOperands()-2; i > 0; i -= 2) { | ||||||
| 819 | const MachineOperand &RO = PN->getOperand(i), &BO = PN->getOperand(i+1); | ||||||
| 820 | if (BO.getMBB() == FP.SplitB) | ||||||
| 821 | SR = RO.getReg(), SSR = RO.getSubReg(); | ||||||
| 822 | else if (BO.getMBB() == FP.TrueB) | ||||||
| 823 | TR = RO.getReg(), TSR = RO.getSubReg(); | ||||||
| 824 | else if (BO.getMBB() == FP.FalseB) | ||||||
| 825 | FR = RO.getReg(), FSR = RO.getSubReg(); | ||||||
| 826 | else | ||||||
| 827 | continue; | ||||||
| 828 | PN->RemoveOperand(i+1); | ||||||
| 829 | PN->RemoveOperand(i); | ||||||
| 830 | } | ||||||
| 831 | if (TR == 0) | ||||||
| 832 | TR = SR, TSR = SSR; | ||||||
| 833 | else if (FR == 0) | ||||||
| 834 | FR = SR, FSR = SSR; | ||||||
| 835 | |||||||
| 836 | assert(TR || FR)((TR || FR) ? static_cast<void> (0) : __assert_fail ("TR || FR" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 836, __PRETTY_FUNCTION__)); | ||||||
| 837 | unsigned MuxR = 0, MuxSR = 0; | ||||||
| 838 | |||||||
| 839 | if (TR && FR) { | ||||||
| 840 | Register DR = PN->getOperand(0).getReg(); | ||||||
| 841 | const TargetRegisterClass *RC = MRI->getRegClass(DR); | ||||||
| 842 | MuxR = buildMux(FP.SplitB, FP.SplitB->getFirstTerminator(), RC, | ||||||
| 843 | FP.PredR, TR, TSR, FR, FSR); | ||||||
| 844 | } else if (TR) { | ||||||
| 845 | MuxR = TR; | ||||||
| 846 | MuxSR = TSR; | ||||||
| 847 | } else { | ||||||
| 848 | MuxR = FR; | ||||||
| 849 | MuxSR = FSR; | ||||||
| 850 | } | ||||||
| 851 | |||||||
| 852 | PN->addOperand(MachineOperand::CreateReg(MuxR, false, false, false, false, | ||||||
| 853 | false, false, MuxSR)); | ||||||
| 854 | PN->addOperand(MachineOperand::CreateMBB(FP.SplitB)); | ||||||
| 855 | } | ||||||
| 856 | } | ||||||
| 857 | |||||||
| 858 | void HexagonEarlyIfConversion::convert(const FlowPattern &FP) { | ||||||
| 859 | MachineBasicBlock *TSB = nullptr, *FSB = nullptr; | ||||||
| 860 | MachineBasicBlock::iterator OldTI = FP.SplitB->getFirstTerminator(); | ||||||
| 861 | assert(OldTI != FP.SplitB->end())((OldTI != FP.SplitB->end()) ? static_cast<void> (0) : __assert_fail ("OldTI != FP.SplitB->end()", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 861, __PRETTY_FUNCTION__)); | ||||||
| 862 | DebugLoc DL = OldTI->getDebugLoc(); | ||||||
| 863 | |||||||
| 864 | if (FP.TrueB) { | ||||||
| 865 | TSB = *FP.TrueB->succ_begin(); | ||||||
| 866 | predicateBlockNB(FP.SplitB, OldTI, FP.TrueB, FP.PredR, true); | ||||||
| 867 | } | ||||||
| 868 | if (FP.FalseB) { | ||||||
| 869 | FSB = *FP.FalseB->succ_begin(); | ||||||
| 870 | MachineBasicBlock::iterator At = FP.SplitB->getFirstTerminator(); | ||||||
| 871 | predicateBlockNB(FP.SplitB, At, FP.FalseB, FP.PredR, false); | ||||||
| 872 | } | ||||||
| 873 | |||||||
| 874 | // Regenerate new terminators in the split block and update the successors. | ||||||
| 875 | // First, remember any information that may be needed later and remove the | ||||||
| 876 | // existing terminators/successors from the split block. | ||||||
| 877 | MachineBasicBlock *SSB = nullptr; | ||||||
| 878 | FP.SplitB->erase(OldTI, FP.SplitB->end()); | ||||||
| 879 | while (FP.SplitB->succ_size() > 0) { | ||||||
| 880 | MachineBasicBlock *T = *FP.SplitB->succ_begin(); | ||||||
| 881 | // It's possible that the split block had a successor that is not a pre- | ||||||
| 882 | // dicated block. This could only happen if there was only one block to | ||||||
| 883 | // be predicated. Example: | ||||||
| 884 | // split_b: | ||||||
| 885 | // if (p) jump true_b | ||||||
| 886 | // jump unrelated2_b | ||||||
| 887 | // unrelated1_b: | ||||||
| 888 | // ... | ||||||
| 889 | // unrelated2_b: ; can have other predecessors, so it's not "false_b" | ||||||
| 890 | // jump other_b | ||||||
| 891 | // true_b: ; only reachable from split_b, can be predicated | ||||||
| 892 | // ... | ||||||
| 893 | // | ||||||
| 894 | // Find this successor (SSB) if it exists. | ||||||
| 895 | if (T != FP.TrueB && T != FP.FalseB) { | ||||||
| 896 | assert(!SSB)((!SSB) ? static_cast<void> (0) : __assert_fail ("!SSB" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 896, __PRETTY_FUNCTION__)); | ||||||
| 897 | SSB = T; | ||||||
| 898 | } | ||||||
| 899 | FP.SplitB->removeSuccessor(FP.SplitB->succ_begin()); | ||||||
| 900 | } | ||||||
| 901 | |||||||
| 902 | // Insert new branches and update the successors of the split block. This | ||||||
| 903 | // may create unconditional branches to the layout successor, etc., but | ||||||
| 904 | // that will be cleaned up later. For now, make sure that correct code is | ||||||
| 905 | // generated. | ||||||
| 906 | if (FP.JoinB) { | ||||||
| 907 | assert(!SSB || SSB == FP.JoinB)((!SSB || SSB == FP.JoinB) ? static_cast<void> (0) : __assert_fail ("!SSB || SSB == FP.JoinB", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 907, __PRETTY_FUNCTION__)); | ||||||
| 908 | BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump)) | ||||||
| 909 | .addMBB(FP.JoinB); | ||||||
| 910 | FP.SplitB->addSuccessor(FP.JoinB); | ||||||
| 911 | } else { | ||||||
| 912 | bool HasBranch = false; | ||||||
| 913 | if (TSB) { | ||||||
| 914 | BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jumpt)) | ||||||
| 915 | .addReg(FP.PredR) | ||||||
| 916 | .addMBB(TSB); | ||||||
| 917 | FP.SplitB->addSuccessor(TSB); | ||||||
| 918 | HasBranch = true; | ||||||
| 919 | } | ||||||
| 920 | if (FSB) { | ||||||
| 921 | const MCInstrDesc &D = HasBranch ? HII->get(Hexagon::J2_jump) | ||||||
| 922 | : HII->get(Hexagon::J2_jumpf); | ||||||
| 923 | MachineInstrBuilder MIB = BuildMI(*FP.SplitB, FP.SplitB->end(), DL, D); | ||||||
| 924 | if (!HasBranch) | ||||||
| 925 | MIB.addReg(FP.PredR); | ||||||
| 926 | MIB.addMBB(FSB); | ||||||
| 927 | FP.SplitB->addSuccessor(FSB); | ||||||
| 928 | } | ||||||
| 929 | if (SSB) { | ||||||
| 930 | // This cannot happen if both TSB and FSB are set. [TF]SB are the | ||||||
| 931 | // successor blocks of the TrueB and FalseB (or null of the TrueB | ||||||
| 932 | // or FalseB block is null). SSB is the potential successor block | ||||||
| 933 | // of the SplitB that is neither TrueB nor FalseB. | ||||||
| 934 | BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump)) | ||||||
| 935 | .addMBB(SSB); | ||||||
| 936 | FP.SplitB->addSuccessor(SSB); | ||||||
| 937 | } | ||||||
| 938 | } | ||||||
| 939 | |||||||
| 940 | // What is left to do is to update the PHI nodes that could have entries | ||||||
| 941 | // referring to predicated blocks. | ||||||
| 942 | if (FP.JoinB) { | ||||||
| 943 | updatePhiNodes(FP.JoinB, FP); | ||||||
| 944 | } else { | ||||||
| 945 | if (TSB) | ||||||
| 946 | updatePhiNodes(TSB, FP); | ||||||
| 947 | if (FSB) | ||||||
| 948 | updatePhiNodes(FSB, FP); | ||||||
| 949 | // Nothing to update in SSB, since SSB's predecessors haven't changed. | ||||||
| 950 | } | ||||||
| 951 | } | ||||||
| 952 | |||||||
| 953 | void HexagonEarlyIfConversion::removeBlock(MachineBasicBlock *B) { | ||||||
| 954 | LLVM_DEBUG(dbgs() << "Removing block " << PrintMB(B) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Removing block " << PrintMB(B) << "\n"; } } while (false); | ||||||
| 955 | |||||||
| 956 | // Transfer the immediate dominator information from B to its descendants. | ||||||
| 957 | MachineDomTreeNode *N = MDT->getNode(B); | ||||||
| 958 | MachineDomTreeNode *IDN = N->getIDom(); | ||||||
| 959 | if (IDN) { | ||||||
| 960 | MachineBasicBlock *IDB = IDN->getBlock(); | ||||||
| 961 | |||||||
| 962 | using GTN = GraphTraits<MachineDomTreeNode *>; | ||||||
| 963 | using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>; | ||||||
| 964 | |||||||
| 965 | DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N)); | ||||||
| 966 | for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) { | ||||||
| 967 | MachineBasicBlock *SB = (*I)->getBlock(); | ||||||
| 968 | MDT->changeImmediateDominator(SB, IDB); | ||||||
| 969 | } | ||||||
| 970 | } | ||||||
| 971 | |||||||
| 972 | while (B->succ_size() > 0) | ||||||
| 973 | B->removeSuccessor(B->succ_begin()); | ||||||
| 974 | |||||||
| 975 | for (auto I = B->pred_begin(), E = B->pred_end(); I != E; ++I) | ||||||
| 976 | (*I)->removeSuccessor(B, true); | ||||||
| 977 | |||||||
| 978 | Deleted.insert(B); | ||||||
| 979 | MDT->eraseNode(B); | ||||||
| 980 | MFN->erase(B->getIterator()); | ||||||
| 981 | } | ||||||
| 982 | |||||||
| 983 | void HexagonEarlyIfConversion::eliminatePhis(MachineBasicBlock *B) { | ||||||
| 984 | LLVM_DEBUG(dbgs() << "Removing phi nodes from block " << PrintMB(B) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Removing phi nodes from block " << PrintMB(B) << "\n"; } } while (false); | ||||||
| 985 | MachineBasicBlock::iterator I, NextI, NonPHI = B->getFirstNonPHI(); | ||||||
| 986 | for (I = B->begin(); I != NonPHI; I = NextI) { | ||||||
| 987 | NextI = std::next(I); | ||||||
| 988 | MachineInstr *PN = &*I; | ||||||
| 989 | assert(PN->getNumOperands() == 3 && "Invalid phi node")((PN->getNumOperands() == 3 && "Invalid phi node") ? static_cast<void> (0) : __assert_fail ("PN->getNumOperands() == 3 && \"Invalid phi node\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp" , 989, __PRETTY_FUNCTION__)); | ||||||
| 990 | MachineOperand &UO = PN->getOperand(1); | ||||||
| 991 | Register UseR = UO.getReg(), UseSR = UO.getSubReg(); | ||||||
| 992 | Register DefR = PN->getOperand(0).getReg(); | ||||||
| 993 | unsigned NewR = UseR; | ||||||
| 994 | if (UseSR) { | ||||||
| 995 | // MRI.replaceVregUsesWith does not allow to update the subregister, | ||||||
| 996 | // so instead of doing the use-iteration here, create a copy into a | ||||||
| 997 | // "non-subregistered" register. | ||||||
| 998 | const DebugLoc &DL = PN->getDebugLoc(); | ||||||
| 999 | const TargetRegisterClass *RC = MRI->getRegClass(DefR); | ||||||
| 1000 | NewR = MRI->createVirtualRegister(RC); | ||||||
| 1001 | NonPHI = BuildMI(*B, NonPHI, DL, HII->get(TargetOpcode::COPY), NewR) | ||||||
| 1002 | .addReg(UseR, 0, UseSR); | ||||||
| 1003 | } | ||||||
| 1004 | MRI->replaceRegWith(DefR, NewR); | ||||||
| 1005 | B->erase(I); | ||||||
| 1006 | } | ||||||
| 1007 | } | ||||||
| 1008 | |||||||
| 1009 | void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB, | ||||||
| 1010 | MachineBasicBlock *SuccB) { | ||||||
| 1011 | LLVM_DEBUG(dbgs() << "Merging blocks " << PrintMB(PredB) << " and "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Merging blocks " << PrintMB(PredB) << " and " << PrintMB(SuccB) << "\n"; } } while (false) | ||||||
| 1012 | << PrintMB(SuccB) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-eif")) { dbgs() << "Merging blocks " << PrintMB(PredB) << " and " << PrintMB(SuccB) << "\n"; } } while (false); | ||||||
| 1013 | bool TermOk = hasUncondBranch(SuccB); | ||||||
| 1014 | eliminatePhis(SuccB); | ||||||
| 1015 | HII->removeBranch(*PredB); | ||||||
| 1016 | PredB->removeSuccessor(SuccB); | ||||||
| 1017 | PredB->splice(PredB->end(), SuccB, SuccB->begin(), SuccB->end()); | ||||||
| 1018 | PredB->transferSuccessorsAndUpdatePHIs(SuccB); | ||||||
| 1019 | removeBlock(SuccB); | ||||||
| 1020 | if (!TermOk) | ||||||
| 1021 | PredB->updateTerminator(); | ||||||
| 1022 | } | ||||||
| 1023 | |||||||
| 1024 | void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) { | ||||||
| 1025 | if (FP.TrueB) | ||||||
| 1026 | removeBlock(FP.TrueB); | ||||||
| 1027 | if (FP.FalseB) | ||||||
| 1028 | removeBlock(FP.FalseB); | ||||||
| 1029 | |||||||
| 1030 | FP.SplitB->updateTerminator(); | ||||||
| 1031 | if (FP.SplitB->succ_size() != 1) | ||||||
| 1032 | return; | ||||||
| 1033 | |||||||
| 1034 | MachineBasicBlock *SB = *FP.SplitB->succ_begin(); | ||||||
| 1035 | if (SB->pred_size() != 1) | ||||||
| 1036 | return; | ||||||
| 1037 | |||||||
| 1038 | // By now, the split block has only one successor (SB), and SB has only | ||||||
| 1039 | // one predecessor. We can try to merge them. We will need to update ter- | ||||||
| 1040 | // minators in FP.Split+SB, and that requires working analyzeBranch, which | ||||||
| 1041 | // fails on Hexagon for blocks that have EH_LABELs. However, if SB ends | ||||||
| 1042 | // with an unconditional branch, we won't need to touch the terminators. | ||||||
| 1043 | if (!hasEHLabel(SB) || hasUncondBranch(SB)) | ||||||
| 1044 | mergeBlocks(FP.SplitB, SB); | ||||||
| 1045 | } | ||||||
| 1046 | |||||||
| 1047 | bool HexagonEarlyIfConversion::runOnMachineFunction(MachineFunction &MF) { | ||||||
| 1048 | if (skipFunction(MF.getFunction())) | ||||||
| |||||||
| 1049 | return false; | ||||||
| 1050 | |||||||
| 1051 | auto &ST = MF.getSubtarget<HexagonSubtarget>(); | ||||||
| 1052 | HII = ST.getInstrInfo(); | ||||||
| 1053 | TRI = ST.getRegisterInfo(); | ||||||
| 1054 | MFN = &MF; | ||||||
| 1055 | MRI = &MF.getRegInfo(); | ||||||
| 1056 | MDT = &getAnalysis<MachineDominatorTree>(); | ||||||
| 1057 | MLI = &getAnalysis<MachineLoopInfo>(); | ||||||
| 1058 | MBPI = EnableHexagonBP ? &getAnalysis<MachineBranchProbabilityInfo>() : | ||||||
| 1059 | nullptr; | ||||||
| 1060 | |||||||
| 1061 | Deleted.clear(); | ||||||
| 1062 | bool Changed = false; | ||||||
| 1063 | |||||||
| 1064 | for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I) | ||||||
| 1065 | Changed |= visitLoop(*I); | ||||||
| 1066 | Changed |= visitLoop(nullptr); | ||||||
| 1067 | |||||||
| 1068 | return Changed; | ||||||
| 1069 | } | ||||||
| 1070 | |||||||
| 1071 | //===----------------------------------------------------------------------===// | ||||||
| 1072 | // Public Constructor Functions | ||||||
| 1073 | //===----------------------------------------------------------------------===// | ||||||
| 1074 | FunctionPass *llvm::createHexagonEarlyIfConversion() { | ||||||
| 1075 | return new HexagonEarlyIfConversion(); | ||||||
| 1076 | } |
| 1 | //===- llvm/CodeGen/MachineInstrBundleIterator.h ----------------*- C++ -*-===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // Defines an iterator class that bundles MachineInstr. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #ifndef LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H |
| 14 | #define LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H |
| 15 | |
| 16 | #include "llvm/ADT/ilist.h" |
| 17 | #include "llvm/ADT/simple_ilist.h" |
| 18 | #include <cassert> |
| 19 | #include <iterator> |
| 20 | #include <type_traits> |
| 21 | |
| 22 | namespace llvm { |
| 23 | |
| 24 | template <class T, bool IsReverse> struct MachineInstrBundleIteratorTraits; |
| 25 | template <class T> struct MachineInstrBundleIteratorTraits<T, false> { |
| 26 | using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>; |
| 27 | using instr_iterator = typename list_type::iterator; |
| 28 | using nonconst_instr_iterator = typename list_type::iterator; |
| 29 | using const_instr_iterator = typename list_type::const_iterator; |
| 30 | }; |
| 31 | template <class T> struct MachineInstrBundleIteratorTraits<T, true> { |
| 32 | using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>; |
| 33 | using instr_iterator = typename list_type::reverse_iterator; |
| 34 | using nonconst_instr_iterator = typename list_type::reverse_iterator; |
| 35 | using const_instr_iterator = typename list_type::const_reverse_iterator; |
| 36 | }; |
| 37 | template <class T> struct MachineInstrBundleIteratorTraits<const T, false> { |
| 38 | using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>; |
| 39 | using instr_iterator = typename list_type::const_iterator; |
| 40 | using nonconst_instr_iterator = typename list_type::iterator; |
| 41 | using const_instr_iterator = typename list_type::const_iterator; |
| 42 | }; |
| 43 | template <class T> struct MachineInstrBundleIteratorTraits<const T, true> { |
| 44 | using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>; |
| 45 | using instr_iterator = typename list_type::const_reverse_iterator; |
| 46 | using nonconst_instr_iterator = typename list_type::reverse_iterator; |
| 47 | using const_instr_iterator = typename list_type::const_reverse_iterator; |
| 48 | }; |
| 49 | |
| 50 | template <bool IsReverse> struct MachineInstrBundleIteratorHelper; |
| 51 | template <> struct MachineInstrBundleIteratorHelper<false> { |
| 52 | /// Get the beginning of the current bundle. |
| 53 | template <class Iterator> static Iterator getBundleBegin(Iterator I) { |
| 54 | if (!I.isEnd()) |
| 55 | while (I->isBundledWithPred()) |
| 56 | --I; |
| 57 | return I; |
| 58 | } |
| 59 | |
| 60 | /// Get the final node of the current bundle. |
| 61 | template <class Iterator> static Iterator getBundleFinal(Iterator I) { |
| 62 | if (!I.isEnd()) |
| 63 | while (I->isBundledWithSucc()) |
| 64 | ++I; |
| 65 | return I; |
| 66 | } |
| 67 | |
| 68 | /// Increment forward ilist iterator. |
| 69 | template <class Iterator> static void increment(Iterator &I) { |
| 70 | I = std::next(getBundleFinal(I)); |
| 71 | } |
| 72 | |
| 73 | /// Decrement forward ilist iterator. |
| 74 | template <class Iterator> static void decrement(Iterator &I) { |
| 75 | I = getBundleBegin(std::prev(I)); |
| 76 | } |
| 77 | }; |
| 78 | |
| 79 | template <> struct MachineInstrBundleIteratorHelper<true> { |
| 80 | /// Get the beginning of the current bundle. |
| 81 | template <class Iterator> static Iterator getBundleBegin(Iterator I) { |
| 82 | return MachineInstrBundleIteratorHelper<false>::getBundleBegin( |
| 83 | I.getReverse()) |
| 84 | .getReverse(); |
| 85 | } |
| 86 | |
| 87 | /// Get the final node of the current bundle. |
| 88 | template <class Iterator> static Iterator getBundleFinal(Iterator I) { |
| 89 | return MachineInstrBundleIteratorHelper<false>::getBundleFinal( |
| 90 | I.getReverse()) |
| 91 | .getReverse(); |
| 92 | } |
| 93 | |
| 94 | /// Increment reverse ilist iterator. |
| 95 | template <class Iterator> static void increment(Iterator &I) { |
| 96 | I = getBundleBegin(std::next(I)); |
| 97 | } |
| 98 | |
| 99 | /// Decrement reverse ilist iterator. |
| 100 | template <class Iterator> static void decrement(Iterator &I) { |
| 101 | I = std::prev(getBundleFinal(I)); |
| 102 | } |
| 103 | }; |
| 104 | |
| 105 | /// MachineBasicBlock iterator that automatically skips over MIs that are |
| 106 | /// inside bundles (i.e. walk top level MIs only). |
| 107 | template <typename Ty, bool IsReverse = false> |
| 108 | class MachineInstrBundleIterator : MachineInstrBundleIteratorHelper<IsReverse> { |
| 109 | using Traits = MachineInstrBundleIteratorTraits<Ty, IsReverse>; |
| 110 | using instr_iterator = typename Traits::instr_iterator; |
| 111 | |
| 112 | instr_iterator MII; |
| 113 | |
| 114 | public: |
| 115 | using value_type = typename instr_iterator::value_type; |
| 116 | using difference_type = typename instr_iterator::difference_type; |
| 117 | using pointer = typename instr_iterator::pointer; |
| 118 | using reference = typename instr_iterator::reference; |
| 119 | using const_pointer = typename instr_iterator::const_pointer; |
| 120 | using const_reference = typename instr_iterator::const_reference; |
| 121 | using iterator_category = std::bidirectional_iterator_tag; |
| 122 | |
| 123 | private: |
| 124 | using nonconst_instr_iterator = typename Traits::nonconst_instr_iterator; |
| 125 | using const_instr_iterator = typename Traits::const_instr_iterator; |
| 126 | using nonconst_iterator = |
| 127 | MachineInstrBundleIterator<typename nonconst_instr_iterator::value_type, |
| 128 | IsReverse>; |
| 129 | using reverse_iterator = MachineInstrBundleIterator<Ty, !IsReverse>; |
| 130 | |
| 131 | public: |
| 132 | MachineInstrBundleIterator(instr_iterator MI) : MII(MI) { |
| 133 | assert((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) &&(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred ()) && "It's not legal to initialize MachineInstrBundleIterator with a " "bundled MI") ? static_cast<void> (0) : __assert_fail ( "(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 135, __PRETTY_FUNCTION__)) |
| 134 | "It's not legal to initialize MachineInstrBundleIterator with a "(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred ()) && "It's not legal to initialize MachineInstrBundleIterator with a " "bundled MI") ? static_cast<void> (0) : __assert_fail ( "(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 135, __PRETTY_FUNCTION__)) |
| 135 | "bundled MI")(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred ()) && "It's not legal to initialize MachineInstrBundleIterator with a " "bundled MI") ? static_cast<void> (0) : __assert_fail ( "(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 135, __PRETTY_FUNCTION__)); |
| 136 | } |
| 137 | |
| 138 | MachineInstrBundleIterator(reference MI) : MII(MI) { |
| 139 | assert(!MI.isBundledWithPred() && "It's not legal to initialize "((!MI.isBundledWithPred() && "It's not legal to initialize " "MachineInstrBundleIterator with a " "bundled MI") ? static_cast <void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 141, __PRETTY_FUNCTION__)) |
| 140 | "MachineInstrBundleIterator with a "((!MI.isBundledWithPred() && "It's not legal to initialize " "MachineInstrBundleIterator with a " "bundled MI") ? static_cast <void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 141, __PRETTY_FUNCTION__)) |
| 141 | "bundled MI")((!MI.isBundledWithPred() && "It's not legal to initialize " "MachineInstrBundleIterator with a " "bundled MI") ? static_cast <void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 141, __PRETTY_FUNCTION__)); |
| 142 | } |
| 143 | |
| 144 | MachineInstrBundleIterator(pointer MI) : MII(MI) { |
| 145 | // FIXME: This conversion should be explicit. |
| 146 | assert((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize " "MachineInstrBundleIterator " "with a bundled MI") ? static_cast <void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 148, __PRETTY_FUNCTION__)) |
| 147 | "MachineInstrBundleIterator "(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize " "MachineInstrBundleIterator " "with a bundled MI") ? static_cast <void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 148, __PRETTY_FUNCTION__)) |
| 148 | "with a bundled MI")(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize " "MachineInstrBundleIterator " "with a bundled MI") ? static_cast <void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\"" , "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h" , 148, __PRETTY_FUNCTION__)); |
| 149 | } |
| 150 | |
| 151 | // Template allows conversion from const to nonconst. |
| 152 | template <class OtherTy> |
| 153 | MachineInstrBundleIterator( |
| 154 | const MachineInstrBundleIterator<OtherTy, IsReverse> &I, |
| 155 | typename std::enable_if<std::is_convertible<OtherTy *, Ty *>::value, |
| 156 | void *>::type = nullptr) |
| 157 | : MII(I.getInstrIterator()) {} |
| 158 | |
| 159 | MachineInstrBundleIterator() : MII(nullptr) {} |
| 160 | |
| 161 | /// Explicit conversion between forward/reverse iterators. |
| 162 | /// |
| 163 | /// Translate between forward and reverse iterators without changing range |
| 164 | /// boundaries. The resulting iterator will dereference (and have a handle) |
| 165 | /// to the previous node, which is somewhat unexpected; but converting the |
| 166 | /// two endpoints in a range will give the same range in reverse. |
| 167 | /// |
| 168 | /// This matches std::reverse_iterator conversions. |
| 169 | explicit MachineInstrBundleIterator( |
| 170 | const MachineInstrBundleIterator<Ty, !IsReverse> &I) |
| 171 | : MachineInstrBundleIterator(++I.getReverse()) {} |
| 172 | |
| 173 | /// Get the bundle iterator for the given instruction's bundle. |
| 174 | static MachineInstrBundleIterator getAtBundleBegin(instr_iterator MI) { |
| 175 | return MachineInstrBundleIteratorHelper<IsReverse>::getBundleBegin(MI); |
| 176 | } |
| 177 | |
| 178 | reference operator*() const { return *MII; } |
| 179 | pointer operator->() const { return &operator*(); } |
| 180 | |
| 181 | /// Check for null. |
| 182 | bool isValid() const { return MII.getNodePtr(); } |
| 183 | |
| 184 | friend bool operator==(const MachineInstrBundleIterator &L, |
| 185 | const MachineInstrBundleIterator &R) { |
| 186 | return L.MII == R.MII; |
| 187 | } |
| 188 | friend bool operator==(const MachineInstrBundleIterator &L, |
| 189 | const const_instr_iterator &R) { |
| 190 | return L.MII == R; // Avoid assertion about validity of R. |
| 191 | } |
| 192 | friend bool operator==(const const_instr_iterator &L, |
| 193 | const MachineInstrBundleIterator &R) { |
| 194 | return L == R.MII; // Avoid assertion about validity of L. |
| 195 | } |
| 196 | friend bool operator==(const MachineInstrBundleIterator &L, |
| 197 | const nonconst_instr_iterator &R) { |
| 198 | return L.MII == R; // Avoid assertion about validity of R. |
| 199 | } |
| 200 | friend bool operator==(const nonconst_instr_iterator &L, |
| 201 | const MachineInstrBundleIterator &R) { |
| 202 | return L == R.MII; // Avoid assertion about validity of L. |
| 203 | } |
| 204 | friend bool operator==(const MachineInstrBundleIterator &L, const_pointer R) { |
| 205 | return L == const_instr_iterator(R); // Avoid assertion about validity of R. |
| 206 | } |
| 207 | friend bool operator==(const_pointer L, const MachineInstrBundleIterator &R) { |
| 208 | return const_instr_iterator(L) == R; // Avoid assertion about validity of L. |
| 209 | } |
| 210 | friend bool operator==(const MachineInstrBundleIterator &L, |
| 211 | const_reference R) { |
| 212 | return L == &R; // Avoid assertion about validity of R. |
| 213 | } |
| 214 | friend bool operator==(const_reference L, |
| 215 | const MachineInstrBundleIterator &R) { |
| 216 | return &L == R; // Avoid assertion about validity of L. |
| 217 | } |
| 218 | |
| 219 | friend bool operator!=(const MachineInstrBundleIterator &L, |
| 220 | const MachineInstrBundleIterator &R) { |
| 221 | return !(L == R); |
| 222 | } |
| 223 | friend bool operator!=(const MachineInstrBundleIterator &L, |
| 224 | const const_instr_iterator &R) { |
| 225 | return !(L == R); |
| 226 | } |
| 227 | friend bool operator!=(const const_instr_iterator &L, |
| 228 | const MachineInstrBundleIterator &R) { |
| 229 | return !(L == R); |
| 230 | } |
| 231 | friend bool operator!=(const MachineInstrBundleIterator &L, |
| 232 | const nonconst_instr_iterator &R) { |
| 233 | return !(L == R); |
| 234 | } |
| 235 | friend bool operator!=(const nonconst_instr_iterator &L, |
| 236 | const MachineInstrBundleIterator &R) { |
| 237 | return !(L == R); |
| 238 | } |
| 239 | friend bool operator!=(const MachineInstrBundleIterator &L, const_pointer R) { |
| 240 | return !(L == R); |
| 241 | } |
| 242 | friend bool operator!=(const_pointer L, const MachineInstrBundleIterator &R) { |
| 243 | return !(L == R); |
| 244 | } |
| 245 | friend bool operator!=(const MachineInstrBundleIterator &L, |
| 246 | const_reference R) { |
| 247 | return !(L == R); |
| 248 | } |
| 249 | friend bool operator!=(const_reference L, |
| 250 | const MachineInstrBundleIterator &R) { |
| 251 | return !(L == R); |
| 252 | } |
| 253 | |
| 254 | // Increment and decrement operators... |
| 255 | MachineInstrBundleIterator &operator--() { |
| 256 | this->decrement(MII); |
| 257 | return *this; |
| 258 | } |
| 259 | MachineInstrBundleIterator &operator++() { |
| 260 | this->increment(MII); |
| 261 | return *this; |
| 262 | } |
| 263 | MachineInstrBundleIterator operator--(int) { |
| 264 | MachineInstrBundleIterator Temp = *this; |
| 265 | --*this; |
| 266 | return Temp; |
| 267 | } |
| 268 | MachineInstrBundleIterator operator++(int) { |
| 269 | MachineInstrBundleIterator Temp = *this; |
| 270 | ++*this; |
| 271 | return Temp; |
| 272 | } |
| 273 | |
| 274 | instr_iterator getInstrIterator() const { return MII; } |
| 275 | |
| 276 | nonconst_iterator getNonConstIterator() const { return MII.getNonConst(); } |
| 277 | |
| 278 | /// Get a reverse iterator to the same node. |
| 279 | /// |
| 280 | /// Gives a reverse iterator that will dereference (and have a handle) to the |
| 281 | /// same node. Converting the endpoint iterators in a range will give a |
| 282 | /// different range; for range operations, use the explicit conversions. |
| 283 | reverse_iterator getReverse() const { return MII.getReverse(); } |
| 284 | }; |
| 285 | |
| 286 | } // end namespace llvm |
| 287 | |
| 288 | #endif // LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H |
| 1 | //===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- C++ -*-===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
| 9 | #ifndef LLVM_ADT_ILIST_ITERATOR_H |
| 10 | #define LLVM_ADT_ILIST_ITERATOR_H |
| 11 | |
| 12 | #include "llvm/ADT/ilist_node.h" |
| 13 | #include <cassert> |
| 14 | #include <cstddef> |
| 15 | #include <iterator> |
| 16 | #include <type_traits> |
| 17 | |
| 18 | namespace llvm { |
| 19 | |
| 20 | namespace ilist_detail { |
| 21 | |
| 22 | /// Find const-correct node types. |
| 23 | template <class OptionsT, bool IsConst> struct IteratorTraits; |
| 24 | template <class OptionsT> struct IteratorTraits<OptionsT, false> { |
| 25 | using value_type = typename OptionsT::value_type; |
| 26 | using pointer = typename OptionsT::pointer; |
| 27 | using reference = typename OptionsT::reference; |
| 28 | using node_pointer = ilist_node_impl<OptionsT> *; |
| 29 | using node_reference = ilist_node_impl<OptionsT> &; |
| 30 | }; |
| 31 | template <class OptionsT> struct IteratorTraits<OptionsT, true> { |
| 32 | using value_type = const typename OptionsT::value_type; |
| 33 | using pointer = typename OptionsT::const_pointer; |
| 34 | using reference = typename OptionsT::const_reference; |
| 35 | using node_pointer = const ilist_node_impl<OptionsT> *; |
| 36 | using node_reference = const ilist_node_impl<OptionsT> &; |
| 37 | }; |
| 38 | |
| 39 | template <bool IsReverse> struct IteratorHelper; |
| 40 | template <> struct IteratorHelper<false> : ilist_detail::NodeAccess { |
| 41 | using Access = ilist_detail::NodeAccess; |
| 42 | |
| 43 | template <class T> static void increment(T *&I) { I = Access::getNext(*I); } |
| 44 | template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); } |
| 45 | }; |
| 46 | template <> struct IteratorHelper<true> : ilist_detail::NodeAccess { |
| 47 | using Access = ilist_detail::NodeAccess; |
| 48 | |
| 49 | template <class T> static void increment(T *&I) { I = Access::getPrev(*I); } |
| 50 | template <class T> static void decrement(T *&I) { I = Access::getNext(*I); } |
| 51 | }; |
| 52 | |
| 53 | } // end namespace ilist_detail |
| 54 | |
| 55 | /// Iterator for intrusive lists based on ilist_node. |
| 56 | template <class OptionsT, bool IsReverse, bool IsConst> |
| 57 | class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> { |
| 58 | friend ilist_iterator<OptionsT, IsReverse, !IsConst>; |
| 59 | friend ilist_iterator<OptionsT, !IsReverse, IsConst>; |
| 60 | friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; |
| 61 | |
| 62 | using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; |
| 63 | using Access = ilist_detail::SpecificNodeAccess<OptionsT>; |
| 64 | |
| 65 | public: |
| 66 | using value_type = typename Traits::value_type; |
| 67 | using pointer = typename Traits::pointer; |
| 68 | using reference = typename Traits::reference; |
| 69 | using difference_type = ptrdiff_t; |
| 70 | using iterator_category = std::bidirectional_iterator_tag; |
| 71 | using const_pointer = typename OptionsT::const_pointer; |
| 72 | using const_reference = typename OptionsT::const_reference; |
| 73 | |
| 74 | private: |
| 75 | using node_pointer = typename Traits::node_pointer; |
| 76 | using node_reference = typename Traits::node_reference; |
| 77 | |
| 78 | node_pointer NodePtr = nullptr; |
| 79 | |
| 80 | public: |
| 81 | /// Create from an ilist_node. |
| 82 | explicit ilist_iterator(node_reference N) : NodePtr(&N) {} |
| 83 | |
| 84 | explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {} |
| 85 | explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {} |
| 86 | ilist_iterator() = default; |
| 87 | |
| 88 | // This is templated so that we can allow constructing a const iterator from |
| 89 | // a nonconst iterator... |
| 90 | template <bool RHSIsConst> |
| 91 | ilist_iterator( |
| 92 | const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, |
| 93 | typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr) |
| 94 | : NodePtr(RHS.NodePtr) {} |
| 95 | |
| 96 | // This is templated so that we can allow assigning to a const iterator from |
| 97 | // a nonconst iterator... |
| 98 | template <bool RHSIsConst> |
| 99 | typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type |
| 100 | operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) { |
| 101 | NodePtr = RHS.NodePtr; |
| 102 | return *this; |
| 103 | } |
| 104 | |
| 105 | /// Explicit conversion between forward/reverse iterators. |
| 106 | /// |
| 107 | /// Translate between forward and reverse iterators without changing range |
| 108 | /// boundaries. The resulting iterator will dereference (and have a handle) |
| 109 | /// to the previous node, which is somewhat unexpected; but converting the |
| 110 | /// two endpoints in a range will give the same range in reverse. |
| 111 | /// |
| 112 | /// This matches std::reverse_iterator conversions. |
| 113 | explicit ilist_iterator( |
| 114 | const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) |
| 115 | : ilist_iterator(++RHS.getReverse()) {} |
| 116 | |
| 117 | /// Get a reverse iterator to the same node. |
| 118 | /// |
| 119 | /// Gives a reverse iterator that will dereference (and have a handle) to the |
| 120 | /// same node. Converting the endpoint iterators in a range will give a |
| 121 | /// different range; for range operations, use the explicit conversions. |
| 122 | ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { |
| 123 | if (NodePtr) |
| 124 | return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); |
| 125 | return ilist_iterator<OptionsT, !IsReverse, IsConst>(); |
| 126 | } |
| 127 | |
| 128 | /// Const-cast. |
| 129 | ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { |
| 130 | if (NodePtr) |
| 131 | return ilist_iterator<OptionsT, IsReverse, false>( |
| 132 | const_cast<typename ilist_iterator<OptionsT, IsReverse, |
| 133 | false>::node_reference>(*NodePtr)); |
| 134 | return ilist_iterator<OptionsT, IsReverse, false>(); |
| 135 | } |
| 136 | |
| 137 | // Accessors... |
| 138 | reference operator*() const { |
| 139 | assert(!NodePtr->isKnownSentinel())((!NodePtr->isKnownSentinel()) ? static_cast<void> ( 0) : __assert_fail ("!NodePtr->isKnownSentinel()", "/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/include/llvm/ADT/ilist_iterator.h" , 139, __PRETTY_FUNCTION__)); |
| 140 | return *Access::getValuePtr(NodePtr); |
| 141 | } |
| 142 | pointer operator->() const { return &operator*(); } |
| 143 | |
| 144 | // Comparison operators |
| 145 | friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) { |
| 146 | return LHS.NodePtr == RHS.NodePtr; |
| 147 | } |
| 148 | friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) { |
| 149 | return LHS.NodePtr != RHS.NodePtr; |
| 150 | } |
| 151 | |
| 152 | // Increment and decrement operators... |
| 153 | ilist_iterator &operator--() { |
| 154 | NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); |
| 155 | return *this; |
| 156 | } |
| 157 | ilist_iterator &operator++() { |
| 158 | NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); |
| 159 | return *this; |
| 160 | } |
| 161 | ilist_iterator operator--(int) { |
| 162 | ilist_iterator tmp = *this; |
| 163 | --*this; |
| 164 | return tmp; |
| 165 | } |
| 166 | ilist_iterator operator++(int) { |
| 167 | ilist_iterator tmp = *this; |
| 168 | ++*this; |
| 169 | return tmp; |
| 170 | } |
| 171 | |
| 172 | /// Get the underlying ilist_node. |
| 173 | node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } |
| 174 | |
| 175 | /// Check for end. Only valid if ilist_sentinel_tracking<true>. |
| 176 | bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } |
| 177 | }; |
| 178 | |
| 179 | template <typename From> struct simplify_type; |
| 180 | |
| 181 | /// Allow ilist_iterators to convert into pointers to a node automatically when |
| 182 | /// used by the dyn_cast, cast, isa mechanisms... |
| 183 | /// |
| 184 | /// FIXME: remove this, since there is no implicit conversion to NodeTy. |
| 185 | template <class OptionsT, bool IsConst> |
| 186 | struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { |
| 187 | using iterator = ilist_iterator<OptionsT, false, IsConst>; |
| 188 | using SimpleType = typename iterator::pointer; |
| 189 | |
| 190 | static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } |
| 191 | }; |
| 192 | template <class OptionsT, bool IsConst> |
| 193 | struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> |
| 194 | : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {}; |
| 195 | |
| 196 | } // end namespace llvm |
| 197 | |
| 198 | #endif // LLVM_ADT_ILIST_ITERATOR_H |