text:
//===- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop -------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This pass transforms loops that contain branches on loop-invariant conditions
// to multiple loops.  For example, it turns the left into the right code:
//
//  for (...)                  if (lic)
//    A                          for (...)
//    if (lic)                     A; B; C
//      B                      else
//    C                          for (...)
//                                 A; C
//
// This can increase the size of the code exponentially (doubling it every time
// a loop is unswitched) so we only unswitch if the resultant code will be
// smaller than a threshold.
//
// This pass expects LICM to be run before it to hoist invariant conditions out
// of the loop, to make the unswitching opportunity obvious.
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LegacyDivergenceAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <map>
#include <set>
#include <tuple>
#include <utility>
#include <vector>

using namespace llvm;

#define DEBUG_TYPE "loop-unswitch"

STATISTIC(NumBranches, "Number of branches unswitched");
STATISTIC(NumSwitches, "Number of switches unswitched");
STATISTIC(NumGuards,   "Number of guards unswitched");
STATISTIC(NumSelects , "Number of selects unswitched");
STATISTIC(NumTrivial , "Number of unswitches that are trivial");
STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
STATISTIC(TotalInsts,  "Total number of instructions analyzed");

// The specific value of 100 here was chosen based only on intuition and a
// few specific examples.
static cl::opt<unsigned>
Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
          cl::init(100), cl::Hidden);

namespace {

  class LUAnalysisCache {
    using UnswitchedValsMap =
        DenseMap<const SwitchInst *, SmallPtrSet<const Value *, 8>>;
    using UnswitchedValsIt = UnswitchedValsMap::iterator;

    struct LoopProperties {
      unsigned CanBeUnswitchedCount;
      unsigned WasUnswitchedCount;
      unsigned SizeEstimation;
      UnswitchedValsMap UnswitchedVals;
    };

    // Here we use std::map instead of DenseMap, since we need to keep valid
    // LoopProperties pointer for current loop for better performance.
    using LoopPropsMap = std::map<const Loop *, LoopProperties>;
    using LoopPropsMapIt = LoopPropsMap::iterator;

    LoopPropsMap LoopsProperties;
    UnswitchedValsMap *CurLoopInstructions = nullptr;
    LoopProperties *CurrentLoopProperties = nullptr;

    // A loop unswitching with an estimated cost above this threshold
    // is not performed. MaxSize is turned into unswitching quota for
    // the current loop, and reduced correspondingly, though note that
    // the quota is returned by releaseMemory() when the loop has been
    // processed, so that MaxSize will return to its previous
    // value. So in most cases MaxSize will equal the Threshold flag
    // when a new loop is processed. An exception to that is that
    // MaxSize will have a smaller value while processing nested loops
    // that were introduced due to loop unswitching of an outer loop.
    //
    // FIXME: The way that MaxSize works is subtle and depends on the
    // pass manager processing loops and calling releaseMemory() in a
    // specific order. It would be good to find a more straightforward
    // way of doing what MaxSize does.
    unsigned MaxSize;

  public:
    LUAnalysisCache() : MaxSize(Threshold) {}

    // Analyze loop. Check its size, calculate is it possible to unswitch
    // it. Returns true if we can unswitch this loop.
    bool countLoop(const Loop *L, const TargetTransformInfo &TTI,
                   AssumptionCache *AC);

    // Clean all data related to given loop.
    void forgetLoop(const Loop *L);

    // Mark case value as unswitched.
    // Since SI instruction can be partly unswitched, in order to avoid
    // extra unswitching in cloned loops keep track all unswitched values.
    void setUnswitched(const SwitchInst *SI, const Value *V);

    // Check was this case value unswitched before or not.
    bool isUnswitched(const SwitchInst *SI, const Value *V);

    // Returns true if another unswitching could be done within the cost
    // threshold.
    bool costAllowsUnswitching();

    // Clone all loop-unswitch related loop properties.
    // Redistribute unswitching quotas.
    // Note, that new loop data is stored inside the VMap.
    void cloneData(const Loop *NewLoop, const Loop *OldLoop,
                   const ValueToValueMapTy &VMap);
  };

  class LoopUnswitch : public LoopPass {
    LoopInfo *LI;  // Loop information
    LPPassManager *LPM;
    AssumptionCache *AC;

    // Used to check if second loop needs processing after
    // rewriteLoopBodyWithConditionConstant rewrites first loop.
    std::vector<Loop*> LoopProcessWorklist;

    LUAnalysisCache BranchesInfo;

    bool OptimizeForSize;
    bool RedoLoop = false;

    Loop *CurrentLoop = nullptr;
    DominatorTree *DT = nullptr;
    MemorySSA *MSSA = nullptr;
    std::unique_ptr<MemorySSAUpdater> MSSAU;
    BasicBlock *LoopHeader = nullptr;
    BasicBlock *LoopPreheader = nullptr;

    bool SanitizeMemory;
    SimpleLoopSafetyInfo SafetyInfo;

    // LoopBlocks contains all of the basic blocks of the loop, including the
    // preheader of the loop, the body of the loop, and the exit blocks of the
    // loop, in that order.
    std::vector<BasicBlock*> LoopBlocks;
    // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
    std::vector<BasicBlock*> NewBlocks;

    bool HasBranchDivergence;

  public:
    static char ID; // Pass ID, replacement for typeid

    explicit LoopUnswitch(bool Os = false, bool HasBranchDivergence = false)
        : LoopPass(ID), OptimizeForSize(Os),
          HasBranchDivergence(HasBranchDivergence) {
      initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());
    }

    bool runOnLoop(Loop *L, LPPassManager &LPM) override;
    bool processCurrentLoop();
    bool isUnreachableDueToPreviousUnswitching(BasicBlock *);

    /// This transformation requires natural loop information & requires that
    /// loop preheaders be inserted into the CFG.
    ///
    void getAnalysisUsage(AnalysisUsage &AU) const override {
      AU.addRequired<AssumptionCacheTracker>();
      AU.addRequired<TargetTransformInfoWrapperPass>();
      if (EnableMSSALoopDependency) {
        AU.addRequired<MemorySSAWrapperPass>();
        AU.addPreserved<MemorySSAWrapperPass>();
      }
      if (HasBranchDivergence)
        AU.addRequired<LegacyDivergenceAnalysis>();
      getLoopAnalysisUsage(AU);
    }

  private:
    void releaseMemory() override { BranchesInfo.forgetLoop(CurrentLoop); }

    void initLoopData() {
      LoopHeader = CurrentLoop->getHeader();
      LoopPreheader = CurrentLoop->getLoopPreheader();
    }

    /// Split all of the edges from inside the loop to their exit blocks.
    /// Update the appropriate Phi nodes as we do so.
    void splitExitEdges(Loop *L,
                        const SmallVectorImpl<BasicBlock *> &ExitBlocks);

    bool tryTrivialLoopUnswitch(bool &Changed);

    bool unswitchIfProfitable(Value *LoopCond, Constant *Val,
                              Instruction *TI = nullptr);
    void unswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
                                  BasicBlock *ExitBlock, Instruction *TI);
    void unswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L,
                                     Instruction *TI);

    void rewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
                                              Constant *Val, bool IsEqual);

    void emitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
                                        BasicBlock *TrueDest,
                                        BasicBlock *FalseDest,
                                        BranchInst *OldBranch, Instruction *TI);

    void simplifyCode(std::vector<Instruction *> &Worklist, Loop *L);

    /// Given that the Invariant is not equal to Val. Simplify instructions
    /// in the loop.
    Value *simplifyInstructionWithNotEqual(Instruction *Inst, Value *Invariant,
                                           Constant *Val);
  };

} // end anonymous namespace

// Analyze loop. Check its size, calculate is it possible to unswitch
// it. Returns true if we can unswitch this loop.
bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI,
                                AssumptionCache *AC) {
  LoopPropsMapIt PropsIt;
  bool Inserted;
  std::tie(PropsIt, Inserted) =
      LoopsProperties.insert(std::make_pair(L, LoopProperties()));

  LoopProperties &Props = PropsIt->second;

  if (Inserted) {
    // New loop.

    // Limit the number of instructions to avoid causing significant code
    // expansion, and the number of basic blocks, to avoid loops with
    // large numbers of branches which cause loop unswitching to go crazy.
    // This is a very ad-hoc heuristic.

    SmallPtrSet<const Value *, 32> EphValues;
    CodeMetrics::collectEphemeralValues(L, AC, EphValues);

    // FIXME: This is overly conservative because it does not take into
    // consideration code simplification opportunities and code that can
    // be shared by the resultant unswitched loops.
    CodeMetrics Metrics;
    for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E;
         ++I)
      Metrics.analyzeBasicBlock(*I, TTI, EphValues);

    Props.SizeEstimation = Metrics.NumInsts;
    Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
    Props.WasUnswitchedCount = 0;
    MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;

    if (Metrics.notDuplicatable) {
      LLVM_DEBUG(dbgs() << "NOT unswitching loop %" << L->getHeader()->getName()
                        << ", contents cannot be "
                        << "duplicated!\n");
      return false;
    }
  }

  // Be careful. This links are good only before new loop addition.
  CurrentLoopProperties = &Props;
  CurLoopInstructions = &Props.UnswitchedVals;

  return true;
}

// Clean all data related to given loop.
void LUAnalysisCache::forgetLoop(const Loop *L) {
  LoopPropsMapIt LIt = LoopsProperties.find(L);

  if (LIt != LoopsProperties.end()) {
    LoopProperties &Props = LIt->second;
    MaxSize += (Props.CanBeUnswitchedCount + Props.WasUnswitchedCount) *
               Props.SizeEstimation;
    LoopsProperties.erase(LIt);
  }

  CurrentLoopProperties = nullptr;
  CurLoopInstructions = nullptr;
}

// Mark case value as unswitched.
// Since SI instruction can be partly unswitched, in order to avoid
// extra unswitching in cloned loops keep track all unswitched values.
void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) {
  (*CurLoopInstructions)[SI].insert(V);
}

// Check was this case value unswitched before or not.
bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) {
  return (*CurLoopInstructions)[SI].count(V);
}

bool LUAnalysisCache::costAllowsUnswitching() {
  return CurrentLoopProperties->CanBeUnswitchedCount > 0;
}

