Fix uninitialized pointer members

[akshaykhadse]

Add formatting changes

[akshaykhadse]

Remove formatting changes

[LuoYuanke]

LGTM

llvm/lib/CodeGen/MachineLICM.cpp

 #include <limits>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "machinelicm"
 
 static cl::opt<bool>
     AvoidSpeculation("avoid-speculation",
                      cl::desc("MachineLICM should avoid speculation"),
                      cl::init(true), cl::Hidden);
 
-static cl::opt<bool>
-HoistCheapInsts("hoist-cheap-insts",
-                cl::desc("MachineLICM should hoist even cheap instructions"),
-                cl::init(false), cl::Hidden);
+static cl::opt<bool> HoistCheapInsts(
+    "hoist-cheap-insts",
 
-static cl::opt<bool>
-HoistConstStores("hoist-const-stores",
+static cl::opt<bool> HoistConstStores("hoist-const-stores",
                                       cl::desc("Hoist invariant stores"),
                                       cl::init(true), cl::Hidden);
 // The default threshold of 100 (i.e. if target block is 100 times hotter)
 // is based on empirical data on a single target and is subject to tuning.
-static cl::opt<unsigned>
-BlockFrequencyRatioThreshold("block-freq-ratio-threshold",
-                             cl::desc("Do not hoist instructions if target"
-                             "block is N times hotter than the source."),
-                             cl::init(100), cl::Hidden);
+static cl::opt<unsigned> BlockFrequencyRatioThreshold(
+    "block-freq-ratio-threshold",
 
 enum class UseBFI { None, PGO, All };
 
-static cl::opt<UseBFI>
-DisableHoistingToHotterBlocks("disable-hoisting-to-hotter-blocks",
-                              cl::desc("Disable hoisting instructions to"
-                              " hotter blocks"),
-                              cl::init(UseBFI::PGO), cl::Hidden,
-                              cl::values(clEnumValN(UseBFI::None, "none",
-                              "disable the feature"),
-                              clEnumValN(UseBFI::PGO, "pgo",
-                              "enable the feature when using profile data"),
-                              clEnumValN(UseBFI::All, "all",
-                              "enable the feature with/wo profile data")));
+static cl::opt<UseBFI> DisableHoistingToHotterBlocks(
+    "disable-hoisting-to-hotter-blocks",
+    cl::values(clEnumValN(UseBFI::None, "none", "disable the feature"),
 
-STATISTIC(NumHoisted,
-          "Number of machine instructions hoisted out of loops");
+STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops");
 STATISTIC(NumLowRP,
           "Number of instructions hoisted in low reg pressure situation");
-STATISTIC(NumHighLatency,
-          "Number of high latency instructions hoisted");
-STATISTIC(NumCSEed,
-          "Number of hoisted machine instructions CSEed");
+STATISTIC(NumHighLatency, "Number of high latency instructions hoisted");
+STATISTIC(NumCSEed, "Number of hoisted machine instructions CSEed");
 STATISTIC(NumPostRAHoisted,
           "Number of machine instructions hoisted out of loops post regalloc");
 STATISTIC(NumStoreConst,
           "Number of stores of const phys reg hoisted out of loops");
 STATISTIC(NumNotHoistedDueToHotness,
           "Number of instructions not hoisted due to block frequency");
 
 namespace {
 
-  class MachineLICMBase : public MachineFunctionPass {
-    const TargetInstrInfo *TII;
-    const TargetLoweringBase *TLI;
-    const TargetRegisterInfo *TRI;
-    const MachineFrameInfo *MFI;
-    MachineRegisterInfo *MRI;
-    TargetSchedModel SchedModel;
-    bool PreRegAlloc;
-    bool HasProfileData;
+  const TargetInstrInfo *TII = nullptr;
+  const TargetLoweringBase *TLI = nullptr;
+  const TargetRegisterInfo *TRI = nullptr;
+  const MachineFrameInfo *MFI = nullptr;
+  MachineRegisterInfo *MRI = nullptr;
 
-    // Various analyses that we use...
-    AliasAnalysis        *AA;      // Alias analysis info.
-    MachineBlockFrequencyInfo *MBFI; // Machine block frequncy info
-    MachineLoopInfo      *MLI;     // Current MachineLoopInfo
-    MachineDominatorTree *DT;      // Machine dominator tree for the cur loop
+  AliasAnalysis *AA = nullptr;               // Alias analysis info.
+  MachineBlockFrequencyInfo *MBFI = nullptr; // Machine block frequncy info
+  MachineLoopInfo *MLI = nullptr;            // Current MachineLoopInfo
+  MachineDominatorTree *DT = nullptr; // Machine dominator tree for the cur loop
 
-    // State that is updated as we process loops
-    bool         Changed;          // True if a loop is changed.
-    bool         FirstInLoop;      // True if it's the first LICM in the loop.
-    MachineLoop *CurLoop;          // The current loop we are working on.
-    MachineBasicBlock *CurPreheader; // The preheader for CurLoop.
+  bool Changed;                   // True if a loop is changed.
+  bool FirstInLoop;               // True if it's the first LICM in the loop.
+  MachineLoop *CurLoop = nullptr; // The current loop we are working on.
+  MachineBasicBlock *CurPreheader = nullptr; // The preheader for CurLoop.
 
-    // Exit blocks for CurLoop.
-    SmallVector<MachineBasicBlock *, 8> ExitBlocks;
 
-    bool isExitBlock(const MachineBasicBlock *MBB) const {
-      return is_contained(ExitBlocks, MBB);
-    }
 
-    // Track 'estimated' register pressure.
-    SmallSet<Register, 32> RegSeen;
-    SmallVector<unsigned, 8> RegPressure;
 
-    // Register pressure "limit" per register pressure set. If the pressure
-    // is higher than the limit, then it's considered high.
-    SmallVector<unsigned, 8> RegLimit;
 
-    // Register pressure on path leading from loop preheader to current BB.
-    SmallVector<SmallVector<unsigned, 8>, 16> BackTrace;
 
-    // For each opcode, keep a list of potential CSE instructions.
-    DenseMap<unsigned, std::vector<MachineInstr *>> CSEMap;
 
-    enum {
-      SpeculateFalse   = 0,
-      SpeculateTrue    = 1,
-      SpeculateUnknown = 2
-    };
+  enum { SpeculateFalse = 0, SpeculateTrue = 1, SpeculateUnknown = 2 };
 
-    // If a MBB does not dominate loop exiting blocks then it may not safe
-    // to hoist loads from this block.
-    // Tri-state: 0 - false, 1 - true, 2 - unknown
-    unsigned SpeculationState;
 
-  public:
-    MachineLICMBase(char &PassID, bool PreRegAlloc)
-        : MachineFunctionPass(PassID), PreRegAlloc(PreRegAlloc) {}
 
-    bool runOnMachineFunction(MachineFunction &MF) override;
 
-    void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.addRequired<MachineLoopInfo>();
-      if (DisableHoistingToHotterBlocks != UseBFI::None)
-        AU.addRequired<MachineBlockFrequencyInfo>();
-      AU.addRequired<MachineDominatorTree>();
-      AU.addRequired<AAResultsWrapperPass>();
-      AU.addPreserved<MachineLoopInfo>();
-      MachineFunctionPass::getAnalysisUsage(AU);
-    }
 
-    void releaseMemory() override {
-      RegSeen.clear();
-      RegPressure.clear();
-      RegLimit.clear();
-      BackTrace.clear();
-      CSEMap.clear();
-    }
 
-  private:
-    /// Keep track of information about hoisting candidates.
-    struct CandidateInfo {
-      MachineInstr *MI;
-      unsigned      Def;
-      int           FI;
+    unsigned Def;
+    int FI;
 
-      CandidateInfo(MachineInstr *mi, unsigned def, int fi)
         : MI(mi), Def(def), FI(fi) {}
-    };
 
-    void HoistRegionPostRA();
 
-    void HoistPostRA(MachineInstr *MI, unsigned Def);
 
-    void ProcessMI(MachineInstr *MI, BitVector &PhysRegDefs,
-                   BitVector &PhysRegClobbers, SmallSet<int, 32> &StoredFIs,
-                   SmallVectorImpl<CandidateInfo> &Candidates);
 
-    void AddToLiveIns(MCRegister Reg);
 
-    bool IsLICMCandidate(MachineInstr &I);
 
-    bool IsLoopInvariantInst(MachineInstr &I);
 
-    bool HasLoopPHIUse(const MachineInstr *MI) const;
 
-    bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx,
-                               Register Reg) const;
 
-    bool IsCheapInstruction(MachineInstr &MI) const;
 
-    bool CanCauseHighRegPressure(const DenseMap<unsigned, int> &Cost,
-                                 bool Cheap);
+  bool CanCauseHighRegPressure(const DenseMap<unsigned, int> &Cost, bool Cheap);
 
-    void UpdateBackTraceRegPressure(const MachineInstr *MI);
 
-    bool IsProfitableToHoist(MachineInstr &MI);
 
-    bool IsGuaranteedToExecute(MachineBasicBlock *BB);
 
-    bool isTriviallyReMaterializable(const MachineInstr &MI) const;
 
-    void EnterScope(MachineBasicBlock *MBB);
 
-    void ExitScope(MachineBasicBlock *MBB);
 
-    void ExitScopeIfDone(
-        MachineDomTreeNode *Node,
-        DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren,
-        const DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap);
 
-    void HoistOutOfLoop(MachineDomTreeNode *HeaderN);
 
-    void InitRegPressure(MachineBasicBlock *BB);
 
-    DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI,
-                                             bool ConsiderSeen,
-                                             bool ConsiderUnseenAsDef);
 
-    void UpdateRegPressure(const MachineInstr *MI,
-                           bool ConsiderUnseenAsDef = false);
 
-    MachineInstr *ExtractHoistableLoad(MachineInstr *MI);
 
-    MachineInstr *LookForDuplicate(const MachineInstr *MI,
-                                   std::vector<MachineInstr *> &PrevMIs);
 
-    bool
-    EliminateCSE(MachineInstr *MI,
-                 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI);
 
-    bool MayCSE(MachineInstr *MI);
 
-    bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader);
 
-    void InitCSEMap(MachineBasicBlock *BB);
 
-    bool isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,
-                            MachineBasicBlock *TgtBlock);
-    MachineBasicBlock *getCurPreheader();
-  };
 
-  class MachineLICM : public MachineLICMBase {
-  public:
-    static char ID;
-    MachineLICM() : MachineLICMBase(ID, false) {
-      initializeMachineLICMPass(*PassRegistry::getPassRegistry());
-    }
-  };
 
-  class EarlyMachineLICM : public MachineLICMBase {
-  public:
-    static char ID;
-    EarlyMachineLICM() : MachineLICMBase(ID, true) {
-      initializeEarlyMachineLICMPass(*PassRegistry::getPassRegistry());
-    }
-  };
 
 } // end anonymous namespace
 
 char MachineLICM::ID;
 char EarlyMachineLICM::ID;
 
 char &llvm::MachineLICMID = MachineLICM::ID;
 char &llvm::EarlyMachineLICMID = EarlyMachineLICM::ID;
