/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp

Bug Summary

File:	llvm/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp
Warning:	line 2276, column 27 Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name AMDGPUMachineCFGStructurizer.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Target/AMDGPU -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Target/AMDGPU -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Target/AMDGPU -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Target/AMDGPU -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp

→

1//===- AMDGPUMachineCFGStructurizer.cpp - Machine code if conversion pass. ===//
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 file implements the machine instruction level CFG structurizer pass.
10//
11//===----------------------------------------------------------------------===//

13#include "AMDGPU.h"
14#include "GCNSubtarget.h"
15#include "llvm/ADT/DenseSet.h"
16#include "llvm/ADT/PostOrderIterator.h"
17#include "llvm/ADT/SetVector.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/CodeGen/MachineBasicBlock.h"
20#include "llvm/CodeGen/MachineInstrBuilder.h"
21#include "llvm/CodeGen/MachineRegionInfo.h"
22#include "llvm/CodeGen/MachineRegisterInfo.h"
23#include "llvm/CodeGen/TargetRegisterInfo.h"
24#include "llvm/InitializePasses.h"

26using namespace llvm;

28#define DEBUG_TYPE"amdgpucfgstructurizer" "amdgpucfgstructurizer"

30namespace {

32class PHILinearizeDestIterator;

34class PHILinearize {
friend class PHILinearizeDestIterator;

37public:
using PHISourceT = std::pair<unsigned, MachineBasicBlock *>;

40private:
using PHISourcesT = DenseSet<PHISourceT>;
using PHIInfoElementT = struct {
  unsigned DestReg;
  DebugLoc DL;
  PHISourcesT Sources;
};
using PHIInfoT = SmallPtrSet<PHIInfoElementT *, 2>;
PHIInfoT PHIInfo;

static unsigned phiInfoElementGetDest(PHIInfoElementT *Info);
static void phiInfoElementSetDef(PHIInfoElementT *Info, unsigned NewDef);
static PHISourcesT &phiInfoElementGetSources(PHIInfoElementT *Info);
static void phiInfoElementAddSource(PHIInfoElementT *Info, unsigned SourceReg,
                                    MachineBasicBlock *SourceMBB);
static void phiInfoElementRemoveSource(PHIInfoElementT *Info,
                                       unsigned SourceReg,
                                       MachineBasicBlock *SourceMBB);
PHIInfoElementT *findPHIInfoElement(unsigned DestReg);
PHIInfoElementT *findPHIInfoElementFromSource(unsigned SourceReg,
                                              MachineBasicBlock *SourceMBB);

62public:
bool findSourcesFromMBB(MachineBasicBlock *SourceMBB,
                        SmallVector<unsigned, 4> &Sources);
void addDest(unsigned DestReg, const DebugLoc &DL);
void replaceDef(unsigned OldDestReg, unsigned NewDestReg);
void deleteDef(unsigned DestReg);
void addSource(unsigned DestReg, unsigned SourceReg,
               MachineBasicBlock *SourceMBB);
void removeSource(unsigned DestReg, unsigned SourceReg,
                  MachineBasicBlock *SourceMBB = nullptr);
bool findDest(unsigned SourceReg, MachineBasicBlock *SourceMBB,
              unsigned &DestReg);
bool isSource(unsigned Reg, MachineBasicBlock *SourceMBB = nullptr);
unsigned getNumSources(unsigned DestReg);
void dump(MachineRegisterInfo *MRI);
void clear();

using source_iterator = PHISourcesT::iterator;
using dest_iterator = PHILinearizeDestIterator;

dest_iterator dests_begin();
dest_iterator dests_end();

source_iterator sources_begin(unsigned Reg);
source_iterator sources_end(unsigned Reg);
87};

89class PHILinearizeDestIterator {
90private:
PHILinearize::PHIInfoT::iterator Iter;

93public:
PHILinearizeDestIterator(PHILinearize::PHIInfoT::iterator I) : Iter(I) {}

unsigned operator*() { return PHILinearize::phiInfoElementGetDest(*Iter); }
PHILinearizeDestIterator &operator++() {
  ++Iter;
  return *this;
}
bool operator==(const PHILinearizeDestIterator &I) const {
  return I.Iter == Iter;
}
bool operator!=(const PHILinearizeDestIterator &I) const {
  return I.Iter != Iter;
}
107};

109} // end anonymous namespace

111unsigned PHILinearize::phiInfoElementGetDest(PHIInfoElementT *Info) {
return Info->DestReg;
113}

115void PHILinearize::phiInfoElementSetDef(PHIInfoElementT *Info,
                                      unsigned NewDef) {
Info->DestReg = NewDef;
118}

120PHILinearize::PHISourcesT &
121PHILinearize::phiInfoElementGetSources(PHIInfoElementT *Info) {
return Info->Sources;
123}

125void PHILinearize::phiInfoElementAddSource(PHIInfoElementT *Info,
                                         unsigned SourceReg,
                                         MachineBasicBlock *SourceMBB) {
// Assertion ensures we don't use the same SourceMBB for the
// sources, because we cannot have different registers with
// identical predecessors, but we can have the same register for
// multiple predecessors.
132#if !defined(NDEBUG1)
for (auto SI : phiInfoElementGetSources(Info)) {
  assert((SI.second != SourceMBB || SourceReg == SI.first))(static_cast<void> (0));
}
136#endif

phiInfoElementGetSources(Info).insert(PHISourceT(SourceReg, SourceMBB));
139}

141void PHILinearize::phiInfoElementRemoveSource(PHIInfoElementT *Info,
                                            unsigned SourceReg,
                                            MachineBasicBlock *SourceMBB) {
auto &Sources = phiInfoElementGetSources(Info);
SmallVector<PHISourceT, 4> ElimiatedSources;
for (auto SI : Sources) {
  if (SI.first == SourceReg &&
      (SI.second == nullptr || SI.second == SourceMBB)) {
    ElimiatedSources.push_back(PHISourceT(SI.first, SI.second));
  }
}

for (auto &Source : ElimiatedSources) {
  Sources.erase(Source);
}
156}

158PHILinearize::PHIInfoElementT *
159PHILinearize::findPHIInfoElement(unsigned DestReg) {
for (auto I : PHIInfo) {
  if (phiInfoElementGetDest(I) == DestReg) {
    return I;
  }
}
return nullptr;
166}

168PHILinearize::PHIInfoElementT *
169PHILinearize::findPHIInfoElementFromSource(unsigned SourceReg,
                                         MachineBasicBlock *SourceMBB) {
for (auto I : PHIInfo) {
  for (auto SI : phiInfoElementGetSources(I)) {
    if (SI.first == SourceReg &&
        (SI.second == nullptr || SI.second == SourceMBB)) {
      return I;
    }
  }
}
return nullptr;
180}

182bool PHILinearize::findSourcesFromMBB(MachineBasicBlock *SourceMBB,
                                    SmallVector<unsigned, 4> &Sources) {
bool FoundSource = false;
for (auto I : PHIInfo) {
  for (auto SI : phiInfoElementGetSources(I)) {
    if (SI.second == SourceMBB) {
      FoundSource = true;
      Sources.push_back(SI.first);
    }
  }
}
return FoundSource;
194}

196void PHILinearize::addDest(unsigned DestReg, const DebugLoc &DL) {
assert(findPHIInfoElement(DestReg) == nullptr && "Dest already exsists")(static_cast<void> (0));
PHISourcesT EmptySet;
PHIInfoElementT *NewElement = new PHIInfoElementT();
NewElement->DestReg = DestReg;
NewElement->DL = DL;
NewElement->Sources = EmptySet;
PHIInfo.insert(NewElement);
204}

206void PHILinearize::replaceDef(unsigned OldDestReg, unsigned NewDestReg) {
phiInfoElementSetDef(findPHIInfoElement(OldDestReg), NewDestReg);
208}

210void PHILinearize::deleteDef(unsigned DestReg) {
PHIInfoElementT *InfoElement = findPHIInfoElement(DestReg);
PHIInfo.erase(InfoElement);
delete InfoElement;
214}

216void PHILinearize::addSource(unsigned DestReg, unsigned SourceReg,
                           MachineBasicBlock *SourceMBB) {
phiInfoElementAddSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
219}

221void PHILinearize::removeSource(unsigned DestReg, unsigned SourceReg,
                              MachineBasicBlock *SourceMBB) {
phiInfoElementRemoveSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
224}

226bool PHILinearize::findDest(unsigned SourceReg, MachineBasicBlock *SourceMBB,
                          unsigned &DestReg) {
PHIInfoElementT *InfoElement =
    findPHIInfoElementFromSource(SourceReg, SourceMBB);
if (InfoElement != nullptr) {
  DestReg = phiInfoElementGetDest(InfoElement);
  return true;
}
return false;
235}

237bool PHILinearize::isSource(unsigned Reg, MachineBasicBlock *SourceMBB) {
unsigned DestReg;
return findDest(Reg, SourceMBB, DestReg);
240}

242unsigned PHILinearize::getNumSources(unsigned DestReg) {
return phiInfoElementGetSources(findPHIInfoElement(DestReg)).size();
244}

246#if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP)
247LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void PHILinearize::dump(MachineRegisterInfo *MRI) {
const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
dbgs() << "=PHIInfo Start=\n";
for (auto PII : this->PHIInfo) {
  PHIInfoElementT &Element = *PII;
  dbgs() << "Dest: " << printReg(Element.DestReg, TRI)
         << " Sources: {";
  for (auto &SI : Element.Sources) {
    dbgs() << printReg(SI.first, TRI) << '(' << printMBBReference(*SI.second)
           << "),";
  }
  dbgs() << "}\n";
}
dbgs() << "=PHIInfo End=\n";
261}
262#endif

264void PHILinearize::clear() { PHIInfo = PHIInfoT(); }

266PHILinearize::dest_iterator PHILinearize::dests_begin() {
return PHILinearizeDestIterator(PHIInfo.begin());
268}

270PHILinearize::dest_iterator PHILinearize::dests_end() {
return PHILinearizeDestIterator(PHIInfo.end());
272}

274PHILinearize::source_iterator PHILinearize::sources_begin(unsigned Reg) {
auto InfoElement = findPHIInfoElement(Reg);
return phiInfoElementGetSources(InfoElement).begin();
277}

279PHILinearize::source_iterator PHILinearize::sources_end(unsigned Reg) {
auto InfoElement = findPHIInfoElement(Reg);
return phiInfoElementGetSources(InfoElement).end();
282}

284static unsigned getPHINumInputs(MachineInstr &PHI) {
assert(PHI.isPHI())(static_cast<void> (0));
return (PHI.getNumOperands() - 1) / 2;
287}

289static MachineBasicBlock *getPHIPred(MachineInstr &PHI, unsigned Index) {
assert(PHI.isPHI())(static_cast<void> (0));
return PHI.getOperand(Index * 2 + 2).getMBB();
292}

294static void setPhiPred(MachineInstr &PHI, unsigned Index,
                     MachineBasicBlock *NewPred) {
PHI.getOperand(Index * 2 + 2).setMBB(NewPred);
297}

299static unsigned getPHISourceReg(MachineInstr &PHI, unsigned Index) {
assert(PHI.isPHI())(static_cast<void> (0));
return PHI.getOperand(Index * 2 + 1).getReg();
302}

304static unsigned getPHIDestReg(MachineInstr &PHI) {
assert(PHI.isPHI())(static_cast<void> (0));
return PHI.getOperand(0).getReg();
307}

309namespace {

311class RegionMRT;
312class MBBMRT;

314class LinearizedRegion {
315protected:
MachineBasicBlock *Entry;
// The exit block is part of the region, and is the last
// merge block before exiting the region.
MachineBasicBlock *Exit;
DenseSet<unsigned> LiveOuts;
SmallPtrSet<MachineBasicBlock *, 1> MBBs;
bool HasLoop;
LinearizedRegion *Parent;
RegionMRT *RMRT;

void storeLiveOutReg(MachineBasicBlock *MBB, Register Reg,
                     MachineInstr *DefInstr, const MachineRegisterInfo *MRI,
                     const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);

void storeLiveOutRegRegion(RegionMRT *Region, Register Reg,
                           MachineInstr *DefInstr,
                           const MachineRegisterInfo *MRI,
                           const TargetRegisterInfo *TRI,
                           PHILinearize &PHIInfo);

void storeMBBLiveOuts(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
                      const TargetRegisterInfo *TRI, PHILinearize &PHIInfo,
                      RegionMRT *TopRegion);

void storeLiveOuts(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
                   const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);

void storeLiveOuts(RegionMRT *Region, const MachineRegisterInfo *MRI,
                   const TargetRegisterInfo *TRI, PHILinearize &PHIInfo,
                   RegionMRT *TopRegion = nullptr);

347public:
LinearizedRegion();
LinearizedRegion(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
                 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
~LinearizedRegion() = default;

void setRegionMRT(RegionMRT *Region) { RMRT = Region; }

RegionMRT *getRegionMRT() { return RMRT; }

void setParent(LinearizedRegion *P) { Parent = P; }
48
←
Returning without writing to 'P->HasLoop', which participates in a condition later→

LinearizedRegion *getParent() { return Parent; }

void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr);

void setBBSelectRegIn(unsigned Reg);

unsigned getBBSelectRegIn();

void setBBSelectRegOut(unsigned Reg, bool IsLiveOut);

unsigned getBBSelectRegOut();

void setHasLoop(bool Value);

bool getHasLoop();

void addLiveOut(unsigned VReg);

void removeLiveOut(unsigned Reg);

void replaceLiveOut(unsigned OldReg, unsigned NewReg);

void replaceRegister(unsigned Register, class Register NewRegister,
                     MachineRegisterInfo *MRI, bool ReplaceInside,
                     bool ReplaceOutside, bool IncludeLoopPHIs);

void replaceRegisterInsideRegion(unsigned Register, unsigned NewRegister,
                                 bool IncludeLoopPHIs,
                                 MachineRegisterInfo *MRI);

void replaceRegisterOutsideRegion(unsigned Register, unsigned NewRegister,
                                  bool IncludeLoopPHIs,
                                  MachineRegisterInfo *MRI);

DenseSet<unsigned> *getLiveOuts();

void setEntry(MachineBasicBlock *NewEntry);

MachineBasicBlock *getEntry();

void setExit(MachineBasicBlock *NewExit);

MachineBasicBlock *getExit();

void addMBB(MachineBasicBlock *MBB);

void addMBBs(LinearizedRegion *InnerRegion);

bool contains(MachineBasicBlock *MBB);

bool isLiveOut(unsigned Reg);

bool hasNoDef(unsigned Reg, MachineRegisterInfo *MRI);

void removeFalseRegisterKills(MachineRegisterInfo *MRI);

void initLiveOut(RegionMRT *Region, const MachineRegisterInfo *MRI,
                 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
417};

419class MRT {
420protected:
RegionMRT *Parent;
unsigned BBSelectRegIn;
unsigned BBSelectRegOut;

425public:
virtual ~MRT() = default;

unsigned getBBSelectRegIn() { return BBSelectRegIn; }

unsigned getBBSelectRegOut() { return BBSelectRegOut; }

void setBBSelectRegIn(unsigned Reg) { BBSelectRegIn = Reg; }

void setBBSelectRegOut(unsigned Reg) { BBSelectRegOut = Reg; }

virtual RegionMRT *getRegionMRT() { return nullptr; }

virtual MBBMRT *getMBBMRT() { return nullptr; }

bool isRegion() { return getRegionMRT() != nullptr; }
31
←
Assuming the condition is false→
32
←
Returning zero, which participates in a condition later→
67
←
Assuming the condition is false→
68
←
Returning zero, which participates in a condition later→

bool isMBB() { return getMBBMRT() != nullptr; }

bool isRoot() { return Parent == nullptr; }

void setParent(RegionMRT *Region) { Parent = Region; }

RegionMRT *getParent() { return Parent; }

static MachineBasicBlock *
initializeMRT(MachineFunction &MF, const MachineRegionInfo *RegionInfo,
              DenseMap<MachineRegion *, RegionMRT *> &RegionMap);

static RegionMRT *buildMRT(MachineFunction &MF,
                           const MachineRegionInfo *RegionInfo,
                           const SIInstrInfo *TII,
                           MachineRegisterInfo *MRI);

virtual void dump(const TargetRegisterInfo *TRI, int depth = 0) = 0;

void dumpDepth(int depth) {
  for (int i = depth; i > 0; --i) {
    dbgs() << "  ";
  }
}
466};

468class MBBMRT : public MRT {
MachineBasicBlock *MBB;

471public:
MBBMRT(MachineBasicBlock *BB) : MBB(BB) {
  setParent(nullptr);
  setBBSelectRegOut(0);
  setBBSelectRegIn(0);
}

MBBMRT *getMBBMRT() override { return this; }

MachineBasicBlock *getMBB() { return MBB; }

void dump(const TargetRegisterInfo *TRI, int depth = 0) override {
  dumpDepth(depth);
  dbgs() << "MBB: " << getMBB()->getNumber();
  dbgs() << " In: " << printReg(getBBSelectRegIn(), TRI);
  dbgs() << ", Out: " << printReg(getBBSelectRegOut(), TRI) << "\n";
}
488};

490class RegionMRT : public MRT {
491protected:
MachineRegion *Region;
LinearizedRegion *LRegion = nullptr;
MachineBasicBlock *Succ = nullptr;
SetVector<MRT *> Children;

497public:
RegionMRT(MachineRegion *MachineRegion) : Region(MachineRegion) {
  setParent(nullptr);
  setBBSelectRegOut(0);
  setBBSelectRegIn(0);
}

~RegionMRT() override {
  if (LRegion) {
    delete LRegion;
  }

  for (auto CI : Children) {
    delete &(*CI);
  }
}

RegionMRT *getRegionMRT() override { return this; }

void setLinearizedRegion(LinearizedRegion *LinearizeRegion) {
  LRegion = LinearizeRegion;
}

LinearizedRegion *getLinearizedRegion() { return LRegion; }

MachineRegion *getMachineRegion() { return Region; }

unsigned getInnerOutputRegister() {
  return (*(Children.begin()))->getBBSelectRegOut();
}

void addChild(MRT *Tree) { Children.insert(Tree); }

SetVector<MRT *> *getChildren() { return &Children; }

void dump(const TargetRegisterInfo *TRI, int depth = 0) override {
  dumpDepth(depth);
  dbgs() << "Region: " << (void *)Region;
  dbgs() << " In: " << printReg(getBBSelectRegIn(), TRI);
  dbgs() << ", Out: " << printReg(getBBSelectRegOut(), TRI) << "\n";

  dumpDepth(depth);
  if (getSucc())
    dbgs() << "Succ: " << getSucc()->getNumber() << "\n";
  else
    dbgs() << "Succ: none \n";
  for (auto MRTI : Children) {
    MRTI->dump(TRI, depth + 1);
  }
}

MRT *getEntryTree() { return Children.back(); }

MRT *getExitTree() { return Children.front(); }

MachineBasicBlock *getEntry() {
  MRT *Tree = Children.back();
  return (Tree->isRegion()) ? Tree->getRegionMRT()->getEntry()
                            : Tree->getMBBMRT()->getMBB();
}

MachineBasicBlock *getExit() {
  MRT *Tree = Children.front();
  return (Tree->isRegion()) ? Tree->getRegionMRT()->getExit()
                            : Tree->getMBBMRT()->getMBB();
}

void setSucc(MachineBasicBlock *MBB) { Succ = MBB; }

MachineBasicBlock *getSucc() { return Succ; }

bool contains(MachineBasicBlock *MBB) {
  for (auto CI : Children) {
    if (CI->isMBB()) {
      if (MBB == CI->getMBBMRT()->getMBB()) {
        return true;
      }
    } else {
      if (CI->getRegionMRT()->contains(MBB)) {
        return true;
      } else if (CI->getRegionMRT()->getLinearizedRegion() != nullptr &&
                 CI->getRegionMRT()->getLinearizedRegion()->contains(MBB)) {
        return true;
      }
    }
  }
  return false;
}

void replaceLiveOutReg(unsigned Register, unsigned NewRegister) {
  LinearizedRegion *LRegion = getLinearizedRegion();
  LRegion->replaceLiveOut(Register, NewRegister);
  for (auto &CI : Children) {
    if (CI->isRegion()) {
      CI->getRegionMRT()->replaceLiveOutReg(Register, NewRegister);
    }
  }
}
595};

597} // end anonymous namespace

599static unsigned createBBSelectReg(const SIInstrInfo *TII,
                                MachineRegisterInfo *MRI) {
return MRI->createVirtualRegister(TII->getPreferredSelectRegClass(32));
602}

604MachineBasicBlock *
605MRT::initializeMRT(MachineFunction &MF, const MachineRegionInfo *RegionInfo,
                 DenseMap<MachineRegion *, RegionMRT *> &RegionMap) {
for (auto &MFI : MF) {
  MachineBasicBlock *ExitMBB = &MFI;
  if (ExitMBB->succ_size() == 0) {
    return ExitMBB;
  }
}
llvm_unreachable("CFG has no exit block")__builtin_unreachable();
return nullptr;
615}

617RegionMRT *MRT::buildMRT(MachineFunction &MF,
                       const MachineRegionInfo *RegionInfo,
                       const SIInstrInfo *TII, MachineRegisterInfo *MRI) {
SmallPtrSet<MachineRegion *, 4> PlacedRegions;
DenseMap<MachineRegion *, RegionMRT *> RegionMap;
MachineRegion *TopLevelRegion = RegionInfo->getTopLevelRegion();
RegionMRT *Result = new RegionMRT(TopLevelRegion);
RegionMap[TopLevelRegion] = Result;

// Insert the exit block first, we need it to be the merge node
// for the top level region.
MachineBasicBlock *Exit = initializeMRT(MF, RegionInfo, RegionMap);

unsigned BBSelectRegIn = createBBSelectReg(TII, MRI);
MBBMRT *ExitMRT = new MBBMRT(Exit);
RegionMap[RegionInfo->getRegionFor(Exit)]->addChild(ExitMRT);
ExitMRT->setBBSelectRegIn(BBSelectRegIn);

for (auto MBBI : post_order(&(MF.front()))) {
  MachineBasicBlock *MBB = &(*MBBI);

  // Skip Exit since we already added it
  if (MBB == Exit) {
    continue;
  }

  LLVM_DEBUG(dbgs() << "Visiting " << printMBBReference(*MBB) << "\n")do { } while (false);
  MBBMRT *NewMBB = new MBBMRT(MBB);
  MachineRegion *Region = RegionInfo->getRegionFor(MBB);

  // Ensure we have the MRT region
  if (RegionMap.count(Region) == 0) {
    RegionMRT *NewMRTRegion = new RegionMRT(Region);
    RegionMap[Region] = NewMRTRegion;

    // Ensure all parents are in the RegionMap
    MachineRegion *Parent = Region->getParent();
    while (RegionMap.count(Parent) == 0) {
      RegionMRT *NewMRTParent = new RegionMRT(Parent);
      NewMRTParent->addChild(NewMRTRegion);
      NewMRTRegion->setParent(NewMRTParent);
      RegionMap[Parent] = NewMRTParent;
      NewMRTRegion = NewMRTParent;
      Parent = Parent->getParent();
    }
    RegionMap[Parent]->addChild(NewMRTRegion);
    NewMRTRegion->setParent(RegionMap[Parent]);
  }

  // Add MBB to Region MRT
  RegionMap[Region]->addChild(NewMBB);
  NewMBB->setParent(RegionMap[Region]);
  RegionMap[Region]->setSucc(Region->getExit());
}
return Result;
672}

674void LinearizedRegion::storeLiveOutReg(MachineBasicBlock *MBB, Register Reg,
                                     MachineInstr *DefInstr,
                                     const MachineRegisterInfo *MRI,
                                     const TargetRegisterInfo *TRI,
                                     PHILinearize &PHIInfo) {
if (Reg.isVirtual()) {
  LLVM_DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI)do { } while (false)
                    << "\n")do { } while (false);
  // If this is a source register to a PHI we are chaining, it
  // must be live out.
  if (PHIInfo.isSource(Reg)) {
    LLVM_DEBUG(dbgs() << "Add LiveOut (PHI): " << printReg(Reg, TRI) << "\n")do { } while (false);
    addLiveOut(Reg);
  } else {
    // If this is live out of the MBB
    for (auto &UI : MRI->use_operands(Reg)) {
      if (UI.getParent()->getParent() != MBB) {
        LLVM_DEBUG(dbgs() << "Add LiveOut (MBB " << printMBBReference(*MBB)do { } while (false)
                          << "): " << printReg(Reg, TRI) << "\n")do { } while (false);
        addLiveOut(Reg);
      } else {
        // If the use is in the same MBB we have to make sure
        // it is after the def, otherwise it is live out in a loop
        MachineInstr *UseInstr = UI.getParent();
        for (MachineBasicBlock::instr_iterator
                 MII = UseInstr->getIterator(),
                 MIE = UseInstr->getParent()->instr_end();
             MII != MIE; ++MII) {
          if ((&(*MII)) == DefInstr) {
            LLVM_DEBUG(dbgs() << "Add LiveOut (Loop): " << printReg(Reg, TRI)do { } while (false)
                              << "\n")do { } while (false);
            addLiveOut(Reg);
          }
        }
      }
    }
  }
}
712}

