Index: lib/Transforms/Scalar/SROA.cpp =================================================================== --- lib/Transforms/Scalar/SROA.cpp +++ lib/Transforms/Scalar/SROA.cpp @@ -28,6 +28,7 @@ #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/PtrUseVisitor.h" #include "llvm/Analysis/ValueTracking.h" @@ -213,7 +214,7 @@ class AllocaSlices { public: /// \brief Construct the slices of a particular alloca. - AllocaSlices(const DataLayout &DL, AllocaInst &AI); + AllocaSlices(const DataLayout &DL, const DominatorTree *DT, AllocaInst &AI); /// \brief Test whether a pointer to the allocation escapes our analysis. /// @@ -271,6 +272,10 @@ class SliceBuilder; friend class AllocaSlices::SliceBuilder; + /// \brief Handle to the dominator tree for SliceBuilder to simplify PHI + /// nodes and select instructions. + const DominatorTree *DT; + #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) /// \brief Handle to alloca instruction to simplify method interfaces. AllocaInst &AI; @@ -312,18 +317,6 @@ }; } -static Value *foldSelectInst(SelectInst &SI) { - // If the condition being selected on is a constant or the same value is - // being selected between, fold the select. Yes this does (rarely) happen - // early on. - if (ConstantInt *CI = dyn_cast(SI.getCondition())) - return SI.getOperand(1+CI->isZero()); - if (SI.getOperand(1) == SI.getOperand(2)) - return SI.getOperand(1); - - return nullptr; -} - /// \brief Builder for the alloca slices. /// /// This class builds a set of alloca slices by recursively visiting the uses @@ -646,57 +639,57 @@ return nullptr; } - void visitPHINode(PHINode &PN) { - if (PN.use_empty()) - return markAsDead(PN); - if (!IsOffsetKnown) - return PI.setAborted(&PN); - - // See if we already have computed info on this node. - uint64_t &PHISize = PHIOrSelectSizes[&PN]; - if (!PHISize) { - // This is a new PHI node, check for an unsafe use of the PHI node. - if (Instruction *UnsafeI = hasUnsafePHIOrSelectUse(&PN, PHISize)) - return PI.setAborted(UnsafeI); - } - - // For PHI and select operands outside the alloca, we can't nuke the entire - // phi or select -- the other side might still be relevant, so we special - // case them here and use a separate structure to track the operands - // themselves which should be replaced with undef. - // FIXME: This should instead be escaped in the event we're instrumenting - // for address sanitization. - if (Offset.uge(AllocSize)) { - S.DeadOperands.push_back(U); - return; - } - - insertUse(PN, Offset, PHISize); - } + void visitPHINodeOrSelectInst(Instruction &I) { + assert(isa(I) || isa(I)); + if (I.use_empty()) + return markAsDead(I); - void visitSelectInst(SelectInst &SI) { - if (SI.use_empty()) - return markAsDead(SI); - if (Value *Result = foldSelectInst(SI)) { - if (Result == *U) + // If we can simplify the PHI/select (e.g., all incoming values of PHI are + // the same), we place it with the simplified instruction. + if (Value *Result = + SimplifyInstruction(&I, /*DL=*/nullptr, /*TLI=*/nullptr, S.DT)) { + if (Result == *U) { // If the result of the constant fold will be the pointer, recurse - // through the select as if we had RAUW'ed it. - enqueueUsers(SI); - else - // Otherwise the operand to the select is dead, and we can replace it - // with undef. + // through the PHI/select as if we had RAUW'ed it. + enqueueUsers(I); + } else { + // Otherwise the operand to the PHI/select is dead, and we can replace + // it with undef. S.DeadOperands.push_back(U); + // When the condition of the select is undef, we cannot simply replace U + // with undef. For instance, suppose loading from %U or %other does not + // trap. Then "load (select undef, %U, %other)" does not trap either. + // However, if we simply replace %U with undef, "load (select undef, + // undef, %other)" may trap because the select may return the first + // operand "undef". Therefore, while we clobber U, we should have the + // select point to the other operand. + if (SelectInst *SI = dyn_cast(&I)) { + if (isa(SI->getCondition())) { + Type *BooleanType = SI->getCondition()->getType(); + if (I.getOperandUse(1) == *U) { + // select undef, *U, other -> select 0, undef, other == other + I.setOperand(0, ConstantInt::getFalse(BooleanType)); + } else { + assert(I.getOperandUse(2) == *U && + "at least one of the operand uses should be *U"); + // select undef, other, *U -> select 1, other, undef == other + I.setOperand(0, ConstantInt::getTrue(BooleanType)); + } + } + } + } return; } + if (!IsOffsetKnown) - return PI.setAborted(&SI); + return PI.setAborted(&I); // See if we already have computed info on this node. - uint64_t &SelectSize = PHIOrSelectSizes[&SI]; - if (!SelectSize) { - // This is a new Select, check for an unsafe use of it. - if (Instruction *UnsafeI = hasUnsafePHIOrSelectUse(&SI, SelectSize)) + uint64_t &Size = PHIOrSelectSizes[&I]; + if (!Size) { + // This is a new PHI/Select, check for an unsafe use of it. + if (Instruction *UnsafeI = hasUnsafePHIOrSelectUse(&I, Size)) return PI.setAborted(UnsafeI); } @@ -711,7 +704,15 @@ return; } - insertUse(SI, Offset, SelectSize); + insertUse(I, Offset, Size); + } + + void visitPHINode(PHINode &PN) { + visitPHINodeOrSelectInst(PN); + } + + void visitSelectInst(SelectInst &SI) { + visitPHINodeOrSelectInst(SI); } /// \brief Disable SROA entirely if there are unhandled users of the alloca. @@ -720,8 +721,9 @@ } }; -AllocaSlices::AllocaSlices(const DataLayout &DL, AllocaInst &AI) - : +AllocaSlices::AllocaSlices(const DataLayout &DL, const DominatorTree *DT, + AllocaInst &AI) + : DT(DT), #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) AI(AI), #endif @@ -3437,7 +3439,7 @@ Changed |= AggRewriter.rewrite(AI); // Build the slices using a recursive instruction-visiting builder. - AllocaSlices S(*DL, AI); + AllocaSlices S(*DL, DT, AI); DEBUG(S.print(dbgs())); if (S.isEscaped()) return Changed; Index: test/Transforms/SROA/basictest.ll =================================================================== --- test/Transforms/SROA/basictest.ll +++ test/Transforms/SROA/basictest.ll @@ -1385,7 +1385,7 @@ ; bail on select instructions. ; ; CHECK-LABEL: @PR16651.2( -; CHECK: alloca <2 x float> +; CHECK: select i1 true, float* null, float* undef ; CHECK: ret void entry: Index: test/Transforms/SROA/phi-and-select.ll =================================================================== --- test/Transforms/SROA/phi-and-select.ll +++ test/Transforms/SROA/phi-and-select.ll @@ -501,3 +501,81 @@ ; CHECK-NOT: load ; CHECK: ret float %[[phi]] } + +; Verifies we fixed PR20425. We should be able to promote all alloca's to +; registers in this test. +; +; %0 = slice +; %1 = slice +; %2 = phi(%0, %1) // == slice +define float @simplify_phi_nodes_that_equal_slice(i1 %cond, float* %temp) { +; CHECK-LABEL: @simplify_phi_nodes_that_equal_slice( +entry: + %arr = alloca [4 x float], align 4 +; CHECK-NOT: alloca + br i1 %cond, label %then, label %else + +then: + %0 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3 + store float 1.000000e+00, float* %0, align 4 + br label %merge + +else: + %1 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3 + store float 2.000000e+00, float* %1, align 4 + br label %merge + +merge: + %2 = phi float* [ %0, %then ], [ %1, %else ] + store float 0.000000e+00, float* %temp, align 4 + %3 = load float* %2, align 4 + ret float %3 +} + +; A slightly complicated example for PR20425. +; +; %0 = slice +; %1 = phi(%0) // == slice +; %2 = slice +; %3 = phi(%1, %2) // == slice +define float @simplify_phi_nodes_that_equal_slice_2(i1 %cond, float* %temp) { +; CHECK-LABEL: @simplify_phi_nodes_that_equal_slice_2( +entry: + %arr = alloca [4 x float], align 4 +; CHECK-NOT: alloca + br i1 %cond, label %then, label %else + +then: + %0 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3 + store float 1.000000e+00, float* %0, align 4 + br label %then2 + +then2: + %1 = phi float* [ %0, %then ] + store float 2.000000e+00, float* %1, align 4 + br label %merge + +else: + %2 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3 + store float 3.000000e+00, float* %2, align 4 + br label %merge + +merge: + %3 = phi float* [ %1, %then2 ], [ %2, %else ] + store float 0.000000e+00, float* %temp, align 4 + %4 = load float* %3, align 4 + ret float %4 +} + +; When clobbering a use by a select, make sure the select does not +; return the undef. +define float @select_undef(float* %wild) { +; CHECK-LABEL: @select_undef( +entry: + %p = alloca float, align 4 + store float 1.000000e+00, float* %p, align 4 + %a = select i1 undef, float* %p, float* %wild +; CHECK: select i1 false, float* undef, float* %wild + %b = load float* %a + ret float %b +}