LoopUnswitch.cpp

    unsigned Offset = WI-Worklist.begin();
    Worklist.erase(WI);
    WI = std::find(Worklist.begin()+Offset, Worklist.end(), I);
  }
}

/// ReplaceUsesOfWith - 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) {
  DOUT << "Replace with '" << *V << "': " << *I;

  // 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 (Value::use_iterator UI = I->use_begin(), E = I->use_end();
       UI != E; ++UI)
    Worklist.push_back(cast<Instruction>(*UI));
  LPM->deleteSimpleAnalysisValue(I, L);
  RemoveFromWorklist(I, Worklist);
  I->replaceAllUsesWith(V);
  I->eraseFromParent();
  ++NumSimplify;
}

/// RemoveBlockIfDead - If the specified block is dead, remove it, update loop
/// information, and remove any dead successors it has.
///
void LoopUnswitch::RemoveBlockIfDead(BasicBlock *BB,
                                     std::vector<Instruction*> &Worklist,
                                     Loop *L) {
  if (pred_begin(BB) != pred_end(BB)) {
    // This block isn't dead, since an edge to BB was just removed, see if there
    // are any easy simplifications we can do now.
    if (BasicBlock *Pred = BB->getSinglePredecessor()) {
      // If it has one pred, fold phi nodes in BB.
      while (isa<PHINode>(BB->begin()))
        ReplaceUsesOfWith(BB->begin(), 
                          cast<PHINode>(BB->begin())->getIncomingValue(0), 
                          Worklist, L, LPM);
      
      // If this is the header of a loop and the only pred is the latch, we now
      // have an unreachable loop.
      if (Loop *L = LI->getLoopFor(BB))
        if (loopHeader == BB && L->contains(Pred)) {
          // Remove the branch from the latch to the header block, this makes
          // the header dead, which will make the latch dead (because the header
          // dominates the latch).
          LPM->deleteSimpleAnalysisValue(Pred->getTerminator(), L);
          Pred->getTerminator()->eraseFromParent();
          new UnreachableInst(Pred);
          
          // The loop is now broken, remove it from LI.
          RemoveLoopFromHierarchy(L);
          
          // Reprocess the header, which now IS dead.
          RemoveBlockIfDead(BB, Worklist, L);
          return;
        }
      
      // If pred ends in a uncond branch, add uncond branch to worklist so that
      // the two blocks will get merged.
      if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator()))
        if (BI->isUnconditional())
          Worklist.push_back(BI);
    }
    return;
  }

  DOUT << "Nuking dead block: " << *BB;
  
  // Remove the instructions in the basic block from the worklist.
  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
    RemoveFromWorklist(I, Worklist);
    
    // Anything that uses the instructions in this basic block should have their
    // uses replaced with undefs.
    if (!I->use_empty())
      I->replaceAllUsesWith(UndefValue::get(I->getType()));
  }
  
  // If this is the edge to the header block for a loop, remove the loop and
  // promote all subloops.
  if (Loop *BBLoop = LI->getLoopFor(BB)) {
    if (BBLoop->getLoopLatch() == BB)
      RemoveLoopFromHierarchy(BBLoop);
  }

  // Remove the block from the loop info, which removes it from any loops it
  // was in.
  LI->removeBlock(BB);
  
  
  // Remove phi node entries in successors for this block.
  TerminatorInst *TI = BB->getTerminator();
  std::vector<BasicBlock*> Succs;
  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
    Succs.push_back(TI->getSuccessor(i));
    TI->getSuccessor(i)->removePredecessor(BB);
  }
  
  // Unique the successors, remove anything with multiple uses.
  std::sort(Succs.begin(), Succs.end());
  Succs.erase(std::unique(Succs.begin(), Succs.end()), Succs.end());
  
  // Remove the basic block, including all of the instructions contained in it.
  LPM->deleteSimpleAnalysisValue(BB, L);  
  BB->eraseFromParent();
  // Remove successor blocks here that are not dead, so that we know we only
  // have dead blocks in this list.  Nondead blocks have a way of becoming dead,
  // then getting removed before we revisit them, which is badness.
  //
  for (unsigned i = 0; i != Succs.size(); ++i)
    if (pred_begin(Succs[i]) != pred_end(Succs[i])) {
      // One exception is loop headers.  If this block was the preheader for a
      // loop, then we DO want to visit the loop so the loop gets deleted.
      // We know that if the successor is a loop header, that this loop had to
      // be the preheader: the case where this was the latch block was handled
      // above and headers can only have two predecessors.
      if (!LI->isLoopHeader(Succs[i])) {
        Succs.erase(Succs.begin()+i);
        --i;
      }
    }
  
  for (unsigned i = 0, e = Succs.size(); i != e; ++i)
    RemoveBlockIfDead(Succs[i], Worklist, L);
}