// Clone all loop-unswitch related loop properties.
// Redistribute unswitching quotas.
// Note, that new loop data is stored inside the VMap.
void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
                                const ValueToValueMapTy &VMap) {
  LoopProperties &NewLoopProps = LoopsProperties[NewLoop];
  LoopProperties &OldLoopProps = *CurrentLoopProperties;
  UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;

  // Reallocate "can-be-unswitched quota"

  --OldLoopProps.CanBeUnswitchedCount;
  ++OldLoopProps.WasUnswitchedCount;
  NewLoopProps.WasUnswitchedCount = 0;
  unsigned Quota = OldLoopProps.CanBeUnswitchedCount;
  NewLoopProps.CanBeUnswitchedCount = Quota / 2;
  OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2;

  NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation;

  // Clone unswitched values info:
  // for new loop switches we clone info about values that was
  // already unswitched and has redundant successors.
  for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) {
    const SwitchInst *OldInst = I->first;
    Value *NewI = VMap.lookup(OldInst);
    const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI);
    assert(NewInst && "All instructions that are in SrcBB must be in VMap.");

    NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst];
  }
}

char LoopUnswitch::ID = 0;

INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
                      false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(LoopPass)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis)
INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
                      false, false)

Pass *llvm::createLoopUnswitchPass(bool Os, bool HasBranchDivergence) {
  return new LoopUnswitch(Os, HasBranchDivergence);
}

/// Operator chain lattice.
enum OperatorChain {
  OC_OpChainNone,    ///< There is no operator.
  OC_OpChainOr,      ///< There are only ORs.
  OC_OpChainAnd,     ///< There are only ANDs.
  OC_OpChainMixed    ///< There are ANDs and ORs.
};

/// Cond is a condition that occurs in L. If it is invariant in the loop, or has
/// an invariant piece, return the invariant. Otherwise, return null.
//
/// NOTE: findLIVLoopCondition will not return a partial LIV by walking up a
/// mixed operator chain, as we can not reliably find a value which will
/// simplify the operator chain. If the chain is AND-only or OR-only, we can use
/// 0 or ~0 to simplify the chain.
///
/// NOTE: In case a partial LIV and a mixed operator chain, we may be able to
/// simplify the condition itself to a loop variant condition, but at the
/// cost of creating an entirely new loop.
static Value *findLIVLoopCondition(Value *Cond, Loop *L, bool &Changed,
                                   OperatorChain &ParentChain,
                                   DenseMap<Value *, Value *> &Cache,
                                   MemorySSAUpdater *MSSAU) {
  auto CacheIt = Cache.find(Cond);
  if (CacheIt != Cache.end())
    return CacheIt->second;

  // We started analyze new instruction, increment scanned instructions counter.
  ++TotalInsts;

  // We can never unswitch on vector conditions.
  if (Cond->getType()->isVectorTy())
    return nullptr;

  // Constants should be folded, not unswitched on!
  if (isa<Constant>(Cond)) return nullptr;

  // TODO: Handle: br (VARIANT|INVARIANT).

  // Hoist simple values out.
  if (L->makeLoopInvariant(Cond, Changed, nullptr, MSSAU)) {
    Cache[Cond] = Cond;
    return Cond;
  }

  // Walk up the operator chain to find partial invariant conditions.
  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
    if (BO->getOpcode() == Instruction::And ||
        BO->getOpcode() == Instruction::Or) {
      // Given the previous operator, compute the current operator chain status.
      OperatorChain NewChain;
      switch (ParentChain) {
      case OC_OpChainNone:
        NewChain = BO->getOpcode() == Instruction::And ? OC_OpChainAnd :
                                      OC_OpChainOr;
        break;
      case OC_OpChainOr:
        NewChain = BO->getOpcode() == Instruction::Or ? OC_OpChainOr :
                                      OC_OpChainMixed;
        break;
      case OC_OpChainAnd:
        NewChain = BO->getOpcode() == Instruction::And ? OC_OpChainAnd :
                                      OC_OpChainMixed;
        break;
      case OC_OpChainMixed:
        NewChain = OC_OpChainMixed;
        break;
      }

      // If we reach a Mixed state, we do not want to keep walking up as we can not
      // reliably find a value that will simplify the chain. With this check, we
      // will return null on the first sight of mixed chain and the caller will
      // either backtrack to find partial LIV in other operand or return null.
      if (NewChain != OC_OpChainMixed) {
        // Update the current operator chain type before we search up the chain.
        ParentChain = NewChain;
        // If either the left or right side is invariant, we can unswitch on this,
        // which will cause the branch to go away in one loop and the condition to
        // simplify in the other one.
        if (Value *LHS = findLIVLoopCondition(BO->getOperand(0), L, Changed,
                                              ParentChain, Cache, MSSAU)) {
          Cache[Cond] = LHS;
          return LHS;
        }
        // We did not manage to find a partial LIV in operand(0). Backtrack and try
        // operand(1).
        ParentChain = NewChain;
        if (Value *RHS = findLIVLoopCondition(BO->getOperand(1), L, Changed,
                                              ParentChain, Cache, MSSAU)) {
          Cache[Cond] = RHS;
          return RHS;
        }
      }
    }

  Cache[Cond] = nullptr;
  return nullptr;
}

/// Cond is a condition that occurs in L. If it is invariant in the loop, or has
/// an invariant piece, return the invariant along with the operator chain type.
/// Otherwise, return null.
static std::pair<Value *, OperatorChain>
findLIVLoopCondition(Value *Cond, Loop *L, bool &Changed,
                     MemorySSAUpdater *MSSAU) {
  DenseMap<Value *, Value *> Cache;
  OperatorChain OpChain = OC_OpChainNone;
  Value *FCond = findLIVLoopCondition(Cond, L, Changed, OpChain, Cache, MSSAU);

  // In case we do find a LIV, it can not be obtained by walking up a mixed
  // operator chain.
  assert((!FCond || OpChain != OC_OpChainMixed) &&
        "Do not expect a partial LIV with mixed operator chain");
  return {FCond, OpChain};
}

bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPMRef) {
  if (skipLoop(L))
    return false;

  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
      *L->getHeader()->getParent());
  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  LPM = &LPMRef;
  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  if (EnableMSSALoopDependency) {
    MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
    MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
    assert(DT && "Cannot update MemorySSA without a valid DomTree.");
  }
  CurrentLoop = L;
  Function *F = CurrentLoop->getHeader()->getParent();

  SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory);
  if (SanitizeMemory)
    SafetyInfo.computeLoopSafetyInfo(L);

  if (MSSA && VerifyMemorySSA)
    MSSA->verifyMemorySSA();

  bool Changed = false;
  do {
    assert(CurrentLoop->isLCSSAForm(*DT));
    if (MSSA && VerifyMemorySSA)
      MSSA->verifyMemorySSA();
    RedoLoop = false;
    Changed |= processCurrentLoop();
  } while (RedoLoop);

  if (MSSA && VerifyMemorySSA)
    MSSA->verifyMemorySSA();

  return Changed;
}

// Return true if the BasicBlock BB is unreachable from the loop header.
// Return false, otherwise.
bool LoopUnswitch::isUnreachableDueToPreviousUnswitching(BasicBlock *BB) {
  auto *Node = DT->getNode(BB)->getIDom();
  BasicBlock *DomBB = Node->getBlock();
  while (CurrentLoop->contains(DomBB)) {
    BranchInst *BInst = dyn_cast<BranchInst>(DomBB->getTerminator());

    Node = DT->getNode(DomBB)->getIDom();
    DomBB = Node->getBlock();

    if (!BInst || !BInst->isConditional())
      continue;

    Value *Cond = BInst->getCondition();
    if (!isa<ConstantInt>(Cond))
      continue;

    BasicBlock *UnreachableSucc =
        Cond == ConstantInt::getTrue(Cond->getContext())
            ? BInst->getSuccessor(1)
            : BInst->getSuccessor(0);

    if (DT->dominates(UnreachableSucc, BB))
      return true;
  }
  return false;
}

/// FIXME: Remove this workaround when freeze related patches are done.
/// LoopUnswitch and Equality propagation in GVN have discrepancy about
/// whether branch on undef/poison has undefine behavior. Here it is to
/// rule out some common cases that we found such discrepancy already
/// causing problems. Detail could be found in PR31652. Note if the
/// func returns true, it is unsafe. But if it is false, it doesn't mean
/// it is necessarily safe.
static bool equalityPropUnSafe(Value &LoopCond) {
  ICmpInst *CI = dyn_cast<ICmpInst>(&LoopCond);
  if (!CI || !CI->isEquality())
    return false;

  Value *LHS = CI->getOperand(0);
  Value *RHS = CI->getOperand(1);
  if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
    return true;

  auto HasUndefInPHI = [](PHINode &PN) {
    for (Value *Opd : PN.incoming_values()) {
      if (isa<UndefValue>(Opd))
        return true;
    }
    return false;
  };
  PHINode *LPHI = dyn_cast<PHINode>(LHS);
  PHINode *RPHI = dyn_cast<PHINode>(RHS);
  if ((LPHI && HasUndefInPHI(*LPHI)) || (RPHI && HasUndefInPHI(*RPHI)))
    return true;

  auto HasUndefInSelect = [](SelectInst &SI) {
    if (isa<UndefValue>(SI.getTrueValue()) ||
        isa<UndefValue>(SI.getFalseValue()))
      return true;
    return false;
  };
  SelectInst *LSI = dyn_cast<SelectInst>(LHS);
  SelectInst *RSI = dyn_cast<SelectInst>(RHS);
  if ((LSI && HasUndefInSelect(*LSI)) || (RSI && HasUndefInSelect(*RSI)))
    return true;
  return false;
}