714void LinearizedRegion::storeLiveOutRegRegion(RegionMRT *Region, Register Reg,
                                           MachineInstr *DefInstr,
                                           const MachineRegisterInfo *MRI,
                                           const TargetRegisterInfo *TRI,
                                           PHILinearize &PHIInfo) {
if (Reg.isVirtual()) {
  LLVM_DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI)do { } while (false)
                    << "\n")do { } while (false);
  for (auto &UI : MRI->use_operands(Reg)) {
    if (!Region->contains(UI.getParent()->getParent())) {
      LLVM_DEBUG(dbgs() << "Add LiveOut (Region " << (void *)Regiondo { } while (false)
                        << "): " << printReg(Reg, TRI) << "\n")do { } while (false);
      addLiveOut(Reg);
    }
  }
}
730}

732void LinearizedRegion::storeLiveOuts(MachineBasicBlock *MBB,
                                   const MachineRegisterInfo *MRI,
                                   const TargetRegisterInfo *TRI,
                                   PHILinearize &PHIInfo) {
LLVM_DEBUG(dbgs() << "-Store Live Outs Begin (" << printMBBReference(*MBB)do { } while (false)
                  << ")-\n")do { } while (false);
for (auto &II : *MBB) {
  for (auto &RI : II.defs()) {
    storeLiveOutReg(MBB, RI.getReg(), RI.getParent(), MRI, TRI, PHIInfo);
  }
  for (auto &IRI : II.implicit_operands()) {
    if (IRI.isDef()) {
      storeLiveOutReg(MBB, IRI.getReg(), IRI.getParent(), MRI, TRI, PHIInfo);
    }
  }
}

// If we have a successor with a PHI, source coming from this MBB we have to
// add the register as live out
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
                                      E = MBB->succ_end();
     SI != E; ++SI) {
  for (auto &II : *(*SI)) {
    if (II.isPHI()) {
      MachineInstr &PHI = II;
      int numPreds = getPHINumInputs(PHI);
      for (int i = 0; i < numPreds; ++i) {
        if (getPHIPred(PHI, i) == MBB) {
          unsigned PHIReg = getPHISourceReg(PHI, i);
          LLVM_DEBUG(dbgs()do { } while (false)
                     << "Add LiveOut (PhiSource " << printMBBReference(*MBB)do { } while (false)
                     << " -> " << printMBBReference(*(*SI))do { } while (false)
                     << "): " << printReg(PHIReg, TRI) << "\n")do { } while (false);
          addLiveOut(PHIReg);
        }
      }
    }
  }
}

LLVM_DEBUG(dbgs() << "-Store Live Outs Endn-\n")do { } while (false);
773}

775void LinearizedRegion::storeMBBLiveOuts(MachineBasicBlock *MBB,
                                      const MachineRegisterInfo *MRI,
                                      const TargetRegisterInfo *TRI,
                                      PHILinearize &PHIInfo,
                                      RegionMRT *TopRegion) {
for (auto &II : *MBB) {
  for (auto &RI : II.defs()) {
    storeLiveOutRegRegion(TopRegion, RI.getReg(), RI.getParent(), MRI, TRI,
                          PHIInfo);
  }
  for (auto &IRI : II.implicit_operands()) {
    if (IRI.isDef()) {
      storeLiveOutRegRegion(TopRegion, IRI.getReg(), IRI.getParent(), MRI,
                            TRI, PHIInfo);
    }
  }
}
792}

794void LinearizedRegion::storeLiveOuts(RegionMRT *Region,
                                   const MachineRegisterInfo *MRI,
                                   const TargetRegisterInfo *TRI,
                                   PHILinearize &PHIInfo,
                                   RegionMRT *CurrentTopRegion) {
MachineBasicBlock *Exit = Region->getSucc();

RegionMRT *TopRegion =
    CurrentTopRegion == nullptr ? Region : CurrentTopRegion;

// Check if exit is end of function, if so, no live outs.
if (Exit == nullptr)
  return;

auto Children = Region->getChildren();
for (auto CI : *Children) {
  if (CI->isMBB()) {
    auto MBB = CI->getMBBMRT()->getMBB();
    storeMBBLiveOuts(MBB, MRI, TRI, PHIInfo, TopRegion);
  } else {
    LinearizedRegion *SubRegion = CI->getRegionMRT()->getLinearizedRegion();
    // We should be limited to only store registers that are live out from the
    // lineaized region
    for (auto MBBI : SubRegion->MBBs) {
      storeMBBLiveOuts(MBBI, MRI, TRI, PHIInfo, TopRegion);
    }
  }
}

if (CurrentTopRegion == nullptr) {
  auto Succ = Region->getSucc();
  for (auto &II : *Succ) {
    if (II.isPHI()) {
      MachineInstr &PHI = II;
      int numPreds = getPHINumInputs(PHI);
      for (int i = 0; i < numPreds; ++i) {
        if (Region->contains(getPHIPred(PHI, i))) {
          unsigned PHIReg = getPHISourceReg(PHI, i);
          LLVM_DEBUG(dbgs() << "Add Region LiveOut (" << (void *)Regiondo { } while (false)
                            << "): " << printReg(PHIReg, TRI) << "\n")do { } while (false);
          addLiveOut(PHIReg);
        }
      }
    }
  }
}
840}

842#ifndef NDEBUG1
843void LinearizedRegion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
OS << "Linearized Region {";
bool IsFirst = true;
for (auto MBB : MBBs) {
  if (IsFirst) {
    IsFirst = false;
  } else {
    OS << " ,";
  }
  OS << MBB->getNumber();
}
OS << "} (" << Entry->getNumber() << ", "
   << (Exit == nullptr ? -1 : Exit->getNumber())
   << "): In:" << printReg(getBBSelectRegIn(), TRI)
   << " Out:" << printReg(getBBSelectRegOut(), TRI) << " {";
for (auto &LI : LiveOuts) {
  OS << printReg(LI, TRI) << " ";
}
OS << "} \n";
862}
863#endif

865unsigned LinearizedRegion::getBBSelectRegIn() {
return getRegionMRT()->getBBSelectRegIn();
867}

869unsigned LinearizedRegion::getBBSelectRegOut() {
return getRegionMRT()->getBBSelectRegOut();
871}

873void LinearizedRegion::setHasLoop(bool Value) { HasLoop = Value; }

875bool LinearizedRegion::getHasLoop() { return HasLoop; }

877void LinearizedRegion::addLiveOut(unsigned VReg) { LiveOuts.insert(VReg); }

879void LinearizedRegion::removeLiveOut(unsigned Reg) {
if (isLiveOut(Reg))
  LiveOuts.erase(Reg);
882}

884void LinearizedRegion::replaceLiveOut(unsigned OldReg, unsigned NewReg) {
if (isLiveOut(OldReg)) {
  removeLiveOut(OldReg);
  addLiveOut(NewReg);
}
889}

891void LinearizedRegion::replaceRegister(unsigned Register,
                                     class Register NewRegister,
                                     MachineRegisterInfo *MRI,
                                     bool ReplaceInside, bool ReplaceOutside,
                                     bool IncludeLoopPHI) {
assert(Register != NewRegister && "Cannot replace a reg with itself")(static_cast<void> (0));

LLVM_DEBUG(do { } while (false)
    dbgs() << "Pepareing to replace register (region): "do { } while (false)
           << printReg(Register, MRI->getTargetRegisterInfo()) << " with "do { } while (false)
           << printReg(NewRegister, MRI->getTargetRegisterInfo()) << "\n")do { } while (false);

// If we are replacing outside, we also need to update the LiveOuts
if (ReplaceOutside &&
    (isLiveOut(Register) || this->getParent()->isLiveOut(Register))) {
  LinearizedRegion *Current = this;
  while (Current != nullptr && Current->getEntry() != nullptr) {
    LLVM_DEBUG(dbgs() << "Region before register replace\n")do { } while (false);
    LLVM_DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()))do { } while (false);
    Current->replaceLiveOut(Register, NewRegister);
    LLVM_DEBUG(dbgs() << "Region after register replace\n")do { } while (false);
    LLVM_DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()))do { } while (false);
    Current = Current->getParent();
  }
}

for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
                                       E = MRI->reg_end();
     I != E;) {
  MachineOperand &O = *I;
  ++I;

  // We don't rewrite defs.
  if (O.isDef())
    continue;

  bool IsInside = contains(O.getParent()->getParent());
  bool IsLoopPHI = IsInside && (O.getParent()->isPHI() &&
                                O.getParent()->getParent() == getEntry());
  bool ShouldReplace = (IsInside && ReplaceInside) ||
                       (!IsInside && ReplaceOutside) ||
                       (IncludeLoopPHI && IsLoopPHI);
  if (ShouldReplace) {

    if (NewRegister.isPhysical()) {
      LLVM_DEBUG(dbgs() << "Trying to substitute physical register: "do { } while (false)
                        << printReg(NewRegister, MRI->getTargetRegisterInfo())do { } while (false)
                        << "\n")do { } while (false);
      llvm_unreachable("Cannot substitute physical registers")__builtin_unreachable();
    } else {
      LLVM_DEBUG(dbgs() << "Replacing register (region): "do { } while (false)
                        << printReg(Register, MRI->getTargetRegisterInfo())do { } while (false)
                        << " with "do { } while (false)
                        << printReg(NewRegister, MRI->getTargetRegisterInfo())do { } while (false)
                        << "\n")do { } while (false);
      O.setReg(NewRegister);
    }
  }
}
950}

952void LinearizedRegion::replaceRegisterInsideRegion(unsigned Register,
                                                 unsigned NewRegister,
                                                 bool IncludeLoopPHIs,
                                                 MachineRegisterInfo *MRI) {
replaceRegister(Register, NewRegister, MRI, true, false, IncludeLoopPHIs);
957}

959void LinearizedRegion::replaceRegisterOutsideRegion(unsigned Register,
                                                  unsigned NewRegister,
                                                  bool IncludeLoopPHIs,
                                                  MachineRegisterInfo *MRI) {
replaceRegister(Register, NewRegister, MRI, false, true, IncludeLoopPHIs);
964}

966DenseSet<unsigned> *LinearizedRegion::getLiveOuts() { return &LiveOuts; }

968void LinearizedRegion::setEntry(MachineBasicBlock *NewEntry) {
Entry = NewEntry;
970}

972MachineBasicBlock *LinearizedRegion::getEntry() { return Entry; }

974void LinearizedRegion::setExit(MachineBasicBlock *NewExit) { Exit = NewExit; }

976MachineBasicBlock *LinearizedRegion::getExit() { return Exit; }

978void LinearizedRegion::addMBB(MachineBasicBlock *MBB) { MBBs.insert(MBB); }

980void LinearizedRegion::addMBBs(LinearizedRegion *InnerRegion) {
for (auto MBB : InnerRegion->MBBs) {
  addMBB(MBB);
}
984}

986bool LinearizedRegion::contains(MachineBasicBlock *MBB) {
return MBBs.contains(MBB);
988}

990bool LinearizedRegion::isLiveOut(unsigned Reg) {
return LiveOuts.contains(Reg);
992}

994bool LinearizedRegion::hasNoDef(unsigned Reg, MachineRegisterInfo *MRI) {
return MRI->def_begin(Reg) == MRI->def_end();
996}

998// After the code has been structurized, what was flagged as kills
999// before are no longer register kills.
1000void LinearizedRegion::removeFalseRegisterKills(MachineRegisterInfo *MRI) {
const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
(void)TRI; // It's used by LLVM_DEBUG.

for (auto MBBI : MBBs) {
  MachineBasicBlock *MBB = MBBI;
  for (auto &II : *MBB) {
    for (auto &RI : II.uses()) {
      if (RI.isReg()) {
        Register Reg = RI.getReg();
        if (Reg.isVirtual()) {
          if (hasNoDef(Reg, MRI))
            continue;
          if (!MRI->hasOneDef(Reg)) {
            LLVM_DEBUG(this->getEntry()->getParent()->dump())do { } while (false);
            LLVM_DEBUG(dbgs() << printReg(Reg, TRI) << "\n")do { } while (false);
          }

          if (MRI->def_begin(Reg) == MRI->def_end()) {
            LLVM_DEBUG(dbgs() << "Register "do { } while (false)
                              << printReg(Reg, MRI->getTargetRegisterInfo())do { } while (false)
                              << " has NO defs\n")do { } while (false);
          } else if (!MRI->hasOneDef(Reg)) {
            LLVM_DEBUG(dbgs() << "Register "do { } while (false)
                              << printReg(Reg, MRI->getTargetRegisterInfo())do { } while (false)
                              << " has multiple defs\n")do { } while (false);
          }

          assert(MRI->hasOneDef(Reg) && "Register has multiple definitions")(static_cast<void> (0));
          MachineOperand *Def = &(*(MRI->def_begin(Reg)));
          MachineOperand *UseOperand = &(RI);
          bool UseIsOutsideDefMBB = Def->getParent()->getParent() != MBB;
          if (UseIsOutsideDefMBB && UseOperand->isKill()) {
            LLVM_DEBUG(dbgs() << "Removing kill flag on register: "do { } while (false)
                              << printReg(Reg, TRI) << "\n")do { } while (false);
            UseOperand->setIsKill(false);
          }
        }
      }
    }
  }
}
1042}

1044void LinearizedRegion::initLiveOut(RegionMRT *Region,
                                 const MachineRegisterInfo *MRI,
                                 const TargetRegisterInfo *TRI,
                                 PHILinearize &PHIInfo) {
storeLiveOuts(Region, MRI, TRI, PHIInfo);
1049}

1051LinearizedRegion::LinearizedRegion(MachineBasicBlock *MBB,
                                 const MachineRegisterInfo *MRI,
                                 const TargetRegisterInfo *TRI,
                                 PHILinearize &PHIInfo) {
setEntry(MBB);
setExit(MBB);
storeLiveOuts(MBB, MRI, TRI, PHIInfo);
MBBs.insert(MBB);
Parent = nullptr;
1060}

1062LinearizedRegion::LinearizedRegion() {
setEntry(nullptr);
setExit(nullptr);
Parent = nullptr;
1066}

1068namespace {

1070class AMDGPUMachineCFGStructurizer : public MachineFunctionPass {
1071private:
const MachineRegionInfo *Regions;
const SIInstrInfo *TII;
const TargetRegisterInfo *TRI;
MachineRegisterInfo *MRI;
unsigned BBSelectRegister;
PHILinearize PHIInfo;
DenseMap<MachineBasicBlock *, MachineBasicBlock *> FallthroughMap;
RegionMRT *RMRT;

void getPHIRegionIndices(RegionMRT *Region, MachineInstr &PHI,
                         SmallVector<unsigned, 2> &RegionIndices);
void getPHIRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
                         SmallVector<unsigned, 2> &RegionIndices);
void getPHINonRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
                            SmallVector<unsigned, 2> &PHINonRegionIndices);

void storePHILinearizationInfoDest(
    unsigned LDestReg, MachineInstr &PHI,
    SmallVector<unsigned, 2> *RegionIndices = nullptr);

unsigned storePHILinearizationInfo(MachineInstr &PHI,
                                   SmallVector<unsigned, 2> *RegionIndices);

void extractKilledPHIs(MachineBasicBlock *MBB);

bool shrinkPHI(MachineInstr &PHI, SmallVector<unsigned, 2> &PHIIndices,
               unsigned *ReplaceReg);

bool shrinkPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
               MachineBasicBlock *SourceMBB,
               SmallVector<unsigned, 2> &PHIIndices, unsigned *ReplaceReg);

void replacePHI(MachineInstr &PHI, unsigned CombinedSourceReg,
                MachineBasicBlock *LastMerge,
                SmallVector<unsigned, 2> &PHIRegionIndices);
void replaceEntryPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
                     MachineBasicBlock *IfMBB,
                     SmallVector<unsigned, 2> &PHIRegionIndices);
void replaceLiveOutRegs(MachineInstr &PHI,
                        SmallVector<unsigned, 2> &PHIRegionIndices,
                        unsigned CombinedSourceReg,
                        LinearizedRegion *LRegion);
void rewriteRegionExitPHI(RegionMRT *Region, MachineBasicBlock *LastMerge,
                          MachineInstr &PHI, LinearizedRegion *LRegion);

void rewriteRegionExitPHIs(RegionMRT *Region, MachineBasicBlock *LastMerge,
                           LinearizedRegion *LRegion);
void rewriteRegionEntryPHI(LinearizedRegion *Region, MachineBasicBlock *IfMBB,
                           MachineInstr &PHI);
void rewriteRegionEntryPHIs(LinearizedRegion *Region,
                            MachineBasicBlock *IfMBB);

bool regionIsSimpleIf(RegionMRT *Region);

void transformSimpleIfRegion(RegionMRT *Region);

void eliminateDeadBranchOperands(MachineBasicBlock::instr_iterator &II);

void insertUnconditionalBranch(MachineBasicBlock *MBB,
                               MachineBasicBlock *Dest,
                               const DebugLoc &DL = DebugLoc());

MachineBasicBlock *createLinearizedExitBlock(RegionMRT *Region);

void insertMergePHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
                    MachineBasicBlock *MergeBB, unsigned DestRegister,
                    unsigned IfSourceRegister, unsigned CodeSourceRegister,
                    bool IsUndefIfSource = false);

MachineBasicBlock *createIfBlock(MachineBasicBlock *MergeBB,
                                 MachineBasicBlock *CodeBBStart,
                                 MachineBasicBlock *CodeBBEnd,
                                 MachineBasicBlock *SelectBB, unsigned IfReg,
                                 bool InheritPreds);

void prunePHIInfo(MachineBasicBlock *MBB);
void createEntryPHI(LinearizedRegion *CurrentRegion, unsigned DestReg);

void createEntryPHIs(LinearizedRegion *CurrentRegion);
void resolvePHIInfos(MachineBasicBlock *FunctionEntry);

void replaceRegisterWith(unsigned Register, class Register NewRegister);