/// RemoveLoopFromHierarchy - We have discovered that the specified loop has
/// become unwrapped, either because the backedge was deleted, or because the
/// edge into the header was removed.  If the edge into the header from the
/// latch block was removed, the loop is unwrapped but subloops are still alive,
/// so they just reparent loops.  If the loops are actually dead, they will be
/// removed later.
void LoopUnswitch::RemoveLoopFromHierarchy(Loop *L) {
  LPM->deleteLoopFromQueue(L);
  RemoveLoopFromWorklist(L);
}



// RewriteLoopBodyWithConditionConstant - 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<User*> Users(LIC->use_begin(), LIC->use_end());
  std::vector<Instruction*> Worklist;

  // 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() == Type::Int1Ty)) {
    Value *Replacement;
    if (IsEqual)
      Replacement = Val;
    else
      Replacement = ConstantInt::get(Type::Int1Ty, 
                                     !cast<ConstantInt>(Val)->getZExtValue());
    
    for (unsigned i = 0, e = Users.size(); i != e; ++i)
      if (Instruction *U = cast<Instruction>(Users[i])) {
        if (!L->contains(U->getParent()))
          continue;
        U->replaceUsesOfWith(LIC, Replacement);
        Worklist.push_back(U);
      }
  } else {
    // 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 (unsigned i = 0, e = Users.size(); i != e; ++i)
      if (Instruction *U = cast<Instruction>(Users[i])) {
        if (!L->contains(U->getParent()))
          continue;

        Worklist.push_back(U);

        // If we know that LIC is not Val, use this info to simplify code.
        if (SwitchInst *SI = dyn_cast<SwitchInst>(U)) {
          for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) {
            if (SI->getCaseValue(i) == Val) {
              // 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.
              
              // 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 an dead code path.
              
              BasicBlock* Old = SI->getParent();
              BasicBlock* Split = SplitBlock(Old, SI, this);
              
              Instruction* OldTerm = Old->getTerminator();
              BranchInst::Create(Split, SI->getSuccessor(i),
                                 ConstantInt::getTrue(), OldTerm);

              LPM->deleteSimpleAnalysisValue(Old->getTerminator(), L);
              Old->getTerminator()->eraseFromParent();
              
              PHINode *PN;
              for (BasicBlock::iterator II = SI->getSuccessor(i)->begin();
                   (PN = dyn_cast<PHINode>(II)); ++II) {
                Value *InVal = PN->removeIncomingValue(Split, false);
                PN->addIncoming(InVal, Old);
              }

              SI->removeCase(i);
              break;
            }
          }
        }
        
        // TODO: We could do other simplifications, for example, turning 
        // LIC == Val -> false.
      }
  }
  
  SimplifyCode(Worklist, L);
}

