#define DEBUG_TYPE "sil-simplify-cfg" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Allocator.h" #include "swift/SIL/SILInstruction.h" #include "swift/SIL/InstructionUtils.h" #include "swift/SILOptimizer/Analysis/DominanceAnalysis.h" #include "swift/SILOptimizer/Utils/CFG.h" #include "swift/SILOptimizer/Utils/Local.h" #include "swift/SILOptimizer/Utils/SILInliner.h" using namespace swift; namespace { /// This is a class implementing a dominator-based jump-threading /// for checked_cast_br [exact]. class CheckedCastBrJumpThreading { // Basic block of the current checked_cast_br instruction. SILBasicBlock *BB; // Condition used by the current checked_cast_br instruction. SILValue Condition; SILBasicBlock *ArgBB; // The current function to be optimized. SILFunction *Fn; // Dominator information to be used. DominanceInfo *DT; // List of predecessors. typedef SmallVector PredList; // Predecessors reached only via a path along the // success branch of the dominating checked_cast_br. PredList SuccessPreds; // Predecessors reached only via a path along the // failure branch of the dominating checked_cast_br. PredList FailurePreds; // All other predecessors, where the outcome of the // checked_cast_br along the path is not known. unsigned numUnknownPreds = 0; // Basic blocks to be added to for reprocessing // after jump-threading is done. SmallVectorImpl &BlocksForWorklist; // Information for transforming a single checked_cast_br. // This is the output of the optimization's analysis phase. struct Edit { // The block containing the checked_cast_br. SILBasicBlock *CCBBlock; // Copy of CheckedCastBrJumpThreading::SuccessPreds. PredList SuccessPreds; // Copy of CheckedCastBrJumpThreading::FailurePreds. PredList FailurePreds; // The argument of the dominating checked_cast_br's successor block. SILValue SuccessArg; bool InvertSuccess; // True if CheckedCastBrJumpThreading::numUnknownPreds is not 0. bool hasUnknownPreds; Edit(SILBasicBlock *CCBBlock, bool InvertSuccess, const PredList &SuccessPreds, const PredList &FailurePreds, bool hasUnknownPreds, SILValue SuccessArg) : CCBBlock(CCBBlock), SuccessPreds(SuccessPreds), FailurePreds(FailurePreds), SuccessArg(SuccessArg), InvertSuccess(InvertSuccess), hasUnknownPreds(hasUnknownPreds) { } void modifyCFGForUnknownPreds(); void modifyCFGForFailurePreds(Optional &Cloner); void modifyCFGForSuccessPreds(Optional &Cloner); }; // Contains an entry for each checked_cast_br to be optimized. llvm::SmallVector Edits; llvm::SpecificBumpPtrAllocator EditAllocator; // Keeps track of what blocks we change the terminator instruction. llvm::SmallPtrSet BlocksToEdit; // Keeps track of what blocks we clone. llvm::SmallPtrSet BlocksToClone; bool areEquivalentConditionsAlongPaths(CheckedCastBranchInst *DomCCBI); bool areEquivalentConditionsAlongSomePaths(CheckedCastBranchInst *DomCCBI, SILValue DomCondition); bool handleArgBBIsEntryBlock(SILBasicBlock *ArgBB, CheckedCastBranchInst *DomCCBI); bool checkCloningConstraints(); void classifyPredecessor( SILBasicBlock *Pred, bool SuccessDominates, bool FailureDominates); SILValue isArgValueEquivalentToCondition(SILValue Value, SILBasicBlock *DomBB, SILValue DomValue, DominanceInfo *DT); bool trySimplify(CheckedCastBranchInst *CCBI); public: CheckedCastBrJumpThreading(SILFunction *Fn, DominanceInfo *DT, SmallVectorImpl &BlocksForWorklist) : Fn(Fn), DT(DT), BlocksForWorklist(BlocksForWorklist) { } void optimizeFunction(); }; } // end anonymous namespace /// Estimate the cost of inlining a given basic block. static unsigned basicBlockInlineCost(SILBasicBlock *BB, unsigned Cutoff) { unsigned Cost = 0; for (auto &I : *BB) { auto ICost = instructionInlineCost(I); Cost += unsigned(ICost); if (Cost > Cutoff) return Cost; } return Cost; } /// We cannot duplicate blocks with AllocStack instructions (they need to be /// FIFO). Other instructions can be duplicated. static bool canDuplicateBlock(SILBasicBlock *BB) { for (auto &I : *BB) { if (!I.isTriviallyDuplicatable()) return false; } return true; } /// Classify a predecessor of a BB containing checked_cast_br as being /// reachable via success or failure branches of a dominating checked_cast_br /// or as unknown if it can be reached via success or failure branches /// at the same time. void CheckedCastBrJumpThreading::classifyPredecessor( SILBasicBlock *Pred, bool SuccessDominates, bool FailureDominates) { if (SuccessDominates == FailureDominates) { numUnknownPreds++; return; } if (SuccessDominates) { SuccessPreds.push_back(Pred); return; } assert(FailureDominates && "success and failure should be mutual exclusive"); FailurePreds.push_back(Pred); } /// Check if the root value for Value that comes /// along the path from DomBB is equivalent to the /// DomCondition. SILValue CheckedCastBrJumpThreading::isArgValueEquivalentToCondition( SILValue Value, SILBasicBlock *DomBB, SILValue DomValue, DominanceInfo *DT) { SmallPtrSet SeenValues; DomValue = stripClassCasts(DomValue); while (true) { Value = stripClassCasts(Value); if (Value == DomValue) return Value; // We know how to propagate through BBArgs only. auto *V = dyn_cast(Value); if (!V) return SILValue(); // Have we visited this BB already? if (!SeenValues.insert(Value).second) return SILValue(); if (SeenValues.size() > 10) return SILValue(); SmallVector IncomingValues; if (!V->getIncomingValues(IncomingValues) || IncomingValues.empty()) return SILValue(); ValueBase *Def = nullptr; for (auto IncomingValue : IncomingValues) { // Each incoming value should be either from a block // dominated by DomBB or it should be the value used in // condition in DomBB Value = stripClassCasts(IncomingValue); if (Value == DomValue) continue; // Values should be the same if (!Def) Def = Value; if (Def != Value) return SILValue(); if (!DT->dominates(DomBB, Value->getParentBB())) return SILValue(); // OK, this value is a potential candidate } Value = IncomingValues[0]; } } void CheckedCastBrJumpThreading::Edit::modifyCFGForUnknownPreds() { if (!hasUnknownPreds) return; // Check the FailureBB if it is a BB that contains a class_method // referring to the same value as a condition. This pattern is typical // for method chaining code like obj.method1().method2().etc() auto *CCBI = cast(CCBBlock->getTerminator()); SILInstruction *Inst = &*CCBI->getFailureBB()->begin(); if (ClassMethodInst *CMI = dyn_cast(Inst)) { if (CMI->getOperand() == stripClassCasts(CCBI->getOperand())) { // Replace checked_cast_br by branch to FailureBB. SILBuilder(CCBI->getParent()).createBranch(CCBI->getLoc(), CCBI->getFailureBB()); CCBI->eraseFromParent(); } } } /// Create a copy of the BB as a landing BB /// for all FailurePreds. void CheckedCastBrJumpThreading::Edit:: modifyCFGForFailurePreds(Optional &Cloner) { if (FailurePreds.empty()) return; assert(!Cloner.hasValue()); Cloner.emplace(BasicBlockCloner(CCBBlock)); Cloner->clone(); SILBasicBlock *TargetFailureBB = Cloner->getDestBB(); auto *TI = TargetFailureBB->getTerminator(); SILBuilderWithScope Builder(TI); // This BB copy branches to a FailureBB. auto *CCBI = cast(CCBBlock->getTerminator()); Builder.createBranch(TI->getLoc(), CCBI->getFailureBB()); TI->eraseFromParent(); splitIfCriticalEdge(CCBBlock, CCBI->getFailureBB()); // Redirect all FailurePreds to the copy of BB. for (auto *Pred : FailurePreds) { TermInst *TI = Pred->getTerminator(); // Replace branch to BB by branch to TargetFailureBB. replaceBranchTarget(TI, CCBBlock, TargetFailureBB, /*PreserveArgs=*/true); } } /// Create a copy of the BB or reuse BB as /// a landing basic block for all FailurePreds. void CheckedCastBrJumpThreading::Edit:: modifyCFGForSuccessPreds(Optional &Cloner) { auto *CCBI = cast(CCBBlock->getTerminator()); if (InvertSuccess) { SILBuilder B(CCBBlock); B.createBranch(CCBI->getLoc(), CCBI->getFailureBB()); CCBI->eraseFromParent(); return; } if (hasUnknownPreds) { if (!SuccessPreds.empty()) { // Create a copy of the BB as a landing BB. // for all SuccessPreds. assert(!Cloner.hasValue()); Cloner.emplace(BasicBlockCloner(CCBBlock)); Cloner->clone(); SILBasicBlock *TargetSuccessBB = Cloner->getDestBB(); auto *TI = TargetSuccessBB->getTerminator(); SILBuilderWithScope Builder(TI); // This BB copy branches to SuccessBB. // Take argument value from the dominating BB. Builder.createBranch(TI->getLoc(), CCBI->getSuccessBB(), {SuccessArg}); TI->eraseFromParent(); splitIfCriticalEdge(CCBBlock, CCBI->getSuccessBB()); // Redirect all SuccessPreds to the copy of BB. for (auto *Pred : SuccessPreds) { TermInst *TI = Pred->getTerminator(); // Replace branch to BB by branch to TargetSuccessBB. replaceBranchTarget(TI, CCBBlock, TargetSuccessBB, /*PreserveArgs=*/true); } } return; } // There are no predecessors where it is not clear // if they are dominated by a success or failure branch // of DomBB. Therefore, there is no need to clone // the BB for SuccessPreds. Current BB can be re-used // instead as their target. // Add an unconditional jump at the end of the block. // Take argument value from the dominating BB SILBuilder(CCBBlock).createBranch(CCBI->getLoc(), CCBI->getSuccessBB(), {SuccessArg}); CCBI->eraseFromParent(); } /// Handle a special case, where ArgBB is the entry block. bool CheckedCastBrJumpThreading::handleArgBBIsEntryBlock(SILBasicBlock *ArgBB, CheckedCastBranchInst *DomCCBI) { if (ArgBB->getPreds().begin() == ArgBB->getPreds().end()) { // It must be the entry block // See if it is reached over Success or Failure path. bool SuccessDominates = DomCCBI->getSuccessBB() == BB; bool FailureDominates = DomCCBI->getFailureBB() == BB; if (BlocksToEdit.count(ArgBB) != 0) return false; classifyPredecessor(ArgBB, SuccessDominates, FailureDominates); return true; } return false; } // Returns false if cloning required by jump threading cannot // be performed, because some of the constraints are violated. bool CheckedCastBrJumpThreading::checkCloningConstraints() { // Check some cloning related constraints. // If this argument from a different BB, then jump-threading // may require too much code duplication. if (ArgBB && ArgBB != BB) return false; // Bail out if current BB cannot be duplicated. if (!canDuplicateBlock(BB)) return false; // Check if code-bloat would be too big when this BB // is jump-threaded. // TODO: Make InlineCostCutoff parameter configurable? // Dec 1, 2014: // We looked at the inline costs of BBs from our benchmark suite // and found that currently the highest inline cost for the // whole benchmark suite is 12. In 95% of all cases it is <=3. const unsigned InlineCostCutoff = 20; if (basicBlockInlineCost(BB, InlineCostCutoff) >= InlineCostCutoff) return false; return true; } /// If conditions are not equivalent along all paths, try harder /// to check if they are actually equivalent along a subset of paths. /// To do it, try to back-propagate the Condition /// backwards and see if it is actually equivalent to DomCondition. /// along some of the paths. bool CheckedCastBrJumpThreading:: areEquivalentConditionsAlongSomePaths(CheckedCastBranchInst *DomCCBI, SILValue DomCondition) { auto *Arg = dyn_cast(Condition); if (!Arg) return false; ArgBB = Arg->getParent(); SILBasicBlock *DomBB = DomCCBI->getParent(); if (!DT->dominates(DomBB, ArgBB)) return false; // Incoming values for the BBArg. SmallVector IncomingValues; if (ArgBB->getIterator() != ArgBB->getParent()->begin() && (!Arg->getIncomingValues(IncomingValues) || IncomingValues.empty())) return false; // Check for each predecessor, if the incoming value coming from it // is equivalent to the DomCondition. If this is the case, it is // possible to try jump-threading along this path. if (!handleArgBBIsEntryBlock(ArgBB, DomCCBI)) { // ArgBB is not the entry block and has predecessors. unsigned idx = 0; for (auto *PredBB : ArgBB->getPreds()) { // We must avoid that we are going to change a block twice. if (BlocksToEdit.count(PredBB) != 0) return false; auto IncomingValue = IncomingValues[idx]; SILValue ReachingValue = isArgValueEquivalentToCondition( IncomingValue, DomBB, DomCondition, DT); if (ReachingValue == SILValue()) { numUnknownPreds++; idx++; continue; } // Condition is the same if BB is reached over a pass through Pred. DEBUG(llvm::dbgs() << "Condition is the same if reached over "); DEBUG(PredBB->print(llvm::dbgs())); // See if it is reached over Success or Failure path. SILBasicBlock *DomSuccessBB = DomCCBI->getSuccessBB(); bool SuccessDominates = DT->dominates(DomSuccessBB, PredBB) || DT->dominates(DomSuccessBB, BB) || DomSuccessBB == BB; SILBasicBlock *DomFailureBB = DomCCBI->getFailureBB(); bool FailureDominates = DT->dominates(DomFailureBB, PredBB) || DT->dominates(DomFailureBB, BB) || DomFailureBB == BB; classifyPredecessor( PredBB, SuccessDominates, FailureDominates); idx++; } } else { // ArgBB is the entry block. Check that conditions are the equivalent in this // case as well. if (!isArgValueEquivalentToCondition(Condition, DomBB, DomCondition, DT)) return false; } // At this point we know for each predecessor of ArgBB if its reached // over the success, failure or unknown path from DomBB. // Now we can generate a new BB for preds reaching BB over the success // path and a new BB for preds reaching BB over the failure path. // Then we redirect those preds to those new basic blocks. return true; } /// Check if conditions of CCBI and DomCCBI are equivalent along /// all or at least some paths. bool CheckedCastBrJumpThreading:: areEquivalentConditionsAlongPaths(CheckedCastBranchInst *DomCCBI) { // Are conditions equivalent along all paths? SILValue DomCondition = stripClassCasts(DomCCBI->getOperand()); if (DomCondition == Condition) { // Conditions are exactly the same, without any restrictions. // They are equivalent along all paths. // Figure out for each predecessor which branch of // the dominating checked_cast_br is used to reach it. for (auto *PredBB : BB->getPreds()) { // All predecessors should either unconditionally branch // to the current BB or be another checked_cast_br instruction. if (!isa(PredBB->getTerminator()) && !isa(PredBB->getTerminator())) return false; // We must avoid that we are going to change a block twice. if (BlocksToEdit.count(PredBB) != 0) return false; // Don't allow critical edges from PredBB to BB. This ensures that // splitAllCriticalEdges() will not invalidate our predecessor lists. if (!BB->getSinglePredecessor() && !PredBB->getSingleSuccessor()) return false; SILBasicBlock *DomSuccessBB = DomCCBI->getSuccessBB(); bool SuccessDominates = DT->dominates(DomSuccessBB, PredBB) || DomSuccessBB == BB; SILBasicBlock *DomFailureBB = DomCCBI->getFailureBB(); bool FailureDominates = DT->dominates(DomFailureBB, PredBB) || DomFailureBB == BB; classifyPredecessor(PredBB, SuccessDominates, FailureDominates); } return true; } // Check if conditions are equivalent along a subset of reaching paths. return areEquivalentConditionsAlongSomePaths(DomCCBI, DomCondition); } /// Try performing a dominator-based jump-threading for /// checked_cast_br instructions. bool CheckedCastBrJumpThreading::trySimplify(CheckedCastBranchInst *CCBI) { // Init information about the checked_cast_br we try to // jump-thread. BB = CCBI->getParent(); if (BlocksToEdit.count(BB) != 0) return false; Condition = stripClassCasts(CCBI->getOperand()); // Find a dominating checked_cast_br, which performs the same check. for (auto *Node = DT->getNode(BB)->getIDom(); Node; Node = Node->getIDom()) { // Get current dominating block. SILBasicBlock *DomBB = Node->getBlock(); auto *DomTerm = DomBB->getTerminator(); if (!DomTerm->getNumOperands()) continue; // Check that it is a dominating checked_cast_br. auto *DomCCBI = dyn_cast(DomTerm); if (!DomCCBI) continue; // We need to verify that the result type is the same in the // dominating checked_cast_br, but only for non-exact casts. // For exact casts, we are interested only in the // fact that the source operand is the same for // both instructions. if (!CCBI->isExact() && !DomCCBI->isExact()) { if (DomCCBI->getCastType() != CCBI->getCastType()) continue; } // Conservatively check that both checked_cast_br instructions // are either exact or non-exact. This is very conservative, // but safe. // // TODO: // If the dominating checked_cast_br is non-exact, then // it is in general not safe to assume that current exact cast // would have the same outcome. But if the dominating non-exact // checked_cast_br fails, then the current exact cast would // always fail as well. // // If the dominating checked_cast_br is exact then then // it is in general not safe to assume that the current non-exact // cast would have the same outcome. But if the dominating exact // checked_cast_br succeeds, then the current non-exact cast // would always succeed as well. // // TODO: In some specific cases, it is possible to prove that // success or failure of the dominating cast is equivalent to // the success or failure of the current cast, even if one // of them is exact and the other not. This is the case // e.g. if the class has no subclasses. if (DomCCBI->isExact() != CCBI->isExact()) continue; // We need the block argument of the DomSuccessBB. If we are going to // clone it for a previous checked_cast_br the argument will not dominate // the blocks which it's used to dominate anymore. if (BlocksToClone.count(DomCCBI->getSuccessBB()) != 0) continue; // Init state variables for paths analysis SuccessPreds.clear(); FailurePreds.clear(); numUnknownPreds = 0; ArgBB = nullptr; // Are conditions of CCBI and DomCCBI equivalent along (some) paths? // If this is the case, classify all incoming paths into SuccessPreds, // FailurePreds or UnknownPreds depending on how they reach CCBI. if (!areEquivalentConditionsAlongPaths(DomCCBI)) continue; // Check if any jump-threading is required and possible. if (SuccessPreds.empty() && FailurePreds.empty()) return false; // If this check is reachable via success, failure and unknown // at the same time, then we don't know the outcome of the // dominating check. No jump-threading is possible in this case. if (!SuccessPreds.empty() && !FailurePreds.empty() && numUnknownPreds > 0) { return false; } unsigned TotalPreds = SuccessPreds.size() + FailurePreds.size() + numUnknownPreds; // We only need to clone the BB if not all of its // predecessors are in the same group. if (TotalPreds != SuccessPreds.size() && TotalPreds != numUnknownPreds) { // Check some cloning related constraints. if (!checkCloningConstraints()) return false; } bool InvertSuccess = false; if (DomCCBI->isExact() && CCBI->isExact() && DomCCBI->getCastType() != CCBI->getCastType()) { if (TotalPreds == SuccessPreds.size()) { // The dominating exact cast was successful, but it casted to a // different type. Therefore, the current cast fails for sure. // Since we are going to change the BB, // add its successors and predecessors // for re-processing. InvertSuccess = true; } else { // Otherwise, we don't know if the current cast will succeed or // fail. return false; } } // If we have predecessors, where it is not known if they are reached over // success or failure path, we cannot eliminate a checked_cast_br. // We have to generate new dedicated BBs as landing BBs for all // FailurePreds and all SuccessPreds. // Since we are going to change the BB, // add its successors and predecessors // for re-processing. for (auto *B : BB->getPreds()) { BlocksForWorklist.push_back(B); } for (auto *B : BB->getSuccessorBlocks()) { BlocksForWorklist.push_back(B); } // Remember the blocks we are going to change. So that we ignore them // for upcoming checked_cast_br instructions. BlocksToEdit.insert(BB); BlocksToClone.insert(BB); for (auto *B : SuccessPreds) BlocksToEdit.insert(B); for (auto *B : FailurePreds) BlocksToEdit.insert(B); // Record what we want to change. Edit *edit = new (EditAllocator.Allocate()) Edit(BB, InvertSuccess, SuccessPreds, FailurePreds, numUnknownPreds != 0, DomCCBI->getSuccessBB()->getBBArg(0)); Edits.push_back(edit); return true; } // Jump-threading was not possible. return false; } /// Optimize the checked_cast_br instructions in a function. void CheckedCastBrJumpThreading::optimizeFunction() { // We separate the work in two phases: analyse and transform. This avoids // re-calculating the dominator tree for each optimized checked_cast_br. // First phase: analysis. for (auto &BB : *Fn) { // Ignore unreachable blocks. if (!DT->getNode(&BB)) continue; if (auto *CCBI = dyn_cast(BB.getTerminator())) trySimplify(CCBI); } assert(BlocksForWorklist.empty() == Edits.empty()); if (Edits.empty()) return; // Second phase: transformation. // Remove critical edges for the SSA-updater. We do this once and keep the // CFG critical-edge free during our transformations. splitAllCriticalEdges(*Fn, true, nullptr, nullptr); for (Edit *edit : Edits) { Optional Cloner; // Create a copy of the BB as a landing BB // for all FailurePreds. edit->modifyCFGForFailurePreds(Cloner); // Create a copy of the BB or reuse BB as // a landing basic block for all SuccessPreds. edit->modifyCFGForSuccessPreds(Cloner); // Handle unknown preds. edit->modifyCFGForUnknownPreds(); if (Cloner.hasValue()) { updateSSAAfterCloning(*Cloner.getPointer(), Cloner->getDestBB(), edit->CCBBlock, false); if (!Cloner->getDestBB()->pred_empty()) BlocksForWorklist.push_back(Cloner->getDestBB()); } if (!edit->CCBBlock->pred_empty()) BlocksForWorklist.push_back(edit->CCBBlock); } } namespace swift { bool tryCheckedCastBrJumpThreading(SILFunction *Fn, DominanceInfo *DT, SmallVectorImpl &BlocksForWorklist) { CheckedCastBrJumpThreading CCBJumpThreading(Fn, DT, BlocksForWorklist); CCBJumpThreading.optimizeFunction(); return !BlocksForWorklist.empty(); } } // end namespace swift