Index: include/llvm/Transforms/Utils/Local.h =================================================================== --- include/llvm/Transforms/Utils/Local.h +++ include/llvm/Transforms/Utils/Local.h @@ -138,7 +138,8 @@ /// the basic block that was pointed to. /// bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, - unsigned BonusInstThreshold, AssumptionCache *AC = nullptr); + unsigned BonusInstThreshold, AssumptionCache *AC = nullptr, + DominatorTree *DT = nullptr, bool *RemovedManyBB = nullptr); /// FlatternCFG - This function is used to flatten a CFG. For /// example, it uses parallel-and and parallel-or mode to collapse Index: lib/Transforms/Scalar/SimplifyCFGPass.cpp =================================================================== --- lib/Transforms/Scalar/SimplifyCFGPass.cpp +++ lib/Transforms/Scalar/SimplifyCFGPass.cpp @@ -32,6 +32,7 @@ #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Module.h" @@ -128,7 +129,8 @@ /// iterating until no more changes are made. static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI, AssumptionCache *AC, - unsigned BonusInstThreshold) { + unsigned BonusInstThreshold, + DominatorTree *DT = nullptr) { bool Changed = false; bool LocalChange = true; while (LocalChange) { @@ -136,8 +138,13 @@ // Loop over all of the basic blocks and remove them if they are unneeded. for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) { - if (SimplifyCFG(&*BBIt++, TTI, BonusInstThreshold, AC)) { + bool ResetBBIt = false; + // ResetBBIt is true when more than one block is removed by SimplifyCFG + // and the iterator could be stale. + if (SimplifyCFG(&*BBIt++, TTI, BonusInstThreshold, AC, DT, &ResetBBIt)) { LocalChange = true; + if (ResetBBIt) + break; ++NumSimpl; } } @@ -147,10 +154,11 @@ } static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI, - AssumptionCache *AC, int BonusInstThreshold) { + AssumptionCache *AC, int BonusInstThreshold, + DominatorTree *DT = nullptr) { bool EverChanged = removeUnreachableBlocks(F); EverChanged |= mergeEmptyReturnBlocks(F); - EverChanged |= iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold); + EverChanged |= iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold, DT); // If neither pass changed anything, we're done. if (!EverChanged) return false; @@ -164,7 +172,7 @@ return true; do { - EverChanged = iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold); + EverChanged = iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold, DT); EverChanged |= removeUnreachableBlocks(F); } while (EverChanged); @@ -192,6 +200,7 @@ struct CFGSimplifyPass : public FunctionPass { static char ID; // Pass identification, replacement for typeid unsigned BonusInstThreshold; + DominatorTree *DT; std::function PredicateFtor; CFGSimplifyPass(int T = -1, @@ -211,11 +220,13 @@ &getAnalysis().getAssumptionCache(F); const TargetTransformInfo &TTI = getAnalysis().getTTI(F); - return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold); + DT = &getAnalysis().getDomTree(); + return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold, DT); } void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addPreserved(); } @@ -227,6 +238,7 @@ false) INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, false) Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -130,6 +130,11 @@ const DataLayout &DL; unsigned BonusInstThreshold; AssumptionCache *AC; + DominatorTree *DT; + // Indicator for the iterator problem: when more than one + // block is removed an iterator over all blocks in a function + // could be stale. In this case the variable is set to true. + bool *RemovedManyBB; Value *isValueEqualityComparison(TerminatorInst *TI); BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, std::vector &Cases); @@ -152,8 +157,10 @@ public: SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL, - unsigned BonusInstThreshold, AssumptionCache *AC) - : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC) {} + unsigned BonusInstThreshold, AssumptionCache *AC, + DominatorTree *DT = nullptr, bool *RemovedManyBB = nullptr) + : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC), + DT(DT), RemovedManyBB(RemovedManyBB) {} bool run(BasicBlock *BB); }; } @@ -3029,7 +3036,7 @@ static bool TryToSimplifyUncondBranchWithICmpInIt( ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI, unsigned BonusInstThreshold, - AssumptionCache *AC) { + AssumptionCache *AC, DominatorTree *DT, bool *RemovedManyBB) { BasicBlock *BB = ICI->getParent(); // If the block has any PHIs in it or the icmp has multiple uses, it is too @@ -3062,7 +3069,8 @@ ICI->eraseFromParent(); } // BB is now empty, so it is likely to simplify away. - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; } // Ok, the block is reachable from the default dest. If the constant we're @@ -3078,7 +3086,8 @@ ICI->replaceAllUsesWith(V); ICI->eraseFromParent(); // BB is now empty, so it is likely to simplify away. - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; } // The use of the icmp has to be in the 'end' block, by the only PHI node in @@ -4844,12 +4853,14 @@ // see if that predecessor totally determines the outcome of this switch. if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; Value *Cond = SI->getCondition(); if (SelectInst *Select = dyn_cast(Cond)) if (SimplifySwitchOnSelect(SI, Select)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; // If the block only contains the switch, see if we can fold the block // away into any preds. @@ -4859,25 +4870,31 @@ ++BBI; if (SI == &*BBI) if (FoldValueComparisonIntoPredecessors(SI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; } // Try to transform the switch into an icmp and a branch. if (TurnSwitchRangeIntoICmp(SI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; // Remove unreachable cases. if (EliminateDeadSwitchCases(SI, AC, DL)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; if (SwitchToSelect(SI, Builder, AC, DL)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; if (ForwardSwitchConditionToPHI(SI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; if (SwitchToLookupTable(SI, Builder, DL, TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; return false; } @@ -4914,7 +4931,8 @@ if (SelectInst *SI = dyn_cast(IBI->getAddress())) { if (SimplifyIndirectBrOnSelect(IBI, SI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; } return Changed; } @@ -5014,8 +5032,8 @@ for (++I; isa(I); ++I) ; if (I->isTerminator() && - TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI, - BonusInstThreshold, AC)) + TryToSimplifyUncondBranchWithICmpInIt( + ICI, Builder, DL, TTI, BonusInstThreshold, AC, DT, RemovedManyBB)) return true; } @@ -5033,7 +5051,8 @@ // predecessor and use logical operations to update the incoming value // for PHI nodes in common successor. if (FoldBranchToCommonDest(BI, BonusInstThreshold)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; return false; } @@ -5058,7 +5077,8 @@ // switch. if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; // This block must be empty, except for the setcond inst, if it exists. // Ignore dbg intrinsics. @@ -5068,14 +5088,16 @@ ++I; if (&*I == BI) { if (FoldValueComparisonIntoPredecessors(BI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; } else if (&*I == cast(BI->getCondition())){ ++I; // Ignore dbg intrinsics. while (isa(I)) ++I; if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; } } @@ -5087,7 +5109,8 @@ // branches to us and one of our successors, fold the comparison into the // predecessor and use logical operations to pick the right destination. if (FoldBranchToCommonDest(BI, BonusInstThreshold)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; // We have a conditional branch to two blocks that are only reachable // from BI. We know that the condbr dominates the two blocks, so see if @@ -5096,7 +5119,8 @@ if (BI->getSuccessor(0)->getSinglePredecessor()) { if (BI->getSuccessor(1)->getSinglePredecessor()) { if (HoistThenElseCodeToIf(BI, TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; } else { // If Successor #1 has multiple preds, we may be able to conditionally // execute Successor #0 if it branches to Successor #1. @@ -5104,7 +5128,9 @@ if (Succ0TI->getNumSuccessors() == 1 && Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, + RemovedManyBB) | + true; } } else if (BI->getSuccessor(1)->getSinglePredecessor()) { // If Successor #0 has multiple preds, we may be able to conditionally @@ -5113,7 +5139,8 @@ if (Succ1TI->getNumSuccessors() == 1 && Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; } // If this is a branch on a phi node in the current block, thread control @@ -5121,14 +5148,17 @@ if (PHINode *PN = dyn_cast(BI->getCondition())) if (PN->getParent() == BI->getParent()) if (FoldCondBranchOnPHI(BI, DL)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) | + true; // Scan predecessor blocks for conditional branches. for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) if (BranchInst *PBI = dyn_cast((*PI)->getTerminator())) if (PBI != BI && PBI->isConditional()) if (SimplifyCondBranchToCondBranch(PBI, BI, DL)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, + RemovedManyBB) | + true; // Look for diamond patterns. if (MergeCondStores) @@ -5136,8 +5166,10 @@ if (BranchInst *PBI = dyn_cast(PrevBB->getTerminator())) if (PBI != BI && PBI->isConditional()) if (mergeConditionalStores(PBI, BI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; - + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, + RemovedManyBB) | + true; + return false; } @@ -5209,19 +5241,96 @@ return false; } +// Remove all blocks dominated by BB. When DT is null remove BB only. +// Return true when more than one block has been removed. +static uint64_t removeAllBlocksDominated(BasicBlock *BB, DominatorTree *DT) { + + // This is a helper routine for run(). Protect from unintended invocations. + assert(((pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) || + BB->getSinglePredecessor() == BB) && + "Invalid BasicBlock \n"); + + SmallVector Worklist; + SmallVector DominatedBlocks; + ; + SmallPtrSet Visited; + + BasicBlock *Root = BB; + DomTreeNode *DRoot = DT ? DT->getNode(Root) : nullptr; + uint64_t Count = 0; + + // Initialize Worklist + if (Visited.insert(Root).second) { + Worklist.push_back(Root); + DominatedBlocks.push_back(Root); + } + + // Collect all block dominate by Root (includes Root) + // Predecessors of all blocks collected must be + // dominated by Root also. This ensures that only + // blocks of the original control-flow graph are + // considered, and not blocks inserted by SimplifyCFG. + // For this reason, dominance must be checked on dominator + // nodes rather than just basic blocks. + while (!Worklist.empty()) { + BasicBlock *SeedBB = Worklist.pop_back_val(); + for (auto *SuccBB : make_range(succ_begin(SeedBB), succ_end(SeedBB))) + if (DT) { + DomTreeNode *DSuccBB = DT->getNode(SuccBB); + if (DRoot && DSuccBB && DT->dominates(DRoot, DSuccBB)) { + bool DominatesAll = true; + for (auto *PredBB : + make_range(pred_begin(SuccBB), pred_end(SuccBB))) { + DomTreeNode *DPredBB = DT->getNode(PredBB); + if (!DPredBB || !DT->dominates(DRoot, DPredBB)) { + DominatesAll = false; + break; + } + } + if (DominatesAll) + if (Visited.insert(SuccBB).second) { + Worklist.push_back(SuccBB); + DominatedBlocks.push_back(SuccBB); + } + } + } + } + // Remove all block dominated by Root + // Note: At least Root is removed here + while (!DominatedBlocks.empty()) { + BasicBlock *DeleteBB = DominatedBlocks.pop_back_val(); + if (DeleteBB != Root && !pred_empty(DeleteBB)) + for (auto *PredBB : + make_range(pred_begin(DeleteBB), pred_end(DeleteBB))) { + DeleteBB->removePredecessor(PredBB); + TerminatorInst *TI = PredBB->getTerminator(); + if (!TI->use_empty()) + TI->replaceAllUsesWith(UndefValue::get(TI->getType())); + new UnreachableInst(TI->getContext(), TI); + TI->eraseFromParent(); + } + Count++; + DeleteDeadBlock(DeleteBB); + } + assert(Count && "Root block not removed!"); + return Count; +} + bool SimplifyCFGOpt::run(BasicBlock *BB) { bool Changed = false; assert(BB && BB->getParent() && "Block not embedded in function!"); assert(BB->getTerminator() && "Degenerate basic block encountered!"); - // Remove basic blocks that have no predecessors (except the entry block)... + // Remove basic blocks that have no predecessors (except the entry block) // or that just have themself as a predecessor. These are unreachable. + // When DT is available also remove all blocks dominated by that block. if ((pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) || BB->getSinglePredecessor() == BB) { - DEBUG(dbgs() << "Removing BB: \n" << *BB); - DeleteDeadBlock(BB); + uint64_t BlocksRemoved = removeAllBlocksDominated(BB, DT); + if (RemovedManyBB) + *RemovedManyBB = BlocksRemoved > 1; return true; } @@ -5283,7 +5392,8 @@ /// of the CFG. It returns true if a modification was made. /// bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, - unsigned BonusInstThreshold, AssumptionCache *AC) { + unsigned BonusInstThreshold, AssumptionCache *AC, + DominatorTree *DT, bool *RemovedManyBB) { return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), - BonusInstThreshold, AC).run(BB); + BonusInstThreshold, AC, DT, RemovedManyBB).run(BB); } Index: test/Transforms/SimplifyCFG/InfLoop.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/InfLoop.ll @@ -0,0 +1,171 @@ +; RUN: opt < %s -simplifycfg -disable-output +; END. + +target datalayout = "e-m:o-p:32:32-f64:32:64-v64:32:64-v128:32:128-a:0:32-n32-S32" +target triple = "thumbv7-apple-ios9.0.0" + +%struct.anon = type { %struct.anon.0, i32, i32, %union.T1 } +%struct.anon.0 = type { i32, [256 x i32], [256 x i8] } +%union.T1 = type { %struct.F} +%struct.G_t = type { i32, i32, i32, i32, i32, i8 } +%struct.F = type { i32 } +%struct.S_t = type { %struct.anon.1 } +%struct.anon.1 = type { i64, i64, i64, i64, i64, i64, i64, i64 } +%struct.T1 = type { %union.T1*, i32, %struct.L_t } +%struct.L_t = type { i32*, i32, i32 } +%struct.T2 = type { [256 x i32] } + +@U = internal global %struct.anon zeroinitializer, align 4 +@S = external global %struct.S_t, align 4 +@G = external global %struct.G_t, align 4 +@table = external global [17 x i32], align 4 +@T1 = external global %struct.T1, align 4 +declare i32 @bar() +declare i32 @extend(i32) +declare i8* @update(i32 %t1Ix, i32 %old_sz, i32 %sz) +declare i32 @getix(i8*) + + +define void @main() { +entry: + %0 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 2), align 4 + %cmp.i = icmp eq i32 %0, -1 + br i1 %cmp.i, label %if.then, label %if.end + +if.then: ; preds = %entry + br label %if.end + +if.end: ; preds = %entry, %if.then + %1 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 2), align 4 + %bf.load = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 3, i32 0, i32 0), align 4 + %cmp = icmp slt i32 %bf.load, 0 + br i1 %cmp, label %if.end7, label %cond.false + +cond.false: ; preds = %if.end + %bf.clear = shl i32 %bf.load, 1 + %add = and i32 %bf.clear, 30 + %shl = add nuw nsw i32 %add, 2 + br label %if.end7 + +if.end7: ; preds = %if.end, %cond.false + %old_sz.0 = phi i32 [ %shl, %cond.false ], [ 0, %if.end ] + %2 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 0, i32 0), align 4 + %cmp.i52 = icmp eq i32 %2, 1 + br i1 %cmp.i52, label %if.then9, label %if.else10 + +if.then9: ; preds = %if.end7 + %3 = load i64, i64* getelementptr inbounds (%struct.S_t, %struct.S_t* @S, i32 0, i32 0, i32 5), align 4 + %inc = add i64 %3, 1 + store i64 %inc, i64* getelementptr inbounds (%struct.S_t, %struct.S_t* @S, i32 0, i32 0, i32 5), align 4 + %4 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 0, i32 1, i32 0), align 4 + br label %if.end29 + +if.else10: ; preds = %if.end7 + %cmp11 = icmp ugt i32 %2, 13 + br i1 %cmp11, label %if.then12, label %if.else14 + +if.then12: ; preds = %if.else10 + %call13 = tail call fastcc i8* @update(i32 %1, i32 %old_sz.0, i32 16) + %5 = bitcast i8* %call13 to %struct.T2* + br label %if.end26 + +if.else14: ; preds = %if.else10 + %6 = load i8, i8* getelementptr inbounds (%struct.G_t, %struct.G_t* @G, i32 0, i32 5), align 4 + %tobool = icmp eq i8 %6, 0 + br i1 %tobool, label %lor.rhs, label %if.then18 + +lor.rhs: ; preds = %if.else14 + %tobool.not.i = icmp eq i8 %6, 0 + br i1 %tobool.not.i, label %if.else21, label %if.end.i54 + +if.end.i54: ; preds = %lor.rhs + %add.i = add i32 %2, 1 + %call.i = tail call i32 @extend(i32 %add.i) + %7 = load i32, i32* getelementptr inbounds (%struct.G_t, %struct.G_t* @G, i32 0, i32 3), align 4 + %add1.i = add i32 %7, %call.i + %8 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 0, i32 0), align 4 + %shl.i = shl i32 1, %add1.i + %9 = load i32, i32* getelementptr inbounds (%struct.G_t, %struct.G_t* @G, i32 0, i32 4), align 4 + %add9.i = add i32 %9, 1 + br label %for.cond.i + +for.cond.i: ; preds = %if.end6.i, %if.end.i54 + %ix.0.i = phi i32 [ 0, %if.end.i54 ], [ %inc.i55, %if.end6.i ] + %ret.0.off0.i = phi i1 [ false, %if.end.i54 ], [ %.ret.0.off0.i, %if.end6.i ] + %cmp2.i = icmp ult i32 %ix.0.i, %8 + br i1 %cmp2.i, label %for.body.i, label %TmpSimpleNeedExt.exit + +for.body.i: ; preds = %for.cond.i + %arrayidx.i = getelementptr inbounds %struct.anon, %struct.anon* @U, i32 0, i32 0, i32 2, i32 %ix.0.i + %10 = load i8, i8* %arrayidx.i, align 1 + %conv.i = zext i8 %10 to i32 + %cmp3.i = icmp sgt i32 %conv.i, %shl.i + br i1 %cmp3.i, label %if.else21, label %if.end6.i + +if.end6.i: ; preds = %for.body.i + %cmp10.i = icmp ugt i32 %conv.i, %add9.i + %.ret.0.off0.i = or i1 %ret.0.off0.i, %cmp10.i + %inc.i55 = add i32 %ix.0.i, 1 + br label %for.cond.i + +TmpSimpleNeedExt.exit: ; preds = %for.cond.i + br i1 %ret.0.off0.i, label %if.then18, label %if.else21 + +if.then18: ; preds = %if.else14, %TmpSimpleNeedExt.exit + %11 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 0, i32 0), align 4 + %add.i56 = add i32 %11, 1 + %arrayidx = getelementptr inbounds [17 x i32], [17 x i32]* @table, i32 0, i32 %add.i56 + %12 = load i32, i32* %arrayidx, align 4 + %call20 = tail call fastcc i8* @update(i32 %1, i32 %old_sz.0, i32 %12) + %13 = bitcast i8* %call20 to %struct.T2* + br label %if.end26 + +if.else21: ; preds = %for.body.i, %lor.rhs, %TmpSimpleNeedExt.exit + %call22 = tail call fastcc i32 @bar() + %arrayidx23 = getelementptr inbounds [17 x i32], [17 x i32]* @table, i32 0, i32 %call22 + %14 = load i32, i32* %arrayidx23, align 4 + %call24 = tail call fastcc i8* @update(i32 %1, i32 %old_sz.0, i32 %14) + %15 = bitcast i8* %call24 to %struct.T2* + br label %if.end26 + +if.end26: ; preds = %if.then18, %if.else21, %if.then12 + %new_.0 = phi i8* [ %call13, %if.then12 ], [ %call20, %if.then18 ], [ %call24, %if.else21 ] + %sz.0 = phi i32 [ 16, %if.then12 ], [ %12, %if.then18 ], [ %14, %if.else21 ] + %call27 = tail call i32 @getix(i8* %new_.0) + %16 = load %union.T1*, %union.T1** getelementptr inbounds (%struct.T1, %struct.T1* @T1, i32 0, i32 0), align 4 + %17 = getelementptr inbounds %union.T1, %union.T1* %16, i32 %1, i32 0, i32 0 + %bf.load.i = load i32, i32* %17, align 4 + %cmp.i51 = icmp slt i32 %bf.load.i, 0 + br i1 %cmp.i51, label %if.then.i, label %if.end.i + +if.then.i: ; preds = %if.end26 + %18 = load i32, i32* getelementptr inbounds (%struct.T1, %struct.T1* @T1, i32 0, i32 2, i32 2), align 4 + %inc.i = add i32 %18, 1 + store i32 %inc.i, i32* getelementptr inbounds (%struct.T1, %struct.T1* @T1, i32 0, i32 2, i32 2), align 4 + br label %if.end.i + +if.end.i: ; preds = %if.then.i, %if.end26 + %and.i = and i32 %call27, 1 + %cmp1.i = icmp eq i32 %and.i, 0 + br i1 %cmp1.i, label %main.exit, label %if.then2.i + +if.then2.i: ; preds = %if.end.i + %.pre.i = load %union.T1*, %union.T1** getelementptr inbounds (%struct.T1, %struct.T1* @T1, i32 0, i32 0), align 4 + br label %main.exit + +main.exit: ; preds = %if.end.i, %if.then2.i + %19 = phi %union.T1* [ %.pre.i, %if.then2.i ], [ %16, %if.end.i ] + %shr.i = lshr i32 %sz.0, 1 + %sub.i = add nuw i32 %shr.i, 15 + %bf.value.i = and i32 %sub.i, 15 + %20 = shl i32 %call27, 3 + %bf.shl.i = and i32 %20, 2147483632 + %bf.set10.i = or i32 %bf.value.i, %bf.shl.i + %ci = getelementptr inbounds %union.T1, %union.T1* %19, i32 %1, i32 0, i32 0 + store i32 %bf.set10.i, i32* %ci, align 1 + br label %if.end29 + +if.end29: ; preds = %main.exit, %if.then9 + store i32 -1, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 2), align 4 + ret void +}