/// Do actual work and unswitch loop if possible and profitable.
bool LoopUnswitch::processCurrentLoop() {
  bool Changed = false;

  initLoopData();

  // If LoopSimplify was unable to form a preheader, don't do any unswitching.
  if (!LoopPreheader)
    return false;

  // Loops with indirectbr cannot be cloned.
  if (!CurrentLoop->isSafeToClone())
    return false;

  // Without dedicated exits, splitting the exit edge may fail.
  if (!CurrentLoop->hasDedicatedExits())
    return false;

  LLVMContext &Context = LoopHeader->getContext();

  // Analyze loop cost, and stop unswitching if loop content can not be duplicated.
  if (!BranchesInfo.countLoop(
          CurrentLoop,
          getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
              *CurrentLoop->getHeader()->getParent()),
          AC))
    return false;

  // Try trivial unswitch first before loop over other basic blocks in the loop.
  if (tryTrivialLoopUnswitch(Changed)) {
    return true;
  }

  // Do not do non-trivial unswitch while optimizing for size.
  // FIXME: Use Function::hasOptSize().
  if (OptimizeForSize ||
      LoopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize))
    return false;

  // Run through the instructions in the loop, keeping track of three things:
  //
  //  - That we do not unswitch loops containing convergent operations, as we
  //    might be making them control dependent on the unswitch value when they
  //    were not before.
  //    FIXME: This could be refined to only bail if the convergent operation is
  //    not already control-dependent on the unswitch value.
  //
  //  - That basic blocks in the loop contain invokes whose predecessor edges we
  //    cannot split.
  //
  //  - The set of guard intrinsics encountered (these are non terminator
  //    instructions that are also profitable to be unswitched).

  SmallVector<IntrinsicInst *, 4> Guards;

  for (const auto BB : CurrentLoop->blocks()) {
    for (auto &I : *BB) {
      auto *CB = dyn_cast<CallBase>(&I);
      if (!CB)
        continue;
      if (CB->isConvergent())
        return false;
      if (auto *II = dyn_cast<InvokeInst>(&I))
        if (!II->getUnwindDest()->canSplitPredecessors())
          return false;
      if (auto *II = dyn_cast<IntrinsicInst>(&I))
        if (II->getIntrinsicID() == Intrinsic::experimental_guard)
          Guards.push_back(II);
    }
  }

  for (IntrinsicInst *Guard : Guards) {
    Value *LoopCond = findLIVLoopCondition(Guard->getOperand(0), CurrentLoop,
                                           Changed, MSSAU.get())
                          .first;
    if (LoopCond &&
        unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) {
      // NB! Unswitching (if successful) could have erased some of the
      // instructions in Guards leaving dangling pointers there.  This is fine
      // because we're returning now, and won't look at Guards again.
      ++NumGuards;
      return true;
    }
  }

  // Loop over all of the basic blocks in the loop.  If we find an interior
  // block that is branching on a loop-invariant condition, we can unswitch this
  // loop.
  for (Loop::block_iterator I = CurrentLoop->block_begin(),
                            E = CurrentLoop->block_end();
       I != E; ++I) {
    Instruction *TI = (*I)->getTerminator();

    // Unswitching on a potentially uninitialized predicate is not
    // MSan-friendly. Limit this to the cases when the original predicate is
    // guaranteed to execute, to avoid creating a use-of-uninitialized-value
    // in the code that did not have one.
    // This is a workaround for the discrepancy between LLVM IR and MSan
    // semantics. See PR28054 for more details.
    if (SanitizeMemory &&
        !SafetyInfo.isGuaranteedToExecute(*TI, DT, CurrentLoop))
      continue;

    if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
      // Some branches may be rendered unreachable because of previous
      // unswitching.
      // Unswitch only those branches that are reachable.
      if (isUnreachableDueToPreviousUnswitching(*I))
        continue;

      // If this isn't branching on an invariant condition, we can't unswitch
      // it.
      if (BI->isConditional()) {
        // See if this, or some part of it, is loop invariant.  If so, we can
        // unswitch on it if we desire.
        Value *LoopCond = findLIVLoopCondition(BI->getCondition(), CurrentLoop,
                                               Changed, MSSAU.get())
                              .first;
        if (LoopCond && !equalityPropUnSafe(*LoopCond) &&
            unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) {
          ++NumBranches;
          return true;
        }
      }
    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
      Value *SC = SI->getCondition();
      Value *LoopCond;
      OperatorChain OpChain;
      std::tie(LoopCond, OpChain) =
          findLIVLoopCondition(SC, CurrentLoop, Changed, MSSAU.get());

      unsigned NumCases = SI->getNumCases();
      if (LoopCond && NumCases) {
        // Find a value to unswitch on:
        // FIXME: this should chose the most expensive case!
        // FIXME: scan for a case with a non-critical edge?
        Constant *UnswitchVal = nullptr;
        // Find a case value such that at least one case value is unswitched
        // out.
        if (OpChain == OC_OpChainAnd) {
          // If the chain only has ANDs and the switch has a case value of 0.
          // Dropping in a 0 to the chain will unswitch out the 0-casevalue.
          auto *AllZero = cast<ConstantInt>(Constant::getNullValue(SC->getType()));
          if (BranchesInfo.isUnswitched(SI, AllZero))
            continue;
          // We are unswitching 0 out.
          UnswitchVal = AllZero;
        } else if (OpChain == OC_OpChainOr) {
          // If the chain only has ORs and the switch has a case value of ~0.
          // Dropping in a ~0 to the chain will unswitch out the ~0-casevalue.
          auto *AllOne = cast<ConstantInt>(Constant::getAllOnesValue(SC->getType()));
          if (BranchesInfo.isUnswitched(SI, AllOne))
            continue;
          // We are unswitching ~0 out.
          UnswitchVal = AllOne;
        } else {
          assert(OpChain == OC_OpChainNone &&
                 "Expect to unswitch on trivial chain");
          // Do not process same value again and again.
          // At this point we have some cases already unswitched and
          // some not yet unswitched. Let's find the first not yet unswitched one.
          for (auto Case : SI->cases()) {
            Constant *UnswitchValCandidate = Case.getCaseValue();
            if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) {
              UnswitchVal = UnswitchValCandidate;
              break;
            }
          }
        }

        if (!UnswitchVal)
          continue;

        if (unswitchIfProfitable(LoopCond, UnswitchVal)) {
          ++NumSwitches;
          // In case of a full LIV, UnswitchVal is the value we unswitched out.
          // In case of a partial LIV, we only unswitch when its an AND-chain
          // or OR-chain. In both cases switch input value simplifies to
          // UnswitchVal.
          BranchesInfo.setUnswitched(SI, UnswitchVal);
          return true;
        }
      }
    }

    // Scan the instructions to check for unswitchable values.
    for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end();
         BBI != E; ++BBI)
      if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) {
        Value *LoopCond = findLIVLoopCondition(SI->getCondition(), CurrentLoop,
                                               Changed, MSSAU.get())
                              .first;
        if (LoopCond &&
            unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) {
          ++NumSelects;
          return true;
        }
      }
  }
  return Changed;
}

/// Check to see if all paths from BB exit the loop with no side effects
/// (including infinite loops).
///
/// If true, we return true and set ExitBB to the block we
/// exit through.
///
static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB,
                                         BasicBlock *&ExitBB,
                                         std::set<BasicBlock*> &Visited) {
  if (!Visited.insert(BB).second) {
    // Already visited. Without more analysis, this could indicate an infinite
    // loop.
    return false;
  }
  if (!L->contains(BB)) {
    // Otherwise, this is a loop exit, this is fine so long as this is the
    // first exit.
    if (ExitBB) return false;
    ExitBB = BB;
    return true;
  }

  // Otherwise, this is an unvisited intra-loop node.  Check all successors.
  for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {
    // Check to see if the successor is a trivial loop exit.
    if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited))
      return false;
  }

  // Okay, everything after this looks good, check to make sure that this block
  // doesn't include any side effects.
  for (Instruction &I : *BB)
    if (I.mayHaveSideEffects())
      return false;

  return true;
}

/// Return true if the specified block unconditionally leads to an exit from
/// the specified loop, and has no side-effects in the process. If so, return
/// the block that is exited to, otherwise return null.
static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {
  std::set<BasicBlock*> Visited;
  Visited.insert(L->getHeader());  // Branches to header make infinite loops.
  BasicBlock *ExitBB = nullptr;
  if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited))
    return ExitBB;
  return nullptr;
}

/// We have found that we can unswitch CurrentLoop when LoopCond == Val to
/// simplify the loop.  If we decide that this is profitable,
/// unswitch the loop, reprocess the pieces, then return true.
bool LoopUnswitch::unswitchIfProfitable(Value *LoopCond, Constant *Val,
                                        Instruction *TI) {
  // Check to see if it would be profitable to unswitch current loop.
  if (!BranchesInfo.costAllowsUnswitching()) {
    LLVM_DEBUG(dbgs() << "NOT unswitching loop %"
                      << CurrentLoop->getHeader()->getName()
                      << " at non-trivial condition '" << *Val
                      << "' == " << *LoopCond << "\n"
                      << ". Cost too high.\n");
    return false;
  }
  if (HasBranchDivergence &&
      getAnalysis<LegacyDivergenceAnalysis>().isDivergent(LoopCond)) {
    LLVM_DEBUG(dbgs() << "NOT unswitching loop %"
                      << CurrentLoop->getHeader()->getName()
                      << " at non-trivial condition '" << *Val
                      << "' == " << *LoopCond << "\n"
                      << ". Condition is divergent.\n");
    return false;
  }

  unswitchNontrivialCondition(LoopCond, Val, CurrentLoop, TI);
  return true;
}

/// Emit a conditional branch on two values if LIC == Val, branch to TrueDst,
/// otherwise branch to FalseDest. Insert the code immediately before OldBranch
/// and remove (but not erase!) it from the function.
void LoopUnswitch::emitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
                                                  BasicBlock *TrueDest,
                                                  BasicBlock *FalseDest,
                                                  BranchInst *OldBranch,
                                                  Instruction *TI) {
  assert(OldBranch->isUnconditional() && "Preheader is not split correctly");
  assert(TrueDest != FalseDest && "Branch targets should be different");
  // Insert a conditional branch on LIC to the two preheaders.  The original
  // code is the true version and the new code is the false version.
  Value *BranchVal = LIC;
  bool Swapped = false;
  if (!isa<ConstantInt>(Val) ||
      Val->getType() != Type::getInt1Ty(LIC->getContext()))
    BranchVal = new ICmpInst(OldBranch, ICmpInst::ICMP_EQ, LIC, Val);
  else if (Val != ConstantInt::getTrue(Val->getContext())) {
    // We want to enter the new loop when the condition is true.
    std::swap(TrueDest, FalseDest);
    Swapped = true;
  }

  // Old branch will be removed, so save its parent and successor to update the
  // DomTree.
  auto *OldBranchSucc = OldBranch->getSuccessor(0);
  auto *OldBranchParent = OldBranch->getParent();

  // Insert the new branch.
  BranchInst *BI =
      IRBuilder<>(OldBranch).CreateCondBr(BranchVal, TrueDest, FalseDest, TI);
  if (Swapped)
    BI->swapProfMetadata();

  // Remove the old branch so there is only one branch at the end. This is
  // needed to perform DomTree's internal DFS walk on the function's CFG.
  OldBranch->removeFromParent();

  // Inform the DT about the new branch.
  if (DT) {
    // First, add both successors.
    SmallVector<DominatorTree::UpdateType, 3> Updates;
    if (TrueDest != OldBranchSucc)
      Updates.push_back({DominatorTree::Insert, OldBranchParent, TrueDest});
    if (FalseDest != OldBranchSucc)
      Updates.push_back({DominatorTree::Insert, OldBranchParent, FalseDest});
    // If both of the new successors are different from the old one, inform the
    // DT that the edge was deleted.
    if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) {
      Updates.push_back({DominatorTree::Delete, OldBranchParent, OldBranchSucc});
    }
    DT->applyUpdates(Updates);

    if (MSSAU)
      MSSAU->applyUpdates(Updates, *DT);
  }

  // If either edge is critical, split it. This helps preserve LoopSimplify
  // form for enclosing loops.
  auto Options =
      CriticalEdgeSplittingOptions(DT, LI, MSSAU.get()).setPreserveLCSSA();
  SplitCriticalEdge(BI, 0, Options);
  SplitCriticalEdge(BI, 1, Options);
}