if (PreRegAlloc) {
     for (unsigned i = 0, e = NumRPS; i != e; ++i)
       RegLimit[i] = TRI->getRegPressureSetLimit(MF, i);
   }
 
   // Get our Loop information...
   if (DisableHoistingToHotterBlocks != UseBFI::None)
     MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
   MLI = &getAnalysis<MachineLoopInfo>();
-  DT  = &getAnalysis<MachineDominatorTree>();
+  DT = &getAnalysis<MachineDominatorTree>();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());
   while (!Worklist.empty()) {
     CurLoop = Worklist.pop_back_val();
     CurPreheader = nullptr;
     ExitBlocks.clear();
 
bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) {
   return Changed;
 }
 
 /// Return true if instruction stores to the specified frame.
 static bool InstructionStoresToFI(const MachineInstr *MI, int FI) {
   // Check mayStore before memory operands so that e.g. DBG_VALUEs will return
   // true since they have no memory operands.
   if (!MI->mayStore())
-     return false;
   // If we lost memory operands, conservatively assume that the instruction
   // writes to all slots.
   if (MI->memoperands_empty())
     return true;
   for (const MachineMemOperand *MemOp : MI->memoperands()) {
     if (!MemOp->isStore() || !MemOp->getPseudoValue())
       continue;
     if (const FixedStackPseudoSourceValue *Value =
             dyn_cast<FixedStackPseudoSourceValue>(MemOp->getPseudoValue())) {
       if (Value->getFrameIndex() == FI)
         return true;
     }
   }
   return false;
 }
 
 /// Examine the instruction for potentai LICM candidate. Also
 /// gather register def and frame object update information.
