diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp --- a/llvm/lib/Transforms/Scalar/SCCP.cpp +++ b/llvm/lib/Transforms/Scalar/SCCP.cpp @@ -28,6 +28,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueLattice.h" #include "llvm/Analysis/ValueLatticeUtils.h" @@ -85,19 +86,13 @@ /// constant - This LLVM Value has a specific constant value. constant, - /// forcedconstant - This LLVM Value was thought to be undef until - /// ResolvedUndefsIn. This is treated just like 'constant', but if merged - /// with another (different) constant, it goes to overdefined, instead of - /// asserting. - forcedconstant, - /// overdefined - This instruction is not known to be constant, and we know /// it has a value. overdefined }; /// Val: This stores the current lattice value along with the Constant* for - /// the constant if this is a 'constant' or 'forcedconstant' value. + /// the constant if this is a 'constant' value. PointerIntPair Val; LatticeValueTy getLatticeValue() const { @@ -109,9 +104,7 @@ bool isUnknown() const { return getLatticeValue() == unknown; } - bool isConstant() const { - return getLatticeValue() == constant || getLatticeValue() == forcedconstant; - } + bool isConstant() const { return getLatticeValue() == constant; } bool isOverdefined() const { return getLatticeValue() == overdefined; } @@ -131,26 +124,15 @@ /// markConstant - Return true if this is a change in status. bool markConstant(Constant *V) { - if (getLatticeValue() == constant) { // Constant but not forcedconstant. + if (getLatticeValue() == constant) { // Constant assert(getConstant() == V && "Marking constant with different value"); return false; } - if (isUnknown()) { - Val.setInt(constant); - assert(V && "Marking constant with NULL"); - Val.setPointer(V); - } else { - assert(getLatticeValue() == forcedconstant && - "Cannot move from overdefined to constant!"); - // Stay at forcedconstant if the constant is the same. - if (V == getConstant()) return false; - - // Otherwise, we go to overdefined. Assumptions made based on the - // forced value are possibly wrong. Assuming this is another constant - // could expose a contradiction. - Val.setInt(overdefined); - } + assert(isUnknown()); + Val.setInt(constant); + assert(V && "Marking constant with NULL"); + Val.setPointer(V); return true; } @@ -170,12 +152,6 @@ return nullptr; } - void markForcedConstant(Constant *V) { - assert(isUnknown() && "Can't force a defined value!"); - Val.setInt(forcedconstant); - Val.setPointer(V); - } - ValueLatticeElement toValueLattice() const { if (isOverdefined()) return ValueLatticeElement::getOverdefined(); @@ -421,7 +397,7 @@ } private: - // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined + // pushToWorkList - Helper for markConstant/markOverdefined void pushToWorkList(LatticeVal &IV, Value *V) { if (IV.isOverdefined()) return OverdefinedInstWorkList.push_back(V); @@ -443,14 +419,6 @@ return markConstant(ValueState[V], V, C); } - void markForcedConstant(Value *V, Constant *C) { - assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); - LatticeVal &IV = ValueState[V]; - IV.markForcedConstant(C); - LLVM_DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n'); - pushToWorkList(IV, V); - } - // markOverdefined - Make a value be marked as "overdefined". If the // value is not already overdefined, add it to the overdefined instruction // work list so that the users of the instruction are updated later. @@ -1032,8 +1000,10 @@ } // If something is undef, wait for it to resolve. - if (!V1State.isOverdefined() && !V2State.isOverdefined()) + if (!V1State.isOverdefined() && !V2State.isOverdefined()) { + return; + } // Otherwise, one of our operands is overdefined. Try to produce something // better than overdefined with some tricks. @@ -1517,173 +1487,75 @@ markOverdefined(&I); return true; } - LatticeVal Op0LV = getValueState(I.getOperand(0)); - LatticeVal Op1LV; if (I.getNumOperands() == 2) { if (I.getOperand(1)->getType()->isStructTy()) { markOverdefined(&I); return true; } - - Op1LV = getValueState(I.getOperand(1)); } - // If this is an instructions whose result is defined even if the input is - // not fully defined, propagate the information. - Type *ITy = I.getType(); - switch (I.getOpcode()) { - case Instruction::Add: - case Instruction::Sub: - case Instruction::Trunc: - case Instruction::FPTrunc: - case Instruction::BitCast: - break; // Any undef -> undef - case Instruction::FSub: - case Instruction::FAdd: - case Instruction::FMul: - case Instruction::FDiv: - case Instruction::FRem: - // Floating-point binary operation: be conservative. - if (Op0LV.isUnknown() && Op1LV.isUnknown()) - markForcedConstant(&I, Constant::getNullValue(ITy)); - else - markOverdefined(&I); - return true; - case Instruction::FNeg: - break; // fneg undef -> undef - case Instruction::ZExt: - case Instruction::SExt: - case Instruction::FPToUI: - case Instruction::FPToSI: - case Instruction::FPExt: - case Instruction::PtrToInt: - case Instruction::IntToPtr: - case Instruction::SIToFP: - case Instruction::UIToFP: - // undef -> 0; some outputs are impossible - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - case Instruction::Mul: - case Instruction::And: - // Both operands undef -> undef - if (Op0LV.isUnknown() && Op1LV.isUnknown()) - break; - // undef * X -> 0. X could be zero. - // undef & X -> 0. X could be zero. - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - case Instruction::Or: - // Both operands undef -> undef - if (Op0LV.isUnknown() && Op1LV.isUnknown()) - break; - // undef | X -> -1. X could be -1. - markForcedConstant(&I, Constant::getAllOnesValue(ITy)); - return true; - case Instruction::Xor: - // undef ^ undef -> 0; strictly speaking, this is not strictly - // necessary, but we try to be nice to people who expect this - // behavior in simple cases - if (Op0LV.isUnknown() && Op1LV.isUnknown()) { - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; + // Returns the corresponding constant if the lattice value for \p Op is a + // constant or the original IR value otherwise. + auto getValue = [this](Value *Op) -> Value * { + auto LV = getValueState(Op); + if (LV.isConstant()) + return LV.getConstant(); + return Op; + }; + + // At least one of the operands if I is unknown. Use InstructionSimplify + // to try to fold explicit undefs. + if (isa(&I)) { + Value *Op1 = getValue(I.getOperand(0)); + if (Value *Res = + SimplifyCastInst(I.getOpcode(), Op1, I.getType(), {DL})) { + if (isa(Res)) { + continue; + } + if (isa(Res)) { + markConstant(&I, cast(Res)); + return true; + } } - // undef ^ X -> undef - break; - case Instruction::SDiv: - case Instruction::UDiv: - case Instruction::SRem: - case Instruction::URem: - // X / undef -> undef. No change. - // X % undef -> undef. No change. - if (Op1LV.isUnknown()) break; - - // X / 0 -> undef. No change. - // X % 0 -> undef. No change. - if (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue()) - break; - - // undef / X -> 0. X could be maxint. - // undef % X -> 0. X could be 1. - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - case Instruction::AShr: - // X >>a undef -> undef. - if (Op1LV.isUnknown()) break; - - // Shifting by the bitwidth or more is undefined. - if (Op1LV.isConstant()) { - if (auto *ShiftAmt = Op1LV.getConstantInt()) - if (ShiftAmt->getLimitedValue() >= - ShiftAmt->getType()->getScalarSizeInBits()) - break; + } else if (isa(&I)) { + Value *Op1 = getValue(I.getOperand(0)); + Value *Op2 = getValue(I.getOperand(1)); + if (Value *Res = SimplifyBinOp(I.getOpcode(), Op1, Op2, {DL})) { + if (isa(Res)) { + continue; + } + if (isa(Res)) { + markConstant(&I, cast(Res)); + return true; + } } - - // undef >>a X -> 0 - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - case Instruction::LShr: - case Instruction::Shl: - // X << undef -> undef. - // X >> undef -> undef. - if (Op1LV.isUnknown()) break; - - // Shifting by the bitwidth or more is undefined. - if (Op1LV.isConstant()) { - if (auto *ShiftAmt = Op1LV.getConstantInt()) - if (ShiftAmt->getLimitedValue() >= - ShiftAmt->getType()->getScalarSizeInBits()) - break; + } else if (isa(&I)) { + Value *Op1 = getValue(I.getOperand(0)); + Value *Op2 = getValue(I.getOperand(1)); + if (Value *Res = SimplifyCmpInst(cast(I).getPredicate(), Op1, + Op2, {DL})) { + if (isa(Res)) { + continue; + } + if (isa(Res)) { + markConstant(&I, cast(Res)); + return true; + } } - - // undef << X -> 0 - // undef >> X -> 0 - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - case Instruction::Select: - Op1LV = getValueState(I.getOperand(1)); - // undef ? X : Y -> X or Y. There could be commonality between X/Y. - if (Op0LV.isUnknown()) { - if (!Op1LV.isConstant()) // Pick the constant one if there is any. - Op1LV = getValueState(I.getOperand(2)); - } else if (Op1LV.isUnknown()) { - // c ? undef : undef -> undef. No change. - Op1LV = getValueState(I.getOperand(2)); - if (Op1LV.isUnknown()) - break; - // Otherwise, c ? undef : x -> x. - } else { - // Leave Op1LV as Operand(1)'s LatticeValue. + } else if (isa(&I)) { + Value *Op1 = getValue(I.getOperand(0)); + if (Value *Res = SimplifyUnOp(I.getOpcode(), Op1, {DL})) { + if (isa(Res)) { + continue; + } + if (isa(Res)) { + markConstant(&I, cast(Res)); + return true; + } } - - if (Op1LV.isConstant()) - markForcedConstant(&I, Op1LV.getConstant()); - else - markOverdefined(&I); - return true; - case Instruction::Load: - // A load here means one of two things: a load of undef from a global, - // a load from an unknown pointer. Either way, having it return undef - // is okay. - break; - case Instruction::ICmp: - // X == undef -> undef. Other comparisons get more complicated. - Op0LV = getValueState(I.getOperand(0)); - Op1LV = getValueState(I.getOperand(1)); - - if ((Op0LV.isUnknown() || Op1LV.isUnknown()) && - cast(&I)->isEquality()) - break; - markOverdefined(&I); - return true; - case Instruction::Call: - case Instruction::Invoke: - case Instruction::CallBr: - llvm_unreachable("Call-like instructions should have be handled early"); - default: - // If we don't know what should happen here, conservatively mark it - // overdefined. - markOverdefined(&I); - return true; } + + markOverdefined(&I); + return true; } // Check to see if we have a branch or switch on an undefined value. If so diff --git a/llvm/test/Transforms/SCCP/apint-bigint2.ll b/llvm/test/Transforms/SCCP/apint-bigint2.ll --- a/llvm/test/Transforms/SCCP/apint-bigint2.ll +++ b/llvm/test/Transforms/SCCP/apint-bigint2.ll @@ -18,7 +18,13 @@ } ; CHECK-LABEL: @large_aggregate -; CHECK-NEXT: ret i101 undef +; CHECK-NEXT: %B = load i101, i101* undef +; CHECK-NEXT: %D = and i101 %B, 1 +; CHECK-NEXT: %DD = or i101 %D, 1 +; CHECK-NEXT: %G = getelementptr i101, i101* getelementptr inbounds ([6 x i101], [6 x i101]* @Y, i32 0, i32 5), i101 %DD +; CHECK-NEXT: %L3 = load i101, i101* %G +; CHECK-NEXT: ret i101 %L3 +; define i101 @large_aggregate() { %B = load i101, i101* undef %D = and i101 %B, 1 @@ -29,6 +35,19 @@ ret i101 %L3 } +; CHECK-LABEL: define i101 @large_aggregate_2() { +; CHECK-NEXT: %L3 = load i101, i101* getelementptr inbounds ([6 x i101], [6 x i101]* @Y, i101 1, i101 0) +; CHECK-NEXT: ret i101 %L3 +; +define i101 @large_aggregate_2() { + %D = and i101 undef, 1 + %DD = or i101 %D, 1 + %F = getelementptr [6 x i101], [6 x i101]* @Y, i32 0, i32 5 + %G = getelementptr i101, i101* %F, i101 %DD + %L3 = load i101, i101* %G + ret i101 %L3 +} + ; CHECK-LABEL: @index_too_large ; CHECK-NEXT: store i101* getelementptr (i101, i101* getelementptr ([6 x i101], [6 x i101]* @Y, i32 0, i32 -1), i101 9224497936761618431), i101** undef ; CHECK-NEXT: ret void diff --git a/llvm/test/Transforms/SCCP/apint-ipsccp3.ll b/llvm/test/Transforms/SCCP/apint-ipsccp3.ll --- a/llvm/test/Transforms/SCCP/apint-ipsccp3.ll +++ b/llvm/test/Transforms/SCCP/apint-ipsccp3.ll @@ -1,23 +1,39 @@ -; RUN: opt < %s -ipsccp -S | not grep global +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -ipsccp -S | FileCheck %s @G = internal global i66 undef - define void @foo() { - %X = load i66, i66* @G - store i66 %X, i66* @G - ret void +; CHECK-LABEL: @foo( +; CHECK-NEXT: [[X:%.*]] = load i66, i66* @G +; CHECK-NEXT: store i66 [[X]], i66* @G +; CHECK-NEXT: ret void +; + %X = load i66, i66* @G + store i66 %X, i66* @G + ret void } define i66 @bar() { - %V = load i66, i66* @G - %C = icmp eq i66 %V, 17 - br i1 %C, label %T, label %F +; CHECK-LABEL: @bar( +; CHECK-NEXT: [[V:%.*]] = load i66, i66* @G +; CHECK-NEXT: [[C:%.*]] = icmp eq i66 [[V]], 17 +; CHECK-NEXT: br i1 [[C]], label [[T:%.*]], label [[F:%.*]] +; CHECK: T: +; CHECK-NEXT: store i66 17, i66* @G +; CHECK-NEXT: ret i66 17 +; CHECK: F: +; CHECK-NEXT: store i66 123, i66* @G +; CHECK-NEXT: ret i66 0 +; + %V = load i66, i66* @G + %C = icmp eq i66 %V, 17 + br i1 %C, label %T, label %F T: - store i66 17, i66* @G - ret i66 %V + store i66 17, i66* @G + ret i66 %V F: - store i66 123, i66* @G - ret i66 0 + store i66 123, i66* @G + ret i66 0 } diff --git a/llvm/test/Transforms/SCCP/ip-constant-ranges.ll b/llvm/test/Transforms/SCCP/ip-constant-ranges.ll --- a/llvm/test/Transforms/SCCP/ip-constant-ranges.ll +++ b/llvm/test/Transforms/SCCP/ip-constant-ranges.ll @@ -141,9 +141,8 @@ ; Constant range for %x is [47, 302) ; CHECK-LABEL: @f5 ; CHECK-NEXT: entry: -; CHECK-NEXT: %cmp = icmp sgt i32 %x, undef -; CHECK-NEXT: %res1 = select i1 %cmp, i32 1, i32 2 -; CHECK-NEXT: %res = add i32 %res1, 3 +; CHECK-NEXT: %res2 = select i1 undef, i32 3, i32 4 +; CHECK-NEXT: %res = add i32 2, %res2 ; CHECK-NEXT: ret i32 %res define internal i32 @f5(i32 %x) { entry: diff --git a/llvm/test/Transforms/SCCP/ipsccp-basic.ll b/llvm/test/Transforms/SCCP/ipsccp-basic.ll --- a/llvm/test/Transforms/SCCP/ipsccp-basic.ll +++ b/llvm/test/Transforms/SCCP/ipsccp-basic.ll @@ -56,7 +56,9 @@ ret void } ; CHECK-LABEL: define void @test3a( -; CHECK-NEXT: ret void +; CHECK-NEXT: %X = load i32, i32* @G +; CHECK-NEXT: store i32 %X, i32* @G +; CHECK-NEXT: ret void define i32 @test3b() { @@ -71,9 +73,17 @@ ret i32 0 } ; CHECK-LABEL: define i32 @test3b( -; CHECK-NOT: store -; CHECK: ret i32 0 +; CHECK-NEXT: %V = load i32, i32* @G +; CHECK-NEXT: %C = icmp eq i32 %V, 17 +; CHECK-NEXT: br i1 %C, label %T, label %F + +; CHECK-LABEL: T: +; CHECK-NEXT: store i32 17, i32* @G +; CHECK-NEXT: ret i32 17 +; CHECK-LABEL: F: +; CHECK-NEXT: store i32 123, i32* @G +; CHECK-NEXT: ret i32 0 ;;======================== test4 @@ -226,8 +236,11 @@ entry: %call = call i32 @test10b(i32 undef) ret i32 %call + ; CHECK-LABEL: define i32 @test10a( -; CHECK: ret i32 0 +; CHECK-NEXT: entry: +; CHECK-NEXT: %call = call i32 @test10b(i32 undef) +; CHECK-NEXT: ret i32 %call } define internal i32 @test10b(i32 %x) nounwind { @@ -235,7 +248,9 @@ %r = and i32 %x, 1 ret i32 %r ; CHECK-LABEL: define internal i32 @test10b( -; CHECK: ret i32 undef +; CHECK-NEXT: entry: +; CHECK-NEXT: %r = and i32 undef, 1 +; CHECK-NEXT: ret i32 %r } ;;======================== test11 diff --git a/llvm/test/Transforms/SCCP/undef-resolve.ll b/llvm/test/Transforms/SCCP/undef-resolve.ll --- a/llvm/test/Transforms/SCCP/undef-resolve.ll +++ b/llvm/test/Transforms/SCCP/undef-resolve.ll @@ -159,7 +159,7 @@ %t = icmp ugt i32 undef, -1 ret i1 %t ; CHECK-LABEL: @test9( -; CHECK: icmp ugt +; CHECK-NEXT: ret i1 false } ; Make sure we handle extractvalue