Index: lib/Transforms/Scalar/SCCP.cpp =================================================================== --- lib/Transforms/Scalar/SCCP.cpp +++ lib/Transforms/Scalar/SCCP.cpp @@ -327,6 +327,10 @@ return BBExecutable.count(BB); } + // isEdgeFeasible - Return true if the control flow edge from the 'From' basic + // block to the 'To' basic block is currently feasible. + bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); + std::vector getStructLatticeValueFor(Value *V) const { std::vector StructValues; auto *STy = dyn_cast(V->getType()); @@ -531,9 +535,9 @@ /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB /// work list if it is not already executable. - void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { + bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) - return; // This edge is already known to be executable! + return false; // This edge is already known to be executable! if (!MarkBlockExecutable(Dest)) { // If the destination is already executable, we just made an *edge* @@ -545,16 +549,13 @@ for (PHINode &PN : Dest->phis()) visitPHINode(PN); } + return true; } // getFeasibleSuccessors - Return a vector of booleans to indicate which // successors are reachable from a given terminator instruction. void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl &Succs); - // isEdgeFeasible - Return true if the control flow edge from the 'From' basic - // block to the 'To' basic block is currently feasible. - bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); - // OperandChangedState - This method is invoked on all of the users of an // instruction that was just changed state somehow. Based on this // information, we need to update the specified user of this instruction. @@ -705,61 +706,10 @@ // isEdgeFeasible - Return true if the control flow edge from the 'From' basic // block to the 'To' basic block is currently feasible. bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { - assert(BBExecutable.count(To) && "Dest should always be alive!"); - - // Make sure the source basic block is executable!! - if (!BBExecutable.count(From)) return false; - - // Check to make sure this edge itself is actually feasible now. - TerminatorInst *TI = From->getTerminator(); - if (auto *BI = dyn_cast(TI)) { - if (BI->isUnconditional()) - return true; - - LatticeVal BCValue = getValueState(BI->getCondition()); - - // Overdefined condition variables mean the branch could go either way, - // undef conditions mean that neither edge is feasible yet. - ConstantInt *CI = BCValue.getConstantInt(); - if (!CI) - return !BCValue.isUnknown(); - - // Constant condition variables mean the branch can only go a single way. - return BI->getSuccessor(CI->isZero()) == To; - } - - // Unwinding instructions successors are always executable. - if (TI->isExceptional()) - return true; - - if (auto *SI = dyn_cast(TI)) { - if (SI->getNumCases() < 1) - return true; - - LatticeVal SCValue = getValueState(SI->getCondition()); - ConstantInt *CI = SCValue.getConstantInt(); - - if (!CI) - return !SCValue.isUnknown(); - - return SI->findCaseValue(CI)->getCaseSuccessor() == To; - } - - // In case of indirect branch and its address is a blockaddress, we mark - // the target as executable. - if (auto *IBR = dyn_cast(TI)) { - LatticeVal IBRValue = getValueState(IBR->getAddress()); - BlockAddress *Addr = IBRValue.getBlockAddress(); - - if (!Addr) - return !IBRValue.isUnknown(); - - // At this point, the indirectbr is branching on a blockaddress. - return Addr->getBasicBlock() == To; - } - - LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << *TI << '\n'); - llvm_unreachable("SCCP: Don't know how to handle this terminator!"); + // 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 + // yet, but there isn't any need.) + return KnownFeasibleEdges.count(Edge(From, To)); } // visit Implementations - Something changed in this instruction, either an @@ -1567,11 +1517,14 @@ } // Otherwise, it is a branch on a symbolic value which is currently - // considered to be undef. Handle this by forcing the input value to the - // branch to false. - markForcedConstant(BI->getCondition(), - ConstantInt::getFalse(TI->getContext())); - return true; + // considered to be undef. Make sure some edge is executable, so a + // branch on "undef" always flows somewhere. + // FIXME: Distinguish between dead code and an LLVM "undef" value. + BasicBlock *DefaultSuccessor = TI->getSuccessor(1); + if (markEdgeExecutable(&BB, DefaultSuccessor)) + return true; + + continue; } if (auto *IBR = dyn_cast(TI)) { @@ -1592,11 +1545,15 @@ } // Otherwise, it is a branch on a symbolic value which is currently - // considered to be undef. Handle this by forcing the input value to the - // branch to the first successor. - markForcedConstant(IBR->getAddress(), - BlockAddress::get(IBR->getSuccessor(0))); - return true; + // considered to be undef. Make sure some edge is executable, so a + // branch on "undef" always flows somewhere. + // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere: + // we can assume the branch has undefined behavior instead. + BasicBlock *DefaultSuccessor = IBR->getSuccessor(0); + if (markEdgeExecutable(&BB, DefaultSuccessor)) + return true; + + continue; } if (auto *SI = dyn_cast(TI)) { @@ -1611,8 +1568,15 @@ return true; } - markForcedConstant(SI->getCondition(), SI->case_begin()->getCaseValue()); - return true; + // Otherwise, it is a branch on a symbolic value which is currently + // considered to be undef. Make sure some edge is executable, so a + // branch on "undef" always flows somewhere. + // FIXME: Distinguish between dead code and an LLVM "undef" value. + BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor(); + if (markEdgeExecutable(&BB, DefaultSuccessor)) + return true; + + continue; } } @@ -1992,6 +1956,31 @@ if (!I) continue; bool Folded = ConstantFoldTerminator(I->getParent()); + if (!Folded) { + // If the branch can't be folded, we must have forced an edge + // for an indeterminate value. Force the terminator to fold + // to that edge. + Constant *C; + BasicBlock *Dest; + if (SwitchInst *SI = dyn_cast(I)) { + Dest = SI->case_begin()->getCaseSuccessor(); + C = SI->case_begin()->getCaseValue(); + } else if (BranchInst *BI = dyn_cast(I)) { + Dest = BI->getSuccessor(1); + C = ConstantInt::getFalse(BI->getContext()); + } else if (IndirectBrInst *IBR = dyn_cast(I)) { + Dest = IBR->getSuccessor(0); + C = BlockAddress::get(IBR->getSuccessor(0)); + } else { + llvm_unreachable("Unexpected terminator instruction"); + } + assert(Solver.isEdgeFeasible(I->getParent(), Dest) && + "Didn't find feasible edge?"); + (void)Dest; + + I->setOperand(0, C); + Folded = ConstantFoldTerminator(I->getParent()); + } assert(Folded && "Expect TermInst on constantint or blockaddress to be folded"); (void) Folded; Index: test/Transforms/SCCP/ipsccp-paramstate-forcedconst.ll =================================================================== --- /dev/null +++ test/Transforms/SCCP/ipsccp-paramstate-forcedconst.ll @@ -0,0 +1,24 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -S -ipsccp | FileCheck %s + +define void @main() { +; CHECK-LABEL: @main( +; CHECK: %call = call i1 @patatino(i1 undef) +; CHECK-NEXT: ret void +; + %call = call i1 @patatino(i1 undef) + ret void +} + +define internal i1 @patatino(i1 %a) { +; CHECK-LABEL: define internal i1 @patatino( +; CHECK-NEXT: br label [[ONFALSE:%.*]] +; CHECK-EMPTY: +; CHECK-NEXT: onfalse: +; CHECK-NEXT: ret i1 undef + br i1 %a, label %ontrue, label %onfalse +ontrue: + ret i1 false +onfalse: + ret i1 false +} Index: test/Transforms/SCCP/ipsccp-phi-one-pred-dead.ll =================================================================== --- test/Transforms/SCCP/ipsccp-phi-one-pred-dead.ll +++ test/Transforms/SCCP/ipsccp-phi-one-pred-dead.ll @@ -7,11 +7,13 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: br label %Flow5.pre ; CHECK: Flow6: -; CHECK-NEXT: br label %end2 +; CHECK-NEXT: br i1 undef, label %end1, label %end2 ; CHECK: Flow5.pre: ; CHECK-NEXT: br label %Flow5 ; CHECK: Flow5: ; CHECK-NEXT: br label %Flow6 +; CHECK: end1: +; CHECK-NEXT: unreachable ; CHECK: end2: ; CHECK-NEXT: unreachable ; Index: test/Transforms/SCCP/return-zapped.ll =================================================================== --- /dev/null +++ test/Transforms/SCCP/return-zapped.ll @@ -0,0 +1,64 @@ +; RUN: opt < %s -S -ipsccp | FileCheck %s + +; After the first round of Solver.Solve(), the return value of @testf still +; undefined as we hit a branch on undef. Therefore the conditional branch on +; @testf's return value in @bar is unknown. In ResolvedUndefsIn, we force the +; false branch to be feasible. We later discover that @testf actually +; returns true and merge that value with the value at the call site, which +; becomes overdefined. We cannot change the return value of @testf to undef, +; because we failed to replace the result of the call with true. +define void @test1() { +; CHECK-LABEL: @test1( +; CHECK-LABEL: if.then: +; CHECK: [[CALL:%.+]] = call i1 @testf() +; CHECK-NEXT: br i1 true, label %if.end, label %if.then +; +entry: + br label %if.then +if.then: ; preds = %entry, %if.then + %foo = phi i32 [ 0, %entry], [ %next, %if.then] + %next = add i32 %foo, 1 + %call = call i1 @testf() + br i1 %call, label %if.end, label %if.then + +if.end: ; preds = %if.then, %entry + ret void +} + +define internal i1 @testf() { +; CHECK-LABEL: define internal i1 @testf( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[IF_END3:%.*]] +; CHECK: if.end3: +; CHECK-NEXT: ret i1 undef +; +entry: + br i1 undef, label %if.then1, label %if.end3 + +if.then1: ; preds = %if.end + br label %if.end3 + +if.end3: ; preds = %if.then1, %entry + ret i1 true +} + + +; Call sites in unreachable blocks should not be a problem. +; CHECK-LABEL: define i1 @test2() { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %if.end +; CHECK-LABEL: if.end: ; preds = %entry +; CHECK-NEXT: %call2 = call i1 @testf() +; CHECK-NEXT: ret i1 true +define i1 @test2() { +entry: + br label %if.end + +if.then: ; preds = %entry, %if.then + %call = call i1 @testf() + br i1 %call, label %if.end, label %if.then + +if.end: ; preds = %if.then, %entry + %call2 = call i1 @testf() + ret i1 %call2 +}