-void MachineLICMBase::ProcessMI(MachineInstr *MI,
-                                BitVector &PhysRegDefs,
+void MachineLICMBase::ProcessMI(MachineInstr *MI, BitVector &PhysRegDefs,
                                 BitVector &PhysRegClobbers,
                                 SmallSet<int, 32> &StoredFIs,
                                 SmallVectorImpl<CandidateInfo> &Candidates) {
   bool RuledOut = false;
   bool HasNonInvariantUse = false;
   unsigned Def = 0;
   for (const MachineOperand &MO : MI->operands()) {
     if (MO.isFI()) {
       // Remember if the instruction stores to the frame index.
       int FI = MO.getIndex();
-      if (!StoredFIs.count(FI) &&
-          MFI->isSpillSlotObjectIndex(FI) &&
+      if (!StoredFIs.count(FI) && MFI->isSpillSlotObjectIndex(FI) &&
           InstructionStoresToFI(MI, FI))
         StoredFIs.insert(FI);
       HasNonInvariantUse = true;
       continue;
     }
 
     // We can't hoist an instruction defining a physreg that is clobbered in
     // the loop.

 /// Walk the specified region of the CFG and hoist loop invariants out to the
 /// preheader.
 void MachineLICMBase::HoistRegionPostRA() {
   MachineBasicBlock *Preheader = getCurPreheader();
   if (!Preheader)
     return;
 
   unsigned NumRegs = TRI->getNumRegs();
-  BitVector PhysRegDefs(NumRegs); // Regs defined once in the loop.
+  BitVector PhysRegDefs(NumRegs);     // Regs defined once in the loop.
   BitVector PhysRegClobbers(NumRegs); // Regs defined more than once.
 
   SmallVector<CandidateInfo, 32> Candidates;
   SmallSet<int, 32> StoredFIs;
 
   // Walk the entire region, count number of defs for each register, and
   // collect potential LICM candidates.
   for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
     // If the header of the loop containing this basic block is a landing pad,
     // then don't try to hoist instructions out of this loop.
     const MachineLoop *ML = MLI->getLoopFor(BB);
-    if (ML && ML->getHeader()->isEHPad()) continue;
+    if (ML && ML->getHeader()->isEHPad())
+      continue;
 
     // Conservatively treat live-in's as an external def.
     // FIXME: That means a reload that're reused in successor block(s) will not
     // be LICM'ed.
     for (const auto &LI : BB->liveins()) {
       for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI)
         PhysRegDefs.set(*AI);
     }
for (CandidateInfo &Candidate : Candidates) {
     unsigned Def = Candidate.Def;
     if (!PhysRegClobbers.test(Def) && !TermRegs.test(Def)) {
       bool Safe = true;
       MachineInstr *MI = Candidate.MI;
       for (const MachineOperand &MO : MI->operands()) {
         if (!MO.isReg() || MO.isDef() || !MO.getReg())
           continue;
         Register Reg = MO.getReg();
-        if (PhysRegDefs.test(Reg) ||
-            PhysRegClobbers.test(Reg)) {
+        if (PhysRegDefs.test(Reg) || PhysRegClobbers.test(Reg)) {
           // If it's using a non-loop-invariant register, then it's obviously
           // not safe to hoist.
           Safe = false;
           break;
         }
       }
       if (Safe)
         HoistPostRA(MI, Candidate.Def);
     }
   }
 }
 
 /// Add register 'Reg' to the livein sets of BBs in the current loop, and make
 /// sure it is not killed by any instructions in the loop.
 void MachineLICMBase::AddToLiveIns(MCRegister Reg) {
   for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
     if (!BB->isLiveIn(Reg))
       BB->addLiveIn(Reg);
     for (MachineInstr &MI : *BB) {
       for (MachineOperand &MO : MI.operands()) {
-        if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue;
+        if (!MO.isReg() || !MO.getReg() || MO.isDef())
+          continue;
         if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg()))
           MO.setIsKill(false);
       }
     }
   }
 }
 
 /// When an instruction is found to only use loop invariant operands that is

 /// Check if this mbb is guaranteed to execute. If not then a load from this mbb
 /// may not be safe to hoist.
 bool MachineLICMBase::IsGuaranteedToExecute(MachineBasicBlock *BB) {
   if (SpeculationState != SpeculateUnknown)
     return SpeculationState == SpeculateFalse;
 
   if (BB != CurLoop->getHeader()) {
     // Check loop exiting blocks.
-    SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks;
+    SmallVector<MachineBasicBlock *, 8> CurrentLoopExitingBlocks;
     CurLoop->getExitingBlocks(CurrentLoopExitingBlocks);
     for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks)
       if (!DT->dominates(BB, CurrentLoopExitingBlock)) {
         SpeculationState = SpeculateTrue;
         return false;
       }
   }
 

 void MachineLICMBase::ExitScope(MachineBasicBlock *MBB) {
   LLVM_DEBUG(dbgs() << "Exiting " << printMBBReference(*MBB) << '\n');
   BackTrace.pop_back();
 }
 
 /// Destroy scope for the MBB that corresponds to the given dominator tree node
 /// if its a leaf or all of its children are done. Walk up the dominator tree to
 /// destroy ancestors which are now done.
-void MachineLICMBase::ExitScopeIfDone(MachineDomTreeNode *Node,
-    DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
-    const DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) {
+void MachineLICMBase::ExitScopeIfDone(
+    MachineDomTreeNode *Node,
+    DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren,
+    const DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap) {
   if (OpenChildren[Node])
     return;
 
-  for(;;) {
+  for (;;) {
     ExitScope(Node->getBlock());
     // Now traverse upwards to pop ancestors whose offsprings are all done.
     MachineDomTreeNode *Parent = ParentMap.lookup(Node);
     if (!Parent || --OpenChildren[Parent] != 0)
       break;
     Node = Parent;
   }
 }
 
 /// Walk the specified loop in the CFG (defined by all blocks dominated by the
 /// specified header block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree. This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 void MachineLICMBase::HoistOutOfLoop(MachineDomTreeNode *HeaderN) {
   MachineBasicBlock *Preheader = getCurPreheader();
   if (!Preheader)
     return;
 
-  SmallVector<MachineDomTreeNode*, 32> Scopes;
-  SmallVector<MachineDomTreeNode*, 8> WorkList;
-  DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap;
-  DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
+  SmallVector<MachineDomTreeNode *, 32> Scopes;
+  SmallVector<MachineDomTreeNode *, 8> WorkList;
+  DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> ParentMap;
+  DenseMap<MachineDomTreeNode *, unsigned> OpenChildren;
 
   // Perform a DFS walk to determine the order of visit.
   WorkList.push_back(HeaderN);
   while (!WorkList.empty()) {
     MachineDomTreeNode *Node = WorkList.pop_back_val();
     assert(Node && "Null dominator tree node?");
     MachineBasicBlock *BB = Node->getBlock();
 
if (MO.isReg()) {
         Reg = TRI->lookThruCopyLike(MO.getReg(), MRI);
       if (Reg.isVirtual())
         return false;
       if (!TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *MI.getMF()))
         return false;
       else
         FoundCallerPresReg = true;
     } else if (!MO.isImm()) {
-        return false;
     }
   }
   return FoundCallerPresReg;
 }
 
 // Return true if the input MI is a copy instruction that feeds an invariant
 // store instruction. This means that the src of the copy has to satisfy
 // isCallerPreservedPhysReg and atleast one of it's users should satisfy
if (!IsLICMCandidate(I)) {
     return false;
   }
   return CurLoop->isLoopInvariant(I);
 }
 
 /// Return true if the specified instruction is used by a phi node and hoisting
 /// it could cause a copy to be inserted.
 bool MachineLICMBase::HasLoopPHIUse(const MachineInstr *MI) const {
-  SmallVector<const MachineInstr*, 8> Work(1, MI);
+  SmallVector<const MachineInstr *, 8> Work(1, MI);
   do {
     MI = Work.pop_back_val();
     for (const MachineOperand &MO : MI->operands()) {
       if (!MO.isReg() || !MO.isDef())
         continue;
       Register Reg = MO.getReg();
       if (!Reg.isVirtual())
         continue;
       for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
         // A PHI may cause a copy to be inserted.
         if (UseMI.isPHI()) {
-          // A PHI inside the loop causes a copy because the live range of Reg is
-          // extended across the PHI.
+          // A PHI inside the loop causes a copy because the live range of Reg
+          // is extended across the PHI.
           if (CurLoop->contains(&UseMI))
             return true;
           // A PHI in an exit block can cause a copy to be inserted if the PHI
           // has multiple predecessors in the loop with different values.
           // For now, approximate by rejecting all exit blocks.
           if (isExitBlock(UseMI.getParent()))
             return true;
           continue;
for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) {
     isCheap = true;
   }
 
   return isCheap;
 }
 
 /// Visit BBs from header to current BB, check if hoisting an instruction of the
 /// given cost matrix can cause high register pressure.
-bool
-MachineLICMBase::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost,
-                                         bool CheapInstr) {
+bool MachineLICMBase::CanCauseHighRegPressure(
+    const DenseMap<unsigned, int> &Cost, bool CheapInstr) {
   for (const auto &RPIdAndCost : Cost) {
     if (RPIdAndCost.second <= 0)
       continue;
 
     unsigned Class = RPIdAndCost.first;
     int Limit = RegLimit[Class];
 
     // Don't hoist cheap instructions if they would increase register pressure,
bool MachineLICMBase::IsProfitableToHoist(MachineInstr &MI) {
   //   loop. This increases register pressure in the loop.
   //
   // - If the value is used by a PHI in the loop, a copy will be required for
   //   lowering the PHI after extending the live range.
   //
   // - When hoisting the last use of a value in the loop, that value no longer
   //   needs to be live in the loop. This lowers register pressure in the loop.
 
-  if (HoistConstStores &&  isCopyFeedingInvariantStore(MI, MRI, TRI))
+  if (HoistConstStores && isCopyFeedingInvariantStore(MI, MRI, TRI))
     return true;
 
   bool CheapInstr = IsCheapInstruction(MI);
   bool CreatesCopy = HasLoopPHIUse(&MI);
 
   // Don't hoist a cheap instruction if it would create a copy in the loop.
   if (CheapInstr && CreatesCopy) {
     LLVM_DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI);
MachineInstr *MachineLICMBase::ExtractHoistableLoad(MachineInstr *MI) {
   // First test whether the instruction is loading from an amenable
   // memory location.
   if (!MI->isDereferenceableInvariantLoad())
     return nullptr;
 
   // Next determine the register class for a temporary register.
   unsigned LoadRegIndex;
   unsigned NewOpc =
       TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(),
                                       /*UnfoldLoad=*/true,
-                                    /*UnfoldStore=*/false,
-                                    &LoadRegIndex);
-  if (NewOpc == 0) return nullptr;
+                                      /*UnfoldStore=*/false, &LoadRegIndex);
+  if (NewOpc == 0)
+    return nullptr;
   const MCInstrDesc &MID = TII->get(NewOpc);
   MachineFunction &MF = *MI->getMF();
   const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF);
   // Ok, we're unfolding. Create a temporary register and do the unfold.
   Register Reg = MRI->createVirtualRegister(RC);
 
   SmallVector<MachineInstr *, 2> NewMIs;
   bool Success = TII->unfoldMemoryOperand(MF, *MI, Reg,
                                           /*UnfoldLoad=*/true,
                                           /*UnfoldStore=*/false, NewMIs);
   (void)Success;
   assert(Success &&
          "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "
          "succeeded!");
-  assert(NewMIs.size() == 2 &&
-         "Unfolded a load into multiple instructions!");
+  assert(NewMIs.size() == 2 && "Unfolded a load into multiple instructions!");
   MachineBasicBlock *MBB = MI->getParent();
   MachineBasicBlock::iterator Pos = MI;
   MBB->insert(Pos, NewMIs[0]);
   MBB->insert(Pos, NewMIs[1]);
   // If unfolding produced a load that wasn't loop-invariant or profitable to
   // hoist, discard the new instructions and bail.
   if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) {
     NewMIs[0]->eraseFromParent();
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
       assert((!MO.isReg() || MO.getReg() == 0 || !MO.getReg().isPhysical() ||
               MO.getReg() == Dup->getOperand(i).getReg()) &&
              "Instructions with different phys regs are not identical!");
 
       if (MO.isReg() && MO.isDef() && !MO.getReg().isPhysical())
         Defs.push_back(i);
     }
 
-    SmallVector<const TargetRegisterClass*, 2> OrigRCs;
+    SmallVector<const TargetRegisterClass *, 2> OrigRCs;
     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
       unsigned Idx = Defs[i];
       Register Reg = MI->getOperand(Idx).getReg();
       Register DupReg = Dup->getOperand(Idx).getReg();
       OrigRCs.push_back(MRI->getRegClass(DupReg));
 
       if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) {
         // Restore old RCs if more than one defs.

 /// When an instruction is found to use only loop invariant operands
 /// that are safe to hoist, this instruction is called to do the dirty work.
 /// It returns true if the instruction is hoisted.
 bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
   MachineBasicBlock *SrcBlock = MI->getParent();
 
   // Disable the instruction hoisting due to block hotness
   if ((DisableHoistingToHotterBlocks == UseBFI::All ||
        (DisableHoistingToHotterBlocks == UseBFI::PGO && HasProfileData)) &&
       isTgtHotterThanSrc(SrcBlock, Preheader)) {
     ++NumNotHoistedDueToHotness;
     return false;
   }
   // First check whether we should hoist this instruction.
   if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
     // If not, try unfolding a hoistable load.
     MI = ExtractHoistableLoad(MI);
-    if (!MI) return false;
+    if (!MI)
+      return false;
   }
 
   // If we have hoisted an instruction that may store, it can only be a constant
   // store.
   if (MI->mayStore())
     NumStoreConst++;
 
   // Now move the instructions to the predecessor, inserting it before any
bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
   }
 
   // Look for opportunity to CSE the hoisted instruction.
   unsigned Opcode = MI->getOpcode();
   DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =
       CSEMap.find(Opcode);
   if (!EliminateCSE(MI, CI)) {
     // Otherwise, splice the instruction to the preheader.
-    Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);
+    Preheader->splice(Preheader->getFirstTerminator(), MI->getParent(), MI);
 
     // Since we are moving the instruction out of its basic block, we do not
     // retain its debug location. Doing so would degrade the debugging
     // experience and adversely affect the accuracy of profiling information.
     assert(!MI->isDebugInstr() && "Should not hoist debug inst");
     MI->setDebugLoc(DebugLoc());
 
     // Update register pressure for BBs from header to this block.