MachineBasicBlock *createIfRegion(MachineBasicBlock *MergeBB,
                                  MachineBasicBlock *CodeBB,
                                  LinearizedRegion *LRegion,
                                  unsigned BBSelectRegIn,
                                  unsigned BBSelectRegOut);

MachineBasicBlock *
createIfRegion(MachineBasicBlock *MergeMBB, LinearizedRegion *InnerRegion,
               LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
               unsigned BBSelectRegIn, unsigned BBSelectRegOut);
void ensureCondIsNotKilled(SmallVector<MachineOperand, 1> Cond);

void rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
                             MachineBasicBlock *MergeBB,
                             unsigned BBSelectReg);

MachineInstr *getDefInstr(unsigned Reg);
void insertChainedPHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
                      MachineBasicBlock *MergeBB,
                      LinearizedRegion *InnerRegion, unsigned DestReg,
                      unsigned SourceReg);
bool containsDef(MachineBasicBlock *MBB, LinearizedRegion *InnerRegion,
                 unsigned Register);
void rewriteLiveOutRegs(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
                        MachineBasicBlock *MergeBB,
                        LinearizedRegion *InnerRegion,
                        LinearizedRegion *LRegion);

void splitLoopPHI(MachineInstr &PHI, MachineBasicBlock *Entry,
                  MachineBasicBlock *EntrySucc, LinearizedRegion *LRegion);
void splitLoopPHIs(MachineBasicBlock *Entry, MachineBasicBlock *EntrySucc,
                   LinearizedRegion *LRegion);

MachineBasicBlock *splitExit(LinearizedRegion *LRegion);

MachineBasicBlock *splitEntry(LinearizedRegion *LRegion);

LinearizedRegion *initLinearizedRegion(RegionMRT *Region);

bool structurizeComplexRegion(RegionMRT *Region);

bool structurizeRegion(RegionMRT *Region);

bool structurizeRegions(RegionMRT *Region, bool isTopRegion);

1200public:
static char ID;

AMDGPUMachineCFGStructurizer() : MachineFunctionPass(ID) {
  initializeAMDGPUMachineCFGStructurizerPass(*PassRegistry::getPassRegistry());
}

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.addRequired<MachineRegionInfoPass>();
  MachineFunctionPass::getAnalysisUsage(AU);
}

void initFallthroughMap(MachineFunction &MF);

void createLinearizedRegion(RegionMRT *Region, unsigned SelectOut);

unsigned initializeSelectRegisters(MRT *MRT, unsigned ExistingExitReg,
                                   MachineRegisterInfo *MRI,
                                   const SIInstrInfo *TII);

void setRegionMRT(RegionMRT *RegionTree) { RMRT = RegionTree; }

RegionMRT *getRegionMRT() { return RMRT; }

bool runOnMachineFunction(MachineFunction &MF) override;
1225};

1227} // end anonymous namespace

1229char AMDGPUMachineCFGStructurizer::ID = 0;

1231bool AMDGPUMachineCFGStructurizer::regionIsSimpleIf(RegionMRT *Region) {
MachineBasicBlock *Entry = Region->getEntry();
MachineBasicBlock *Succ = Region->getSucc();
bool FoundBypass = false;
bool FoundIf = false;

if (Entry->succ_size() != 2) {
  return false;
}

for (MachineBasicBlock::const_succ_iterator SI = Entry->succ_begin(),
                                            E = Entry->succ_end();
     SI != E; ++SI) {
  MachineBasicBlock *Current = *SI;

  if (Current == Succ) {
    FoundBypass = true;
  } else if ((Current->succ_size() == 1) &&
             *(Current->succ_begin()) == Succ) {
    FoundIf = true;
  }
}

return FoundIf && FoundBypass;
1255}

1257void AMDGPUMachineCFGStructurizer::transformSimpleIfRegion(RegionMRT *Region) {
MachineBasicBlock *Entry = Region->getEntry();
MachineBasicBlock *Exit = Region->getExit();
TII->convertNonUniformIfRegion(Entry, Exit);
1261}

1263static void fixMBBTerminator(MachineBasicBlock *MBB) {
if (MBB->succ_size() == 1) {
  auto *Succ = *(MBB->succ_begin());
  for (auto &TI : MBB->terminators()) {
    for (auto &UI : TI.uses()) {
      if (UI.isMBB() && UI.getMBB() != Succ) {
        UI.setMBB(Succ);
      }
    }
  }
}
1274}

1276static void fixRegionTerminator(RegionMRT *Region) {
MachineBasicBlock *InternalSucc = nullptr;
MachineBasicBlock *ExternalSucc = nullptr;
LinearizedRegion *LRegion = Region->getLinearizedRegion();
auto Exit = LRegion->getExit();

SmallPtrSet<MachineBasicBlock *, 2> Successors;
for (MachineBasicBlock::const_succ_iterator SI = Exit->succ_begin(),
                                            SE = Exit->succ_end();
     SI != SE; ++SI) {
  MachineBasicBlock *Succ = *SI;
  if (LRegion->contains(Succ)) {
    // Do not allow re-assign
    assert(InternalSucc == nullptr)(static_cast<void> (0));
    InternalSucc = Succ;
  } else {
    // Do not allow re-assign
    assert(ExternalSucc == nullptr)(static_cast<void> (0));
    ExternalSucc = Succ;
  }
}

for (auto &TI : Exit->terminators()) {
  for (auto &UI : TI.uses()) {
    if (UI.isMBB()) {
      auto Target = UI.getMBB();
      if (Target != InternalSucc && Target != ExternalSucc) {
        UI.setMBB(ExternalSucc);
      }
    }
  }
}
1308}

1310// If a region region is just a sequence of regions (and the exit
1311// block in the case of the top level region), we can simply skip
1312// linearizing it, because it is already linear
1313bool regionIsSequence(RegionMRT *Region) {
auto Children = Region->getChildren();
for (auto CI : *Children) {
  if (!CI->isRegion()) {
    if (CI->getMBBMRT()->getMBB()->succ_size() > 1) {
      return false;
    }
  }
}
return true;
1323}

1325void fixupRegionExits(RegionMRT *Region) {
auto Children = Region->getChildren();
for (auto CI : *Children) {
  if (!CI->isRegion()) {
    fixMBBTerminator(CI->getMBBMRT()->getMBB());
  } else {
    fixRegionTerminator(CI->getRegionMRT());
  }
}
1334}

1336void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
  RegionMRT *Region, MachineInstr &PHI,
  SmallVector<unsigned, 2> &PHIRegionIndices) {
unsigned NumInputs = getPHINumInputs(PHI);
for (unsigned i = 0; i < NumInputs; ++i) {
  MachineBasicBlock *Pred = getPHIPred(PHI, i);
  if (Region->contains(Pred)) {
    PHIRegionIndices.push_back(i);
  }
}
1346}

1348void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
  LinearizedRegion *Region, MachineInstr &PHI,
  SmallVector<unsigned, 2> &PHIRegionIndices) {
unsigned NumInputs = getPHINumInputs(PHI);
for (unsigned i = 0; i < NumInputs; ++i) {
  MachineBasicBlock *Pred = getPHIPred(PHI, i);
  if (Region->contains(Pred)) {
    PHIRegionIndices.push_back(i);
  }
}
1358}

1360void AMDGPUMachineCFGStructurizer::getPHINonRegionIndices(
  LinearizedRegion *Region, MachineInstr &PHI,
  SmallVector<unsigned, 2> &PHINonRegionIndices) {
unsigned NumInputs = getPHINumInputs(PHI);
for (unsigned i = 0; i < NumInputs; ++i) {
  MachineBasicBlock *Pred = getPHIPred(PHI, i);
  if (!Region->contains(Pred)) {
    PHINonRegionIndices.push_back(i);
  }
}
1370}

1372void AMDGPUMachineCFGStructurizer::storePHILinearizationInfoDest(
  unsigned LDestReg, MachineInstr &PHI,
  SmallVector<unsigned, 2> *RegionIndices) {
if (RegionIndices) {
  for (auto i : *RegionIndices) {
    PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
  }
} else {
  unsigned NumInputs = getPHINumInputs(PHI);
  for (unsigned i = 0; i < NumInputs; ++i) {
    PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
  }
}
1385}

1387unsigned AMDGPUMachineCFGStructurizer::storePHILinearizationInfo(
  MachineInstr &PHI, SmallVector<unsigned, 2> *RegionIndices) {
unsigned DestReg = getPHIDestReg(PHI);
Register LinearizeDestReg =
    MRI->createVirtualRegister(MRI->getRegClass(DestReg));
PHIInfo.addDest(LinearizeDestReg, PHI.getDebugLoc());
storePHILinearizationInfoDest(LinearizeDestReg, PHI, RegionIndices);
return LinearizeDestReg;
1395}

1397void AMDGPUMachineCFGStructurizer::extractKilledPHIs(MachineBasicBlock *MBB) {
// We need to create a new chain for the killed phi, but there is no
// need to do the renaming outside or inside the block.
SmallPtrSet<MachineInstr *, 2> PHIs;
for (MachineBasicBlock::instr_iterator I = MBB->instr_begin(),
                                       E = MBB->instr_end();
     I != E; ++I) {
  MachineInstr &Instr = *I;
  if (Instr.isPHI()) {
    unsigned PHIDestReg = getPHIDestReg(Instr);
    LLVM_DEBUG(dbgs() << "Extractking killed phi:\n")do { } while (false);
    LLVM_DEBUG(Instr.dump())do { } while (false);
    PHIs.insert(&Instr);
    PHIInfo.addDest(PHIDestReg, Instr.getDebugLoc());
    storePHILinearizationInfoDest(PHIDestReg, Instr);
  }
}

for (auto PI : PHIs) {
  PI->eraseFromParent();
}
1418}

1420static bool isPHIRegionIndex(SmallVector<unsigned, 2> PHIRegionIndices,
                           unsigned Index) {
return llvm::is_contained(PHIRegionIndices, Index);
1423}

1425bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
                                     SmallVector<unsigned, 2> &PHIIndices,
                                     unsigned *ReplaceReg) {
return shrinkPHI(PHI, 0, nullptr, PHIIndices, ReplaceReg);
1429}

1431bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
                                     unsigned CombinedSourceReg,
                                     MachineBasicBlock *SourceMBB,
                                     SmallVector<unsigned, 2> &PHIIndices,
                                     unsigned *ReplaceReg) {
LLVM_DEBUG(dbgs() << "Shrink PHI: ")do { } while (false);
LLVM_DEBUG(PHI.dump())do { } while (false);
LLVM_DEBUG(dbgs() << " to " << printReg(getPHIDestReg(PHI), TRI)do { } while (false)
                  << " = PHI(")do { } while (false);

bool Replaced = false;
unsigned NumInputs = getPHINumInputs(PHI);
int SingleExternalEntryIndex = -1;
for (unsigned i = 0; i < NumInputs; ++i) {
  if (!isPHIRegionIndex(PHIIndices, i)) {
    if (SingleExternalEntryIndex == -1) {
      // Single entry
      SingleExternalEntryIndex = i;
    } else {
      // Multiple entries
      SingleExternalEntryIndex = -2;
    }
  }
}

if (SingleExternalEntryIndex > -1) {
  *ReplaceReg = getPHISourceReg(PHI, SingleExternalEntryIndex);
  // We should not rewrite the code, we should only pick up the single value
  // that represents the shrunk PHI.
  Replaced = true;
} else {
  MachineBasicBlock *MBB = PHI.getParent();
  MachineInstrBuilder MIB =
      BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
              getPHIDestReg(PHI));
  if (SourceMBB) {
    MIB.addReg(CombinedSourceReg);
    MIB.addMBB(SourceMBB);
    LLVM_DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "do { } while (false)
                      << printMBBReference(*SourceMBB))do { } while (false);
  }

  for (unsigned i = 0; i < NumInputs; ++i) {
    if (isPHIRegionIndex(PHIIndices, i)) {
      continue;
    }
    unsigned SourceReg = getPHISourceReg(PHI, i);
    MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    MIB.addReg(SourceReg);
    MIB.addMBB(SourcePred);
    LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "do { } while (false)
                      << printMBBReference(*SourcePred))do { } while (false);
  }
  LLVM_DEBUG(dbgs() << ")\n")do { } while (false);
}
PHI.eraseFromParent();
return Replaced;
1488}

1490void AMDGPUMachineCFGStructurizer::replacePHI(
  MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *LastMerge,
  SmallVector<unsigned, 2> &PHIRegionIndices) {
LLVM_DEBUG(dbgs() << "Replace PHI: ")do { } while (false);
LLVM_DEBUG(PHI.dump())do { } while (false);
LLVM_DEBUG(dbgs() << " with " << printReg(getPHIDestReg(PHI), TRI)do { } while (false)
                  << " = PHI(")do { } while (false);

bool HasExternalEdge = false;
unsigned NumInputs = getPHINumInputs(PHI);
for (unsigned i = 0; i < NumInputs; ++i) {
  if (!isPHIRegionIndex(PHIRegionIndices, i)) {
    HasExternalEdge = true;
  }
}

if (HasExternalEdge) {
  MachineBasicBlock *MBB = PHI.getParent();
  MachineInstrBuilder MIB =
      BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
              getPHIDestReg(PHI));
  MIB.addReg(CombinedSourceReg);
  MIB.addMBB(LastMerge);
  LLVM_DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "do { } while (false)
                    << printMBBReference(*LastMerge))do { } while (false);
  for (unsigned i = 0; i < NumInputs; ++i) {
    if (isPHIRegionIndex(PHIRegionIndices, i)) {
      continue;
    }
    unsigned SourceReg = getPHISourceReg(PHI, i);
    MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    MIB.addReg(SourceReg);
    MIB.addMBB(SourcePred);
    LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "do { } while (false)
                      << printMBBReference(*SourcePred))do { } while (false);
  }
  LLVM_DEBUG(dbgs() << ")\n")do { } while (false);
} else {
  replaceRegisterWith(getPHIDestReg(PHI), CombinedSourceReg);
}
PHI.eraseFromParent();
1531}

1533void AMDGPUMachineCFGStructurizer::replaceEntryPHI(
  MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *IfMBB,
  SmallVector<unsigned, 2> &PHIRegionIndices) {
LLVM_DEBUG(dbgs() << "Replace entry PHI: ")do { } while (false);
LLVM_DEBUG(PHI.dump())do { } while (false);
LLVM_DEBUG(dbgs() << " with ")do { } while (false);

unsigned NumInputs = getPHINumInputs(PHI);
unsigned NumNonRegionInputs = NumInputs;
for (unsigned i = 0; i < NumInputs; ++i) {
  if (isPHIRegionIndex(PHIRegionIndices, i)) {
    NumNonRegionInputs--;
  }
}

if (NumNonRegionInputs == 0) {
  auto DestReg = getPHIDestReg(PHI);
  replaceRegisterWith(DestReg, CombinedSourceReg);
  LLVM_DEBUG(dbgs() << " register " << printReg(CombinedSourceReg, TRI)do { } while (false)
                    << "\n")do { } while (false);
  PHI.eraseFromParent();
} else {
  LLVM_DEBUG(dbgs() << printReg(getPHIDestReg(PHI), TRI) << " = PHI(")do { } while (false);
  MachineBasicBlock *MBB = PHI.getParent();
  MachineInstrBuilder MIB =
      BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
              getPHIDestReg(PHI));
  MIB.addReg(CombinedSourceReg);
  MIB.addMBB(IfMBB);
  LLVM_DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "do { } while (false)
                    << printMBBReference(*IfMBB))do { } while (false);
  unsigned NumInputs = getPHINumInputs(PHI);
  for (unsigned i = 0; i < NumInputs; ++i) {
    if (isPHIRegionIndex(PHIRegionIndices, i)) {
      continue;
    }
    unsigned SourceReg = getPHISourceReg(PHI, i);
    MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    MIB.addReg(SourceReg);
    MIB.addMBB(SourcePred);
    LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "do { } while (false)
                      << printMBBReference(*SourcePred))do { } while (false);
  }
  LLVM_DEBUG(dbgs() << ")\n")do { } while (false);
  PHI.eraseFromParent();
}
1579}

1581void AMDGPUMachineCFGStructurizer::replaceLiveOutRegs(
  MachineInstr &PHI, SmallVector<unsigned, 2> &PHIRegionIndices,
  unsigned CombinedSourceReg, LinearizedRegion *LRegion) {
bool WasLiveOut = false;
for (auto PII : PHIRegionIndices) {
  unsigned Reg = getPHISourceReg(PHI, PII);
  if (LRegion->isLiveOut(Reg)) {
    bool IsDead = true;

    // Check if register is live out of the basic block
    MachineBasicBlock *DefMBB = getDefInstr(Reg)->getParent();
    for (auto UI = MRI->use_begin(Reg), E = MRI->use_end(); UI != E; ++UI) {
      if ((*UI).getParent()->getParent() != DefMBB) {
        IsDead = false;
      }
    }

    LLVM_DEBUG(dbgs() << "Register " << printReg(Reg, TRI) << " is "do { } while (false)
                      << (IsDead ? "dead" : "alive")do { } while (false)
                      << " after PHI replace\n")do { } while (false);
    if (IsDead) {
      LRegion->removeLiveOut(Reg);
    }
    WasLiveOut = true;
  }
}

if (WasLiveOut)
  LRegion->addLiveOut(CombinedSourceReg);
1610}

1612void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHI(RegionMRT *Region,
                                                MachineBasicBlock *LastMerge,
                                                MachineInstr &PHI,
                                                LinearizedRegion *LRegion) {
SmallVector<unsigned, 2> PHIRegionIndices;
getPHIRegionIndices(Region, PHI, PHIRegionIndices);
unsigned LinearizedSourceReg =
    storePHILinearizationInfo(PHI, &PHIRegionIndices);

replacePHI(PHI, LinearizedSourceReg, LastMerge, PHIRegionIndices);
replaceLiveOutRegs(PHI, PHIRegionIndices, LinearizedSourceReg, LRegion);
1623}

1625void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHI(LinearizedRegion *Region,
                                                 MachineBasicBlock *IfMBB,
                                                 MachineInstr &PHI) {
SmallVector<unsigned, 2> PHINonRegionIndices;
getPHINonRegionIndices(Region, PHI, PHINonRegionIndices);
unsigned LinearizedSourceReg =
    storePHILinearizationInfo(PHI, &PHINonRegionIndices);
replaceEntryPHI(PHI, LinearizedSourceReg, IfMBB, PHINonRegionIndices);
1633}

1635static void collectPHIs(MachineBasicBlock *MBB,
                      SmallVector<MachineInstr *, 2> &PHIs) {
for (auto &BBI : *MBB) {
  if (BBI.isPHI()) {
    PHIs.push_back(&BBI);
  }
}
1642}

1644void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHIs(RegionMRT *Region,
                                                 MachineBasicBlock *LastMerge,
                                                 LinearizedRegion *LRegion) {
SmallVector<MachineInstr *, 2> PHIs;
auto Exit = Region->getSucc();
if (Exit == nullptr)
13
←
Assuming the condition is false→
14
←
Taking false branch→
  return;

collectPHIs(Exit, PHIs);

for (auto PHII : PHIs) {
15
←
Assuming '__begin1' is equal to '__end1'→
  rewriteRegionExitPHI(Region, LastMerge, *PHII, LRegion);
}
1657}
16
←
Returning without writing to 'LRegion->HasLoop', which participates in a condition later→

1659void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHIs(LinearizedRegion *Region,
                                                  MachineBasicBlock *IfMBB) {
SmallVector<MachineInstr *, 2> PHIs;
auto Entry = Region->getEntry();

collectPHIs(Entry, PHIs);

for (auto PHII : PHIs) {
  rewriteRegionEntryPHI(Region, IfMBB, *PHII);
}
1669}

1671void AMDGPUMachineCFGStructurizer::insertUnconditionalBranch(MachineBasicBlock *MBB,
                                                     MachineBasicBlock *Dest,
                                                     const DebugLoc &DL) {
LLVM_DEBUG(dbgs() << "Inserting unconditional branch: " << MBB->getNumber()do { } while (false)
                  << " -> " << Dest->getNumber() << "\n")do { } while (false);
MachineBasicBlock::instr_iterator Terminator = MBB->getFirstInstrTerminator();
bool HasTerminator = Terminator != MBB->instr_end();
if (HasTerminator) {
  TII->ReplaceTailWithBranchTo(Terminator, Dest);
}
if (++MachineFunction::iterator(MBB) != MachineFunction::iterator(Dest)) {
  TII->insertUnconditionalBranch(*MBB, Dest, DL);
}
1684}

1686static MachineBasicBlock *getSingleExitNode(MachineFunction &MF) {
MachineBasicBlock *result = nullptr;
for (auto &MFI : MF) {
  if (MFI.succ_size() == 0) {
    if (result == nullptr) {
      result = &MFI;
    } else {
      return nullptr;
    }
  }
}

return result;
1699}

1701static bool hasOneExitNode(MachineFunction &MF) {
return getSingleExitNode(MF) != nullptr;
1703}

1705MachineBasicBlock *
1706AMDGPUMachineCFGStructurizer::createLinearizedExitBlock(RegionMRT *Region) {
auto Exit = Region->getSucc();

// If the exit is the end of the function, we just use the existing
MachineFunction *MF = Region->getEntry()->getParent();
if (Exit == nullptr && hasOneExitNode(*MF)) {
  return &(*(--(Region->getEntry()->getParent()->end())));
}

MachineBasicBlock *LastMerge = MF->CreateMachineBasicBlock();
if (Exit == nullptr) {
  MachineFunction::iterator ExitIter = MF->end();
  MF->insert(ExitIter, LastMerge);
} else {
  MachineFunction::iterator ExitIter = Exit->getIterator();
  MF->insert(ExitIter, LastMerge);
  LastMerge->addSuccessor(Exit);
  insertUnconditionalBranch(LastMerge, Exit);
  LLVM_DEBUG(dbgs() << "Created exit block: " << LastMerge->getNumber()do { } while (false)
                    << "\n")do { } while (false);
}
return LastMerge;
1728}