/// Given a loop that has a trivial unswitchable condition in it (a cond branch
/// from its header block to its latch block, where the path through the loop
/// that doesn't execute its body has no side-effects), unswitch it. This
/// doesn't involve any code duplication, just moving the conditional branch
/// outside of the loop and updating loop info.
void LoopUnswitch::unswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
                                            BasicBlock *ExitBlock,
                                            Instruction *TI) {
  LLVM_DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
                    << LoopHeader->getName() << " [" << L->getBlocks().size()
                    << " blocks] in Function "
                    << L->getHeader()->getParent()->getName()
                    << " on cond: " << *Val << " == " << *Cond << "\n");
  // We are going to make essential changes to CFG. This may invalidate cached
  // information for L or one of its parent loops in SCEV.
  if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
    SEWP->getSE().forgetTopmostLoop(L);

  // First step, split the preheader, so that we know that there is a safe place
  // to insert the conditional branch.  We will change LoopPreheader to have a
  // conditional branch on Cond.
  BasicBlock *NewPH = SplitEdge(LoopPreheader, LoopHeader, DT, LI, MSSAU.get());

  // Now that we have a place to insert the conditional branch, create a place
  // to branch to: this is the exit block out of the loop that we should
  // short-circuit to.

  // Split this block now, so that the loop maintains its exit block, and so
  // that the jump from the preheader can execute the contents of the exit block
  // without actually branching to it (the exit block should be dominated by the
  // loop header, not the preheader).
  assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
  BasicBlock *NewExit =
      SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI, MSSAU.get());

  // Okay, now we have a position to branch from and a position to branch to,
  // insert the new conditional branch.
  auto *OldBranch = dyn_cast<BranchInst>(LoopPreheader->getTerminator());
  assert(OldBranch && "Failed to split the preheader");
  emitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OldBranch, TI);

  // emitPreheaderBranchOnCondition removed the OldBranch from the function.
  // Delete it, as it is no longer needed.
  delete OldBranch;

  // We need to reprocess this loop, it could be unswitched again.
  RedoLoop = true;

  // Now that we know that the loop is never entered when this condition is a
  // particular value, rewrite the loop with this info.  We know that this will
  // at least eliminate the old branch.
  rewriteLoopBodyWithConditionConstant(L, Cond, Val, /*IsEqual=*/false);

  ++NumTrivial;
}

/// Check if the first non-constant condition starting from the loop header is
/// a trivial unswitch condition: that is, a condition controls whether or not
/// the loop does anything at all. If it is a trivial condition, unswitching
/// produces no code duplications (equivalently, it produces a simpler loop and
/// a new empty loop, which gets deleted). Therefore always unswitch trivial
/// condition.
bool LoopUnswitch::tryTrivialLoopUnswitch(bool &Changed) {
  BasicBlock *CurrentBB = CurrentLoop->getHeader();
  Instruction *CurrentTerm = CurrentBB->getTerminator();
  LLVMContext &Context = CurrentBB->getContext();

  // If loop header has only one reachable successor (currently via an
  // unconditional branch or constant foldable conditional branch, but
  // should also consider adding constant foldable switch instruction in
  // future), we should keep looking for trivial condition candidates in
  // the successor as well. An alternative is to constant fold conditions
  // and merge successors into loop header (then we only need to check header's
  // terminator). The reason for not doing this in LoopUnswitch pass is that
  // it could potentially break LoopPassManager's invariants. Folding dead
  // branches could either eliminate the current loop or make other loops
  // unreachable. LCSSA form might also not be preserved after deleting
  // branches. The following code keeps traversing loop header's successors
  // until it finds the trivial condition candidate (condition that is not a
  // constant). Since unswitching generates branches with constant conditions,
  // this scenario could be very common in practice.
  SmallPtrSet<BasicBlock*, 8> Visited;

  while (true) {
    // If we exit loop or reach a previous visited block, then
    // we can not reach any trivial condition candidates (unfoldable
    // branch instructions or switch instructions) and no unswitch
    // can happen. Exit and return false.
    if (!CurrentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second)
      return false;

    // Check if this loop will execute any side-effecting instructions (e.g.
    // stores, calls, volatile loads) in the part of the loop that the code
    // *would* execute. Check the header first.
    for (Instruction &I : *CurrentBB)
      if (I.mayHaveSideEffects())
        return false;

    if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
      if (BI->isUnconditional()) {
        CurrentBB = BI->getSuccessor(0);
      } else if (BI->getCondition() == ConstantInt::getTrue(Context)) {
        CurrentBB = BI->getSuccessor(0);
      } else if (BI->getCondition() == ConstantInt::getFalse(Context)) {
        CurrentBB = BI->getSuccessor(1);
      } else {
        // Found a trivial condition candidate: non-foldable conditional branch.
        break;
      }
    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
      // At this point, any constant-foldable instructions should have probably
      // been folded.
      ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
      if (!Cond)
        break;
      // Find the target block we are definitely going to.
      CurrentBB = SI->findCaseValue(Cond)->getCaseSuccessor();
    } else {
      // We do not understand these terminator instructions.
      break;
    }

    CurrentTerm = CurrentBB->getTerminator();
  }

  // CondVal is the condition that controls the trivial condition.
  // LoopExitBB is the BasicBlock that loop exits when meets trivial condition.
  Constant *CondVal = nullptr;
  BasicBlock *LoopExitBB = nullptr;

  if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
    // If this isn't branching on an invariant condition, we can't unswitch it.
    if (!BI->isConditional())
      return false;

    Value *LoopCond = findLIVLoopCondition(BI->getCondition(), CurrentLoop,
                                           Changed, MSSAU.get())
                          .first;

    // Unswitch only if the trivial condition itself is an LIV (not
    // partial LIV which could occur in and/or)
    if (!LoopCond || LoopCond != BI->getCondition())
      return false;

    // Check to see if a successor of the branch is guaranteed to
    // exit through a unique exit block without having any
    // side-effects.  If so, determine the value of Cond that causes
    // it to do this.
    if ((LoopExitBB =
             isTrivialLoopExitBlock(CurrentLoop, BI->getSuccessor(0)))) {
      CondVal = ConstantInt::getTrue(Context);
    } else if ((LoopExitBB =
                    isTrivialLoopExitBlock(CurrentLoop, BI->getSuccessor(1)))) {
      CondVal = ConstantInt::getFalse(Context);
    }

    // If we didn't find a single unique LoopExit block, or if the loop exit
    // block contains phi nodes, this isn't trivial.
    if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
      return false;   // Can't handle this.

    if (equalityPropUnSafe(*LoopCond))
      return false;

    unswitchTrivialCondition(CurrentLoop, LoopCond, CondVal, LoopExitBB,
                             CurrentTerm);
    ++NumBranches;
    return true;
  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
    // If this isn't switching on an invariant condition, we can't unswitch it.
    Value *LoopCond = findLIVLoopCondition(SI->getCondition(), CurrentLoop,
                                           Changed, MSSAU.get())
                          .first;

    // Unswitch only if the trivial condition itself is an LIV (not
    // partial LIV which could occur in and/or)
    if (!LoopCond || LoopCond != SI->getCondition())
      return false;

    // Check to see if a successor of the switch is guaranteed to go to the
    // latch block or exit through a one exit block without having any
    // side-effects.  If so, determine the value of Cond that causes it to do
    // this.
    // Note that we can't trivially unswitch on the default case or
    // on already unswitched cases.
    for (auto Case : SI->cases()) {
      BasicBlock *LoopExitCandidate;
      if ((LoopExitCandidate =
               isTrivialLoopExitBlock(CurrentLoop, Case.getCaseSuccessor()))) {
        // Okay, we found a trivial case, remember the value that is trivial.
        ConstantInt *CaseVal = Case.getCaseValue();

        // Check that it was not unswitched before, since already unswitched
        // trivial vals are looks trivial too.
        if (BranchesInfo.isUnswitched(SI, CaseVal))
          continue;
        LoopExitBB = LoopExitCandidate;
        CondVal = CaseVal;
        break;
      }
    }

    // If we didn't find a single unique LoopExit block, or if the loop exit
    // block contains phi nodes, this isn't trivial.
    if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
      return false;   // Can't handle this.

    unswitchTrivialCondition(CurrentLoop, LoopCond, CondVal, LoopExitBB,
                             nullptr);

    // We are only unswitching full LIV.
    BranchesInfo.setUnswitched(SI, CondVal);
    ++NumSwitches;
    return true;
  }
  return false;
}

/// Split all of the edges from inside the loop to their exit blocks.
/// Update the appropriate Phi nodes as we do so.
void LoopUnswitch::splitExitEdges(
    Loop *L, const SmallVectorImpl<BasicBlock *> &ExitBlocks) {

  for (unsigned I = 0, E = ExitBlocks.size(); I != E; ++I) {
    BasicBlock *ExitBlock = ExitBlocks[I];
    SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
                                       pred_end(ExitBlock));

    // Although SplitBlockPredecessors doesn't preserve loop-simplify in
    // general, if we call it on all predecessors of all exits then it does.
    SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, MSSAU.get(),
                           /*PreserveLCSSA*/ true);
  }
}