llvm/lib/CodeGen/RegAllocBasic.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "regalloc"
 
 static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
                                       createBasicRegisterAllocator);
 
 namespace {
-  struct CompSpillWeight {
-    bool operator()(const LiveInterval *A, const LiveInterval *B) const {
-      return A->weight() < B->weight();
-    }
-  };
-}
+} // namespace
 
 namespace {
 /// RABasic provides a minimal implementation of the basic register allocation
 /// algorithm. It prioritizes live virtual registers by spill weight and spills
 /// whenever a register is unavailable. This is not practical in production but
 /// provides a useful baseline both for measuring other allocators and comparing
 /// the speed of the basic algorithm against other styles of allocators.
 class RABasic : public MachineFunctionPass,
                 public RegAllocBase,
                 private LiveRangeEdit::Delegate {
   // context
-  MachineFunction *MF;
+  MachineFunction *MF = nullptr;
 
   // state
   std::unique_ptr<Spiller> SpillerInstance;
   std::priority_queue<const LiveInterval *, std::vector<const LiveInterval *>,
                       CompSpillWeight>
       Queue;
 
   // Scratch space.  Allocated here to avoid repeated malloc calls in
public:
 
   MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::NoPHIs);
   }
 
   MachineFunctionProperties getClearedProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::IsSSA);
   }
 
   // Helper for spilling all live virtual registers currently unified under preg
   // that interfere with the most recently queried lvr.  Return true if spilling
   // was successful, and append any new spilled/split intervals to splitLVRs.
   bool spillInterferences(const LiveInterval &VirtReg, MCRegister PhysReg,
                           SmallVectorImpl<Register> &SplitVRegs);
 