1730void AMDGPUMachineCFGStructurizer::insertMergePHI(MachineBasicBlock *IfBB,
                                          MachineBasicBlock *CodeBB,
                                          MachineBasicBlock *MergeBB,
                                          unsigned DestRegister,
                                          unsigned IfSourceRegister,
                                          unsigned CodeSourceRegister,
                                          bool IsUndefIfSource) {
// If this is the function exit block, we don't need a phi.
if (MergeBB->succ_begin() == MergeBB->succ_end()) {
  return;
}
LLVM_DEBUG(dbgs() << "Merge PHI (" << printMBBReference(*MergeBB)do { } while (false)
                  << "): " << printReg(DestRegister, TRI) << " = PHI("do { } while (false)
                  << printReg(IfSourceRegister, TRI) << ", "do { } while (false)
                  << printMBBReference(*IfBB)do { } while (false)
                  << printReg(CodeSourceRegister, TRI) << ", "do { } while (false)
                  << printMBBReference(*CodeBB) << ")\n")do { } while (false);
const DebugLoc &DL = MergeBB->findDebugLoc(MergeBB->begin());
MachineInstrBuilder MIB = BuildMI(*MergeBB, MergeBB->instr_begin(), DL,
                                  TII->get(TargetOpcode::PHI), DestRegister);
if (IsUndefIfSource && false) {
  MIB.addReg(IfSourceRegister, RegState::Undef);
} else {
  MIB.addReg(IfSourceRegister);
}
MIB.addMBB(IfBB);
MIB.addReg(CodeSourceRegister);
MIB.addMBB(CodeBB);
1758}

1760static void removeExternalCFGSuccessors(MachineBasicBlock *MBB) {
for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(),
                                      E = MBB->succ_end();
     PI != E; ++PI) {
  if ((*PI) != MBB) {
    (MBB)->removeSuccessor(*PI);
  }
}
1768}

1770static void removeExternalCFGEdges(MachineBasicBlock *StartMBB,
                                 MachineBasicBlock *EndMBB) {

// We have to check against the StartMBB successor becasuse a
// structurized region with a loop will have the entry block split,
// and the backedge will go to the entry successor.
DenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>> Succs;
unsigned SuccSize = StartMBB->succ_size();
if (SuccSize > 0) {
  MachineBasicBlock *StartMBBSucc = *(StartMBB->succ_begin());
  for (MachineBasicBlock::succ_iterator PI = EndMBB->succ_begin(),
                                        E = EndMBB->succ_end();
       PI != E; ++PI) {
    // Either we have a back-edge to the entry block, or a back-edge to the
    // successor of the entry block since the block may be split.
    if ((*PI) != StartMBB &&
        !((*PI) == StartMBBSucc && StartMBB != EndMBB && SuccSize == 1)) {
      Succs.insert(
          std::pair<MachineBasicBlock *, MachineBasicBlock *>(EndMBB, *PI));
    }
  }
}

for (MachineBasicBlock::pred_iterator PI = StartMBB->pred_begin(),
                                      E = StartMBB->pred_end();
     PI != E; ++PI) {
  if ((*PI) != EndMBB) {
    Succs.insert(
        std::pair<MachineBasicBlock *, MachineBasicBlock *>(*PI, StartMBB));
  }
}

for (auto SI : Succs) {
  std::pair<MachineBasicBlock *, MachineBasicBlock *> Edge = SI;
  LLVM_DEBUG(dbgs() << "Removing edge: " << printMBBReference(*Edge.first)do { } while (false)
                    << " -> " << printMBBReference(*Edge.second) << "\n")do { } while (false);
  Edge.first->removeSuccessor(Edge.second);
}
1808}

1810MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfBlock(
  MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBBStart,
  MachineBasicBlock *CodeBBEnd, MachineBasicBlock *SelectBB, unsigned IfReg,
  bool InheritPreds) {
MachineFunction *MF = MergeBB->getParent();
MachineBasicBlock *IfBB = MF->CreateMachineBasicBlock();

if (InheritPreds) {
  for (MachineBasicBlock::pred_iterator PI = CodeBBStart->pred_begin(),
                                        E = CodeBBStart->pred_end();
       PI != E; ++PI) {
    if ((*PI) != CodeBBEnd) {
      MachineBasicBlock *Pred = (*PI);
      Pred->addSuccessor(IfBB);
    }
  }
}

removeExternalCFGEdges(CodeBBStart, CodeBBEnd);

auto CodeBBStartI = CodeBBStart->getIterator();
auto CodeBBEndI = CodeBBEnd->getIterator();
auto MergeIter = MergeBB->getIterator();
MF->insert(MergeIter, IfBB);
MF->splice(MergeIter, CodeBBStartI, ++CodeBBEndI);
IfBB->addSuccessor(MergeBB);
IfBB->addSuccessor(CodeBBStart);

LLVM_DEBUG(dbgs() << "Created If block: " << IfBB->getNumber() << "\n")do { } while (false);
// Ensure that the MergeBB is a successor of the CodeEndBB.
if (!CodeBBEnd->isSuccessor(MergeBB))
  CodeBBEnd->addSuccessor(MergeBB);

LLVM_DEBUG(dbgs() << "Moved " << printMBBReference(*CodeBBStart)do { } while (false)
                  << " through " << printMBBReference(*CodeBBEnd) << "\n")do { } while (false);

// If we have a single predecessor we can find a reasonable debug location
MachineBasicBlock *SinglePred =
    CodeBBStart->pred_size() == 1 ? *(CodeBBStart->pred_begin()) : nullptr;
const DebugLoc &DL = SinglePred
                  ? SinglePred->findDebugLoc(SinglePred->getFirstTerminator())
                  : DebugLoc();

Register Reg =
    TII->insertEQ(IfBB, IfBB->begin(), DL, IfReg,
                  SelectBB->getNumber() /* CodeBBStart->getNumber() */);
if (&(*(IfBB->getParent()->begin())) == IfBB) {
  TII->materializeImmediate(*IfBB, IfBB->begin(), DL, IfReg,
                            CodeBBStart->getNumber());
}
MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
ArrayRef<MachineOperand> Cond(RegOp);
TII->insertBranch(*IfBB, MergeBB, CodeBBStart, Cond, DL);

return IfBB;
1865}

1867void AMDGPUMachineCFGStructurizer::ensureCondIsNotKilled(
  SmallVector<MachineOperand, 1> Cond) {
if (Cond.size() != 1)
  return;
if (!Cond[0].isReg())
  return;

Register CondReg = Cond[0].getReg();
for (auto UI = MRI->use_begin(CondReg), E = MRI->use_end(); UI != E; ++UI) {
  (*UI).setIsKill(false);
}
1878}

1880void AMDGPUMachineCFGStructurizer::rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
                                                   MachineBasicBlock *MergeBB,
                                                   unsigned BBSelectReg) {
MachineBasicBlock *TrueBB = nullptr;
MachineBasicBlock *FalseBB = nullptr;
SmallVector<MachineOperand, 1> Cond;
MachineBasicBlock *FallthroughBB = FallthroughMap[CodeBB];
TII->analyzeBranch(*CodeBB, TrueBB, FalseBB, Cond);

const DebugLoc &DL = CodeBB->findDebugLoc(CodeBB->getFirstTerminator());

if (FalseBB == nullptr && TrueBB == nullptr && FallthroughBB == nullptr) {
  // This is an exit block, hence no successors. We will assign the
  // bb select register to the entry block.
  TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
                            BBSelectReg,
                            CodeBB->getParent()->begin()->getNumber());
  insertUnconditionalBranch(CodeBB, MergeBB, DL);
  return;
}

if (FalseBB == nullptr && TrueBB == nullptr) {
  TrueBB = FallthroughBB;
} else if (TrueBB != nullptr) {
  FalseBB =
      (FallthroughBB && (FallthroughBB != TrueBB)) ? FallthroughBB : FalseBB;
}

if ((TrueBB != nullptr && FalseBB == nullptr) || (TrueBB == FalseBB)) {
  TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
                            BBSelectReg, TrueBB->getNumber());
} else {
  const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectReg);
  Register TrueBBReg = MRI->createVirtualRegister(RegClass);
  Register FalseBBReg = MRI->createVirtualRegister(RegClass);
  TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
                            TrueBBReg, TrueBB->getNumber());
  TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
                            FalseBBReg, FalseBB->getNumber());
  ensureCondIsNotKilled(Cond);
  TII->insertVectorSelect(*CodeBB, CodeBB->getFirstTerminator(), DL,
                          BBSelectReg, Cond, TrueBBReg, FalseBBReg);
}

insertUnconditionalBranch(CodeBB, MergeBB, DL);
1925}

1927MachineInstr *AMDGPUMachineCFGStructurizer::getDefInstr(unsigned Reg) {
if (MRI->def_begin(Reg) == MRI->def_end()) {
  LLVM_DEBUG(dbgs() << "Register "do { } while (false)
                    << printReg(Reg, MRI->getTargetRegisterInfo())do { } while (false)
                    << " has NO defs\n")do { } while (false);
} else if (!MRI->hasOneDef(Reg)) {
  LLVM_DEBUG(dbgs() << "Register "do { } while (false)
                    << printReg(Reg, MRI->getTargetRegisterInfo())do { } while (false)
                    << " has multiple defs\n")do { } while (false);
  LLVM_DEBUG(dbgs() << "DEFS BEGIN:\n")do { } while (false);
  for (auto DI = MRI->def_begin(Reg), DE = MRI->def_end(); DI != DE; ++DI) {
    LLVM_DEBUG(DI->getParent()->dump())do { } while (false);
  }
  LLVM_DEBUG(dbgs() << "DEFS END\n")do { } while (false);
}

assert(MRI->hasOneDef(Reg) && "Register has multiple definitions")(static_cast<void> (0));
return (*(MRI->def_begin(Reg))).getParent();
1945}

1947void AMDGPUMachineCFGStructurizer::insertChainedPHI(MachineBasicBlock *IfBB,
                                            MachineBasicBlock *CodeBB,
                                            MachineBasicBlock *MergeBB,
                                            LinearizedRegion *InnerRegion,
                                            unsigned DestReg,
                                            unsigned SourceReg) {
// In this function we know we are part of a chain already, so we need
// to add the registers to the existing chain, and rename the register
// inside the region.
bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
MachineInstr *DefInstr = getDefInstr(SourceReg);
if (DefInstr->isPHI() && DefInstr->getParent() == CodeBB && IsSingleBB) {
  // Handle the case where the def is a PHI-def inside a basic
  // block, then we only need to do renaming. Special care needs to
  // be taken if the PHI-def is part of an existing chain, or if a
  // new one needs to be created.
  InnerRegion->replaceRegisterInsideRegion(SourceReg, DestReg, true, MRI);

  // We collect all PHI Information, and if we are at the region entry,
  // all PHIs will be removed, and then re-introduced if needed.
  storePHILinearizationInfoDest(DestReg, *DefInstr);
  // We have picked up all the information we need now and can remove
  // the PHI
  PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
  DefInstr->eraseFromParent();
} else {
  // If this is not a phi-def, or it is a phi-def but from a linearized region
  if (IsSingleBB && DefInstr->getParent() == InnerRegion->getEntry()) {
    // If this is a single BB and the definition is in this block we
    // need to replace any uses outside the region.
    InnerRegion->replaceRegisterOutsideRegion(SourceReg, DestReg, false, MRI);
  }
  const TargetRegisterClass *RegClass = MRI->getRegClass(DestReg);
  Register NextDestReg = MRI->createVirtualRegister(RegClass);
  bool IsLastDef = PHIInfo.getNumSources(DestReg) == 1;
  LLVM_DEBUG(dbgs() << "Insert Chained PHI\n")do { } while (false);
  insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, DestReg, NextDestReg,
                 SourceReg, IsLastDef);

  PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
  if (IsLastDef) {
    const DebugLoc &DL = IfBB->findDebugLoc(IfBB->getFirstTerminator());
    TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DL,
                              NextDestReg, 0);
    PHIInfo.deleteDef(DestReg);
  } else {
    PHIInfo.replaceDef(DestReg, NextDestReg);
  }
}
1996}

1998bool AMDGPUMachineCFGStructurizer::containsDef(MachineBasicBlock *MBB,
                                       LinearizedRegion *InnerRegion,
                                       unsigned Register) {
return getDefInstr(Register)->getParent() == MBB ||
       InnerRegion->contains(getDefInstr(Register)->getParent());
2003}

2005void AMDGPUMachineCFGStructurizer::rewriteLiveOutRegs(MachineBasicBlock *IfBB,
                                              MachineBasicBlock *CodeBB,
                                              MachineBasicBlock *MergeBB,
                                              LinearizedRegion *InnerRegion,
                                              LinearizedRegion *LRegion) {
DenseSet<unsigned> *LiveOuts = InnerRegion->getLiveOuts();
SmallVector<unsigned, 4> OldLiveOuts;
bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
for (auto OLI : *LiveOuts) {
  OldLiveOuts.push_back(OLI);
}

for (auto LI : OldLiveOuts) {
  LLVM_DEBUG(dbgs() << "LiveOut: " << printReg(LI, TRI))do { } while (false);
  if (!containsDef(CodeBB, InnerRegion, LI) ||
      (!IsSingleBB && (getDefInstr(LI)->getParent() == LRegion->getExit()))) {
    // If the register simly lives through the CodeBB, we don't have
    // to rewrite anything since the register is not defined in this
    // part of the code.
    LLVM_DEBUG(dbgs() << "- through")do { } while (false);
    continue;
  }
  LLVM_DEBUG(dbgs() << "\n")do { } while (false);
  unsigned Reg = LI;
  if (/*!PHIInfo.isSource(Reg) &&*/ Reg != InnerRegion->getBBSelectRegOut()) {
    // If the register is live out, we do want to create a phi,
    // unless it is from the Exit block, becasuse in that case there
    // is already a PHI, and no need to create a new one.

    // If the register is just a live out def and not part of a phi
    // chain, we need to create a PHI node to handle the if region,
    // and replace all uses outside of the region with the new dest
    // register, unless it is the outgoing BB select register. We have
    // already creaed phi nodes for these.
    const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
    Register PHIDestReg = MRI->createVirtualRegister(RegClass);
    Register IfSourceReg = MRI->createVirtualRegister(RegClass);
    // Create initializer, this value is never used, but is needed
    // to satisfy SSA.
    LLVM_DEBUG(dbgs() << "Initializer for reg: " << printReg(Reg) << "\n")do { } while (false);
    TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DebugLoc(),
                      IfSourceReg, 0);

    InnerRegion->replaceRegisterOutsideRegion(Reg, PHIDestReg, true, MRI);
    LLVM_DEBUG(dbgs() << "Insert Non-Chained Live out PHI\n")do { } while (false);
    insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, PHIDestReg,
                   IfSourceReg, Reg, true);
  }
}

// Handle the chained definitions in PHIInfo, checking if this basic block
// is a source block for a definition.
SmallVector<unsigned, 4> Sources;
if (PHIInfo.findSourcesFromMBB(CodeBB, Sources)) {
  LLVM_DEBUG(dbgs() << "Inserting PHI Live Out from "do { } while (false)
                    << printMBBReference(*CodeBB) << "\n")do { } while (false);
  for (auto SI : Sources) {
    unsigned DestReg;
    PHIInfo.findDest(SI, CodeBB, DestReg);
    insertChainedPHI(IfBB, CodeBB, MergeBB, InnerRegion, DestReg, SI);
  }
  LLVM_DEBUG(dbgs() << "Insertion done.\n")do { } while (false);
}

LLVM_DEBUG(PHIInfo.dump(MRI))do { } while (false);
2070}

2072void AMDGPUMachineCFGStructurizer::prunePHIInfo(MachineBasicBlock *MBB) {
LLVM_DEBUG(dbgs() << "Before PHI Prune\n")do { } while (false);
LLVM_DEBUG(PHIInfo.dump(MRI))do { } while (false);
SmallVector<std::tuple<unsigned, unsigned, MachineBasicBlock *>, 4>
    ElimiatedSources;
for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
     ++DRI) {

  unsigned DestReg = *DRI;
  auto SE = PHIInfo.sources_end(DestReg);

  bool MBBContainsPHISource = false;
  // Check if there is a PHI source in this MBB
  for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    unsigned SourceReg = (*SRI).first;
    MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
    if (Def->getParent()->getParent() == MBB) {
      MBBContainsPHISource = true;
    }
  }

  // If so, all other sources are useless since we know this block
  // is always executed when the region is executed.
  if (MBBContainsPHISource) {
    for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
      PHILinearize::PHISourceT Source = *SRI;
      unsigned SourceReg = Source.first;
      MachineBasicBlock *SourceMBB = Source.second;
      MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
      if (Def->getParent()->getParent() != MBB) {
        ElimiatedSources.push_back(
            std::make_tuple(DestReg, SourceReg, SourceMBB));
      }
    }
  }
}

// Remove the PHI sources that are in the given MBB
for (auto &SourceInfo : ElimiatedSources) {
  PHIInfo.removeSource(std::get<0>(SourceInfo), std::get<1>(SourceInfo),
                       std::get<2>(SourceInfo));
}
LLVM_DEBUG(dbgs() << "After PHI Prune\n")do { } while (false);
LLVM_DEBUG(PHIInfo.dump(MRI))do { } while (false);
2116}

2118void AMDGPUMachineCFGStructurizer::createEntryPHI(LinearizedRegion *CurrentRegion,
                                          unsigned DestReg) {
MachineBasicBlock *Entry = CurrentRegion->getEntry();
MachineBasicBlock *Exit = CurrentRegion->getExit();

LLVM_DEBUG(dbgs() << "RegionExit: " << Exit->getNumber() << " Pred: "do { } while (false)
                  << (*(Entry->pred_begin()))->getNumber() << "\n")do { } while (false);

int NumSources = 0;
auto SE = PHIInfo.sources_end(DestReg);

for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
  NumSources++;
}

if (NumSources == 1) {
  auto SRI = PHIInfo.sources_begin(DestReg);
  unsigned SourceReg = (*SRI).first;
  replaceRegisterWith(DestReg, SourceReg);
} else {
  const DebugLoc &DL = Entry->findDebugLoc(Entry->begin());
  MachineInstrBuilder MIB = BuildMI(*Entry, Entry->instr_begin(), DL,
                                    TII->get(TargetOpcode::PHI), DestReg);
  LLVM_DEBUG(dbgs() << "Entry PHI " << printReg(DestReg, TRI) << " = PHI(")do { } while (false);

  unsigned CurrentBackedgeReg = 0;

  for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    unsigned SourceReg = (*SRI).first;

    if (CurrentRegion->contains((*SRI).second)) {
      if (CurrentBackedgeReg == 0) {
        CurrentBackedgeReg = SourceReg;
      } else {
        MachineInstr *PHIDefInstr = getDefInstr(SourceReg);
        MachineBasicBlock *PHIDefMBB = PHIDefInstr->getParent();
        const TargetRegisterClass *RegClass =
            MRI->getRegClass(CurrentBackedgeReg);
        Register NewBackedgeReg = MRI->createVirtualRegister(RegClass);
        MachineInstrBuilder BackedgePHI =
            BuildMI(*PHIDefMBB, PHIDefMBB->instr_begin(), DL,
                    TII->get(TargetOpcode::PHI), NewBackedgeReg);
        BackedgePHI.addReg(CurrentBackedgeReg);
        BackedgePHI.addMBB(getPHIPred(*PHIDefInstr, 0));
        BackedgePHI.addReg(getPHISourceReg(*PHIDefInstr, 1));
        BackedgePHI.addMBB((*SRI).second);
        CurrentBackedgeReg = NewBackedgeReg;
        LLVM_DEBUG(dbgs()do { } while (false)
                   << "Inserting backedge PHI: "do { } while (false)
                   << printReg(NewBackedgeReg, TRI) << " = PHI("do { } while (false)
                   << printReg(CurrentBackedgeReg, TRI) << ", "do { } while (false)
                   << printMBBReference(*getPHIPred(*PHIDefInstr, 0)) << ", "do { } while (false)
                   << printReg(getPHISourceReg(*PHIDefInstr, 1), TRI) << ", "do { } while (false)
                   << printMBBReference(*(*SRI).second))do { } while (false);
      }
    } else {
      MIB.addReg(SourceReg);
      MIB.addMBB((*SRI).second);
      LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "do { } while (false)
                        << printMBBReference(*(*SRI).second) << ", ")do { } while (false);
    }
  }

  // Add the final backedge register source to the entry phi
  if (CurrentBackedgeReg != 0) {
    MIB.addReg(CurrentBackedgeReg);
    MIB.addMBB(Exit);
    LLVM_DEBUG(dbgs() << printReg(CurrentBackedgeReg, TRI) << ", "do { } while (false)
                      << printMBBReference(*Exit) << ")\n")do { } while (false);
  } else {
    LLVM_DEBUG(dbgs() << ")\n")do { } while (false);
  }
}
2191}

2193void AMDGPUMachineCFGStructurizer::createEntryPHIs(LinearizedRegion *CurrentRegion) {
LLVM_DEBUG(PHIInfo.dump(MRI))do { } while (false);

for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
     ++DRI) {

  unsigned DestReg = *DRI;
  createEntryPHI(CurrentRegion, DestReg);
}
PHIInfo.clear();
2203}