/// SimplifyCode - Okay, 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) {
  while (!Worklist.empty()) {
    Instruction *I = Worklist.back();
    Worklist.pop_back();
    
    // Simple constant folding.
    if (Constant *C = ConstantFoldInstruction(I)) {
      ReplaceUsesOfWith(I, C, Worklist, L, LPM);
      continue;
    }
    
    // Simple DCE.
    if (isInstructionTriviallyDead(I)) {
      DOUT << "Remove dead instruction '" << *I;
      
      // 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);
      LPM->deleteSimpleAnalysisValue(I, L);
      RemoveFromWorklist(I, Worklist);
      I->eraseFromParent();
      ++NumSimplify;
      continue;
    }
    
    // Special case hacks that appear commonly in unswitched code.
    switch (I->getOpcode()) {
    case Instruction::Select:
      if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(0))) {
        ReplaceUsesOfWith(I, I->getOperand(!CB->getZExtValue()+1), Worklist, L,
                          LPM);
        continue;
      }
      break;
    case Instruction::And:
      if (isa<ConstantInt>(I->getOperand(0)) && 
          I->getOperand(0)->getType() == Type::Int1Ty)   // constant -> RHS
        cast<BinaryOperator>(I)->swapOperands();
      if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(1))) 
        if (CB->getType() == Type::Int1Ty) {
          if (CB->isOne())      // X & 1 -> X
            ReplaceUsesOfWith(I, I->getOperand(0), Worklist, L, LPM);
          else                  // X & 0 -> 0
            ReplaceUsesOfWith(I, I->getOperand(1), Worklist, L, LPM);
          continue;
        }
      break;
    case Instruction::Or:
      if (isa<ConstantInt>(I->getOperand(0)) &&
          I->getOperand(0)->getType() == Type::Int1Ty)   // constant -> RHS
        cast<BinaryOperator>(I)->swapOperands();
      if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(1)))
        if (CB->getType() == Type::Int1Ty) {
          if (CB->isOne())   // X | 1 -> 1
            ReplaceUsesOfWith(I, I->getOperand(1), Worklist, L, LPM);
          else                  // X | 0 -> X
            ReplaceUsesOfWith(I, I->getOperand(0), Worklist, L, LPM);
          continue;
        }
      break;
    case Instruction::Br: {
      BranchInst *BI = 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();
        BasicBlock *Succ = BI->getSuccessor(0);
        BasicBlock *SinglePred = Succ->getSinglePredecessor();
        if (!SinglePred) continue;  // Nothing to do.
        assert(SinglePred == Pred && "CFG broken");

        DOUT << "Merging blocks: " << Pred->getName() << " <- " 
             << Succ->getName() << "\n";
        
        // Resolve any single entry PHI nodes in Succ.
        while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))
          ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);
        
        // Move all of the successor contents from Succ to Pred.
        Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(),
                                   Succ->end());
        LPM->deleteSimpleAnalysisValue(BI, L);
        BI->eraseFromParent();
        RemoveFromWorklist(BI, Worklist);
        
        // If Succ has any successors with PHI nodes, update them to have
        // entries coming from Pred instead of Succ.
        Succ->replaceAllUsesWith(Pred);
        
        // Remove Succ from the loop tree.
        LI->removeBlock(Succ);
        LPM->deleteSimpleAnalysisValue(Succ, L);
        Succ->eraseFromParent();
        ++NumSimplify;
      } else if (ConstantInt *CB = dyn_cast<ConstantInt>(BI->getCondition())){
        // Conditional branch.  Turn it into an unconditional branch, then
        // remove dead blocks.
        break;  // FIXME: Enable.

        DOUT << "Folded branch: " << *BI;
        BasicBlock *DeadSucc = BI->getSuccessor(CB->getZExtValue());
        BasicBlock *LiveSucc = BI->getSuccessor(!CB->getZExtValue());
        DeadSucc->removePredecessor(BI->getParent(), true);
        Worklist.push_back(BranchInst::Create(LiveSucc, BI));
        LPM->deleteSimpleAnalysisValue(BI, L);
        BI->eraseFromParent();
        RemoveFromWorklist(BI, Worklist);
        ++NumSimplify;

        RemoveBlockIfDead(DeadSucc, Worklist, L);
      }
      break;
    }
    }
  }
}