if (!VRM->hasPhys(VirtReg))
     return;
 
   // Register is assigned, put it back on the queue for reassignment.
   LiveInterval &LI = LIS->getInterval(VirtReg);
   Matrix->unassign(LI);
   enqueue(&LI);
 }
 
-RABasic::RABasic(RegClassFilterFunc F):
-  MachineFunctionPass(ID),
-  RegAllocBase(F) {
-}
+RABasic::RABasic(RegClassFilterFunc F)
+    : MachineFunctionPass(ID), RegAllocBase(F) {}
 
 void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
   AU.addRequired<AAResultsWrapperPass>();
   AU.addPreserved<AAResultsWrapperPass>();
   AU.addRequired<LiveIntervals>();
   AU.addPreserved<LiveIntervals>();
   AU.addPreserved<SlotIndexes>();
void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addPreserved<MachineLoopInfo>();
   AU.addRequired<VirtRegMap>();
   AU.addPreserved<VirtRegMap>();
   AU.addRequired<LiveRegMatrix>();
   AU.addPreserved<LiveRegMatrix>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
-void RABasic::releaseMemory() {
-  SpillerInstance.reset();
-}
-
+void RABasic::releaseMemory() { SpillerInstance.reset(); }
 
 // Spill or split all live virtual registers currently unified under PhysReg
 // that interfere with VirtReg. The newly spilled or split live intervals are
 // returned by appending them to SplitVRegs.
 bool RABasic::spillInterferences(const LiveInterval &VirtReg,
                                  MCRegister PhysReg,
                                  SmallVectorImpl<Register> &SplitVRegs) {
   // Record each interference and determine if all are spillable before mutating
MCRegister RABasic::selectOrSplit(const LiveInterval &VirtReg,
   return 0;
 }
 
 bool RABasic::runOnMachineFunction(MachineFunction &mf) {
   LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
                     << "********** Function: " << mf.getName() << '\n');
 
   MF = &mf;
-  RegAllocBase::init(getAnalysis<VirtRegMap>(),
-                     getAnalysis<LiveIntervals>(),
+  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>(),
                      getAnalysis<LiveRegMatrix>());
   VirtRegAuxInfo VRAI(*MF, *LIS, *VRM, getAnalysis<MachineLoopInfo>(),
                       getAnalysis<MachineBlockFrequencyInfo>());
   VRAI.calculateSpillWeightsAndHints();
 
   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM, VRAI));
 
   allocatePhysRegs();
   postOptimization();
 
   // Diagnostic output before rewriting
   LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
 
   releaseMemory();
   return true;
 }
 
