+ 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();
+ new BranchInst(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(new BranchInst(LiveSucc, BI));
+ LPM->deleteSimpleAnalysisValue(BI, L);
+ BI->eraseFromParent();
+ RemoveFromWorklist(BI, Worklist);
+ ++NumSimplify;
+
+ RemoveBlockIfDead(DeadSucc, Worklist, L);
+ }
+ break;
+ }
+ }
+ }