Changeset View
Changeset View
Standalone View
Standalone View
llvm/lib/Transforms/Scalar/SCCP.cpp
| Show First 20 Lines • Show All 270 Lines • ▼ Show 20 Lines | public: | ||||
| bool ResolvedUndefsIn(Function &F); | bool ResolvedUndefsIn(Function &F); | ||||
| bool isBlockExecutable(BasicBlock *BB) const { | bool isBlockExecutable(BasicBlock *BB) const { | ||||
| return BBExecutable.count(BB); | return BBExecutable.count(BB); | ||||
| } | } | ||||
| // isEdgeFeasible - Return true if the control flow edge from the 'From' basic | // isEdgeFeasible - Return true if the control flow edge from the 'From' basic | ||||
| // block to the 'To' basic block is currently feasible. | // block to the 'To' basic block is currently feasible. | ||||
| bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); | bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const; | ||||
| std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const { | std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const { | ||||
| std::vector<ValueLatticeElement> StructValues; | std::vector<ValueLatticeElement> StructValues; | ||||
| auto *STy = dyn_cast<StructType>(V->getType()); | auto *STy = dyn_cast<StructType>(V->getType()); | ||||
| assert(STy && "getStructLatticeValueFor() can be called only on structs"); | assert(STy && "getStructLatticeValueFor() can be called only on structs"); | ||||
| for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { | ||||
| auto I = StructValueState.find(std::make_pair(V, i)); | auto I = StructValueState.find(std::make_pair(V, i)); | ||||
| assert(I != StructValueState.end() && "Value not in valuemap!"); | assert(I != StructValueState.end() && "Value not in valuemap!"); | ||||
| ▲ Show 20 Lines • Show All 412 Lines • ▼ Show 20 Lines | void SCCPSolver::getFeasibleSuccessors(Instruction &TI, | ||||
| } | } | ||||
| LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n'); | LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n'); | ||||
| llvm_unreachable("SCCP: Don't know how to handle this terminator!"); | llvm_unreachable("SCCP: Don't know how to handle this terminator!"); | ||||
| } | } | ||||
| // isEdgeFeasible - Return true if the control flow edge from the 'From' basic | // isEdgeFeasible - Return true if the control flow edge from the 'From' basic | ||||
| // block to the 'To' basic block is currently feasible. | // block to the 'To' basic block is currently feasible. | ||||
| bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { | bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const { | ||||
| // Check if we've called markEdgeExecutable on the edge yet. (We could | // Check if we've called markEdgeExecutable on the edge yet. (We could | ||||
| // be more aggressive and try to consider edges which haven't been marked | // be more aggressive and try to consider edges which haven't been marked | ||||
| // yet, but there isn't any need.) | // yet, but there isn't any need.) | ||||
| return KnownFeasibleEdges.count(Edge(From, To)); | return KnownFeasibleEdges.count(Edge(From, To)); | ||||
| } | } | ||||
| // visit Implementations - Something changed in this instruction, either an | // visit Implementations - Something changed in this instruction, either an | ||||
| // operand made a transition, or the instruction is newly executable. Change | // operand made a transition, or the instruction is newly executable. Change | ||||
| ▲ Show 20 Lines • Show All 1,085 Lines • ▼ Show 20 Lines | for (BasicBlock &BB : F) { | ||||
| } | } | ||||
| if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator())) | if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator())) | ||||
| if (!isa<UndefValue>(RI->getOperand(0))) | if (!isa<UndefValue>(RI->getOperand(0))) | ||||
| ReturnsToZap.push_back(RI); | ReturnsToZap.push_back(RI); | ||||
| } | } | ||||
| } | } | ||||
| // Update the condition for terminators that are branching on indeterminate | static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB, | ||||
| // values, forcing them to use a specific edge. | DomTreeUpdater &DTU) { | ||||
| static void forceIndeterminateEdge(Instruction* I, SCCPSolver &Solver) { | SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors; | ||||
| BasicBlock *Dest = nullptr; | bool HasNonFeasibleEdges = false; | ||||
| Constant *C = nullptr; | for (BasicBlock *Succ : successors(BB)) { | ||||
| if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) { | if (Solver.isEdgeFeasible(BB, Succ)) | ||||
| if (!isa<ConstantInt>(SI->getCondition())) { | FeasibleSuccessors.insert(Succ); | ||||
| // Indeterminate switch; use first case value. | else | ||||
| Dest = SI->case_begin()->getCaseSuccessor(); | HasNonFeasibleEdges = true; | ||||
| C = SI->case_begin()->getCaseValue(); | |||||
| } | |||||
| } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) { | |||||
| if (!isa<ConstantInt>(BI->getCondition())) { | |||||
| // Indeterminate branch; use false. | |||||
| Dest = BI->getSuccessor(1); | |||||
| C = ConstantInt::getFalse(BI->getContext()); | |||||
| } | |||||
| } else if (IndirectBrInst *IBR = dyn_cast<IndirectBrInst>(I)) { | |||||
| if (!isa<BlockAddress>(IBR->getAddress()->stripPointerCasts())) { | |||||
| // Indeterminate indirectbr; use successor 0. | |||||
| Dest = IBR->getSuccessor(0); | |||||
| C = BlockAddress::get(IBR->getSuccessor(0)); | |||||
| } | } | ||||
| } else { | |||||
| llvm_unreachable("Unexpected terminator instruction"); | // All edges feasible, nothing to do. | ||||
| if (!HasNonFeasibleEdges) | |||||
| return false; | |||||
| if (FeasibleSuccessors.size() == 1) { | |||||
efriedma: Iterating over a smallptrset is non-deterministic. | |||||
The updated version no longer iterates over SmallPtrSet :) nikic: The updated version no longer iterates over SmallPtrSet :) | |||||
| // Replace with an unconditional branch to the only feasible successor. | |||||
| Instruction *TI = BB->getTerminator(); | |||||
I'm not sure calling removePredecessor once is enough if there are multiple edges to the same successor, for example in a switch. efriedma: I'm not sure calling removePredecessor once is enough if there are multiple edges to the same… | |||||
I think you are right. removePredecessor() is basically removeIncomingValue() on all phi nodes, and that function only removes a single incoming value. I'll try to come up with a failing test case. nikic: I think you are right. removePredecessor() is basically removeIncomingValue() on all phi nodes… | |||||
This is now fixed. Previously the test case from https://github.com/llvm/llvm-project/commit/eae6bb3807977a2998ac9114a1d6ecb6bdafc3cd crashed. nikic: This is now fixed. Previously the test case from https://github.com/llvm/llvm… | |||||
| assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) || | |||||
| isa<IndirectBrInst>(TI)) && | |||||
| "Terminator must be a br, switch or indirectbr"); | |||||
Not Done ReplyInline ActionsCan we skip creating the unconditional branch if the terminator is already an unconditional branch? Is it possible for this code to see other branches which inherently only have one successor, e.g. catchret? efriedma: Can we skip creating the unconditional branch if the terminator is already an unconditional… | |||||
Any of this code is only executed if there is at least one non-feasible successor, i.e. only cases for which SCCP supports feasible edge analysis (that is more precise than "all successors"). Those are conditional branches, switches and indirectbr, thus the types in the assert. nikic: Any of this code is only executed if there is at least one non-feasible successor, i.e. only… | |||||
| BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin(); | |||||
| SmallVector<DominatorTree::UpdateType, 8> Updates; | |||||
| bool HaveSeenOnlyFeasibleSuccessor = false; | |||||
| for (BasicBlock *Succ : successors(BB)) { | |||||
| if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) { | |||||
| // Don't remove the edge to the only feasible successor the first time | |||||
Not Done ReplyInline ActionsEven if only one basic block is a possible successor, there could still be multiple edges, for example in a switch. (This matters because you might need to update PHI nodes.) ConstantFoldTerminator does some stuff with profile metadata; do we need something similar here? efriedma: Even if only one basic block is a possible successor, there could still be multiple edges, for… | |||||
The profile metadata adjustment is only done when merging cases into the default destination. We don't need to adjust metadata if we convert into an unconditional branch. nikic: The profile metadata adjustment is only done when merging cases into the default destination. | |||||
Any response to this? efriedma: > Even if only one basic block is a possible successor, there could still be multiple edges… | |||||
Sorry, I misunderstood what you meant here and thought this was resolved by the previous change. I've now added two additional test cases in https://github.com/llvm/llvm-project/commit/e20b3079c14d8e68ebc90125eb95156f2e1ee9e4 and fixed this to remove all but one of the edges. nikic: Sorry, I misunderstood what you meant here and thought this was resolved by the previous change. | |||||
| // we see it. We still do need to remove any multi-edges to it though. | |||||
| HaveSeenOnlyFeasibleSuccessor = true; | |||||
| continue; | |||||
Not Done ReplyInline ActionsIs it possible that no successor is feasible? efriedma: Is it possible that no successor is feasible? | |||||
This shouldn't be possible right now, as we always force one successor to be feasible, even if it was undef/unknown. It might be possible in the future if we want to make use of branch-on-undef being UB and all successors being non-feasible. nikic: This shouldn't be possible right now, as we always force one successor to be feasible, even if… | |||||
| } | } | ||||
| if (C) { | |||||
| assert(Solver.isEdgeFeasible(I->getParent(), Dest) && | |||||
| "Didn't find feasible edge?"); | |||||
| (void)Dest; | |||||
| I->setOperand(0, C); | Succ->removePredecessor(BB); | ||||
| Updates.push_back({DominatorTree::Delete, BB, Succ}); | |||||
| } | |||||
| DTU.applyUpdatesPermissive(Updates); | |||||
| BranchInst::Create(OnlyFeasibleSuccessor, BB); | |||||
| TI->eraseFromParent(); | |||||
| } else { | |||||
| llvm_unreachable("Either all successors are feasible, or exactly one is"); | |||||
| } | } | ||||
| return true; | |||||
| } | } | ||||
| bool llvm::runIPSCCP( | bool llvm::runIPSCCP( | ||||
| Module &M, const DataLayout &DL, | Module &M, const DataLayout &DL, | ||||
| std::function<const TargetLibraryInfo &(Function &)> GetTLI, | std::function<const TargetLibraryInfo &(Function &)> GetTLI, | ||||
| function_ref<AnalysisResultsForFn(Function &)> getAnalysis) { | function_ref<AnalysisResultsForFn(Function &)> getAnalysis) { | ||||
| SCCPSolver Solver(DL, GetTLI, M.getContext()); | SCCPSolver Solver(DL, GetTLI, M.getContext()); | ||||
| ▲ Show 20 Lines • Show All 96 Lines • ▼ Show 20 Lines | for (BasicBlock *BB : BlocksToErase) { | ||||
| changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false, | changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false, | ||||
| /*PreserveLCSSA=*/false, &DTU); | /*PreserveLCSSA=*/false, &DTU); | ||||
| } | } | ||||
| if (!Solver.isBlockExecutable(&F.front())) | if (!Solver.isBlockExecutable(&F.front())) | ||||
| NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(), | NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(), | ||||
| /*UseLLVMTrap=*/false, | /*UseLLVMTrap=*/false, | ||||
| /*PreserveLCSSA=*/false, &DTU); | /*PreserveLCSSA=*/false, &DTU); | ||||
| // Now that all instructions in the function are constant folded, | for (BasicBlock &BB : F) | ||||
| // use ConstantFoldTerminator to get rid of in-edges, record DT updates and | removeNonFeasibleEdges(Solver, &BB, DTU); | ||||
| // delete dead BBs. | |||||
| for (BasicBlock *DeadBB : BlocksToErase) { | for (BasicBlock *DeadBB : BlocksToErase) | ||||
| // If there are any PHI nodes in this successor, drop entries for BB now. | |||||
| for (Value::user_iterator UI = DeadBB->user_begin(), | |||||
| UE = DeadBB->user_end(); | |||||
| UI != UE;) { | |||||
| // Grab the user and then increment the iterator early, as the user | |||||
| // will be deleted. Step past all adjacent uses from the same user. | |||||
| auto *I = dyn_cast<Instruction>(*UI); | |||||
| do { ++UI; } while (UI != UE && *UI == I); | |||||
| // Ignore blockaddress users; BasicBlock's dtor will handle them. | |||||
| if (!I) continue; | |||||
| // If we have forced an edge for an indeterminate value, then force the | |||||
| // terminator to fold to that edge. | |||||
| forceIndeterminateEdge(I, Solver); | |||||
| BasicBlock *InstBB = I->getParent(); | |||||
| bool Folded = ConstantFoldTerminator(InstBB, | |||||
| /*DeleteDeadConditions=*/false, | |||||
| /*TLI=*/nullptr, &DTU); | |||||
| assert(Folded && | |||||
| "Expect TermInst on constantint or blockaddress to be folded"); | |||||
| (void) Folded; | |||||
| // If we folded the terminator to an unconditional branch to another | |||||
| // dead block, replace it with Unreachable, to avoid trying to fold that | |||||
| // branch again. | |||||
| BranchInst *BI = cast<BranchInst>(InstBB->getTerminator()); | |||||
| if (BI && BI->isUnconditional() && | |||||
| !Solver.isBlockExecutable(BI->getSuccessor(0))) { | |||||
| InstBB->getTerminator()->eraseFromParent(); | |||||
| new UnreachableInst(InstBB->getContext(), InstBB); | |||||
| } | |||||
| } | |||||
| // Mark dead BB for deletion. | |||||
| DTU.deleteBB(DeadBB); | DTU.deleteBB(DeadBB); | ||||
| } | |||||
| for (BasicBlock &BB : F) { | for (BasicBlock &BB : F) { | ||||
| for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) { | for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) { | ||||
| Instruction *Inst = &*BI++; | Instruction *Inst = &*BI++; | ||||
| if (Solver.getPredicateInfoFor(Inst)) { | if (Solver.getPredicateInfoFor(Inst)) { | ||||
| if (auto *II = dyn_cast<IntrinsicInst>(Inst)) { | if (auto *II = dyn_cast<IntrinsicInst>(Inst)) { | ||||
| if (II->getIntrinsicID() == Intrinsic::ssa_copy) { | if (II->getIntrinsicID() == Intrinsic::ssa_copy) { | ||||
| Value *Op = II->getOperand(0); | Value *Op = II->getOperand(0); | ||||
| ▲ Show 20 Lines • Show All 99 Lines • Show Last 20 Lines | |||||
Iterating over a smallptrset is non-deterministic.