-FunctionPass* llvm::createBasicRegisterAllocator() {
-  return new RABasic();
-}
+FunctionPass *llvm::createBasicRegisterAllocator() { return new RABasic(); }
 
-FunctionPass* llvm::createBasicRegisterAllocator(RegClassFilterFunc F) {
+FunctionPass *llvm::createBasicRegisterAllocator(RegClassFilterFunc F) {
   return new RABasic(F);
 }

llvm/lib/CodeGen/RenameIndependentSubregs.cpp

public:
   bool runOnMachineFunction(MachineFunction &MF) override;
 
 private:
   struct SubRangeInfo {
     ConnectedVNInfoEqClasses ConEQ;
     LiveInterval::SubRange *SR;
     unsigned Index;
 
-    SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
-                 unsigned Index)
+    SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR, unsigned Index)
         : ConEQ(LIS), SR(&SR), Index(Index) {}
   };
 
   /// Split unrelated subregister components and rename them to new vregs.
   bool renameComponents(LiveInterval &LI) const;
 
   /// Build a vector of SubRange infos and a union find set of
   /// equivalence classes.
   /// Returns true if more than 1 equivalence class was found.
   bool findComponents(IntEqClasses &Classes,
                       SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
                       LiveInterval &LI) const;
 
   /// Distribute the LiveInterval segments into the new LiveIntervals
   /// belonging to their class.
   void distribute(const IntEqClasses &Classes,
                   const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-                  const SmallVectorImpl<LiveInterval*> &Intervals) const;
