+/// IsTrivialUnswitchCondition - Check to see if this unswitch condition is
+/// trivial: that is, that the condition controls whether or not the loop does
+/// anything at all. If this is a trivial condition, unswitching produces no
+/// code duplications (equivalently, it produces a simpler loop and a new empty
+/// loop, which gets deleted).
+///
+/// If this is a trivial condition, return ConstantBool::True if the loop body
+/// runs when the condition is true, False if the loop body executes when the
+/// condition is false. Otherwise, return null to indicate a complex condition.
+static ConstantBool *IsTrivialUnswitchCondition(Loop *L, Value *Cond) {
+ BasicBlock *Header = L->getHeader();
+ BranchInst *HeaderTerm = dyn_cast<BranchInst>(Header->getTerminator());
+ ConstantBool *RetVal = 0;
+
+ // If the header block doesn't end with a conditional branch on Cond, we can't
+ // handle it.
+ if (!HeaderTerm || !HeaderTerm->isConditional() ||
+ HeaderTerm->getCondition() != Cond)
+ return 0;
+
+ // Check to see if the conditional branch goes to the latch block. If not,
+ // it's not trivial. This also determines the value of Cond that will execute
+ // the loop.
+ BasicBlock *Latch = L->getLoopLatch();
+ if (HeaderTerm->getSuccessor(1) == Latch)
+ RetVal = ConstantBool::True;
+ else if (HeaderTerm->getSuccessor(0) == Latch)
+ RetVal = ConstantBool::False;
+ else
+ return 0; // Doesn't branch to latch block.
+
+ // The latch block must end with a conditional branch where one edge goes to
+ // the header (this much we know) and one edge goes OUT of the loop.
+ BranchInst *LatchBranch = dyn_cast<BranchInst>(Latch->getTerminator());
+ if (!LatchBranch || !LatchBranch->isConditional()) return 0;
+
+ if (LatchBranch->getSuccessor(0) == Header) {
+ if (L->contains(LatchBranch->getSuccessor(1))) return 0;
+ } else {
+ assert(LatchBranch->getSuccessor(1) == Header);
+ if (L->contains(LatchBranch->getSuccessor(0))) return 0;
+ }
+
+ // We already know that nothing uses any scalar values defined inside of this
+ // loop. As such, we just have to check to see 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.
+ for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; ++I)
+ if (I->mayWriteToMemory())
+ return 0;
+ for (BasicBlock::iterator I = Latch->begin(), E = Latch->end(); I != E; ++I)
+ if (I->mayWriteToMemory())
+ return 0;
+ return RetVal;
+}
+
+/// getLoopUnswitchCost - Return the cost (code size growth) that will happen if
+/// we choose to unswitch the specified loop on the specified value.
+///
+unsigned LoopUnswitch::getLoopUnswitchCost(Loop *L, Value *LIC) {
+ // If the condition is trivial, always unswitch. There is no code growth for
+ // this case.
+ if (IsTrivialUnswitchCondition(L, LIC))
+ return 0;
+
+ unsigned Cost = 0;
+ // FIXME: this is brain dead. It should take into consideration code
+ // shrinkage.
+ for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
+ I != E; ++I) {
+ BasicBlock *BB = *I;
+ // Do not include empty blocks in the cost calculation. This happen due to
+ // loop canonicalization and will be removed.
+ if (BB->begin() == BasicBlock::iterator(BB->getTerminator()))
+ continue;
+
+ // Count basic blocks.
+ ++Cost;
+ }
+
+ return Cost;
+}
+