2205void AMDGPUMachineCFGStructurizer::replaceRegisterWith(
  unsigned Register, class Register NewRegister) {
assert(Register != NewRegister && "Cannot replace a reg with itself")(static_cast<void> (0));

for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
                                       E = MRI->reg_end();
     I != E;) {
  MachineOperand &O = *I;
  ++I;
  if (NewRegister.isPhysical()) {
    LLVM_DEBUG(dbgs() << "Trying to substitute physical register: "do { } while (false)
                      << printReg(NewRegister, MRI->getTargetRegisterInfo())do { } while (false)
                      << "\n")do { } while (false);
    llvm_unreachable("Cannot substitute physical registers")__builtin_unreachable();
    // We don't handle physical registers, but if we need to
    // in the future This is how we do it:
    // O.substPhysReg(NewRegister, *TRI);
  } else {
    LLVM_DEBUG(dbgs() << "Replacing register: "do { } while (false)
                      << printReg(Register, MRI->getTargetRegisterInfo())do { } while (false)
                      << " with "do { } while (false)
                      << printReg(NewRegister, MRI->getTargetRegisterInfo())do { } while (false)
                      << "\n")do { } while (false);
    O.setReg(NewRegister);
  }
}
PHIInfo.deleteDef(Register);

getRegionMRT()->replaceLiveOutReg(Register, NewRegister);

LLVM_DEBUG(PHIInfo.dump(MRI))do { } while (false);
2236}

2238void AMDGPUMachineCFGStructurizer::resolvePHIInfos(MachineBasicBlock *FunctionEntry) {
LLVM_DEBUG(dbgs() << "Resolve PHI Infos\n")do { } while (false);
LLVM_DEBUG(PHIInfo.dump(MRI))do { } while (false);
for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
     ++DRI) {
  unsigned DestReg = *DRI;
  LLVM_DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI) << "\n")do { } while (false);
  auto SRI = PHIInfo.sources_begin(DestReg);
  unsigned SourceReg = (*SRI).first;
  LLVM_DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI)do { } while (false)
                    << " SourceReg: " << printReg(SourceReg, TRI) << "\n")do { } while (false);

  assert(PHIInfo.sources_end(DestReg) == ++SRI &&(static_cast<void> (0))
         "More than one phi source in entry node")(static_cast<void> (0));
  replaceRegisterWith(DestReg, SourceReg);
}
2254}

2256static bool isFunctionEntryBlock(MachineBasicBlock *MBB) {
return ((&(*(MBB->getParent()->begin()))) == MBB);
41
←
Assuming the condition is false→
42
←
Returning zero, which participates in a condition later→
78
←
Assuming the condition is false→
79
←
Returning zero, which participates in a condition later→
2258}

2260MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion(
  MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBB,
  LinearizedRegion *CurrentRegion, unsigned BBSelectRegIn,
  unsigned BBSelectRegOut) {
if (isFunctionEntryBlock(CodeBB) && !CurrentRegion->getHasLoop()) {
40
←
Calling 'isFunctionEntryBlock'→
43
←
Returning from 'isFunctionEntryBlock'→
77
←
Calling 'isFunctionEntryBlock'→
80
←
Returning from 'isFunctionEntryBlock'→
  // Handle non-loop function entry block.
  // We need to allow loops to the entry block and then
  rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
  resolvePHIInfos(CodeBB);
  removeExternalCFGSuccessors(CodeBB);
  CodeBB->addSuccessor(MergeBB);
  CurrentRegion->addMBB(CodeBB);
  return nullptr;
}
if (CurrentRegion->getEntry() == CodeBB && !CurrentRegion->getHasLoop()) {
44
←
Assuming the condition is false→
81
←
Assuming the condition is true→
82
←
Assuming the condition is true→
83
←
Taking true branch→
  // Handle non-loop region entry block.
  MachineFunction *MF = MergeBB->getParent();
84
←
Called C++ object pointer is null
  auto MergeIter = MergeBB->getIterator();
  auto CodeBBStartIter = CodeBB->getIterator();
  auto CodeBBEndIter = ++(CodeBB->getIterator());
  if (CodeBBEndIter != MergeIter) {
    MF->splice(MergeIter, CodeBBStartIter, CodeBBEndIter);
  }
  rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
  prunePHIInfo(CodeBB);
  createEntryPHIs(CurrentRegion);
  removeExternalCFGSuccessors(CodeBB);
  CodeBB->addSuccessor(MergeBB);
  CurrentRegion->addMBB(CodeBB);
  return nullptr;
} else {
  // Handle internal block.
  const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectRegIn);
  Register CodeBBSelectReg = MRI->createVirtualRegister(RegClass);
  rewriteCodeBBTerminator(CodeBB, MergeBB, CodeBBSelectReg);
  bool IsRegionEntryBB = CurrentRegion->getEntry() == CodeBB;
  MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeBB, CodeBB, CodeBB,
45
←
'IfBB' initialized here→
                                          BBSelectRegIn, IsRegionEntryBB);
  CurrentRegion->addMBB(IfBB);
  // If this is the entry block we need to make the If block the new
  // linearized region entry.
  if (IsRegionEntryBB45.1
'IsRegionEntryBB' is false
1
'IsRegionEntryBB' is false
) {
46
←
Taking false branch→
    CurrentRegion->setEntry(IfBB);

    if (CurrentRegion->getHasLoop()) {
      MachineBasicBlock *RegionExit = CurrentRegion->getExit();
      MachineBasicBlock *ETrueBB = nullptr;
      MachineBasicBlock *EFalseBB = nullptr;
      SmallVector<MachineOperand, 1> ECond;

      const DebugLoc &DL = DebugLoc();
      TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond);
      TII->removeBranch(*RegionExit);

      // We need to create a backedge if there is a loop
      Register Reg = TII->insertNE(
          RegionExit, RegionExit->instr_end(), DL,
          CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
          CurrentRegion->getRegionMRT()->getEntry()->getNumber());
      MachineOperand RegOp =
          MachineOperand::CreateReg(Reg, false, false, true);
      ArrayRef<MachineOperand> Cond(RegOp);
      LLVM_DEBUG(dbgs() << "RegionExitReg: ")do { } while (false);
      LLVM_DEBUG(Cond[0].print(dbgs(), TRI))do { } while (false);
      LLVM_DEBUG(dbgs() << "\n")do { } while (false);
      TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
                        Cond, DebugLoc());
      RegionExit->addSuccessor(CurrentRegion->getEntry());
    }
  }
  CurrentRegion->addMBB(CodeBB);
  LinearizedRegion InnerRegion(CodeBB, MRI, TRI, PHIInfo);

  InnerRegion.setParent(CurrentRegion);
47
←
Calling 'LinearizedRegion::setParent'→
49
←
Returning from 'LinearizedRegion::setParent'→
  LLVM_DEBUG(dbgs() << "Insert BB Select PHI (BB)\n")do { } while (false);
50
←
Loop condition is false.  Exiting loop→
  insertMergePHI(IfBB, CodeBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
                 CodeBBSelectReg);
  InnerRegion.addMBB(MergeBB);

  LLVM_DEBUG(InnerRegion.print(dbgs(), TRI))do { } while (false);
51
←
Loop condition is false.  Exiting loop→
  rewriteLiveOutRegs(IfBB, CodeBB, MergeBB, &InnerRegion, CurrentRegion);
  extractKilledPHIs(CodeBB);
  if (IsRegionEntryBB51.1
'IsRegionEntryBB' is false
1
'IsRegionEntryBB' is false
) {
52
←
Taking false branch→
    createEntryPHIs(CurrentRegion);
  }
  return IfBB;
53
←
Returning pointer (loaded from 'IfBB')→
}
2347}

2349MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion(
  MachineBasicBlock *MergeBB, LinearizedRegion *InnerRegion,
  LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
  unsigned BBSelectRegIn, unsigned BBSelectRegOut) {
unsigned CodeBBSelectReg =
    InnerRegion->getRegionMRT()->getInnerOutputRegister();
MachineBasicBlock *CodeEntryBB = InnerRegion->getEntry();
MachineBasicBlock *CodeExitBB = InnerRegion->getExit();
MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeEntryBB, CodeExitBB,
                                        SelectBB, BBSelectRegIn, true);
CurrentRegion->addMBB(IfBB);
bool isEntry = CurrentRegion->getEntry() == InnerRegion->getEntry();
if (isEntry) {

  if (CurrentRegion->getHasLoop()) {
    MachineBasicBlock *RegionExit = CurrentRegion->getExit();
    MachineBasicBlock *ETrueBB = nullptr;
    MachineBasicBlock *EFalseBB = nullptr;
    SmallVector<MachineOperand, 1> ECond;

    const DebugLoc &DL = DebugLoc();
    TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond);
    TII->removeBranch(*RegionExit);

    // We need to create a backedge if there is a loop
    Register Reg =
        TII->insertNE(RegionExit, RegionExit->instr_end(), DL,
                      CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
                      CurrentRegion->getRegionMRT()->getEntry()->getNumber());
    MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
    ArrayRef<MachineOperand> Cond(RegOp);
    LLVM_DEBUG(dbgs() << "RegionExitReg: ")do { } while (false);
    LLVM_DEBUG(Cond[0].print(dbgs(), TRI))do { } while (false);
    LLVM_DEBUG(dbgs() << "\n")do { } while (false);
    TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
                      Cond, DebugLoc());
    RegionExit->addSuccessor(IfBB);
  }
}
CurrentRegion->addMBBs(InnerRegion);
LLVM_DEBUG(dbgs() << "Insert BB Select PHI (region)\n")do { } while (false);
insertMergePHI(IfBB, CodeExitBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
               CodeBBSelectReg);

rewriteLiveOutRegs(IfBB, /* CodeEntryBB */ CodeExitBB, MergeBB, InnerRegion,
                   CurrentRegion);

rewriteRegionEntryPHIs(InnerRegion, IfBB);

if (isEntry) {
  CurrentRegion->setEntry(IfBB);
}

if (isEntry) {
  createEntryPHIs(CurrentRegion);
}

return IfBB;
2407}

2409void AMDGPUMachineCFGStructurizer::splitLoopPHI(MachineInstr &PHI,
                                        MachineBasicBlock *Entry,
                                        MachineBasicBlock *EntrySucc,
                                        LinearizedRegion *LRegion) {
SmallVector<unsigned, 2> PHIRegionIndices;
getPHIRegionIndices(LRegion, PHI, PHIRegionIndices);

assert(PHIRegionIndices.size() == 1)(static_cast<void> (0));

unsigned RegionIndex = PHIRegionIndices[0];
unsigned RegionSourceReg = getPHISourceReg(PHI, RegionIndex);
MachineBasicBlock *RegionSourceMBB = getPHIPred(PHI, RegionIndex);
unsigned PHIDest = getPHIDestReg(PHI);
unsigned PHISource = PHIDest;
unsigned ReplaceReg;

if (shrinkPHI(PHI, PHIRegionIndices, &ReplaceReg)) {
  PHISource = ReplaceReg;
}

const TargetRegisterClass *RegClass = MRI->getRegClass(PHIDest);
Register NewDestReg = MRI->createVirtualRegister(RegClass);
LRegion->replaceRegisterInsideRegion(PHIDest, NewDestReg, false, MRI);
MachineInstrBuilder MIB =
    BuildMI(*EntrySucc, EntrySucc->instr_begin(), PHI.getDebugLoc(),
            TII->get(TargetOpcode::PHI), NewDestReg);
LLVM_DEBUG(dbgs() << "Split Entry PHI " << printReg(NewDestReg, TRI)do { } while (false)
                  << " = PHI(")do { } while (false);
MIB.addReg(PHISource);
MIB.addMBB(Entry);
LLVM_DEBUG(dbgs() << printReg(PHISource, TRI) << ", "do { } while (false)
                  << printMBBReference(*Entry))do { } while (false);
MIB.addReg(RegionSourceReg);
MIB.addMBB(RegionSourceMBB);
LLVM_DEBUG(dbgs() << " ," << printReg(RegionSourceReg, TRI) << ", "do { } while (false)
                  << printMBBReference(*RegionSourceMBB) << ")\n")do { } while (false);
2445}

2447void AMDGPUMachineCFGStructurizer::splitLoopPHIs(MachineBasicBlock *Entry,
                                         MachineBasicBlock *EntrySucc,
                                         LinearizedRegion *LRegion) {
SmallVector<MachineInstr *, 2> PHIs;
collectPHIs(Entry, PHIs);

for (auto PHII : PHIs) {
  splitLoopPHI(*PHII, Entry, EntrySucc, LRegion);
}
2456}

2458// Split the exit block so that we can insert a end control flow
2459MachineBasicBlock *
2460AMDGPUMachineCFGStructurizer::splitExit(LinearizedRegion *LRegion) {
auto MRTRegion = LRegion->getRegionMRT();
auto Exit = LRegion->getExit();
auto MF = Exit->getParent();
auto Succ = MRTRegion->getSucc();

auto NewExit = MF->CreateMachineBasicBlock();
auto AfterExitIter = Exit->getIterator();
AfterExitIter++;
MF->insert(AfterExitIter, NewExit);
Exit->removeSuccessor(Succ);
Exit->addSuccessor(NewExit);
NewExit->addSuccessor(Succ);
insertUnconditionalBranch(NewExit, Succ);
LRegion->addMBB(NewExit);
LRegion->setExit(NewExit);

LLVM_DEBUG(dbgs() << "Created new exit block: " << NewExit->getNumber()do { } while (false)
                  << "\n")do { } while (false);

// Replace any PHI Predecessors in the successor with NewExit
for (auto &II : *Succ) {
  MachineInstr &Instr = II;

  // If we are past the PHI instructions we are done
  if (!Instr.isPHI())
    break;

  int numPreds = getPHINumInputs(Instr);
  for (int i = 0; i < numPreds; ++i) {
    auto Pred = getPHIPred(Instr, i);
    if (Pred == Exit) {
      setPhiPred(Instr, i, NewExit);
    }
  }
}

return NewExit;
2498}

2500static MachineBasicBlock *split(MachineBasicBlock::iterator I) {
// Create the fall-through block.
MachineBasicBlock *MBB = (*I).getParent();
MachineFunction *MF = MBB->getParent();
MachineBasicBlock *SuccMBB = MF->CreateMachineBasicBlock();
auto MBBIter = ++(MBB->getIterator());
MF->insert(MBBIter, SuccMBB);
SuccMBB->transferSuccessorsAndUpdatePHIs(MBB);
MBB->addSuccessor(SuccMBB);

// Splice the code over.
SuccMBB->splice(SuccMBB->end(), MBB, I, MBB->end());

return SuccMBB;
2514}

2516// Split the entry block separating PHI-nodes and the rest of the code
2517// This is needed to insert an initializer for the bb select register
2518// inloop regions.

2520MachineBasicBlock *
2521AMDGPUMachineCFGStructurizer::splitEntry(LinearizedRegion *LRegion) {
MachineBasicBlock *Entry = LRegion->getEntry();
MachineBasicBlock *EntrySucc = split(Entry->getFirstNonPHI());
MachineBasicBlock *Exit = LRegion->getExit();

LLVM_DEBUG(dbgs() << "Split " << printMBBReference(*Entry) << " to "do { } while (false)
                  << printMBBReference(*Entry) << " -> "do { } while (false)
                  << printMBBReference(*EntrySucc) << "\n")do { } while (false);
LRegion->addMBB(EntrySucc);

// Make the backedge go to Entry Succ
if (Exit->isSuccessor(Entry)) {
  Exit->removeSuccessor(Entry);
}
Exit->addSuccessor(EntrySucc);
MachineInstr &Branch = *(Exit->instr_rbegin());
for (auto &UI : Branch.uses()) {
  if (UI.isMBB() && UI.getMBB() == Entry) {
    UI.setMBB(EntrySucc);
  }
}

splitLoopPHIs(Entry, EntrySucc, LRegion);

return EntrySucc;
2546}

2548LinearizedRegion *
2549AMDGPUMachineCFGStructurizer::initLinearizedRegion(RegionMRT *Region) {
LinearizedRegion *LRegion = Region->getLinearizedRegion();
LRegion->initLiveOut(Region, MRI, TRI, PHIInfo);
LRegion->setEntry(Region->getEntry());
return LRegion;
2554}

2556static void removeOldExitPreds(RegionMRT *Region) {
MachineBasicBlock *Exit = Region->getSucc();
if (Exit == nullptr) {
  return;
}
for (MachineBasicBlock::pred_iterator PI = Exit->pred_begin(),
                                      E = Exit->pred_end();
     PI != E; ++PI) {
  if (Region->contains(*PI)) {
    (*PI)->removeSuccessor(Exit);
  }
}
2568}

2570static bool mbbHasBackEdge(MachineBasicBlock *MBB,
                         SmallPtrSet<MachineBasicBlock *, 8> &MBBs) {
for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) {
  if (MBBs.contains(*SI)) {
    return true;
  }
}
return false;
2578}

2580static bool containsNewBackedge(MRT *Tree,
                              SmallPtrSet<MachineBasicBlock *, 8> &MBBs) {
// Need to traverse this in reverse since it is in post order.
if (Tree == nullptr)
  return false;

if (Tree->isMBB()) {
  MachineBasicBlock *MBB = Tree->getMBBMRT()->getMBB();
  MBBs.insert(MBB);
  if (mbbHasBackEdge(MBB, MBBs)) {
    return true;
  }
} else {
  RegionMRT *Region = Tree->getRegionMRT();
  SetVector<MRT *> *Children = Region->getChildren();
  for (auto CI = Children->rbegin(), CE = Children->rend(); CI != CE; ++CI) {
    if (containsNewBackedge(*CI, MBBs))
      return true;
  }
}
return false;
2601}

2603static bool containsNewBackedge(RegionMRT *Region) {
SmallPtrSet<MachineBasicBlock *, 8> MBBs;
return containsNewBackedge(Region, MBBs);
2606}

2608bool AMDGPUMachineCFGStructurizer::structurizeComplexRegion(RegionMRT *Region) {
auto *LRegion = initLinearizedRegion(Region);
LRegion->setHasLoop(containsNewBackedge(Region));
MachineBasicBlock *LastMerge = createLinearizedExitBlock(Region);
MachineBasicBlock *CurrentMerge = LastMerge;
LRegion->addMBB(LastMerge);
LRegion->setExit(LastMerge);

rewriteRegionExitPHIs(Region, LastMerge, LRegion);
12
←
Calling 'AMDGPUMachineCFGStructurizer::rewriteRegionExitPHIs'→
17
←
Returning from 'AMDGPUMachineCFGStructurizer::rewriteRegionExitPHIs'→
removeOldExitPreds(Region);

LLVM_DEBUG(PHIInfo.dump(MRI))do { } while (false);
18
←
Loop condition is false.  Exiting loop→

SetVector<MRT *> *Children = Region->getChildren();
LLVM_DEBUG(dbgs() << "===========If Region Start===============\n")do { } while (false);
19
←
Loop condition is false.  Exiting loop→
if (LRegion->getHasLoop()) {
20
←
Assuming the condition is false→
21
←
Taking false branch→
  LLVM_DEBUG(dbgs() << "Has Backedge: Yes\n")do { } while (false);
} else {
  LLVM_DEBUG(dbgs() << "Has Backedge: No\n")do { } while (false);
22
←
Loop condition is false.  Exiting loop→
}

unsigned BBSelectRegIn;
unsigned BBSelectRegOut;
for (auto CI = Children->begin(), CE = Children->end(); CI != CE; ++CI) {
23
←
Calling 'operator!=<(anonymous namespace)::MRT *const *, std::vector<(anonymous namespace)::MRT *>>'→
26
←
Returning from 'operator!=<(anonymous namespace)::MRT *const *, std::vector<(anonymous namespace)::MRT *>>'→
27
←
Loop condition is true.  Entering loop body→
59
←
Calling 'operator!=<(anonymous namespace)::MRT *const *, std::vector<(anonymous namespace)::MRT *>>'→
62
←
Returning from 'operator!=<(anonymous namespace)::MRT *const *, std::vector<(anonymous namespace)::MRT *>>'→
63
←
Loop condition is true.  Entering loop body→
  LLVM_DEBUG(dbgs() << "CurrentRegion: \n")do { } while (false);
28
←
Loop condition is false.  Exiting loop→
64
←
Loop condition is false.  Exiting loop→
  LLVM_DEBUG(LRegion->print(dbgs(), TRI))do { } while (false);
29
←
Loop condition is false.  Exiting loop→
65
←
Loop condition is false.  Exiting loop→

  auto CNI = CI;
  ++CNI;

  MRT *Child = (*CI);

  if (Child->isRegion()) {
30
←
Calling 'MRT::isRegion'→
33
←
Returning from 'MRT::isRegion'→
34
←
Taking false branch→
66
←
Calling 'MRT::isRegion'→
69
←
Returning from 'MRT::isRegion'→
70
←
Taking false branch→

    LinearizedRegion *InnerLRegion =
        Child->getRegionMRT()->getLinearizedRegion();
    // We found the block is the exit of an inner region, we need
    // to put it in the current linearized region.

    LLVM_DEBUG(dbgs() << "Linearizing region: ")do { } while (false);
    LLVM_DEBUG(InnerLRegion->print(dbgs(), TRI))do { } while (false);
    LLVM_DEBUG(dbgs() << "\n")do { } while (false);

    MachineBasicBlock *InnerEntry = InnerLRegion->getEntry();
    if ((&(*(InnerEntry->getParent()->begin()))) == InnerEntry) {
      // Entry has already been linearized, no need to do this region.
      unsigned OuterSelect = InnerLRegion->getBBSelectRegOut();
      unsigned InnerSelectReg =
          InnerLRegion->getRegionMRT()->getInnerOutputRegister();
      replaceRegisterWith(InnerSelectReg, OuterSelect),
          resolvePHIInfos(InnerEntry);
      if (!InnerLRegion->getExit()->isSuccessor(CurrentMerge))
        InnerLRegion->getExit()->addSuccessor(CurrentMerge);
      continue;
    }

    BBSelectRegOut = Child->getBBSelectRegOut();
    BBSelectRegIn = Child->getBBSelectRegIn();

    LLVM_DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI)do { } while (false)
                      << "\n")do { } while (false);
    LLVM_DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI)do { } while (false)
                      << "\n")do { } while (false);

    MachineBasicBlock *IfEnd = CurrentMerge;
    CurrentMerge = createIfRegion(CurrentMerge, InnerLRegion, LRegion,
                                  Child->getRegionMRT()->getEntry(),
                                  BBSelectRegIn, BBSelectRegOut);
    TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
  } else {
    MachineBasicBlock *MBB = Child->getMBBMRT()->getMBB();
    LLVM_DEBUG(dbgs() << "Linearizing block: " << MBB->getNumber() << "\n")do { } while (false);
35
←
Loop condition is false.  Exiting loop→
71
←
Loop condition is false.  Exiting loop→

    if (MBB == getSingleExitNode(*(MBB->getParent()))) {
36
←
Taking false branch→
72
←
Taking false branch→
      // If this is the exit block then we need to skip to the next.
      // The "in" register will be transferred to "out" in the next
      // iteration.
      continue;
    }

    BBSelectRegOut = Child->getBBSelectRegOut();
    BBSelectRegIn = Child->getBBSelectRegIn();

    LLVM_DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI)do { } while (false)