/// We determined that the loop is profitable to unswitch when LIC equal Val.
/// Split it into loop versions and test the condition outside of either loop.
/// Return the loops created as Out1/Out2.
void LoopUnswitch::unswitchNontrivialCondition(Value *LIC, Constant *Val,
                                               Loop *L, Instruction *TI) {
  Function *F = LoopHeader->getParent();
  LLVM_DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
                    << LoopHeader->getName() << " [" << L->getBlocks().size()
                    << " blocks] in Function " << F->getName() << " when '"
                    << *Val << "' == " << *LIC << "\n");

  // We are going to make essential changes to CFG. This may invalidate cached
  // information for L or one of its parent loops in SCEV.
  if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
    SEWP->getSE().forgetTopmostLoop(L);

  LoopBlocks.clear();
  NewBlocks.clear();

  if (MSSAU && VerifyMemorySSA)
    MSSA->verifyMemorySSA();

  // First step, split the preheader and exit blocks, and add these blocks to
  // the LoopBlocks list.
  BasicBlock *NewPreheader =
      SplitEdge(LoopPreheader, LoopHeader, DT, LI, MSSAU.get());
  LoopBlocks.push_back(NewPreheader);

  // We want the loop to come after the preheader, but before the exit blocks.
  LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());

  SmallVector<BasicBlock*, 8> ExitBlocks;
  L->getUniqueExitBlocks(ExitBlocks);

  // Split all of the edges from inside the loop to their exit blocks.  Update
  // the appropriate Phi nodes as we do so.
  splitExitEdges(L, ExitBlocks);

  // The exit blocks may have been changed due to edge splitting, recompute.
  ExitBlocks.clear();
  L->getUniqueExitBlocks(ExitBlocks);

  // Add exit blocks to the loop blocks.
  LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());

  // Next step, clone all of the basic blocks that make up the loop (including
  // the loop preheader and exit blocks), keeping track of the mapping between
  // the instructions and blocks.
  NewBlocks.reserve(LoopBlocks.size());
  ValueToValueMapTy VMap;
  for (unsigned I = 0, E = LoopBlocks.size(); I != E; ++I) {
    BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[I], VMap, ".us", F);

    NewBlocks.push_back(NewBB);
    VMap[LoopBlocks[I]] = NewBB; // Keep the BB mapping.
  }

  // Splice the newly inserted blocks into the function right before the
  // original preheader.
  F->getBasicBlockList().splice(NewPreheader->getIterator(),
                                F->getBasicBlockList(),
                                NewBlocks[0]->getIterator(), F->end());

  // Now we create the new Loop object for the versioned loop.
  Loop *NewLoop = cloneLoop(L, L->getParentLoop(), VMap, LI, LPM);

  // Recalculate unswitching quota, inherit simplified switches info for NewBB,
  // Probably clone more loop-unswitch related loop properties.
  BranchesInfo.cloneData(NewLoop, L, VMap);

  Loop *ParentLoop = L->getParentLoop();
  if (ParentLoop) {
    // Make sure to add the cloned preheader and exit blocks to the parent loop
    // as well.
    ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI);
  }

  for (unsigned EBI = 0, EBE = ExitBlocks.size(); EBI != EBE; ++EBI) {
    BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[EBI]]);
    // The new exit block should be in the same loop as the old one.
    if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[EBI]))
      ExitBBLoop->addBasicBlockToLoop(NewExit, *LI);

    assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&
           "Exit block should have been split to have one successor!");
    BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);

    // If the successor of the exit block had PHI nodes, add an entry for
    // NewExit.
    for (PHINode &PN : ExitSucc->phis()) {
      Value *V = PN.getIncomingValueForBlock(ExitBlocks[EBI]);
      ValueToValueMapTy::iterator It = VMap.find(V);
      if (It != VMap.end()) V = It->second;
      PN.addIncoming(V, NewExit);
    }

    if (LandingPadInst *LPad = NewExit->getLandingPadInst()) {
      PHINode *PN = PHINode::Create(LPad->getType(), 0, "",
                                    &*ExitSucc->getFirstInsertionPt());

      for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc);
           I != E; ++I) {
        BasicBlock *BB = *I;
        LandingPadInst *LPI = BB->getLandingPadInst();
        LPI->replaceAllUsesWith(PN);
        PN->addIncoming(LPI, BB);
      }
    }
  }

  // Rewrite the code to refer to itself.
  for (unsigned NBI = 0, NBE = NewBlocks.size(); NBI != NBE; ++NBI) {
    for (Instruction &I : *NewBlocks[NBI]) {
      RemapInstruction(&I, VMap,
                       RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
      if (auto *II = dyn_cast<IntrinsicInst>(&I))
        if (II->getIntrinsicID() == Intrinsic::assume)
          AC->registerAssumption(II);
    }
  }

  // Rewrite the original preheader to select between versions of the loop.
  BranchInst *OldBR = cast<BranchInst>(LoopPreheader->getTerminator());
  assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
         "Preheader splitting did not work correctly!");

  if (MSSAU) {
    // Update MemorySSA after cloning, and before splitting to unreachables,
    // since that invalidates the 1:1 mapping of clones in VMap.
    LoopBlocksRPO LBRPO(L);
    LBRPO.perform(LI);
    MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, VMap);
  }

  // Emit the new branch that selects between the two versions of this loop.
  emitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR,
                                 TI);
  if (MSSAU) {
    // Update MemoryPhis in Exit blocks.
    MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMap, *DT);
    if (VerifyMemorySSA)
      MSSA->verifyMemorySSA();
  }

  // The OldBr was replaced by a new one and removed (but not erased) by
  // emitPreheaderBranchOnCondition. It is no longer needed, so delete it.
  delete OldBR;

  LoopProcessWorklist.push_back(NewLoop);
  RedoLoop = true;

  // Keep a WeakTrackingVH holding onto LIC.  If the first call to
  // RewriteLoopBody
  // deletes the instruction (for example by simplifying a PHI that feeds into
  // the condition that we're unswitching on), we don't rewrite the second
  // iteration.
  WeakTrackingVH LICHandle(LIC);

  // Now we rewrite the original code to know that the condition is true and the
  // new code to know that the condition is false.
  rewriteLoopBodyWithConditionConstant(L, LIC, Val, /*IsEqual=*/false);

  // It's possible that simplifying one loop could cause the other to be
  // changed to another value or a constant.  If its a constant, don't simplify
  // it.
  if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
      LICHandle && !isa<Constant>(LICHandle))
    rewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val,
                                         /*IsEqual=*/true);

  if (MSSA && VerifyMemorySSA)
    MSSA->verifyMemorySSA();
}

/// Remove all instances of I from the worklist vector specified.
static void removeFromWorklist(Instruction *I,
                               std::vector<Instruction *> &Worklist) {

  Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),
                 Worklist.end());
}

/// When we find that I really equals V, remove I from the
/// program, replacing all uses with V and update the worklist.
static void replaceUsesOfWith(Instruction *I, Value *V,
                              std::vector<Instruction *> &Worklist, Loop *L,
                              LPPassManager *LPM, MemorySSAUpdater *MSSAU) {
  LLVM_DEBUG(dbgs() << "Replace with '" << *V << "': " << *I << "\n");

  // Add uses to the worklist, which may be dead now.
  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
    if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
      Worklist.push_back(Use);

  // Add users to the worklist which may be simplified now.
  for (User *U : I->users())
    Worklist.push_back(cast<Instruction>(U));
  removeFromWorklist(I, Worklist);
  I->replaceAllUsesWith(V);
  if (!I->mayHaveSideEffects()) {
    if (MSSAU)
      MSSAU->removeMemoryAccess(I);
    I->eraseFromParent();
  }
  ++NumSimplify;
}

/// We know either that the value LIC has the value specified by Val in the
/// specified loop, or we know it does NOT have that value.
/// Rewrite any uses of LIC or of properties correlated to it.
void LoopUnswitch::rewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
                                                        Constant *Val,
                                                        bool IsEqual) {
  assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");

  // FIXME: Support correlated properties, like:
  //  for (...)
  //    if (li1 < li2)
  //      ...
  //    if (li1 > li2)
  //      ...

  // FOLD boolean conditions (X|LIC), (X&LIC).  Fold conditional branches,
  // selects, switches.
  std::vector<Instruction*> Worklist;
  LLVMContext &Context = Val->getContext();

  // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
  // in the loop with the appropriate one directly.
  if (IsEqual || (isa<ConstantInt>(Val) &&
      Val->getType()->isIntegerTy(1))) {
    Value *Replacement;
    if (IsEqual)
      Replacement = Val;
    else
      Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()),
                                     !cast<ConstantInt>(Val)->getZExtValue());

    for (User *U : LIC->users()) {
      Instruction *UI = dyn_cast<Instruction>(U);
      if (!UI || !L->contains(UI))
        continue;
      Worklist.push_back(UI);
    }

    for (Instruction *UI : Worklist)
      UI->replaceUsesOfWith(LIC, Replacement);

    simplifyCode(Worklist, L);
    return;
  }

  // Otherwise, we don't know the precise value of LIC, but we do know that it
  // is certainly NOT "Val".  As such, simplify any uses in the loop that we
  // can.  This case occurs when we unswitch switch statements.
  for (User *U : LIC->users()) {
    Instruction *UI = dyn_cast<Instruction>(U);
    if (!UI || !L->contains(UI))
      continue;

    // At this point, we know LIC is definitely not Val. Try to use some simple
    // logic to simplify the user w.r.t. to the context.
    if (Value *Replacement = simplifyInstructionWithNotEqual(UI, LIC, Val)) {
      if (LI->replacementPreservesLCSSAForm(UI, Replacement)) {
        // This in-loop instruction has been simplified w.r.t. its context,
        // i.e. LIC != Val, make sure we propagate its replacement value to
        // all its users.
        //
        // We can not yet delete UI, the LIC user, yet, because that would invalidate
        // the LIC->users() iterator !. However, we can make this instruction
        // dead by replacing all its users and push it onto the worklist so that
        // it can be properly deleted and its operands simplified.
        UI->replaceAllUsesWith(Replacement);
      }
    }

    // This is a LIC user, push it into the worklist so that simplifyCode can
    // attempt to simplify it.
    Worklist.push_back(UI);

    // If we know that LIC is not Val, use this info to simplify code.
    SwitchInst *SI = dyn_cast<SwitchInst>(UI);
    if (!SI || !isa<ConstantInt>(Val)) continue;

    // NOTE: if a case value for the switch is unswitched out, we record it
    // after the unswitch finishes. We can not record it here as the switch
    // is not a direct user of the partial LIV.
    SwitchInst::CaseHandle DeadCase =
        *SI->findCaseValue(cast<ConstantInt>(Val));
    // Default case is live for multiple values.
    if (DeadCase == *SI->case_default())
      continue;

    // Found a dead case value.  Don't remove PHI nodes in the
    // successor if they become single-entry, those PHI nodes may
    // be in the Users list.

    BasicBlock *Switch = SI->getParent();
    BasicBlock *SISucc = DeadCase.getCaseSuccessor();
    BasicBlock *Latch = L->getLoopLatch();

    if (!SI->findCaseDest(SISucc)) continue;  // Edge is critical.
    // If the DeadCase successor dominates the loop latch, then the
    // transformation isn't safe since it will delete the sole predecessor edge
    // to the latch.
    if (Latch && DT->dominates(SISucc, Latch))
      continue;

    // FIXME: This is a hack.  We need to keep the successor around
    // and hooked up so as to preserve the loop structure, because
    // trying to update it is complicated.  So instead we preserve the
    // loop structure and put the block on a dead code path.
    SplitEdge(Switch, SISucc, DT, LI, MSSAU.get());
    // Compute the successors instead of relying on the return value
    // of SplitEdge, since it may have split the switch successor
    // after PHI nodes.
    BasicBlock *NewSISucc = DeadCase.getCaseSuccessor();
    BasicBlock *OldSISucc = *succ_begin(NewSISucc);
    // Create an "unreachable" destination.
    BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
                                           Switch->getParent(),
                                           OldSISucc);
    new UnreachableInst(Context, Abort);
    // Force the new case destination to branch to the "unreachable"
    // block while maintaining a (dead) CFG edge to the old block.
    NewSISucc->getTerminator()->eraseFromParent();
    BranchInst::Create(Abort, OldSISucc,
                       ConstantInt::getTrue(Context), NewSISucc);
    // Release the PHI operands for this edge.
    for (PHINode &PN : NewSISucc->phis())
      PN.setIncomingValueForBlock(Switch, UndefValue::get(PN.getType()));
    // Tell the domtree about the new block. We don't fully update the
    // domtree here -- instead we force it to do a full recomputation
    // after the pass is complete -- but we do need to inform it of
    // new blocks.
    DT->addNewBlock(Abort, NewSISucc);
  }

  simplifyCode(Worklist, L);
}