+                  const SmallVectorImpl<LiveInterval *> &Intervals) const;
 
   /// Constructs main liverange and add missing undef+dead flags.
-  void computeMainRangesFixFlags(const IntEqClasses &Classes,
+  void computeMainRangesFixFlags(
+      const IntEqClasses &Classes,
       const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-      const SmallVectorImpl<LiveInterval*> &Intervals) const;
+      const SmallVectorImpl<LiveInterval *> &Intervals) const;
 
   /// Rewrite Machine Operands to use the new vreg belonging to their class.
   void rewriteOperands(const IntEqClasses &Classes,
                        const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-                       const SmallVectorImpl<LiveInterval*> &Intervals) const;
+                       const SmallVectorImpl<LiveInterval *> &Intervals) const;
 
-
-  LiveIntervals *LIS;
-  MachineRegisterInfo *MRI;
-  const TargetInstrInfo *TII;
+  LiveIntervals *LIS = nullptr;
+  MachineRegisterInfo *MRI = nullptr;
+  const TargetInstrInfo *TII = nullptr;
 };
 
 } // end anonymous namespace
 
 char RenameIndependentSubregs::ID;
 
 char &llvm::RenameIndependentSubregsID = RenameIndependentSubregs::ID;
 
bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const {
   SmallVector<SubRangeInfo, 4> SubRangeInfos;
   IntEqClasses Classes;
   if (!findComponents(Classes, SubRangeInfos, LI))
     return false;
 
   // Create a new VReg for each class.
   Register Reg = LI.reg();
   const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
-  SmallVector<LiveInterval*, 4> Intervals;
+  SmallVector<LiveInterval *, 4> Intervals;
   Intervals.push_back(&LI);
   LLVM_DEBUG(dbgs() << printReg(Reg) << ": Found " << Classes.getNumClasses()
                     << " equivalence classes.\n");
   LLVM_DEBUG(dbgs() << printReg(Reg) << ": Splitting into newly created:");
   for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
        ++I) {
     Register NewVReg = MRI->createVirtualRegister(RegClass);
     LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);
     Intervals.push_back(&NewLI);
     LLVM_DEBUG(dbgs() << ' ' << printReg(NewVReg));
   }
   LLVM_DEBUG(dbgs() << '\n');
 
   rewriteOperands(Classes, SubRangeInfos, Intervals);
   distribute(Classes, SubRangeInfos, Intervals);
   computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
   return true;
 }
 