37
←
Loop condition is false.  Exiting loop→
73
←
Loop condition is false.  Exiting loop→
                      << "\n")do { } while (false);
    LLVM_DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI)do { } while (false)
38
←
Loop condition is false.  Exiting loop→
74
←
Loop condition is false.  Exiting loop→
                      << "\n")do { } while (false);

    MachineBasicBlock *IfEnd = CurrentMerge;
    // This is a basic block that is not part of an inner region, we
    // need to put it in the current linearized region.
    CurrentMerge = createIfRegion(CurrentMerge, MBB, LRegion, BBSelectRegIn,
39
←
Calling 'AMDGPUMachineCFGStructurizer::createIfRegion'→
54
←
Returning from 'AMDGPUMachineCFGStructurizer::createIfRegion'→
55
←
Value assigned to 'CurrentMerge'→
75
←
Passing null pointer value via 1st parameter 'MergeBB'→
76
←
Calling 'AMDGPUMachineCFGStructurizer::createIfRegion'→
                                  BBSelectRegOut);
    if (CurrentMerge) {
56
←
Assuming 'CurrentMerge' is null→
57
←
Taking false branch→
      TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
    }

    LLVM_DEBUG(PHIInfo.dump(MRI))do { } while (false);
58
←
Loop condition is false.  Exiting loop→
  }
}

LRegion->removeFalseRegisterKills(MRI);

if (LRegion->getHasLoop()) {
  MachineBasicBlock *NewSucc = splitEntry(LRegion);
  if (isFunctionEntryBlock(LRegion->getEntry())) {
    resolvePHIInfos(LRegion->getEntry());
  }
  const DebugLoc &DL = NewSucc->findDebugLoc(NewSucc->getFirstNonPHI());
  unsigned InReg = LRegion->getBBSelectRegIn();
  Register InnerSelectReg =
      MRI->createVirtualRegister(MRI->getRegClass(InReg));
  Register NewInReg = MRI->createVirtualRegister(MRI->getRegClass(InReg));
  TII->materializeImmediate(*(LRegion->getEntry()),
                            LRegion->getEntry()->getFirstTerminator(), DL,
                            NewInReg, Region->getEntry()->getNumber());
  // Need to be careful about updating the registers inside the region.
  LRegion->replaceRegisterInsideRegion(InReg, InnerSelectReg, false, MRI);
  LLVM_DEBUG(dbgs() << "Loop BBSelect Merge PHI:\n")do { } while (false);
  insertMergePHI(LRegion->getEntry(), LRegion->getExit(), NewSucc,
                 InnerSelectReg, NewInReg,
                 LRegion->getRegionMRT()->getInnerOutputRegister());
  splitExit(LRegion);
  TII->convertNonUniformLoopRegion(NewSucc, LastMerge);
}

if (Region->isRoot()) {
  TII->insertReturn(*LastMerge);
}

LLVM_DEBUG(Region->getEntry()->getParent()->dump())do { } while (false);
LLVM_DEBUG(LRegion->print(dbgs(), TRI))do { } while (false);
LLVM_DEBUG(PHIInfo.dump(MRI))do { } while (false);

LLVM_DEBUG(dbgs() << "===========If Region End===============\n")do { } while (false);

Region->setLinearizedRegion(LRegion);
return true;
2746}

2748bool AMDGPUMachineCFGStructurizer::structurizeRegion(RegionMRT *Region) {
if (false && regionIsSimpleIf(Region)) {
  transformSimpleIfRegion(Region);
  return true;
} else if (regionIsSequence(Region)) {
10
←
Taking false branch→
  fixupRegionExits(Region);
  return false;
} else {
  structurizeComplexRegion(Region);
11
←
Calling 'AMDGPUMachineCFGStructurizer::structurizeComplexRegion'→
}
return false;
2759}

2761static int structurize_once = 0;

2763bool AMDGPUMachineCFGStructurizer::structurizeRegions(RegionMRT *Region,
                                              bool isTopRegion) {
bool Changed = false;

auto Children = Region->getChildren();
for (auto CI : *Children) {
  if (CI->isRegion()) {
6
←
Taking true branch→
    Changed |= structurizeRegions(CI->getRegionMRT(), false);
7
←
Calling 'AMDGPUMachineCFGStructurizer::structurizeRegions'→
  }
}

if (structurize_once < 2 || true) {
8
←
Assuming 'structurize_once' is < 2→
  Changed |= structurizeRegion(Region);
9
←
Calling 'AMDGPUMachineCFGStructurizer::structurizeRegion'→
  structurize_once++;
}
return Changed;
2779}

2781void AMDGPUMachineCFGStructurizer::initFallthroughMap(MachineFunction &MF) {
LLVM_DEBUG(dbgs() << "Fallthrough Map:\n")do { } while (false);
for (auto &MBBI : MF) {
  MachineBasicBlock *MBB = MBBI.getFallThrough();
  if (MBB != nullptr) {
    LLVM_DEBUG(dbgs() << "Fallthrough: " << MBBI.getNumber() << " -> "do { } while (false)
                      << MBB->getNumber() << "\n")do { } while (false);
  }
  FallthroughMap[&MBBI] = MBB;
}
2791}

2793void AMDGPUMachineCFGStructurizer::createLinearizedRegion(RegionMRT *Region,
                                                  unsigned SelectOut) {
LinearizedRegion *LRegion = new LinearizedRegion();
if (SelectOut) {
  LRegion->addLiveOut(SelectOut);
  LLVM_DEBUG(dbgs() << "Add LiveOut (BBSelect): " << printReg(SelectOut, TRI)do { } while (false)
                    << "\n")do { } while (false);
}
LRegion->setRegionMRT(Region);
Region->setLinearizedRegion(LRegion);
LRegion->setParent(Region->getParent()
                       ? Region->getParent()->getLinearizedRegion()
                       : nullptr);
2806}

2808unsigned
2809AMDGPUMachineCFGStructurizer::initializeSelectRegisters(MRT *MRT, unsigned SelectOut,
                                                MachineRegisterInfo *MRI,
                                                const SIInstrInfo *TII) {
if (MRT->isRegion()) {
  RegionMRT *Region = MRT->getRegionMRT();
  Region->setBBSelectRegOut(SelectOut);
  unsigned InnerSelectOut = createBBSelectReg(TII, MRI);

  // Fixme: Move linearization creation to the original spot
  createLinearizedRegion(Region, SelectOut);

  for (auto CI = Region->getChildren()->begin(),
            CE = Region->getChildren()->end();
       CI != CE; ++CI) {
    InnerSelectOut =
        initializeSelectRegisters((*CI), InnerSelectOut, MRI, TII);
  }
  MRT->setBBSelectRegIn(InnerSelectOut);
  return InnerSelectOut;
} else {
  MRT->setBBSelectRegOut(SelectOut);
  unsigned NewSelectIn = createBBSelectReg(TII, MRI);
  MRT->setBBSelectRegIn(NewSelectIn);
  return NewSelectIn;
}
2834}

2836static void checkRegOnlyPHIInputs(MachineFunction &MF) {
for (auto &MBBI : MF) {
  for (MachineBasicBlock::instr_iterator I = MBBI.instr_begin(),
                                         E = MBBI.instr_end();
       I != E; ++I) {
    MachineInstr &Instr = *I;
    if (Instr.isPHI()) {
      int numPreds = getPHINumInputs(Instr);
      for (int i = 0; i < numPreds; ++i) {
        assert(Instr.getOperand(i * 2 + 1).isReg() &&(static_cast<void> (0))
               "PHI Operand not a register")(static_cast<void> (0));
      }
    }
  }
}
2851}

2853bool AMDGPUMachineCFGStructurizer::runOnMachineFunction(MachineFunction &MF) {
const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
const SIInstrInfo *TII = ST.getInstrInfo();
TRI = ST.getRegisterInfo();
MRI = &(MF.getRegInfo());
initFallthroughMap(MF);

checkRegOnlyPHIInputs(MF);
LLVM_DEBUG(dbgs() << "----STRUCTURIZER START----\n")do { } while (false);
1
Loop condition is false.  Exiting loop→
LLVM_DEBUG(MF.dump())do { } while (false);
2
←
Loop condition is false.  Exiting loop→

Regions = &(getAnalysis<MachineRegionInfoPass>().getRegionInfo());
LLVM_DEBUG(Regions->dump())do { } while (false);
3
←
Loop condition is false.  Exiting loop→

RegionMRT *RTree = MRT::buildMRT(MF, Regions, TII, MRI);
setRegionMRT(RTree);
initializeSelectRegisters(RTree, 0, MRI, TII);
LLVM_DEBUG(RTree->dump(TRI))do { } while (false);
4
←
Loop condition is false.  Exiting loop→
bool result = structurizeRegions(RTree, true);
5
←
Calling 'AMDGPUMachineCFGStructurizer::structurizeRegions'→
delete RTree;
LLVM_DEBUG(dbgs() << "----STRUCTURIZER END----\n")do { } while (false);
initFallthroughMap(MF);
return result;
2876}

2878char AMDGPUMachineCFGStructurizerID = AMDGPUMachineCFGStructurizer::ID;

2880INITIALIZE_PASS_BEGIN(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",static void *initializeAMDGPUMachineCFGStructurizerPassOnce(PassRegistry
 &Registry) {
                    "AMDGPU Machine CFG Structurizer", false, false)static void *initializeAMDGPUMachineCFGStructurizerPassOnce(PassRegistry
 &Registry) {
2882INITIALIZE_PASS_DEPENDENCY(MachineRegionInfoPass)initializeMachineRegionInfoPassPass(Registry);
2883INITIALIZE_PASS_END(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",PassInfo *PI = new PassInfo( "AMDGPU Machine CFG Structurizer"
, "amdgpu-machine-cfg-structurizer", &AMDGPUMachineCFGStructurizer
::ID, PassInfo::NormalCtor_t(callDefaultCtor<AMDGPUMachineCFGStructurizer
>), false, false); Registry.registerPass(*PI, true); return
 PI; } static llvm::once_flag InitializeAMDGPUMachineCFGStructurizerPassFlag
; void llvm::initializeAMDGPUMachineCFGStructurizerPass(PassRegistry
 &Registry) { llvm::call_once(InitializeAMDGPUMachineCFGStructurizerPassFlag
, initializeAMDGPUMachineCFGStructurizerPassOnce, std::ref(Registry
)); }
                  "AMDGPU Machine CFG Structurizer", false, false)PassInfo *PI = new PassInfo( "AMDGPU Machine CFG Structurizer"
, "amdgpu-machine-cfg-structurizer", &AMDGPUMachineCFGStructurizer
::ID, PassInfo::NormalCtor_t(callDefaultCtor<AMDGPUMachineCFGStructurizer
>), false, false); Registry.registerPass(*PI, true); return
 PI; } static llvm::once_flag InitializeAMDGPUMachineCFGStructurizerPassFlag
; void llvm::initializeAMDGPUMachineCFGStructurizerPass(PassRegistry
 &Registry) { llvm::call_once(InitializeAMDGPUMachineCFGStructurizerPassFlag
, initializeAMDGPUMachineCFGStructurizerPassOnce, std::ref(Registry
)); }

2886FunctionPass *llvm::createAMDGPUMachineCFGStructurizerPass() {
return new AMDGPUMachineCFGStructurizer();
2888}

←

/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/stl_iterator.h

1// Iterators -*- C++ -*-

3// Copyright (C) 2001-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.

20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.

25/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.  Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose.  It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996-1998
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.  Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose.  It is provided "as is" without express or implied warranty.
*/

51/** @file bits/stl_iterator.h
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{iterator}
*
*  This file implements reverse_iterator, back_insert_iterator,
*  front_insert_iterator, insert_iterator, __normal_iterator, and their
*  supporting functions and overloaded operators.
*/

60#ifndef _STL_ITERATOR_H1
61#define _STL_ITERATOR_H1 1

63#include <bits/cpp_type_traits.h>
64#include <ext/type_traits.h>
65#include <bits/move.h>
66#include <bits/ptr_traits.h>

68#if __cplusplus201402L >= 201103L
69# include <type_traits>
70#endif

72#if __cplusplus201402L > 201703L
73# define __cpp_lib_array_constexpr 201811L
74# define __cpp_lib_constexpr_iterator 201811L
75#elif __cplusplus201402L == 201703L
76# define __cpp_lib_array_constexpr 201803L
77#endif

79#if __cplusplus201402L > 201703L
80# include <compare>
81# include <new>
82# include <bits/iterator_concepts.h>
83#endif

85namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
86{
87_GLIBCXX_BEGIN_NAMESPACE_VERSION

/**
 * @addtogroup iterators
 * @{
 */

94#if __cplusplus201402L > 201703L && __cpp_lib_concepts
namespace __detail
{
  // Weaken iterator_category _Cat to _Limit if it is derived from that,
  // otherwise use _Otherwise.
  template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
    using __clamp_iter_cat
= conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
}
103#endif

// 24.4.1 Reverse iterators
/**
 *  Bidirectional and random access iterators have corresponding reverse
 *  %iterator adaptors that iterate through the data structure in the
 *  opposite direction.  They have the same signatures as the corresponding
 *  iterators.  The fundamental relation between a reverse %iterator and its
 *  corresponding %iterator @c i is established by the identity:
 *  @code
 *      &*(reverse_iterator(i)) == &*(i - 1)
 *  @endcode
 *
 *  <em>This mapping is dictated by the fact that while there is always a
 *  pointer past the end of an array, there might not be a valid pointer
 *  before the beginning of an array.</em> [24.4.1]/1,2
 *
 *  Reverse iterators can be tricky and surprising at first.  Their
 *  semantics make sense, however, and the trickiness is a side effect of
 *  the requirement that the iterators must be safe.
*/
template<typename _Iterator>
  class reverse_iterator
  : public iterator<typename iterator_traits<_Iterator>::iterator_category,
      typename iterator_traits<_Iterator>::value_type,
      typename iterator_traits<_Iterator>::difference_type,
      typename iterator_traits<_Iterator>::pointer,
                    typename iterator_traits<_Iterator>::reference>
  {
  protected:
    _Iterator current;

    typedef iterator_traits<_Iterator>		__traits_type;

  public:
    typedef _Iterator					iterator_type;
    typedef typename __traits_type::difference_type	difference_type;
    typedef typename __traits_type::pointer		pointer;
    typedef typename __traits_type::reference		reference;

143#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    using iterator_concept
= conditional_t<random_access_iterator<_Iterator>,
	random_access_iterator_tag,
	bidirectional_iterator_tag>;
    using iterator_category
= __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
		     random_access_iterator_tag>;
151#endif

    /**
     *  The default constructor value-initializes member @p current.
     *  If it is a pointer, that means it is zero-initialized.
    */
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 235 No specification of default ctor for reverse_iterator
    // 1012. reverse_iterator default ctor should value initialize
    _GLIBCXX17_CONSTEXPR
    reverse_iterator() : current() { }

    /**
     *  This %iterator will move in the opposite direction that @p x does.
    */
    explicit _GLIBCXX17_CONSTEXPR
    reverse_iterator(iterator_type __x) : current(__x) { }

    /**
     *  The copy constructor is normal.
    */
    _GLIBCXX17_CONSTEXPR
    reverse_iterator(const reverse_iterator& __x)
    : current(__x.current) { }

176#if __cplusplus201402L >= 201103L
    reverse_iterator& operator=(const reverse_iterator&) = default;
178#endif

    /**
     *  A %reverse_iterator across other types can be copied if the
     *  underlying %iterator can be converted to the type of @c current.
    */
    template<typename _Iter>
_GLIBCXX17_CONSTEXPR
      reverse_iterator(const reverse_iterator<_Iter>& __x)
: current(__x.base()) { }

    /**
     *  @return  @c current, the %iterator used for underlying work.
    */
    _GLIBCXX17_CONSTEXPR iterator_type
    base() const
    { return current; }

    /**
     *  @return  A reference to the value at @c --current
     *
     *  This requires that @c --current is dereferenceable.
     *
     *  @warning This implementation requires that for an iterator of the
     *           underlying iterator type, @c x, a reference obtained by
     *           @c *x remains valid after @c x has been modified or
     *           destroyed. This is a bug: http://gcc.gnu.org/PR51823
    */
    _GLIBCXX17_CONSTEXPR reference
    operator*() const
    {
_Iterator __tmp = current;
return *--__tmp;
    }

    /**
     *  @return  A pointer to the value at @c --current
     *
     *  This requires that @c --current is dereferenceable.
    */
    _GLIBCXX17_CONSTEXPR pointer
    operator->() const
220#if __cplusplus201402L > 201703L && __cpp_concepts >= 201907L
    requires is_pointer_v<_Iterator>
|| requires(const _Iterator __i) { __i.operator->(); }
223#endif
    {
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 1052. operator-> should also support smart pointers
_Iterator __tmp = current;
--__tmp;
return _S_to_pointer(__tmp);
    }

    /**
     *  @return  @c *this
     *
     *  Decrements the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator&
    operator++()
    {
--current;
return *this;
    }

    /**
     *  @return  The original value of @c *this
     *
     *  Decrements the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator
    operator++(int)
    {
reverse_iterator __tmp = *this;
--current;
return __tmp;
    }

    /**
     *  @return  @c *this
     *
     *  Increments the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator&
    operator--()
    {
++current;
return *this;
    }

    /**
     *  @return  A reverse_iterator with the previous value of @c *this
     *
     *  Increments the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator
    operator--(int)
    {
reverse_iterator __tmp = *this;
++current;
return __tmp;
    }

    /**
     *  @return  A reverse_iterator that refers to @c current - @a __n
     *
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator
    operator+(difference_type __n) const
    { return reverse_iterator(current - __n); }

    /**
     *  @return  *this
     *
     *  Moves the underlying iterator backwards @a __n steps.
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator&
    operator+=(difference_type __n)
    {
current -= __n;
return *this;
    }

    /**
     *  @return  A reverse_iterator that refers to @c current - @a __n
     *
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator
    operator-(difference_type __n) const
    { return reverse_iterator(current + __n); }

    /**
     *  @return  *this
     *
     *  Moves the underlying iterator forwards @a __n steps.
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator&
    operator-=(difference_type __n)
    {
current += __n;
return *this;
    }

    /**
     *  @return  The value at @c current - @a __n - 1
     *
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPR reference
    operator[](difference_type __n) const
    { return *(*this + __n); }

335#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    friend constexpr iter_rvalue_reference_t<_Iterator>
    iter_move(const reverse_iterator& __i)
    noexcept(is_nothrow_copy_constructible_v<_Iterator>
      && noexcept(ranges::iter_move(--std::declval<_Iterator&>())))
    {
auto __tmp = __i.base();
return ranges::iter_move(--__tmp);
    }

    template<indirectly_swappable<_Iterator> _Iter2>
friend constexpr void
iter_swap(const reverse_iterator& __x,
  const reverse_iterator<_Iter2>& __y)
noexcept(is_nothrow_copy_constructible_v<_Iterator>
 && is_nothrow_copy_constructible_v<_Iter2>
 && noexcept(ranges::iter_swap(--std::declval<_Iterator&>(),
			       --std::declval<_Iter2&>())))
{
 auto __xtmp = __x.base();
 auto __ytmp = __y.base();
 ranges::iter_swap(--__xtmp, --__ytmp);
}
358#endif

  private:
    template<typename _Tp>
static _GLIBCXX17_CONSTEXPR _Tp*
_S_to_pointer(_Tp* __p)
      { return __p; }

    template<typename _Tp>
static _GLIBCXX17_CONSTEXPR pointer
_S_to_pointer(_Tp __t)
      { return __t.operator->(); }
  };

//@{
/**
 *  @param  __x  A %reverse_iterator.
 *  @param  __y  A %reverse_iterator.
 *  @return  A simple bool.
 *
 *  Reverse iterators forward comparisons to their underlying base()
 *  iterators.
 *
*/
382#if __cplusplus201402L <= 201703L || ! defined __cpp_lib_concepts
template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator==(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return __x.base() == __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<(const reverse_iterator<_Iterator>& __x,
     const reverse_iterator<_Iterator>& __y)
  { return __y.base() < __x.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator!=(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return !(__x == __y); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>(const reverse_iterator<_Iterator>& __x,
     const reverse_iterator<_Iterator>& __y)
  { return __y < __x; }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<=(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return !(__y < __x); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>=(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return !(__x < __y); }

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 280. Comparison of reverse_iterator to const reverse_iterator.
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator==(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return __x.base() == __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  { return __y.base() < __x.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator!=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return !(__x == __y); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  { return __y < __x; }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return !(__y < __x); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return !(__x < __y); }
456#else // C++20
template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator==(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
  { return __x.base() == __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator!=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
  { return __x.base() != __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator<(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
  { return __x.base() > __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator>(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
  { return __x.base() < __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator<=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
  { return __x.base() >= __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator>=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
  { return __x.base() <= __y.base(); }

template<typename _IteratorL,
  three_way_comparable_with<_IteratorL> _IteratorR>
  constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
  operator<=>(const reverse_iterator<_IteratorL>& __x,
const reverse_iterator<_IteratorR>& __y)
  { return __y.base() <=> __x.base(); }
505#endif // C++20
//@}

508#if __cplusplus201402L < 201103L
template<typename _Iterator>
  inline typename reverse_iterator<_Iterator>::difference_type
  operator-(const reverse_iterator<_Iterator>& __x,
     const reverse_iterator<_Iterator>& __y)
  { return __y.base() - __x.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline typename reverse_iterator<_IteratorL>::difference_type
  operator-(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  { return __y.base() - __x.base(); }
520#else
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 685. reverse_iterator/move_iterator difference has invalid signatures
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR auto
  operator-(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  -> decltype(__y.base() - __x.base())
  { return __y.base() - __x.base(); }
529#endif

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
  operator+(typename reverse_iterator<_Iterator>::difference_type __n,
     const reverse_iterator<_Iterator>& __x)
  { return reverse_iterator<_Iterator>(__x.base() - __n); }

537#if __cplusplus201402L >= 201103L
// Same as C++14 make_reverse_iterator but used in C++11 mode too.
template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
  __make_reverse_iterator(_Iterator __i)
  { return reverse_iterator<_Iterator>(__i); }

544# if __cplusplus201402L >= 201402L
545#  define __cpp_lib_make_reverse_iterator201402 201402

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 2285. make_reverse_iterator
/// Generator function for reverse_iterator.
template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
  make_reverse_iterator(_Iterator __i)
  { return reverse_iterator<_Iterator>(__i); }

555#  if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
template<typename _Iterator1, typename _Iterator2>
  requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
  inline constexpr bool
  disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
	       reverse_iterator<_Iterator2>> = true;
561#  endif // C++20
562# endif // C++14

template<typename _Iterator>
  _GLIBCXX20_CONSTEXPR
  auto
  __niter_base(reverse_iterator<_Iterator> __it)
  -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
  { return __make_reverse_iterator(__niter_base(__it.base())); }

template<typename _Iterator>
  struct __is_move_iterator<reverse_iterator<_Iterator> >
    : __is_move_iterator<_Iterator>
  { };

template<typename _Iterator>
  _GLIBCXX20_CONSTEXPR
  auto
  __miter_base(reverse_iterator<_Iterator> __it)
  -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
  { return __make_reverse_iterator(__miter_base(__it.base())); }
582#endif // C++11

// 24.4.2.2.1 back_insert_iterator
/**
 *  @brief  Turns assignment into insertion.
 *
 *  These are output iterators, constructed from a container-of-T.
 *  Assigning a T to the iterator appends it to the container using
 *  push_back.
 *
 *  Tip:  Using the back_inserter function to create these iterators can
 *  save typing.
*/
template<typename _Container>
  class back_insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
  {
  protected:
    _Container* container;

  public:
    /// A nested typedef for the type of whatever container you used.
    typedef _Container          container_type;
605#if __cplusplus201402L > 201703L
    using difference_type = ptrdiff_t;

    constexpr back_insert_iterator() noexcept : container(nullptr) { }
609#endif

    /// The only way to create this %iterator is with a container.
    explicit _GLIBCXX20_CONSTEXPR
    back_insert_iterator(_Container& __x)
    : container(std::__addressof(__x)) { }

    /**
     *  @param  __value  An instance of whatever type
     *                 container_type::const_reference is; presumably a
     *                 reference-to-const T for container<T>.
     *  @return  This %iterator, for chained operations.
     *
     *  This kind of %iterator doesn't really have a @a position in the
     *  container (you can think of the position as being permanently at
     *  the end, if you like).  Assigning a value to the %iterator will
     *  always append the value to the end of the container.
    */
627#if __cplusplus201402L < 201103L
    back_insert_iterator&
    operator=(typename _Container::const_reference __value)
    {
container->push_back(__value);
return *this;
    }
634#else
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator=(const typename _Container::value_type& __value)
    {
container->push_back(__value);
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator=(typename _Container::value_type&& __value)
    {
container->push_back(std::move(__value));
return *this;
    }
650#endif

    /// Simply returns *this.
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator*()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator++()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator
    operator++(int)
    { return *this; }
  };

/**
 *  @param  __x  A container of arbitrary type.
 *  @return  An instance of back_insert_iterator working on @p __x.
 *
 *  This wrapper function helps in creating back_insert_iterator instances.
 *  Typing the name of the %iterator requires knowing the precise full
 *  type of the container, which can be tedious and impedes generic
 *  programming.  Using this function lets you take advantage of automatic
 *  template parameter deduction, making the compiler match the correct
 *  types for you.
*/
template<typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline back_insert_iterator<_Container>
  back_inserter(_Container& __x)
  { return back_insert_iterator<_Container>(__x); }

/**
 *  @brief  Turns assignment into insertion.
 *
 *  These are output iterators, constructed from a container-of-T.
 *  Assigning a T to the iterator prepends it to the container using
 *  push_front.
 *
 *  Tip:  Using the front_inserter function to create these iterators can
 *  save typing.
*/
template<typename _Container>
  class front_insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
  {
  protected:
    _Container* container;

  public:
    /// A nested typedef for the type of whatever container you used.
    typedef _Container          container_type;
708#if __cplusplus201402L > 201703L
    using difference_type = ptrdiff_t;

    constexpr front_insert_iterator() noexcept : container(nullptr) { }
712#endif

    /// The only way to create this %iterator is with a container.
    explicit _GLIBCXX20_CONSTEXPR
    front_insert_iterator(_Container& __x)
    : container(std::__addressof(__x)) { }

    /**
     *  @param  __value  An instance of whatever type
     *                 container_type::const_reference is; presumably a
     *                 reference-to-const T for container<T>.
     *  @return  This %iterator, for chained operations.
     *
     *  This kind of %iterator doesn't really have a @a position in the
     *  container (you can think of the position as being permanently at
     *  the front, if you like).  Assigning a value to the %iterator will
     *  always prepend the value to the front of the container.
    */
730#if __cplusplus201402L < 201103L
    front_insert_iterator&
    operator=(typename _Container::const_reference __value)
    {
container->push_front(__value);
return *this;
    }
737#else
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator=(const typename _Container::value_type& __value)
    {
container->push_front(__value);
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator=(typename _Container::value_type&& __value)
    {
container->push_front(std::move(__value));
return *this;
    }
753#endif

    /// Simply returns *this.
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator*()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator++()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator
    operator++(int)
    { return *this; }
  };

/**
 *  @param  __x  A container of arbitrary type.
 *  @return  An instance of front_insert_iterator working on @p x.
 *
 *  This wrapper function helps in creating front_insert_iterator instances.
 *  Typing the name of the %iterator requires knowing the precise full
 *  type of the container, which can be tedious and impedes generic
 *  programming.  Using this function lets you take advantage of automatic
 *  template parameter deduction, making the compiler match the correct
 *  types for you.
*/
template<typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline front_insert_iterator<_Container>
  front_inserter(_Container& __x)
  { return front_insert_iterator<_Container>(__x); }

/**
 *  @brief  Turns assignment into insertion.
 *
 *  These are output iterators, constructed from a container-of-T.
 *  Assigning a T to the iterator inserts it in the container at the
 *  %iterator's position, rather than overwriting the value at that
 *  position.
 *
 *  (Sequences will actually insert a @e copy of the value before the
 *  %iterator's position.)
 *
 *  Tip:  Using the inserter function to create these iterators can
 *  save typing.
*/
template<typename _Container>
  class insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
  {
809#if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
    using _Iter = std::__detail::__range_iter_t<_Container>;

  protected:
    _Container* container = nullptr;
    _Iter iter = _Iter();
815#else
    typedef typename _Container::iterator		_Iter;

  protected:
    _Container* container;
    _Iter iter;
821#endif

  public:
    /// A nested typedef for the type of whatever container you used.
    typedef _Container          container_type;

827#if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
    using difference_type = ptrdiff_t;

    insert_iterator() = default;
831#endif

    /**
     *  The only way to create this %iterator is with a container and an
     *  initial position (a normal %iterator into the container).
    */
    _GLIBCXX20_CONSTEXPR
    insert_iterator(_Container& __x, _Iter __i)
    : container(std::__addressof(__x)), iter(__i) {}

    /**
     *  @param  __value  An instance of whatever type
     *                 container_type::const_reference is; presumably a
     *                 reference-to-const T for container<T>.
     *  @return  This %iterator, for chained operations.
     *
     *  This kind of %iterator maintains its own position in the
     *  container.  Assigning a value to the %iterator will insert the
     *  value into the container at the place before the %iterator.
     *
     *  The position is maintained such that subsequent assignments will
     *  insert values immediately after one another.  For example,
     *  @code
     *     // vector v contains A and Z
     *
     *     insert_iterator i (v, ++v.begin());
     *     i = 1;
     *     i = 2;
     *     i = 3;
     *
     *     // vector v contains A, 1, 2, 3, and Z
     *  @endcode
    */
864#if __cplusplus201402L < 201103L
    insert_iterator&
    operator=(typename _Container::const_reference __value)
    {
iter = container->insert(iter, __value);
++iter;
return *this;
    }
872#else
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator=(const typename _Container::value_type& __value)
    {
iter = container->insert(iter, __value);
++iter;
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator=(typename _Container::value_type&& __value)
    {
iter = container->insert(iter, std::move(__value));
++iter;
return *this;
    }
890#endif

    /// Simply returns *this.
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator*()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator++()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator++(int)
    { return *this; }
  };

/**
 *  @param __x  A container of arbitrary type.
 *  @param __i  An iterator into the container.
 *  @return  An instance of insert_iterator working on @p __x.
 *
 *  This wrapper function helps in creating insert_iterator instances.
 *  Typing the name of the %iterator requires knowing the precise full
 *  type of the container, which can be tedious and impedes generic
 *  programming.  Using this function lets you take advantage of automatic
 *  template parameter deduction, making the compiler match the correct
 *  types for you.
*/
923#if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
template<typename _Container>
  constexpr insert_iterator<_Container>
  inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
  { return insert_iterator<_Container>(__x, __i); }
928#else
template<typename _Container, typename _Iterator>
  inline insert_iterator<_Container>
  inserter(_Container& __x, _Iterator __i)
  {
    return insert_iterator<_Container>(__x,
			 typename _Container::iterator(__i));
  }
936#endif

// @} group iterators

940_GLIBCXX_END_NAMESPACE_VERSION
941} // namespace

943namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
944{
945_GLIBCXX_BEGIN_NAMESPACE_VERSION

// This iterator adapter is @a normal in the sense that it does not
// change the semantics of any of the operators of its iterator
// parameter.  Its primary purpose is to convert an iterator that is
// not a class, e.g. a pointer, into an iterator that is a class.
// The _Container parameter exists solely so that different containers
// using this template can instantiate different types, even if the
// _Iterator parameter is the same.
template<typename _Iterator, typename _Container>
  class __normal_iterator
  {
  protected:
    _Iterator _M_current;

    typedef std::iterator_traits<_Iterator>		__traits_type;

  public:
    typedef _Iterator					iterator_type;
    typedef typename __traits_type::iterator_category iterator_category;
    typedef typename __traits_type::value_type  	value_type;
    typedef typename __traits_type::difference_type 	difference_type;
    typedef typename __traits_type::reference 	reference;
    typedef typename __traits_type::pointer   	pointer;

970#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    using iterator_concept = std::__detail::__iter_concept<_Iterator>;
972#endif

    _GLIBCXX_CONSTEXPRconstexpr __normal_iterator() _GLIBCXX_NOEXCEPTnoexcept
    : _M_current(_Iterator()) { }

    explicit _GLIBCXX20_CONSTEXPR
    __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPTnoexcept
    : _M_current(__i) { }

    // Allow iterator to const_iterator conversion
    template<typename _Iter>
      _GLIBCXX20_CONSTEXPR
      __normal_iterator(const __normal_iterator<_Iter,
	  typename __enable_if<
    	       (std::__are_same<_Iter, typename _Container::pointer>::__value),
      _Container>::__type>& __i) _GLIBCXX_NOEXCEPTnoexcept
      : _M_current(__i.base()) { }

    // Forward iterator requirements
    _GLIBCXX20_CONSTEXPR
    reference
    operator*() const _GLIBCXX_NOEXCEPTnoexcept
    { return *_M_current; }

    _GLIBCXX20_CONSTEXPR
    pointer
    operator->() const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_current; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator++() _GLIBCXX_NOEXCEPTnoexcept
    {
++_M_current;
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator++(int) _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current++); }

    // Bidirectional iterator requirements
    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator--() _GLIBCXX_NOEXCEPTnoexcept
    {
--_M_current;
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator--(int) _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current--); }

    // Random access iterator requirements
    _GLIBCXX20_CONSTEXPR
    reference
    operator[](difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_current[__n]; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator+=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
    { _M_current += __n; return *this; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator+(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current + __n); }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator-=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
    { _M_current -= __n; return *this; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator-(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current - __n); }

    _GLIBCXX20_CONSTEXPR
    const _Iterator&
    base() const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_current; }
  };

// Note: In what follows, the left- and right-hand-side iterators are
// allowed to vary in types (conceptually in cv-qualification) so that
// comparison between cv-qualified and non-cv-qualified iterators be
// valid.  However, the greedy and unfriendly operators in std::rel_ops
// will make overload resolution ambiguous (when in scope) if we don't
// provide overloads whose operands are of the same type.  Can someone
// remind me what generic programming is about? -- Gaby

1068#if __cpp_lib_three_way_comparison
template<typename _IteratorL, typename _IteratorR, typename _Container>
  requires requires (_IteratorL __lhs, _IteratorR __rhs)
  { { __lhs == __rhs } -> std::convertible_to<bool>; }
  constexpr bool
  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  noexcept(noexcept(__lhs.base() == __rhs.base()))
  { return __lhs.base() == __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
  operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
const __normal_iterator<_IteratorR, _Container>& __rhs)
  noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
  { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1084#else
 // Forward iterator requirements
template<typename _IteratorL, typename _IteratorR, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() == __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() == __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() != __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() != __rhs.base(); }
24
←
Assuming the condition is true→
25
←
Returning the value 1, which participates in a condition later→
60
←
Assuming the condition is true→
61
←
Returning the value 1, which participates in a condition later→

// Random access iterator requirements
template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() < __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
     const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() < __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() > __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
     const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() > __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() <= __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() <= __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() >= __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() >= __rhs.base(); }
1178#endif // three-way comparison

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// According to the resolution of DR179 not only the various comparison
// operators but also operator- must accept mixed iterator/const_iterator
// parameters.
template<typename _IteratorL, typename _IteratorR, typename _Container>
1185#if __cplusplus201402L >= 201103L
  // DR 685.
  _GLIBCXX20_CONSTEXPR
  inline auto
  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
  -> decltype(__lhs.base() - __rhs.base())
1192#else
  inline typename __normal_iterator<_IteratorL, _Container>::difference_type
  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs)
1196#endif
  { return __lhs.base() - __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline typename __normal_iterator<_Iterator, _Container>::difference_type
  operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
     const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() - __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline __normal_iterator<_Iterator, _Container>
  operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
     __n, const __normal_iterator<_Iterator, _Container>& __i)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }

1215_GLIBCXX_END_NAMESPACE_VERSION
1216} // namespace

1218namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
1219{
1220_GLIBCXX_BEGIN_NAMESPACE_VERSION

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  _Iterator
  __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
  _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)noexcept(std::is_nothrow_copy_constructible<_Iterator>::
value)
  { return __it.base(); }

1229#if __cplusplus201402L >= 201103L
/**
 * @addtogroup iterators
 * @{
 */

1235#if __cplusplus201402L > 201703L && __cpp_lib_concepts
template<semiregular _Sent>
  class move_sentinel
  {
  public:
    constexpr
    move_sentinel()
    noexcept(is_nothrow_default_constructible_v<_Sent>)
    : _M_last() { }

    constexpr explicit
    move_sentinel(_Sent __s)
    noexcept(is_nothrow_move_constructible_v<_Sent>)
    : _M_last(std::move(__s)) { }

    template<typename _S2> requires convertible_to<const _S2&, _Sent>
constexpr
move_sentinel(const move_sentinel<_S2>& __s)
noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
: _M_last(__s.base())
{ }

    template<typename _S2> requires assignable_from<_Sent&, const _S2&>
constexpr move_sentinel&
operator=(const move_sentinel<_S2>& __s)
noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
{
 _M_last = __s.base();
 return *this;
}

    constexpr _Sent
    base() const
    noexcept(is_nothrow_copy_constructible_v<_Sent>)
    { return _M_last; }

  private:
    _Sent _M_last;
  };
1274#endif // C++20

// 24.4.3  Move iterators
/**
 *  Class template move_iterator is an iterator adapter with the same
 *  behavior as the underlying iterator except that its dereference
 *  operator implicitly converts the value returned by the underlying
 *  iterator's dereference operator to an rvalue reference.  Some
 *  generic algorithms can be called with move iterators to replace
 *  copying with moving.
 */
template<typename _Iterator>
  class move_iterator
  {
    _Iterator _M_current;

    using __traits_type = iterator_traits<_Iterator>;
1291#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    using __base_cat = typename __traits_type::iterator_category;
1293#else
    using __base_ref = typename __traits_type::reference;
1295#endif

  public:
    using iterator_type = _Iterator;

1300#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    using iterator_concept = input_iterator_tag;
    using iterator_category
= __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
    using value_type = iter_value_t<_Iterator>;
    using difference_type = iter_difference_t<_Iterator>;
    using pointer = _Iterator;
    using reference = iter_rvalue_reference_t<_Iterator>;
1308#else
    typedef typename __traits_type::iterator_category iterator_category;
    typedef typename __traits_type::value_type  	value_type;
    typedef typename __traits_type::difference_type	difference_type;
    // NB: DR 680.
    typedef _Iterator					pointer;
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 2106. move_iterator wrapping iterators returning prvalues
    typedef typename conditional<is_reference<__base_ref>::value,
	 typename remove_reference<__base_ref>::type&&,
	 __base_ref>::type		reference;
1319#endif

    _GLIBCXX17_CONSTEXPR
    move_iterator()
    : _M_current() { }

    explicit _GLIBCXX17_CONSTEXPR
    move_iterator(iterator_type __i)
    : _M_current(std::move(__i)) { }

    template<typename _Iter>
_GLIBCXX17_CONSTEXPR
move_iterator(const move_iterator<_Iter>& __i)
: _M_current(__i.base()) { }

1334#if __cplusplus201402L <= 201703L
    _GLIBCXX17_CONSTEXPR iterator_type
    base() const
    { return _M_current; }
1338#else
    constexpr iterator_type
    base() const &
1341#if __cpp_lib_concepts
requires copy_constructible<iterator_type>
1343#endif
    { return _M_current; }

    constexpr iterator_type
    base() &&
    { return std::move(_M_current); }
1349#endif

    _GLIBCXX17_CONSTEXPR reference
    operator*() const
1353#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    { return ranges::iter_move(_M_current); }
1355#else
    { return static_cast<reference>(*_M_current); }
1357#endif

    _GLIBCXX17_CONSTEXPR pointer
    operator->() const
    { return _M_current; }

    _GLIBCXX17_CONSTEXPR move_iterator&
    operator++()
    {
++_M_current;
return *this;
    }

    _GLIBCXX17_CONSTEXPR move_iterator
    operator++(int)
    {
move_iterator __tmp = *this;
++_M_current;
return __tmp;
    }

1378#if __cpp_lib_concepts
    constexpr void
    operator++(int) requires (!forward_iterator<_Iterator>)
    { ++_M_current; }
1382#endif

    _GLIBCXX17_CONSTEXPR move_iterator&
    operator--()
    {
--_M_current;
return *this;
    }

    _GLIBCXX17_CONSTEXPR move_iterator
    operator--(int)
    {
move_iterator __tmp = *this;
--_M_current;
return __tmp;
    }

    _GLIBCXX17_CONSTEXPR move_iterator
    operator+(difference_type __n) const
    { return move_iterator(_M_current + __n); }

    _GLIBCXX17_CONSTEXPR move_iterator&
    operator+=(difference_type __n)
    {
_M_current += __n;
return *this;
    }

    _GLIBCXX17_CONSTEXPR move_iterator
    operator-(difference_type __n) const
    { return move_iterator(_M_current - __n); }
  
    _GLIBCXX17_CONSTEXPR move_iterator&
    operator-=(difference_type __n)
    { 
_M_current -= __n;
return *this;
    }

    _GLIBCXX17_CONSTEXPR reference
    operator[](difference_type __n) const
1423#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    { return ranges::iter_move(_M_current + __n); }
1425#else
    { return std::move(_M_current[__n]); }
1427#endif

1429#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    template<sentinel_for<_Iterator> _Sent>
friend constexpr bool
operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
{ return __x.base() == __y.base(); }

    template<sized_sentinel_for<_Iterator> _Sent>
friend constexpr iter_difference_t<_Iterator>
operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
{ return __x.base() - __y.base(); }

    template<sized_sentinel_for<_Iterator> _Sent>
friend constexpr iter_difference_t<_Iterator>
operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
{ return __x.base() - __y.base(); }

    friend constexpr iter_rvalue_reference_t<_Iterator>
    iter_move(const move_iterator& __i)
    noexcept(noexcept(ranges::iter_move(__i._M_current)))
    { return ranges::iter_move(__i._M_current); }

    template<indirectly_swappable<_Iterator> _Iter2>
friend constexpr void
iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
{ return ranges::iter_swap(__x._M_current, __y._M_current); }
1455#endif // C++20
  };

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator==(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
1462#if __cplusplus201402L > 201703L && __cpp_lib_concepts
  requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1464#endif
  { return __x.base() == __y.base(); }

1467#if __cpp_lib_three_way_comparison
template<typename _IteratorL,
  three_way_comparable_with<_IteratorL> _IteratorR>
  constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
  operator<=>(const move_iterator<_IteratorL>& __x,
const move_iterator<_IteratorR>& __y)
  { return __x.base() <=> __y.base(); }
1474#else
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator!=(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
  { return !(__x == __y); }
1480#endif

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<(const move_iterator<_IteratorL>& __x,
     const move_iterator<_IteratorR>& __y)
1486#if __cplusplus201402L > 201703L && __cpp_lib_concepts
  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1488#endif
  { return __x.base() < __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<=(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
1495#if __cplusplus201402L > 201703L && __cpp_lib_concepts
  requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1497#endif
  { return !(__y < __x); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>(const move_iterator<_IteratorL>& __x,
     const move_iterator<_IteratorR>& __y)
1504#if __cplusplus201402L > 201703L && __cpp_lib_concepts
  requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1506#endif
  { return __y < __x; }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>=(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
1513#if __cplusplus201402L > 201703L && __cpp_lib_concepts
  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1515#endif
  { return !(__x < __y); }

1518#if ! (__cplusplus201402L > 201703L && __cpp_lib_concepts)
// Note: See __normal_iterator operators note from Gaby to understand
// why we have these extra overloads for some move_iterator operators.

// These extra overloads are not needed in C++20, because the ones above
// are constrained with a requires-clause and so overload resolution will
// prefer them to greedy unconstrained function templates.

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator==(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return __x.base() == __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator!=(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return !(__x == __y); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<(const move_iterator<_Iterator>& __x,
     const move_iterator<_Iterator>& __y)
  { return __x.base() < __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<=(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return !(__y < __x); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>(const move_iterator<_Iterator>& __x,
     const move_iterator<_Iterator>& __y)
  { return __y < __x; }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>=(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return !(__x < __y); }
1561#endif // ! C++20

// DR 685.
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR auto
  operator-(const move_iterator<_IteratorL>& __x,
     const move_iterator<_IteratorR>& __y)
  -> decltype(__x.base() - __y.base())
  { return __x.base() - __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
  operator+(typename move_iterator<_Iterator>::difference_type __n,
     const move_iterator<_Iterator>& __x)
  { return __x + __n; }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
  make_move_iterator(_Iterator __i)
  { return move_iterator<_Iterator>(std::move(__i)); }

template<typename _Iterator, typename _ReturnType
  = typename conditional<__move_if_noexcept_cond
    <typename iterator_traits<_Iterator>::value_type>::value,
              _Iterator, move_iterator<_Iterator>>::type>
  inline _GLIBCXX17_CONSTEXPR _ReturnType
  __make_move_if_noexcept_iterator(_Iterator __i)
  { return _ReturnType(__i); }

// Overload for pointers that matches std::move_if_noexcept more closely,
// returning a constant iterator when we don't want to move.
template<typename _Tp, typename _ReturnType
  = typename conditional<__move_if_noexcept_cond<_Tp>::value,
	   const _Tp*, move_iterator<_Tp*>>::type>
  inline _GLIBCXX17_CONSTEXPR _ReturnType
  __make_move_if_noexcept_iterator(_Tp* __i)
  { return _ReturnType(__i); }

1599#if __cplusplus201402L > 201703L && __cpp_lib_concepts
// [iterators.common] Common iterators

namespace __detail
{
  template<typename _It>
    concept __common_iter_has_arrow = indirectly_readable<const _It>
&& (requires(const _It& __it) { __it.operator->(); }
   || is_reference_v<iter_reference_t<_It>>
   || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);

} // namespace __detail

/// An iterator/sentinel adaptor for representing a non-common range.
template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
  requires (!same_as<_It, _Sent>) && copyable<_It>
class common_iterator
{
  template<typename _Tp, typename _Up>
    static constexpr bool
    _S_noexcept1()
    {
if constexpr (is_trivially_default_constructible_v<_Tp>)
 return is_nothrow_assignable_v<_Tp, _Up>;
else
 return is_nothrow_constructible_v<_Tp, _Up>;
    }

  template<typename _It2, typename _Sent2>
    static constexpr bool
    _S_noexcept()
    { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }

  class _Proxy
  {
    iter_value_t<_It> _M_keep;

    _Proxy(iter_reference_t<_It>&& __x)
    : _M_keep(std::move(__x)) { }

    friend class common_iterator;

  public:
    const iter_value_t<_It>*
    operator->() const
    { return std::__addressof(_M_keep); }
  };

public:
  constexpr
  common_iterator()
  noexcept(is_nothrow_default_constructible_v<_It>)
  : _M_it(), _M_index(0)
  { }

  constexpr
  common_iterator(_It __i)
  noexcept(is_nothrow_move_constructible_v<_It>)
  : _M_it(std::move(__i)), _M_index(0)
  { }

  constexpr
  common_iterator(_Sent __s)
  noexcept(is_nothrow_move_constructible_v<_Sent>)
  : _M_sent(std::move(__s)), _M_index(1)
  { }

  template<typename _It2, typename _Sent2>
    requires convertible_to<const _It2&, _It>
&& convertible_to<const _Sent2&, _Sent>
    constexpr
    common_iterator(const common_iterator<_It2, _Sent2>& __x)
    noexcept(_S_noexcept<const _It2&, const _Sent2&>())
    : _M_valueless(), _M_index(__x._M_index)
    {
if (_M_index == 0)
 {
   if constexpr (is_trivially_default_constructible_v<_It>)
     _M_it = std::move(__x._M_it);
   else
     ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
 }
else if (_M_index == 1)
 {
   if constexpr (is_trivially_default_constructible_v<_Sent>)
     _M_sent = std::move(__x._M_sent);
   else
     ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
 }
    }

  constexpr
  common_iterator(const common_iterator& __x)
  noexcept(_S_noexcept<const _It&, const _Sent&>())
  : _M_valueless(), _M_index(__x._M_index)
  {
    if (_M_index == 0)
{
 if constexpr (is_trivially_default_constructible_v<_It>)
   _M_it = std::move(__x._M_it);
 else
   ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
}
    else if (_M_index == 1)
{
 if constexpr (is_trivially_default_constructible_v<_Sent>)
   _M_sent = std::move(__x._M_sent);
 else
   ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
}
  }

  common_iterator&
  operator=(const common_iterator& __x)
  noexcept(is_nothrow_copy_assignable_v<_It>
    && is_nothrow_copy_assignable_v<_Sent>
    && is_nothrow_copy_constructible_v<_It>
    && is_nothrow_copy_constructible_v<_Sent>)
  {
    return this->operator=<_It, _Sent>(__x);
  }

  template<typename _It2, typename _Sent2>
    requires convertible_to<const _It2&, _It>
&& convertible_to<const _Sent2&, _Sent>
&& assignable_from<_It&, const _It2&>
&& assignable_from<_Sent&, const _Sent2&>
    common_iterator&
    operator=(const common_iterator<_It2, _Sent2>& __x)
    noexcept(is_nothrow_constructible_v<_It, const _It2&>
      && is_nothrow_constructible_v<_Sent, const _Sent2&>
      && is_nothrow_assignable_v<_It, const _It2&>
      && is_nothrow_assignable_v<_Sent, const _Sent2&>)
    {
switch(_M_index << 2 | __x._M_index)
 {
 case 0b0000:
   _M_it = __x._M_it;
   break;
 case 0b0101:
   _M_sent = __x._M_sent;
   break;
 case 0b0001:
   _M_it.~_It();
   _M_index = -1;
   [[fallthrough]];
 case 0b1001:
   ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
   _M_index = 1;
   break;
 case 0b0100:
   _M_sent.~_Sent();
   _M_index = -1;
   [[fallthrough]];
 case 0b1000:
   ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
   _M_index = 0;
   break;
 default:
   __glibcxx_assert(__x._M_has_value());
   __builtin_unreachable();
 }
return *this;
    }

  ~common_iterator()
  {
    switch (_M_index)
{
case 0:
 _M_it.~_It();
 break;
case 1:
 _M_sent.~_Sent();
 break;
}
  }

  decltype(auto)
  operator*()
  {
    __glibcxx_assert(_M_index == 0);
    return *_M_it;
  }

  decltype(auto)
  operator*() const requires __detail::__dereferenceable<const _It>
  {
    __glibcxx_assert(_M_index == 0);
    return *_M_it;
  }

  decltype(auto)
  operator->() const requires __detail::__common_iter_has_arrow<_It>
  {
    __glibcxx_assert(_M_index == 0);
    if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
return _M_it;
    else if constexpr (is_reference_v<iter_reference_t<_It>>)
{
 auto&& __tmp = *_M_it;
 return std::__addressof(__tmp);
}
    else
return _Proxy{*_M_it};
  }

  common_iterator&
  operator++()
  {
    __glibcxx_assert(_M_index == 0);
    ++_M_it;
    return *this;
  }

  decltype(auto)
  operator++(int)
  {
    __glibcxx_assert(_M_index == 0);
    if constexpr (forward_iterator<_It>)
{
 common_iterator __tmp = *this;
 ++*this;
 return __tmp;
}
    else
return _M_it++;
  }

  template<typename _It2, sentinel_for<_It> _Sent2>
    requires sentinel_for<_Sent, _It2>
    friend bool
    operator==(const common_iterator& __x,
 const common_iterator<_It2, _Sent2>& __y)
    {
switch(__x._M_index << 2 | __y._M_index)
 {
 case 0b0000:
 case 0b0101:
   return true;
 case 0b0001:
   return __x._M_it == __y._M_sent;
 case 0b0100:
   return __x._M_sent == __y._M_it;
 default:
   __glibcxx_assert(__x._M_has_value());
   __glibcxx_assert(__y._M_has_value());
   __builtin_unreachable();
 }
    }

  template<typename _It2, sentinel_for<_It> _Sent2>
    requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
    friend bool
    operator==(const common_iterator& __x,
 const common_iterator<_It2, _Sent2>& __y)
    {
switch(__x._M_index << 2 | __y._M_index)
 {
 case 0b0101:
   return true;
 case 0b0000:
   return __x._M_it == __y._M_it;
 case 0b0001:
   return __x._M_it == __y._M_sent;
 case 0b0100:
   return __x._M_sent == __y._M_it;
 default:
   __glibcxx_assert(__x._M_has_value());
   __glibcxx_assert(__y._M_has_value());
   __builtin_unreachable();
 }
    }

  template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
    requires sized_sentinel_for<_Sent, _It2>
    friend iter_difference_t<_It2>
    operator-(const common_iterator& __x,
const common_iterator<_It2, _Sent2>& __y)
    {
switch(__x._M_index << 2 | __y._M_index)
 {
 case 0b0101:
   return 0;
 case 0b0000:
   return __x._M_it - __y._M_it;
 case 0b0001:
   return __x._M_it - __y._M_sent;
 case 0b0100:
   return __x._M_sent - __y._M_it;
 default:
   __glibcxx_assert(__x._M_has_value());
   __glibcxx_assert(__y._M_has_value());
   __builtin_unreachable();
 }
    }

  friend iter_rvalue_reference_t<_It>
  iter_move(const common_iterator& __i)
  noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
  requires input_iterator<_It>
  {
    __glibcxx_assert(__i._M_index == 0);
    return ranges::iter_move(__i._M_it);
  }

  template<indirectly_swappable<_It> _It2, typename _Sent2>
    friend void
    iter_swap(const common_iterator& __x,
const common_iterator<_It2, _Sent2>& __y)
    noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
			  std::declval<const _It2&>())))
    {
__glibcxx_assert(__x._M_index == 0);
__glibcxx_assert(__y._M_index == 0);
return ranges::iter_swap(__x._M_it, __y._M_it);
    }

private:
  template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
    friend class common_iterator;

  bool _M_has_value() const noexcept { return _M_index < 2; }

  union
  {
    _It _M_it;
    _Sent _M_sent;
    unsigned char _M_valueless;
  };
  unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless
};

template<typename _It, typename _Sent>
  struct incrementable_traits<common_iterator<_It, _Sent>>
  {
    using difference_type = iter_difference_t<_It>;
  };

template<input_iterator _It, typename _Sent>
  struct iterator_traits<common_iterator<_It, _Sent>>
  {
  private:
    template<typename _Iter>
struct __ptr
{
 using type = void;
};

    template<typename _Iter>
requires __detail::__common_iter_has_arrow<_Iter>
struct __ptr<_Iter>
{
 using _CIter = common_iterator<_Iter, _Sent>;
 using type = decltype(std::declval<const _CIter&>().operator->());
};

  public:
    using iterator_concept = conditional_t<forward_iterator<_It>,
   forward_iterator_tag, input_iterator_tag>;
    using iterator_category = __detail::__clamp_iter_cat<
typename iterator_traits<_It>::iterator_category,
forward_iterator_tag, input_iterator_tag>;
    using value_type = iter_value_t<_It>;
    using difference_type = iter_difference_t<_It>;
    using pointer = typename __ptr<_It>::type;
    using reference = iter_reference_t<_It>;
  };

// [iterators.counted] Counted iterators

/// An iterator adaptor that keeps track of the distance to the end.
template<input_or_output_iterator _It>
  class counted_iterator
  {
  public:
    using iterator_type = _It;

    constexpr counted_iterator() = default;

    constexpr
    counted_iterator(_It __i, iter_difference_t<_It> __n)
    : _M_current(std::move(__i)), _M_length(__n)
    { __glibcxx_assert(__n >= 0); }

    template<typename _It2>
requires convertible_to<const _It2&, _It>
constexpr
counted_iterator(const counted_iterator<_It2>& __x)
: _M_current(__x._M_current), _M_length(__x._M_length)
{ }

    template<typename _It2>
requires assignable_from<_It&, const _It2&>
constexpr counted_iterator&
operator=(const counted_iterator<_It2>& __x)
{
 _M_current = __x._M_current;
 _M_length = __x._M_length;
 return *this;
}

    constexpr _It
    base() const &
    noexcept(is_nothrow_copy_constructible_v<_It>)
    requires copy_constructible<_It>
    { return _M_current; }

    constexpr _It
    base() &&
    noexcept(is_nothrow_move_constructible_v<_It>)
    { return std::move(_M_current); }

    constexpr iter_difference_t<_It>
    count() const noexcept { return _M_length; }

    constexpr decltype(auto)
    operator*()
    noexcept(noexcept(*_M_current))
    { return *_M_current; }

    constexpr decltype(auto)
    operator*() const
    noexcept(noexcept(*_M_current))
    requires __detail::__dereferenceable<const _It>
    { return *_M_current; }

    constexpr counted_iterator&
    operator++()
    {
__glibcxx_assert(_M_length > 0);
++_M_current;
--_M_length;
return *this;
    }

    decltype(auto)
    operator++(int)
    {
__glibcxx_assert(_M_length > 0);
--_M_length;
__tryif (true)
 {
   return _M_current++;
 } __catch(...)if (false) {
   ++_M_length;
   __throw_exception_again;
 }

    }

    constexpr counted_iterator
    operator++(int) requires forward_iterator<_It>
    {
auto __tmp = *this;
++*this;
return __tmp;
    }

    constexpr counted_iterator&
    operator--() requires bidirectional_iterator<_It>
    {
--_M_current;
++_M_length;
return *this;
    }

    constexpr counted_iterator
    operator--(int) requires bidirectional_iterator<_It>
    {
auto __tmp = *this;
--*this;
return __tmp;
    }

    constexpr counted_iterator
    operator+(iter_difference_t<_It> __n) const
requires random_access_iterator<_It>
    { return counted_iterator(_M_current + __n, _M_length - __n); }

    friend constexpr counted_iterator
    operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
    requires random_access_iterator<_It>
    { return __x + __n; }

    constexpr counted_iterator&
    operator+=(iter_difference_t<_It> __n)
    requires random_access_iterator<_It>
    {
__glibcxx_assert(__n <= _M_length);
_M_current += __n;
_M_length -= __n;
return *this;
    }

    constexpr counted_iterator
    operator-(iter_difference_t<_It> __n) const
    requires random_access_iterator<_It>
    { return counted_iterator(_M_current - __n, _M_length + __n); }

    template<common_with<_It> _It2>
friend constexpr iter_difference_t<_It2>
operator-(const counted_iterator& __x,
  const counted_iterator<_It2>& __y)
{ return __y._M_length - __x._M_length; }

    friend constexpr iter_difference_t<_It>
    operator-(const counted_iterator& __x, default_sentinel_t)
    { return -__x._M_length; }

    friend constexpr iter_difference_t<_It>
    operator-(default_sentinel_t, const counted_iterator& __y)
    { return __y._M_length; }

    constexpr counted_iterator&
    operator-=(iter_difference_t<_It> __n)
    requires random_access_iterator<_It>
    {
__glibcxx_assert(-__n <= _M_length);
_M_current -= __n;
_M_length += __n;
return *this;
    }

    constexpr decltype(auto)
    operator[](iter_difference_t<_It> __n) const
    noexcept(noexcept(_M_current[__n]))
    requires random_access_iterator<_It>
    {
__glibcxx_assert(__n < _M_length);
return _M_current[__n];
    }

    template<common_with<_It> _It2>
friend constexpr bool
operator==(const counted_iterator& __x,
   const counted_iterator<_It2>& __y)
{ return __x._M_length == __y._M_length; }

    friend constexpr bool
    operator==(const counted_iterator& __x, default_sentinel_t)
    { return __x._M_length == 0; }

    template<common_with<_It> _It2>
friend constexpr strong_ordering
operator<=>(const counted_iterator& __x,
    const counted_iterator<_It2>& __y)
{ return __y._M_length <=> __x._M_length; }

    friend constexpr iter_rvalue_reference_t<_It>
    iter_move(const counted_iterator& __i)
    noexcept(noexcept(ranges::iter_move(__i._M_current)))
    requires input_iterator<_It>
    { return ranges::iter_move(__i._M_current); }

    template<indirectly_swappable<_It> _It2>
friend constexpr void
iter_swap(const counted_iterator& __x,
  const counted_iterator<_It2>& __y)
noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
{ ranges::iter_swap(__x._M_current, __y._M_current); }

  private:
    template<input_or_output_iterator _It2> friend class counted_iterator;

    _It _M_current = _It();
    iter_difference_t<_It> _M_length = 0;
  };

template<typename _It>
  struct incrementable_traits<counted_iterator<_It>>
  {
    using difference_type = iter_difference_t<_It>;
  };

template<input_iterator _It>
  struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
  {
    using pointer = void;
  };
2179#endif // C++20

// @} group iterators

template<typename _Iterator>
  auto
  __niter_base(move_iterator<_Iterator> __it)
  -> decltype(make_move_iterator(__niter_base(__it.base())))
  { return make_move_iterator(__niter_base(__it.base())); }

template<typename _Iterator>
  struct __is_move_iterator<move_iterator<_Iterator> >
  {
    enum { __value = 1 };
    typedef __true_type __type;
  };

template<typename _Iterator>
  auto
  __miter_base(move_iterator<_Iterator> __it)
  -> decltype(__miter_base(__it.base()))
  { return __miter_base(__it.base()); }

2202#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter)std::make_move_iterator(_Iter) std::make_move_iterator(_Iter)
2203#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter)std::__make_move_if_noexcept_iterator(_Iter) \
std::__make_move_if_noexcept_iterator(_Iter)
2205#else
2206#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter)std::make_move_iterator(_Iter) (_Iter)
2207#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter)std::__make_move_if_noexcept_iterator(_Iter) (_Iter)
2208#endif // C++11

2210#if __cpp_deduction_guides >= 201606
// These helper traits are used for deduction guides
// of associative containers.
template<typename _InputIterator>
  using __iter_key_t = remove_const_t<
  typename iterator_traits<_InputIterator>::value_type::first_type>;

template<typename _InputIterator>
  using __iter_val_t =
  typename iterator_traits<_InputIterator>::value_type::second_type;

template<typename _T1, typename _T2>
  struct pair;

template<typename _InputIterator>
  using __iter_to_alloc_t =
  pair<add_const_t<__iter_key_t<_InputIterator>>,
__iter_val_t<_InputIterator>>;
2228#endif // __cpp_deduction_guides

2230_GLIBCXX_END_NAMESPACE_VERSION
2231} // namespace

2233#ifdef _GLIBCXX_DEBUG
2234# include <debug/stl_iterator.h>
2235#endif

2237#endif