/// Now that we have simplified some instructions in the loop, walk over it and
/// constant prop, dce, and fold control flow where possible. Note that this is
/// effectively a very simple loop-structure-aware optimizer. During processing
/// of this loop, L could very well be deleted, so it must not be used.
///
/// FIXME: When the loop optimizer is more mature, separate this out to a new
/// pass.
///
void LoopUnswitch::simplifyCode(std::vector<Instruction *> &Worklist, Loop *L) {
  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
  while (!Worklist.empty()) {
    Instruction *I = Worklist.back();
    Worklist.pop_back();

    // Simple DCE.
    if (isInstructionTriviallyDead(I)) {
      LLVM_DEBUG(dbgs() << "Remove dead instruction '" << *I << "\n");

      // Add uses to the worklist, which may be dead now.
      for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
        if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
          Worklist.push_back(Use);
      removeFromWorklist(I, Worklist);
      if (MSSAU)
        MSSAU->removeMemoryAccess(I);
      I->eraseFromParent();
      ++NumSimplify;
      continue;
    }

    // See if instruction simplification can hack this up.  This is common for
    // things like "select false, X, Y" after unswitching made the condition be
    // 'false'.  TODO: update the domtree properly so we can pass it here.
    if (Value *V = SimplifyInstruction(I, DL))
      if (LI->replacementPreservesLCSSAForm(I, V)) {
        replaceUsesOfWith(I, V, Worklist, L, LPM, MSSAU.get());
        continue;
      }

    // Special case hacks that appear commonly in unswitched code.
    if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
      if (BI->isUnconditional()) {
        // If BI's parent is the only pred of the successor, fold the two blocks
        // together.
        BasicBlock *Pred = BI->getParent();
        (void)Pred;
        BasicBlock *Succ = BI->getSuccessor(0);
        BasicBlock *SinglePred = Succ->getSinglePredecessor();
        if (!SinglePred) continue;  // Nothing to do.
        assert(SinglePred == Pred && "CFG broken");

        // Make the LPM and Worklist updates specific to LoopUnswitch.
        removeFromWorklist(BI, Worklist);
        auto SuccIt = Succ->begin();
        while (PHINode *PN = dyn_cast<PHINode>(SuccIt++)) {
          for (unsigned It = 0, E = PN->getNumOperands(); It != E; ++It)
            if (Instruction *Use = dyn_cast<Instruction>(PN->getOperand(It)))
              Worklist.push_back(Use);
          for (User *U : PN->users())
            Worklist.push_back(cast<Instruction>(U));
          removeFromWorklist(PN, Worklist);
          ++NumSimplify;
        }
        // Merge the block and make the remaining analyses updates.
        DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
        MergeBlockIntoPredecessor(Succ, &DTU, LI, MSSAU.get());
        ++NumSimplify;
        continue;
      }

      continue;
    }
  }
}

/// Simple simplifications we can do given the information that Cond is
/// definitely not equal to Val.
Value *LoopUnswitch::simplifyInstructionWithNotEqual(Instruction *Inst,
                                                     Value *Invariant,
                                                     Constant *Val) {
  // icmp eq cond, val -> false
  ICmpInst *CI = dyn_cast<ICmpInst>(Inst);
  if (CI && CI->isEquality()) {
    Value *Op0 = CI->getOperand(0);
    Value *Op1 = CI->getOperand(1);
    if ((Op0 == Invariant && Op1 == Val) || (Op0 == Val && Op1 == Invariant)) {
      LLVMContext &Ctx = Inst->getContext();
      if (CI->getPredicate() == CmpInst::ICMP_EQ)
        return ConstantInt::getFalse(Ctx);
      else
        return ConstantInt::getTrue(Ctx);
     }
  }

  // FIXME: there may be other opportunities, e.g. comparison with floating
  // point, or Invariant - Val != 0, etc.
  return nullptr;
}

redpajama_set_name: RedPajamaGithub


Peach Charcoal Paper - 19 in. x 25 in.
Finest-quality sulphite charcoal/pastel paper. Specially prepared surface will not pick up or lift under repeated stumping and erasure! Excellent tooth for charcoal, soft and half-hard pastels, and pencil. Both price and quality recommended for art class use. Acid free.


text:
Austin Dog Bakery Aims to Eliminate Ruff Days
According to the American Pet Products Association, owners are projected to pay more than $60 billion on their animals this year.
One person helping that statistic is 42-year-old Michelle Taylor, founder and owner of Austin's dog boutique and bakery, Bentley's Biscuits & Bones.
Taylor left her marketing director job of 15 years to pursue happiness alongside her yellow Labrador retriever named Bentley.
"Five years ago, I realized that there was more to life than just financial success, and my time was better spent with my dog," Taylor said. "With a background in cake decorating and two business degrees under my belt, I didn't want life to pass me by without trying to succeed in this dream of mine."
This dream morphed into the reality of Bentley's Biscuits & Bones, a storefront lined with photos of each dog that walks through the doors giddy with excitement. Featuring all-natural homemade cakes and treats along with dog accessories such as collars and bowls, the store acts as homage to Bentley and many of his four-legged friends in the city.
Taylor's store is one of six dog bakeries in town, though she said what makes her business stand out is how much time and energy she puts into her products everyday.
"I did a lot of research to make sure everything was safe for the dogs because that is my main concern, which meant shipping off all of my recipes to a lab before selling my products," Taylor said. "I'm actually one of the few dog stores in Austin that makes products in the brick-and-mortar store. The rest are either franchised or use bakeries in other locations."
Whether it's birthday cakes or spur-of-the-moment toys, the American Pet Products Association calculated that owners have increased their pet expenditures an average 20 percent in the last five years. One of those owners is 19-year-old Communication Sciences and Disorders sophomore Jennie Levy, who began purchasing products from BarkBox last year.
Founded in 2011, BarkBox delivers monthly treats and toys to their tail-wagging customers. The gifts are personalized, based on a survey that owners fill out explaining their dogs' likes and dislikes.
"When I was little, we used to have birthday parties for my dog and buy him a toy to celebrate," Levy said. "As I got older and moved from Houston to Austin, I wanted to give Jack more since I was far away."
Levy continues the tradition of celebrating her Tibetan terrier's special day each year with her family. However, the decision to purchase BarkBox was not completely made on her own.
"I love my dog and want to make him happy. There are so many cute and creative things geared towards pets out there that you can't help but want them all." Levy said.
Taylor understood that Bentley's Biscuits & Bones could only thrive in a dog-friendly city, with customers like Levy who see their dogs as more than just a pet. Deciding to open her store in Austin was a decision based on the city's continued dedication towards animals.
"I am from El Paso, and I would never open a dog bakery there because people do not value dogs in El Paso the way they do here in Austin," Taylor said. "I opened my store during the recession, and I truly believe the only way I came out successful is because of how much influence dogs have on this city."
Some of those influences are Austin Pets Alive!, Austin Boxer Rescue and the Bastrop Animal Rescue, three non-profit organizations that Bentley's Biscuits & Bones has partnered with for adoption events. A donation jar sits on top of the store's bakery counter, which Taylor personally drops off to various rescue groups once a month. This passion for giving back brought Second in Command Meghan Smith to start working at Bentley's Biscuits & Bones four years ago.
"Having three rescue dogs of my own, when I found out about Bentley's Biscuits & Bones, I knew that I wanted to get involved," Smith said.
Smith works in the store seven days a week, accompanied by Bentley who greets each customer with a slobbery smile and a tail wag. Smith answers all questions about retails items, and helps Taylor make dog-friendly treats, including frozen yogurt and cakes, every morning.
"Our customers know us, trust us and know we care about dogs. Just looking at these photos on our walls, I can name almost every dog and tell you their favorite item," Smith said. "Customer retention and happiness is key. Plus, our job allows us to see happy dogs all day long."
Tagged American Pet Products Association, Austin, Austin Pets Alive!, BarkBox, Bentley's Biscuits & Bones, Birthday Cakes, Dog Bakery, Dogs, Labrador, Pets, Texas Leave a comment
← Food Truck Infographic
Austin Aims to Eliminate Ruff Days (Photos) →

redpajama_set_name: RedPajamaCommonCrawl