-bool RenameIndependentSubregs::findComponents(IntEqClasses &Classes,
+bool RenameIndependentSubregs::findComponents(
+    IntEqClasses &Classes,
     SmallVectorImpl<RenameIndependentSubregs::SubRangeInfo> &SubRangeInfos,
     LiveInterval &LI) const {
   // First step: Create connected components for the VNInfos inside the
   // subranges and count the global number of such components.
   unsigned NumComponents = 0;
   for (LiveInterval::SubRange &SR : LI.subranges()) {
     SubRangeInfos.push_back(SubRangeInfo(*LIS, SR, NumComponents));
     ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;
for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     unsigned SubRegIdx = MO.getSubReg();
     LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
     unsigned MergedID = ~0u;
     for (RenameIndependentSubregs::SubRangeInfo &SRInfo : SubRangeInfos) {
       const LiveInterval::SubRange &SR = *SRInfo.SR;
       if ((SR.LaneMask & LaneMask).none())
         continue;
       SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
-      Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
-                       : Pos.getBaseIndex();
+      Pos =
+          MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber()) : Pos.getBaseIndex();
       const VNInfo *VNI = SR.getVNInfoAt(Pos);
       if (VNI == nullptr)
         continue;
 
       // Map to local representant ID.
       unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
       // Global ID
       unsigned ID = LocalID + SRInfo.Index;
       // Merge other sets
       MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID);
     }
   }
 
   // Early exit if we ended up with a single equivalence class.
   Classes.compress();
   unsigned NumClasses = Classes.getNumClasses();
   return NumClasses > 1;
 }
 
-void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,
+void RenameIndependentSubregs::rewriteOperands(
+    const IntEqClasses &Classes,
     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-    const SmallVectorImpl<LiveInterval*> &Intervals) const {
+    const SmallVectorImpl<LiveInterval *> &Intervals) const {
   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
   unsigned Reg = Intervals[0]->reg();
   for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
-       E = MRI->reg_nodbg_end(); I != E; ) {
+                                               E = MRI->reg_nodbg_end();
+       I != E;) {
     MachineOperand &MO = *I++;
     if (!MO.isDef() && !MO.readsReg())
       continue;
 
     auto *MI = MO.getParent();
     SlotIndex Pos = LIS->getInstructionIndex(*MI);
-    Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
-                     : Pos.getBaseIndex();
+    Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber()) : Pos.getBaseIndex();
     unsigned SubRegIdx = MO.getSubReg();
     LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
 
     unsigned ID = ~0u;
     for (const SubRangeInfo &SRInfo : SubRangeInfos) {
       const LiveInterval::SubRange &SR = *SRInfo.SR;
       if ((SR.LaneMask & LaneMask).none())
         continue;
if (MO.isTied() && Reg != VReg) {
       I = MRI->reg_nodbg_begin(Reg);
     }
   }
   // TODO: We could attempt to recompute new register classes while visiting
   // the operands: Some of the split register may be fine with less constraint
   // classes than the original vreg.
 }
 
-void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,
+void RenameIndependentSubregs::distribute(
+    const IntEqClasses &Classes,
     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-    const SmallVectorImpl<LiveInterval*> &Intervals) const {
+    const SmallVectorImpl<LiveInterval *> &Intervals) const {
   unsigned NumClasses = Classes.getNumClasses();
   SmallVector<unsigned, 8> VNIMapping;
-  SmallVector<LiveInterval::SubRange*, 8> SubRanges;
+  SmallVector<LiveInterval::SubRange *, 8> SubRanges;
   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
   for (const SubRangeInfo &SRInfo : SubRangeInfos) {
     LiveInterval::SubRange &SR = *SRInfo.SR;
     unsigned NumValNos = SR.valnos.size();
     VNIMapping.clear();
     VNIMapping.reserve(NumValNos);
     SubRanges.clear();
-    SubRanges.resize(NumClasses-1, nullptr);
+    SubRanges.resize(NumClasses - 1, nullptr);
     for (unsigned I = 0; I < NumValNos; ++I) {
       const VNInfo &VNI = *SR.valnos[I];
       unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
       unsigned ID = Classes[LocalID + SRInfo.Index];
       VNIMapping.push_back(ID);
-      if (ID > 0 && SubRanges[ID-1] == nullptr)
-        SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
+      if (ID > 0 && SubRanges[ID - 1] == nullptr)
+        SubRanges[ID - 1] =
+            Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
     }
     DistributeRange(SR, SubRanges.data(), VNIMapping);
   }
 }
 
 static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
   for (const LiveInterval::SubRange &SR : LI.subranges()) {
     if (SR.liveAt(Pos))
       return true;
   }
   return false;
 }
 
 void RenameIndependentSubregs::computeMainRangesFixFlags(
     const IntEqClasses &Classes,
     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-    const SmallVectorImpl<LiveInterval*> &Intervals) const {
+    const SmallVectorImpl<LiveInterval *> &Intervals) const {
   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
   const SlotIndexes &Indexes = *LIS->getSlotIndexes();
   for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
     LiveInterval &LI = *Intervals[I];
     Register Reg = LI.reg();
 
     LI.removeEmptySubRanges();
 
for (const LiveInterval::SubRange &SR : LI.subranges()) {
         SlotIndex Def = VNI.def;
         MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def);
         for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
           SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB);
           if (subRangeLiveAt(LI, PredEnd.getPrevSlot()))
             continue;
 
           MachineBasicBlock::iterator InsertPos =
               llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg);
           const MCInstrDesc &MCDesc = TII->get(TargetOpcode::IMPLICIT_DEF);
-          MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos,
-                                               DebugLoc(), MCDesc, Reg);
+          MachineInstrBuilder ImpDef =
+              BuildMI(*PredMBB, InsertPos, DebugLoc(), MCDesc, Reg);
           SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(*ImpDef);
           SlotIndex RegDefIdx = DefIdx.getRegSlot();
           for (LiveInterval::SubRange &SR : LI.subranges()) {
             VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator);
             SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
           }
         }
       }