Index: lib/Transforms/Scalar/CorrelatedValuePropagation.cpp =================================================================== --- lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -123,6 +123,62 @@ return true; } +/// Try to simplify a phi with constant incoming values that match the edge +/// values of a non-constant value on all other edges: +/// bb0: +/// %isnull = icmp eq i8* %x, null +/// br i1 %isnull, label %bb2, label %bb1 +/// bb1: +/// br label %bb2 +/// bb2: +/// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ] +/// --> +/// %r = %x +static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI, + const SimplifyQuery &SQ) { + // Collect incoming constants and initialize possible common value. + SmallVector, 4> IncomingConstants; + Value *CommonValue = nullptr; + for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { + Value *Incoming = P->getIncomingValue(i); + if (auto *IncomingConstant = dyn_cast(Incoming)) { + IncomingConstants.push_back(std::make_pair(IncomingConstant, i)); + } else if (!CommonValue) { + // The potential common value is initialized to the first non-constant. + CommonValue = Incoming; + } else if (Incoming != CommonValue) { + // There can be only one non-constant common value. + return false; + } + } + + if (!CommonValue || IncomingConstants.empty()) + return false; + + // We have a phi with exactly 1 variable incoming value and 1 or more constant + // incoming values. See if all constant incoming values can be mapped back to + // the same incoming variable value. + BasicBlock *ToBB = P->getParent(); + for (auto &IncomingConstant : IncomingConstants) { + // Make sure that the common value is valid in the incoming block. + BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second); + if (auto *CommonInst = dyn_cast(CommonValue)) + if (!SQ.DT->dominates(CommonInst, IncomingBB)) + return false; + + // Check if the common value matches the phi constant on the edge. + Constant *C = IncomingConstant.first; + if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P)) + return false; + } + + // All constant incoming values map to the same variable along the incoming + // edges of the phi. The phi is unnecessary. + P->replaceAllUsesWith(CommonValue); + P->eraseFromParent(); + return true; +} + static bool processPHI(PHINode *P, LazyValueInfo *LVI, const SimplifyQuery &SQ) { bool Changed = false; @@ -184,6 +240,9 @@ Changed = true; } + if (!Changed) + Changed = simplifyCommonValuePhi(P, LVI, SQ); + if (Changed) ++NumPhis; Index: test/Transforms/CorrelatedValuePropagation/phi-common-val.ll =================================================================== --- test/Transforms/CorrelatedValuePropagation/phi-common-val.ll +++ test/Transforms/CorrelatedValuePropagation/phi-common-val.ll @@ -0,0 +1,94 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -correlated-propagation -S | FileCheck %s + +define i8* @simplify_phi_common_value_op0(i8* %ptr, i32* %b) { +; CHECK-LABEL: @simplify_phi_common_value_op0( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[ISNULL:%.*]] = icmp eq i8* [[PTR:%.*]], null +; CHECK-NEXT: br i1 [[ISNULL]], label [[RETURN:%.*]], label [[ELSE:%.*]] +; CHECK: else: +; CHECK-NEXT: [[LB:%.*]] = load i32, i32* [[B:%.*]] +; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[LB]], 1 +; CHECK-NEXT: store i32 [[ADD]], i32* [[B]] +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: ret i8* [[PTR]] +; +entry: + %isnull = icmp eq i8* %ptr, null + br i1 %isnull, label %return, label %else + +else: + %lb = load i32, i32* %b + %add = add nsw i32 %lb, 1 + store i32 %add, i32* %b + br label %return + +return: + %r = phi i8* [ %ptr, %else ], [ null, %entry ] + ret i8* %r +} + +define i8* @simplify_phi_common_value_op1(i8* %ptr, i32* %b) { +; CHECK-LABEL: @simplify_phi_common_value_op1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[ISNULL:%.*]] = icmp eq i8* [[PTR:%.*]], null +; CHECK-NEXT: br i1 [[ISNULL]], label [[RETURN:%.*]], label [[ELSE:%.*]] +; CHECK: else: +; CHECK-NEXT: [[LB:%.*]] = load i32, i32* [[B:%.*]] +; CHECK-NEXT: [[ADD:%.*]] = add i32 [[LB]], 1 +; CHECK-NEXT: store i32 [[ADD]], i32* [[B]] +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: ret i8* [[PTR]] +; +entry: + %isnull = icmp eq i8* %ptr, null + br i1 %isnull, label %return, label %else + +else: + %lb = load i32, i32* %b + %add = add i32 %lb, 1 + store i32 %add, i32* %b + br label %return + +return: + %r = phi i8* [ null, %entry], [ %ptr, %else ] + ret i8* %r +} + +define i8 @simplify_phi_multiple_constants(i8 %x, i32* %b) { +; CHECK-LABEL: @simplify_phi_multiple_constants( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[IS0:%.*]] = icmp eq i8 [[X:%.*]], 0 +; CHECK-NEXT: br i1 [[IS0]], label [[RETURN:%.*]], label [[ELSE1:%.*]] +; CHECK: else1: +; CHECK-NEXT: [[IS42:%.*]] = icmp eq i8 [[X]], 42 +; CHECK-NEXT: br i1 [[IS42]], label [[RETURN]], label [[ELSE2:%.*]] +; CHECK: else2: +; CHECK-NEXT: [[LB:%.*]] = load i32, i32* [[B:%.*]] +; CHECK-NEXT: [[ADD:%.*]] = add i32 [[LB]], 1 +; CHECK-NEXT: store i32 [[ADD]], i32* [[B]] +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: ret i8 [[X]] +; +entry: + %is0 = icmp eq i8 %x, 0 + br i1 %is0, label %return, label %else1 + +else1: + %is42 = icmp eq i8 %x, 42 + br i1 %is42, label %return, label %else2 + +else2: + %lb = load i32, i32* %b + %add = add i32 %lb, 1 + store i32 %add, i32* %b + br label %return + +return: + %r = phi i8 [ 0, %entry], [ %x, %else2 ], [ 42, %else1 ] + ret i8 %r +} +