text:
Federal Budget 2015
Pensioner concessions decision weighs on SA Treasurer Tom Koutsantonis
Posted Wed 13 May 2015 at 11:03am Wednesday 13 May 2015 at 11:03am Wed 13 May 2015 at 11:03am
pensioners (ABC News)
abc.net.au/news/concession-rate-decision-to-be-made-soon-government-says/6467524
The South Australian Government has all but conceded it will pick up the $30 million per year cost of pensioner concessions on local council rates.
Treasurer Tom Koutsantonis hinted at an announcement in the hours after the federal budget was delivered, but later indicated any news for pensioners and councils would take a little longer.
Annual rates on properties owned by pensioners or concession card holders are expected to rise by up to $190 from July because a federal subsidy was cut in the 2014-15 budget.
The SA Government covered a $30 million shortfall in the current financial year. What will happen beyond the end of June remains unclear.
Mr Koutsantonis was hoping the latest federal budget would restore the funding.
But there was no such measure announced on Tuesday night and Mr Koutsantonis said he would now consult Cabinet colleagues about what to do.
"We are going to be making a decision very, very soon about what to do about these cuts," he said.
We are going to be making a decision very, very soon about what to do about these cuts.
"When our Cabinet considers it, and we'll do it in a collegial way, we'll have a response for South Australian pensioners."
Local Government Association president Dave Burgess said pensioners were growing anxious about what might happen to their bills in the next financial year.
He said some councils had already started printing their rates notices.
"It's been a long, long waiting game and we keep waiting," Mr Burgess said.
"It's been a state responsibility for 40 years and I think they should just continue to roll on with it."
Budget promises GST boost for SA
South Australia will get a GST boost over the next three years because of the federal budget.
The Federal Government said it could amount to $900 million, but Mr Koutsantonis claimed it would be nearer to $600 million.
"Either way, the extra money does not make up the difference for the cuts that are in place that the Commonwealth have made," the SA Treasurer said.
Steven Marshall said SA would get an "avalanche" of GST funds. (ABC News)
SA Opposition Leader Steven Marshall referred to the GST boost as an "avalanche of new money".
He said there was no reason for the State Government not to restore pensioners' rate bill concessions and a remission on the state Emergency Services Levy.
Mr Marshall also urged the Government to reverse its plan to close the Repatriation Hospital in Adelaide.
"They are three things which this Government could do immediately," he said.
Meanwhile, Mr Koutsantonis accused the Federal Government of delaying infrastructure programs in SA, including one which would separate freight and passenger rail lines just north-west of the city.
Finance Minister Mathias Cormann said the State Government could be blamed for the hold-up and he was "flabbergasted" by claims to the contrary.
"We were keen to get moving but the State Government [was] not in a position to commence with the project," he said.
"The relevant department in the South Australian Government has been in touch with our department here in Canberra and has said 'We're not actually ready to proceed, can you please slow down and give us the money at a later stage'."
Doctors pleased with federal budget measures
Measures in the federal budget won praise from rural doctors in SA.
Their association welcomed a redirection of funds into a $2.6 million program to encourage more doctors to work in small towns across the nation.
It also praised the announcement of a $20 million promotional campaign against illegal drug use.
The Commonwealth also will provide $10.2 million over two years from July for a scheme aimed at boosting organ donation.
It will support clinical education in hospitals and help develop a new organ-matching system.
Transplant Australia chief Chris Thomas said a registration website would be set up for people willing to donate their organs.
"Families will always be asked to confirm a person's decision to become a donor, but we do know that when someone has taken the time to register it is far more likely that the family will support that decision," he said.
Conservation Council chief Craig Wilkins said the environment barely got a mention in this year's federal budget speech.
"The budget falls way short of the investment required to drive our future economy in things like public transport, green energy, water investment, those things [that] underpin our future prosperity," he said.
Posted 13 May 2015 13 May 2015 Wed 13 May 2015 at 11:03am
Cuts to health outweigh any new revenue for SA in 2015 budget: Koutsantonis
LGA writes to ratepayers warning of concession cut hit
Budget 2015: Winners and losers
Doctors and Medical Professionals
Federal - State Issues


The Board is the beating heart of your business. The experience around the Board table is the ultimate tool in combatting the fierce current global climate and extending the innovation that keeps your company relevant.
However, even in some of the biggest companies in the world, historic Boards have come to inadequate conclusions and the outcomes have negatively impacted the company. Sometimes, the decisions have been poor, because of a lack of adequate information, yet sometimes the decisions have been poor because the Board itself isn't fit to make the decision.


text:
Q: Android service's method called in different thread. Does it still run on the main thread? If I am understanding correctly, Android Services, by default, run on the main UI thread.
Thus, for any off-the-main-thread operation to work, I found people suggesting that one starts a separate thread in the Service.
However, my question is if a Service's method is called in another thread, i.e. AsyncTask or new Thread(...).start();, does the Service's method run in the calling thread? or does it run on the main thread, which supposedly the Service is running in?
In other words,
new Thread(new Runnable() {

    @Overrde
    public void run() {
        myAndroidService.doSomething();
    }
}).start();

would MyAndroidService#doSomething() be called in this new Thread?

A: A method is always run in the thread that invokes it.
A method doesn't really belong to any thread, so yes, even though the method is defined in your Service it will be executed in the AsyncTask thread, not the main thread that your Service is running in.

A: Yes, as Martin has metioned above.
Also, you can check out a method's thread info by:
private void doSomething(){
    Log.i(TAG, "I'm doing something in thread " + Thread.currentThread().toString());
}

redpajama_set_name: RedPajamaStackExchange


The French Academy was founded by Cardinal de Richelieu in 1635. For several years a number of learned gentlemen, such as Godeau, de Gombeaud, Giry, Chaplain, Habert, de Serizay, and the Abbé Cerisy de Malleville, had met once a week at Conrart's house for the purpose of discussing literary subjects. Through the Abbé de Boisrobert the existence of this society became known to Cardinal de Richelieu, who conceived the idea of making it a national institution. In 1635 the French Academy was formally established by royal letters-patent. The number of its members was fixed at forty, and statutes were drawn up which have suffered scarcely any change since that time. At the head of the Academy were three officers: a director, to preside at its meetings; a chancellor, to have the custody of its archives and the seal; a perpetual secretary, to prepare its work and keep its records. The perpetual secretary was appointed by lot for life with a salary of 6,000 francs a year. The director and the chancellor were at first appointed by lot for two months only. At present they are elected by vote for the term of three months. They are simply primi inter pares, and receive, like all the other members, an annual salary of 1,500 francs. The manner of electing members has been changed several times since 1635. At present, when an Academician dies, candidates who think themselves eligible present themselves to fill the vacancy. The new member is elected by the majority of the entire body. About a year later his public reception takes place. In the early years of the Academy all its members were Catholics. Among the distinguished men who held seats in it are the following: Corneille, Racine, Boileau, La Bruyère, d'Aguesseau, Bossuet, Fénelon, Fléchier, Mabillon, Lamoignon, Séguier, Fleury, Delille, Chateaubriand, Lamartine, de Barante, de Tocqueville, Berryer, Lacordaire, Dupanloup, de Falloux, Gratry, Montalembert, Ampère, Pasteur, de Bornier, Cardinal Perraud, all of them faithful sons of the Church. Among other Catholic members of the French Academy we shall mention: Brunetière, Coppée, de Mun, Lamy, Mézières, Duc de Broglie, René Bazin, Comte d'Haussonville, and Thureau-Dangin. The entire number of members of the French Academy from 1634 to 1906 has been 500. Of these fourteen were cardinals, nine archbishops, and twenty-five bishops; three belonged to reigning families: Comte de Clermont, Lucien Bonaparte and Duc d'Aumale: one member, A. Thiers, was President of the French Republic; fifteen were prime ministers; forty-nine, ministers; thirty-six, ambassadors; twenty, dukes and peers; six, grandees of Spain; thirty-nine, knights of the orders of the King, of the Holy Ghost, or of St. Louis, eleven, Knights of the Golden Fleece; and thirty, grand cross of the Legion of Honour. Twenty-four members were elected to the French Academy before they were twenty-three years of age; twenty-three were at least seventy years of age before their reception took place; fifteen died before reaching the age of forty-five; eighteen were about ninety years old when they died and two lived to be almost centenarians.
The object for which the Academy was founded as set forth in its statutes, was the purification of the French language. To attain this end it proposed to compile a dictionary, a grammar, a treatise on rhetoric, and a treatise on poetics. Only the dictionary has been carried out. From 1694 to 1878 seven editions of this work were published. The office of the Academy is not to create but to register words approved by the authority of the best writers and by good society. The dictionary is prepared by six members named for life, who are assisted by the perpetual secretary. Each word is submitted by the chairman of this committee to the Academy for approval. Besides this dictionary, the French Academy, at the suggestion of Voltaire, in 1778, began an "Historical Dictionary of the French Language", which, however, never progressed beyond the letter A. This undertaking was abandoned some twenty years ago. Every year the Academy awards a number of prizes. Previous to 1780 only two prizes were distributed. Since that period legacies and donations have provided an annual sum of more than 200,000 francs for the "Prixde Vertu", and the literary prizes. Some prizes for prose and poetry are given after competition. The "Prix Monthyon" (for literature, 19,000 francs), the "Prix Thérouanne" (for historical works, 4,000 francs), the "Prix Marcellin Guérin" (for literary works, 5,000 francs), and the "Prix Gobert" (for French history, 10,000 francs), are the most important. The "Prixde Vertu", of which the first was established by M. de Monthyon in 1784, are given to poor persons who have accomplished some remarkable act of charity or courage. Many of these have gone to missionaries and sisters belonging to various religious orders.
The Academy of Moral and Political Sciences.
What has been the influence of the French Academy? Some critics have reproached it with a tendency to hamper and crush originality. But it is the general opinion of scholars that it has corrected the judgment, purified the taste, and formed the language of French writers. Matthew Arnold, in his essay on "The Literary Influence of the Academies", praised it as a high court of letters and a rallying point for educated opinion. To it he ascribed the most, striking characteristics of the French language, its purity, delicacy, and flexibility.
In 1663, at the suggestion of Colbert, Louis XIV appointed a committee of four members of the French Academy charged with the duty of furnishing legends and inscriptions for medals. This was the origin of the Academy of Inscriptions and Belles-Lettres, founded in 1701. It was composed of ten honorary members, ten pensionnaires, ten associates, and ten pupils. The Academy of Inscriptions and Belles-Lettres deals with the history, geography, and antiquities of France, with Oriental, Greek, and Latin antiquities, the history of science among the ancients, and comparative philology.
The Academy of Moral and Political Sciences was founded in 1795. Suppressed by Napoleon in 1803, it was reestablished by Louis Philippe in 1832. It was then composed of thirty members divided into five sections: philosophy; morals; legislation, public law, and Jurisprudence; political economy; general and philosophic history. Another section was added in 1855: politics, administration, and finances. In 1872 the number of the members was fixed at forty, besides ten honorary members, six associates, and from thirty to forty corresponding members. Every year on 5 October, the five sections of the Institute hold a general public session, when prizes awarded by the several Academies are distributed. In 1877, the Duc d'Aumale left to the Institute of France by his will the château of Chantilly with its art collections.
MLA citation. Lebars, Jean. "The French Academy." The Catholic Encyclopedia. Vol. 1. New York: Robert Appleton Company, 1907. <http://www.newadvent.org/cathen/01089a.htm>.


text:
MERIT RESEARCH JOURNAL OF MICROBIOLOGY AND BIOLOGICAL SCIENCES (MRJMBS) (ISSN:2408-7076)
About MRJMBS
Merit Research Journals of Microbiology and Biological Sciences (MRJMBS), a purpose driven journal organization, was sprung into actions for two reasons: To publish excellent and unprecedented researches that are in line with the interest of our journals. Secondly, to create avenue for exploration, ravaging and manifestation of the world of knowledge, and to disseminate the articles freely for teaching and reference purposes, especially for researchers and teachers in developing nations.
The establishment of this Journal, Merit Research Journals of Microbiology and Biological Sciences (MRJMBS) is an answer to the wishes and desires of many researchers and teachers in developing nations especially in Africa and Asia who lack free access to quality materials online. This Journal opts to bring panacea to this problem, and to encourage research development.
Merit Research Journals of Microbiology and Biological Sciences (MRJMBS) aims at establishing a publishing house that is open to all. It aims to disseminate knowledge; provide a learned reference in the field; and establish channels of communication between academic and research experts, policy makers and executives in industry, commerce and investment institutions.
PROCESSING FEE POLICY
To bring the highest quality research to the widest possible audience. All the journals from this organization will be freely distributed and available from multiple websites.
It is the vision of Merit Research Journals of Microbiology and Biological Sciences (MRJMBS) to support the Open Access initiative. All journals by Merit Research Journals of Microbiology and Biological Sciences (MRJMBS) are published without restriction to the global community. We strongly believe that the open access model will spur researches across the world especially in developing nations as researchers gain unrestricted access to high quality research articles.
It is the policy of Merit Research Journals of Microbiology and Biological Sciences (MRJMBS) not to request for grants for its operations as grants sometimes fail forcing the organization to discontinue its operations. Rather we have chosen the model of self sustenance through collecting processing fee for articles published.
Authors are required to make payment only after their articles have been accepted. Thus, we resulted to collecting the processing fee once an article has been reviewed and accepted for publication by an editor.
There are no financial reward for reviewers and editors of the various journals. These positions are purely voluntary.
Merit Research Journals of Microbiology and Biological Sciences (MRJMBS) is a self supporting organization and does not receive funding from any institution / government. Hence, the operation of the journal is solely financed by the processing fees received from authors. The processing fees are required to meet operations expenses such as employees' salaries, internet services, electricity etc. Being an Open Access Publisher, Merit Research Journals does not receive payment for subscription as the journals are freely accessible over the internet.
It costs money to produce a peer-reviewed, edited, and formatted article that is ready for online publication, and to host it on a server that is freely accessible without barriers around the clock. We ask that - as a small part of the cost of doing the research--the author, institution, or funding agency pays a modest fee to help cover the actual cost of the essential final step, the publication.
To bring the largest pool of OPEN ACCESS Journals with a bias for African and Asian subjects, publishing over 200 journals by 2020.
Open Access is a publication model that enables the dissemination of research findings to the global community without restriction. Thus, all articles published under open access can be accessed by anyone with internet connection.
Merit Research Journals© 2019 || Advertisement | Privacy policy.


text:
Nigeria's 2.25 per cent GDP underscores citizens' worsening poverty rate – Expert
EconomicsECONOMY
By PAVA REPORTER On Nov 26, 2022
An economic expert, Dr Boniface Chizea has said the 2.25 per cent slow of Nigeria's Gross Domestic Product, GDP, underscores the worsening poverty rate of citizens.
Chizea made this disclosure to DAILY POST on Friday while reacting to the latest Gross Domestic Product Report by the National Bureau of Statistics, NBS.
On Thursday in Abuja, the NBS reported that Nigeria's GDP grew by 2.25 per cent in the third quarter of 2022, representing a slow growth rate.
Reacting to the development, Chizea stated that with the Non-Oil sector contributing 94.34 per cent of GDP, while the Oil sector makes up the balance of 5.66%, the Nigerian economy is no longer oil-based.
He added that the country needs to get its leadership right in the forthcoming election, stability of foreign exchange market, subsidised energy cost, support the productivity sector and overcome insecurity to jump-start faster GDP growth.
"The Nigeria Bureau of Statistics in its report released on Thursday November 24, 2022 reported a slower growth of the Nigerian economy in the third quarter of the year 2022 and naturally there is some concern. Some cold comfort however is that the Nigerian economy has recorded positive growths in the last eight quarters signalling the fact that recession remains a distant possibility.
"But this report should not come to us as a surprise considering the ongoing Russia/Ukraine war which has had devastating consequences as it destabilised the world economy and has resulted in a spike in inflationary spiral across many countries of the world including the United Kingdom which is currently suspected might slip into recession.
"For Nigerians this underscores the worsening welfare conditions as most Nigerians today are really ravaged by poverty and are struggling to eke out a living. Therefore, not surprising the Bureau recently reported that using a multi dimensional index that 130 million Nigerians are poor! So much therefore about the talk of lifting 100 million Nigerians out of poverty over a period of ten years!
"It will be interesting to review the source of this reported growth. What is reassuring is that non oil now contributes 94.34% of GDP with oil making up the balance of 5.66%. This clearly informs us that we are not an oil based economy. Oil becomes prominent from the perspective that it contributes over 70% of government revenue and up to 90% of its foreign exchange income. This explains why oil is referred to as an enclave sector so insular. Even then the contribution of the oil sector has witnessed considerable decline as production levels have been negatively impacted due to massive and heartless theft which has made Nigeria unable to meet its OPEC production quota. The level production currently stands at 1.22 mbpd compared to 1.56 mbpd for the same period in 2021. There is also the lingering uncertainty as the Nigerian National Petroleum Company makes its hesitant transition to a publicly quoted company.
"Service sector of the economy has traditionally played a dominant role from the perspectives of sectoral contribution to GDP standing at over 50% with Information & Communications Technology contributing about 10%. The contribution of Agriculture is slightly down to 24% which is not surprising if we factor in the floods and the ongoing insecurity in the farm regions of Nigeria. Industry and construction adds up the remaining 11%.
"What to do to jump start faster growth in the land is well canvassed. We must get elections 2023 right otherwise the situation will deteriorate rapidly. There will be the urgent need to tackle head long insecurity which has lingered for too long in the country. There is a need to end promptly subsidy on the pump price of fuel. In fact we should be looking urgently in the direction of quick termination of fuel importation if Dangote Refinery can live up to its billing. There is also the need to address the instability with the rate of exchange of the Naira. Is it time to float the rate of exchange of the Naira?
"Nigeria somehow must revive production otherwise we might harvest unrest which the world is worried about because of our massive population", he said.
Controversy trails unveiling of new currency redesign
Atiku is my brother, God will bless him – Peter Obi to ex-VP on 76th birthday
Abia State News
Abia will witness massive development if elected, says High Chief Ikechi Emenike…
Oyo: Bridge linking Eruwa, Lanlate collapses
Presidency: Nigeria in safe hands with Tinubu – Aisha Buhari
EFCC arraigns fake president's CSO for N200m fraud


text:
What Spiritual Needs Mean?
What are some examples of spiritual needs?
What are the seven spiritual needs?
What is a spiritual issue?
What is the meaning of spiritual?
How can you ensure a person's cultural needs are met?
What are some examples of spiritual wellness?
How do you show spiritual support?
How do you address a spiritual needs of a patient?
How do you express spirituality in life?
How is spirituality related to health?
Is spirituality related to God?
What are spiritual matters?
What does spiritual support mean?
What is a spirit of a person?
How do you develop spirituality?
What are the spiritual principles?
How do you assess spiritual needs of a patient?
Spiritual needs can include:the need for meaning and purpose in our lives.the need to love and feel loved.the need to feel a sense of belonging.the need to feel hope, peace and gratitude..
Well being: A personal plan for exploring and enriching the seven dimensions of life: Mind, body, spirit, love, work, play, the world.
Finding or making some kind of meaning in your life: Everyone deals with issues such as identity, suffering and hope. What makes such issues spiritual is that they raise questions about the meaning of life, life in general and your life in particular. Your spirituality is shaped by the answers you give these questions.
Spiritual means relating to people's thoughts and beliefs, rather than to their bodies and physical surroundings. She lived entirely by spiritual values, in a world of poetry and imagination. Synonyms: nonmaterial, metaphysical, other-worldly, ethereal More Synonyms of spiritual.
Whenever possible, it's best to ensure the person is in a calm, familiar environment with people they are close to. The person might enjoy things that stimulate their senses, such as familiar music or aromas (such as lavender) and hand massages. The person's cultural needs should be acknowledged and respected.
Spiritual wellness provides us with systems of faith, beliefs, values, ethics, principles and morals. A healthy spiritual practice may include examples of volunteerism, social contributions, belonging to a group, fellowship, optimism, forgiveness and expressions of compassion.
As you interact, imagine what it's like to be in their shoes and ask God for wisdom to support them in the way they need.Take Your Cues from the Patient. … Demonstrate a Christ-like Attitude. … Support Patients Within Their Own Faith Tradition. … Share an Encouraging Thought or Word. … Join a Team that Supports Spiritual Care.
Also, the interventions to meet patients' spiritual needs included respect for privacy; helping patients to connect; helping patients to complete unfinished business; listening to patients' concerns; comforting and reassuring; using personal religious beliefs to assist patients and observation of religious beliefs and …
What can I do now?Try meditation. Check out if there's a regular class near you or download the Smiling Mind app for a guided meditation.Practise self-awareness and knowing what's important to you.Read books about alternative ways to incorporate spirituality in your life.
Some research shows a connection between your beliefs and your sense of well being. Positive beliefs, comfort, and strength gained from religion, meditation, and prayer can contribute to well being. It may even promote healing. Improving your spiritual health may not cure an illness, but it may help you feel better.
Spirituality is the shorthand term used in Western society to talk about a person's relationship with God. For many people, how they think about religion and spirituality is certainly guided by what they see and do in their congregations.
adj. 1 relating to the spirit or soul and not to physical nature or matter; intangible. 2 of, relating to, or characteristic of sacred things, the Church, religion, etc. 3 standing in a relationship based on communication between the souls or minds of the persons involved.
What is Spiritual Support? Spiritual support is typically the work of hospital chaplains, who work with local religious and spiritual leaders to help provide spiritual support for patients near the end of their lives. The goal is to help the person feel peace and comfort.
The human spirit includes our intellect, emotions, fears, passions, and creativity. In the models of Daniel A. Helminiak and Bernard Lonergan, human spirit is considered to be the mental functions of awareness, insight, understanding, judgement and other reasoning powers.
Seven Ways to Improve Your Spiritual HealthExplore your spiritual core. By exploring your spiritual core, you are simply asking yourself questions about the person you are and your meaning. … Look for deeper meanings. … Get it out. … Try yoga. … Travel. … Think positively. … Take time to meditate.
Freeing Ourselves From Chaos Through Spiritual PrinciplesAcceptance.Hope.Faith.Courage.Honesty.Willingness.Humility.Responsibility.More items…
Providing a Spiritual AssessmentProvide a safe, therapeutic setting for patients to discuss their spiritual needs related to medical care.Use an approach that will be acceptable and helpful for any patient regardless of religious or cultural background.Keep patient's needs as the primary focus.More items…
How Do I Claim Tax Back For Self Assessment?
How do I claim my self assessment tax refund?
Quick Answer: What Do Helicopter Pilots Wear?
What do helicopter pilots do? A helicopter pilot flies
What Percentage Is 3 Minutes Of An Hour?
What percentage is one minute of an hour?
Question: What Is Same Day Delivery?
Why is fast delivery important? Boost customer satisfaction
What GPA Is Needed For Engineering?
Is a 3.4 GPA good for engineering? GPA absolutely matters.
What Is The Best Position To Sleep When You Are Drunk?
How do you sleep after being drunk? Filter out the
Quick Answer: How Much Can I Afford For A House Based On Monthly Payment?
What's the monthly payment on a $300 000 mortgage?