Chris,
Thanks for your detailed review. Obviously there's still much I need to
learn about InstCombine. I'll try to slow down a bit and review things
myself on the next patches.
Below are some comments on your comments. I've made all the changes
except for InstCombine. That will take a little more thought so I'll
follow up on InstCombine separately.
On Mon, 2006-10-23 at 22:52 -0700, Chris Lattner wrote:
>
> On Oct 22, 2006, at 7:50 PM, Reid Spencer wrote:
>
> > Attached is a patch to implement splitting the signless DIV
> > instruction
> > into UDiv (unsigned), SDiv (signed), and FDiv (floating point)
> > instructions. This is part of the Signless Types work I'm doing.
>
> Overall, this patch looks like a great first step, but it has
> significant flaws. In particular, the patch seems unable to produce a
> [su]div instruction with operands of the opposite sign from that of
> the instruction.
Well, I didn't think it was a requirement. However, I can see why it is
because of the pending removal of signedness from types.
> Further, handling of this (very important) case is seriously buggy in
> many cases.
I will look into it.
> I strongly recommend adding a transformation to instcombine that will
> produce more divs with such operands. For example, changing something
> like:
>
>
> %X = cast uint %A to int
> %Y = sdiv int %X, 1234
> %Z = cast int %Y to uint
>
>
> into:
>
>
> %Z = sdiv uint %A, 1234
>
>
> Fortunately, instcombine already does this for other operations
> (mul/add/and/or/xor, etc) at line 5658 of Instcombine in CVS. Please
> add a case there for UDIV/SDIV. This will hopefully help flush out
> bugs in the patch that I didn't catch.
My goal is not to add any new functionality and make the smallest change
set possible to get existing functionality working with the the new
instructions. However, I see your point. This transform could help
locate bugs elsewhere. I'll add this transform.
> When you get the comments in this email address and things retested,
> please resend the patch for review.
Okay.
> Comments preceded with ***'s
>
>
> --- include/llvm/Instruction.def 8 Apr 2006 01:15:18 -0000 1.19
> +++ include/llvm/Instruction.def 23 Oct 2006 02:43:18 -0000
> @@ -88,52 +88,50 @@ HANDLE_TERM_INST ( 5, Unwind , Unwi
> ...
>
>
> *** Why not reserve some space for all the new instructions you plan
> to add? That way the CVS bc format won't be changing as much.
>
>
> -HANDLE_BINARY_INST( 7, Add , BinaryOperator)
> -HANDLE_BINARY_INST( 8, Sub , BinaryOperator)
> -HANDLE_BINARY_INST( 9, Mul , BinaryOperator)
> +HANDLE_BINARY_INST( 7, Add , BinaryOperator)
> +HANDLE_BINARY_INST( 8, Sub , BinaryOperator)
> +HANDLE_BINARY_INST( 9, Mul , BinaryOperator)
>
>
> *** Why remove the space?
>
>
> --- lib/Analysis/ScalarEvolution.cpp 20 Oct 2006 07:07:24 -0000 1.54
> +++ lib/Analysis/ScalarEvolution.cpp 23 Oct 2006 02:43:20 -0000
> @@ -1382,12 +1382,12 @@ SCEVHandle ScalarEvolutionsImpl::createS
> return SCEVAddExpr::get(getSCEV(I->getOperand(0)),
> getSCEV(I->getOperand(1)));
> case Instruction::Mul:
> return SCEVMulExpr::get(getSCEV(I->getOperand(0)),
> getSCEV(I->getOperand(1)));
> - case Instruction::Div:
> - if (V->getType()->isInteger() && V->getType()->isSigned())
> + case Instruction::SDiv:
> + if (V->getType()->isInteger())
> return SCEVSDivExpr::get(getSCEV(I->getOperand(0)),
> getSCEV(I->getOperand(1)));
> break;
>
>
> *** No need to check for isInteger anymore.
Done.
>
>
> ===================================================================
> RCS file: /var/cvs/llvm/llvm/lib/AsmParser/llvmAsmParser.y,v
> retrieving revision 1.269
> diff -t -d -u -p -5 -r1.269 llvmAsmParser.y
> --- lib/AsmParser/llvmAsmParser.y 22 Oct 2006 07:03:09 -0000 1.269
> +++ lib/AsmParser/llvmAsmParser.y 23 Oct 2006 02:43:24 -0000
> @@ -811,10 +811,41 @@ static PATypeHolder HandleUpRefs(const T
> +// This template function is used to obtain the correct opcode for
> an
> +// instruction when an obsolete opcode is encountered. The OpcodeInfo
> template
> +// keeps track of the opcode and the "obsolete" flag. These are
> generated by
> +// the lexer and obsolete will be true when the lexer encounters the
> token for
> +// an obsolete opcode. For example, "div" was replaced by [usf]div
> but we need
> +// to maintain backwards compatibility for asm files that still have
> the "div"
> +// instruction. This function handles converting div -> [usf]div
> appropriately.
> +template <class EnumKind>
> +static void sanitizeOpCode(OpcodeInfo<EnumKind> &OI, const
> PATypeHolder& Ty) {
> + if (OI.obsolete) {
> + switch (OI.opcode) {
> + default:
> + GenerateError("Invalid Obsolete OpCode");
> + break;
> + case Instruction::UDiv:
> + if (Ty->isFloatingPoint())
> + OI.opcode = Instruction::FDiv;
> + else if (Ty->isSigned())
> + OI.opcode = Instruction::SDiv;
> + break;
> + case Instruction::SDiv:
> + if (Ty->isFloatingPoint())
> + OI.opcode = Instruction::FDiv;
> + else if (Ty->isUnsigned())
> + OI.opcode = Instruction::UDiv;
> + break;
> ...
>
>
> *** I like your approach. I don't think sanitizeOpCode should be a
> template though. This specific one only works for binops, because
> that is what enum values it has.
> I'd just have one function for each class of upgraded op, no
> templates.
I was designing for the future. Soon enough there will be a category of
instructions named ConvertOps which will contain the 10 conversion
instructions that will replace cast. I was thinking they could share the
same code, but I see what you mean. Each enum corresponds to a
particular group of case values so they might as well be separate
non-template functions.
Done.
> Also, the lexer can't return an "obsolete sdiv", it appears to only
> return udiv, so the sdiv case above seems dead. Am I missing
> something?
Nope. It was just a little defensive programming. When depending on
things in another file, I tend to be a bit more cautious. There's
nothing to stop someone from using the RET_TOK_OBSOLETE with SDiv in
Lexer.l. However its guarding against an obscure case that probably
won't happen in practice so I'll remove it.
> Finally, the code would be simpler if you started it as "if (!
> OI.obsolete) return;"
Yup. Done.
>
>
> Index: lib/Bytecode/Reader/Reader.cpp
> ===================================================================
> RCS file: /var/cvs/llvm/llvm/lib/Bytecode/Reader/Reader.cpp,v
> retrieving revision 1.199
> diff -t -d -u -p -5 -r1.199 Reader.cpp
> --- lib/Bytecode/Reader/Reader.cpp 20 Oct 2006 07:07:24 -0000 1.199
> +++ lib/Bytecode/Reader/Reader.cpp 23 Oct 2006 02:43:26 -0000
> @@ -560,10 +560,239 @@ void BytecodeReader::insertArguments(Fun
> ...
> + // Declare the resulting instruction we might build.
> + Instruction *Result = 0;
> +
> + // If this is a bytecode format that did not include the
> unreachable
> + // instruction, bump up the opcode number to adjust
> + if (hasNoUnreachableInst) {
> + if (Opcode >= Instruction::Unreachable &&
> + Opcode < 62) { // 62
> + ++Opcode;
> + }
> + }
> +
> + // First, short circuit this if no conversion is required. When
> signless
> + // instructions were implemented the entire opcode sequence was
> revised so
> + // we key on this first which means that the opcode value read is
> the one
> + // we should use.
> + if (!hasSignlessInstructions)
> + return Result;
>
>
> *** If hasSignlessInstructions is true, hasNoUnreachableInst is false,
> right?
Theoretically, yes :)
> If so, move the fast path above the hasNoUnreachableInst check?
Yup. Done.
> It would be more clear to return 0 here explicitly and mention in the
> method comment that this returns null if no upgrading is needed.
Except that's not quite the case. The function can return 0 but alter
the OpCode argument. I'll fix the comment to explain in more detail.
>
>
> +// Upgrade obsolte constant expression opcodes (ver. 5 and prior) to
> the new
>
>
> *** Typo obsolete.
Done.
>
>
>
>
> + // need to note that we have signed integer types in prior
> versions.
> + hasSignedIntegers = true;
> +
> + // FALL THROUGH
> +
> + case 6: // SignlessTypes Implementation (1.10
> release)
>
>
> *** 1.9?
Yes. I wrote that code before we had our discussion about whether this
change set was going into the 1.9 release or not. I was assuming it was
not, but would make it into the next release, 1.10
>
>
> Index: lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
> ===================================================================
> RCS
> file: /var/cvs/llvm/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp,v
> retrieving revision 1.294
> diff -t -d -u -p -5 -r1.294 SelectionDAGISel.cpp
> --- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp 22 Oct 2006 23:00:53
> -0000 1.294
> +++ lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp 23 Oct 2006 02:43:28
> -0000
> +void
> +SelectionDAGLowering::visitIntBinary(User &I, unsigned IntOp,
> unsigned VecOp) {
> const Type *Ty = I.getType();
> SDOperand Op1 = getValue(I.getOperand(0));
> SDOperand Op2 = getValue(I.getOperand(1));
>
>
> if (Ty->isIntegral()) {
> setValue(&I, DAG.getNode(IntOp, Op1.getValueType(), Op1, Op2));
> - } else if (Ty->isFloatingPoint()) {
> + } else {
> + const PackedType *PTy = cast<PackedType>(Ty);
> + SDOperand Num = DAG.getConstant(PTy->getNumElements(), MVT::i32);
> + SDOperand Typ =
> DAG.getValueType(TLI.getValueType(PTy->getElementType()));
> + setValue(&I, DAG.getNode(VecOp, MVT::Vector, Op1, Op2, Num,
> Typ));
> + }
> +}
>
>
> *** In visitIntBinary/visitFPBinary please change the condition to "if
> (const PackedType *PTy = dyn_cast<PackedType>(Ty)) {", swapping the
> order of the if conditions. Checking "isIntegral" is a non-obvious
> way to check that it's not a vector type (your code is correct, just
> not obvious what it does).
Okay. Done.
>
>
> --- lib/ExecutionEngine/Interpreter/Execution.cpp 20 Oct 2006 07:07:24
> -0000 1.140
> +++ lib/ExecutionEngine/Interpreter/Execution.cpp 23 Oct 2006 02:43:29
> -0000
> @@ -87,11 +87,13 @@ GenericValue Interpreter::getConstantExp
> CE->getOperand(0)->getType());
> case Instruction::Mul:
> return executeMulInst(getOperandValue(CE->getOperand(0), SF),
> getOperandValue(CE->getOperand(1), SF),
> CE->getOperand(0)->getType());
> - case Instruction::Div:
> + case Instruction::SDiv:
> + case Instruction::UDiv:
> + case Instruction::FDiv:
> return executeDivInst(getOperandValue(CE->getOperand(0), SF),
> getOperandValue(CE->getOperand(1), SF),
> CE->getOperand(0)->getType());
> case Instruction::Rem:
> return executeRemInst(getOperandValue(CE->getOperand(0), SF),
> @@ -502,11 +504,13 @@ void Interpreter::visitBinaryOperator(Bi
>
>
> switch (I.getOpcode()) {
> case Instruction::Add: R = executeAddInst (Src1, Src2, Ty);
> break;
> case Instruction::Sub: R = executeSubInst (Src1, Src2, Ty);
> break;
> case Instruction::Mul: R = executeMulInst (Src1, Src2, Ty);
> break;
> - case Instruction::Div: R = executeDivInst (Src1, Src2, Ty);
> break;
> + case Instruction::SDiv:
> + case Instruction::UDiv:
> + case Instruction::FDiv: R = executeDivInst (Src1, Src2, Ty);
> break;
> case Instruction::Rem: R = executeRemInst (Src1, Src2, Ty);
> break;
> case Instruction::And: R = executeAndInst (Src1, Src2, Ty);
> break;
> case Instruction::Or: R = executeOrInst (Src1, Src2, Ty);
> break;
> case Instruction::Xor: R = executeXorInst (Src1, Src2, Ty);
> break;
> case Instruction::SetEQ: R = executeSetEQInst(Src1, Src2, Ty);
> break;
> *** This is flat out incorrect. It should have separate
> execute*DivInst functions that do the operation not based on the type.
> This would misinterpret 'udiv int -4, 2' for example. This must be
> fixed before you checkin.
>
Another casualty of thinking the operand types had to match the
instruction type. I've created the three functions. The SDiv case now
looks like:
static GenericValue executeSDivInst(GenericValue Src1, GenericValue
Src2,
const Type *Ty) {
GenericValue Dest;
** if (Ty->isUnsigned())
** Ty = Ty->getSignedVersion();
switch (Ty->getTypeID()) {
IMPLEMENT_BINARY_OPERATOR(/, SByte);
IMPLEMENT_BINARY_OPERATOR(/, Short);
IMPLEMENT_BINARY_OPERATOR(/, Int);
IMPLEMENT_BINARY_OPERATOR(/, Long);
default:
std::cout << "Unhandled type for SDiv instruction: " << *Ty << "\n";
abort();
}
return Dest;
}
I've added the ** lines. and removed the floating point and unsigned
cases from the switch. Basically, I'm forcing it to select the signed
member from the GenericValue union. Since I used getSignedVersion() the
only difference should be the sign (no size difference) and I shouldn't
need to do anything special for sign extension. If the SDiv is provided
unsigned values, they will be plucked out of the union as signed values.
I did a similar thing for UDiv. For FDiv, nothing special is needed for
sign management but there are only two cases in the switch: Float and
Double.
>
> --- lib/Target/CBackend/Writer.cpp 22 Oct 2006 09:58:21 -0000 1.274
> +++ lib/Target/CBackend/Writer.cpp 23 Oct 2006 02:43:30 -0000
> @@ -584,11 +584,13 @@ void CWriter::printConstant(Constant *CP
> @@ -603,11 +605,13 @@ void CWriter::printConstant(Constant *CP
> printConstant(CE->getOperand(0));
> switch (CE->getOpcode()) {
> case Instruction::Add: Out << " + "; break;
> case Instruction::Sub: Out << " - "; break;
> case Instruction::Mul: Out << " * "; break;
> - case Instruction::Div: Out << " / "; break;
> + case Instruction::UDiv:
> + case Instruction::SDiv:
> + case Instruction::FDiv: Out << " / "; break;
> case Instruction::Rem: Out << " % "; break;
> case Instruction::And: Out << " & "; break;
> case Instruction::Or: Out << " | "; break;
> case Instruction::Xor: Out << " ^ "; break;
> case Instruction::SetEQ: Out << " == "; break;
>
>
> *** The CBE has the same problem. You need to force the operands to
> the right sign in the C output so that the C compiler will generate
> the appropriately signed operation. This must be fixed before you
> checkin.
Yes. Done. I added a writeOperandWithCast(Value*, unsigned opcode)
method to the CWriter. It writes the operand with the correct cast based
on the opcode the value is used with. I call this instead of
writeOperand(Value*) to write the operands for these binary operators
(just before and after the switch statement you quoted above).
>
> --- lib/Transforms/IPO/SimplifyLibCalls.cpp 20 Oct 2006 07:07:24 -0000
> 1.70
> +++ lib/Transforms/IPO/SimplifyLibCalls.cpp 23 Oct 2006 02:43:30 -0000
> @@ -1273,11 +1273,11 @@ public:
> ci->replaceAllUsesWith(base);
> ci->eraseFromParent();
> return true;
> } else if (Op2V == -1.0) {
> // pow(x,-1.0) -> 1.0/x
> - BinaryOperator* div_inst= BinaryOperator::createDiv(
> + BinaryOperator* div_inst= BinaryOperator::createSDiv(
> ConstantFP::get(Ty,1.0), base, ci->getName()+".pow", ci);
> ci->replaceAllUsesWith(div_inst);
> ci->eraseFromParent();
> return true;
> }
>
>
> *** Shouldn't this be fdiv? Please fix before you checkin, and add a
> regression test.
Yes, I caught that one too after I sent the patches.
>
> ===================================================================
> RCS file: /var/cvs/llvm/llvm/lib/VMCore/ConstantFolding.cpp,v
> retrieving revision 1.94
> diff -t -d -u -p -5 -r1.94 ConstantFolding.cpp
> --- lib/VMCore/ConstantFolding.cpp 20 Oct 2006 07:07:24 -0000 1.94
> +++ lib/VMCore/ConstantFolding.cpp 23 Oct 2006 02:43:35 -0000
> @@ -491,20 +507,32 @@ struct VISIBILITY_HIDDEN DirectIntRules
> DEF_CAST(ULong , ConstantInt, uint64_t)
> DEF_CAST(Float , ConstantFP , float)
> DEF_CAST(Double, ConstantFP , double)
> #undef DEF_CAST
>
>
> - static Constant *Div(const ConstantInt *V1, const ConstantInt *V2)
> {
> - if (V2->isNullValue()) return 0;
> + static Constant *UDiv(const ConstantInt *V1, const ConstantInt *V2)
> {
> + if (V2->isNullValue())
> + return 0;
> if (V2->isAllOnesValue() && // MIN_INT / -1
> (BuiltinType)V1->getZExtValue() ==
> -(BuiltinType)V1->getZExtValue())
> return 0;
> BuiltinType R =
> (BuiltinType)V1->getZExtValue() /
> (BuiltinType)V2->getZExtValue();
> return ConstantInt::get(*Ty, R);
> }
>
>
> + static Constant *SDiv(const ConstantInt *V1, const ConstantInt *V2)
> {
> + if (V2->isNullValue())
> + return 0;
> + if (V2->isAllOnesValue() && // MIN_INT / -1
> + (BuiltinType)V1->getSExtValue() ==
> -(BuiltinType)V1->getSExtValue())
> + return 0;
> + BuiltinType R =
> + (BuiltinType)V1->getSExtValue() /
> (BuiltinType)V2->getSExtValue();
> + return ConstantInt::get(*Ty, R);
> + }
> +
>
>
> You properly sign/zero extend the values here, but then proceed to do
> the wrong division. For example, this will do signed division for
> 'udiv int -2, 2'. What does the -constfold pass produce for:
>
>
> int %test() { %X = udiv int -2, 2 ret int %X }
>
>
> I bet it is folded to -1, which is incorrect.
There's no -constfold pass on opt, but I ran it through gccas and yes,
it does produce -1. I fixed it by changing:
BuiltinType R =
> (BuiltinType)V1->getSExtValue() / (BuiltinType)V2->getSExtValue();
to:
BuiltinType R = (BuiltinType)(V1->getSExtValue() / V2->getSExtValue());
That produced the value of 2147483647 ((MAX_UINT-1)/2) for your test
case which I think is correct. Please confirm.
>
> ===================================================================
> RCS file: /var/cvs/llvm/llvm/lib/VMCore/Constants.cpp,v
> retrieving revision 1.165
> diff -t -d -u -p -5 -r1.165 Constants.cpp
> --- lib/VMCore/Constants.cpp 20 Oct 2006 07:07:24 -0000 1.165
> +++ lib/VMCore/Constants.cpp 23 Oct 2006 02:43:36 -0000
> ..
> @@ -444,12 +446,18 @@ Constant *ConstantExpr::getSub(Constant
> return get(Instruction::Sub, C1, C2);
> }
> Constant *ConstantExpr::getMul(Constant *C1, Constant *C2) {
> return get(Instruction::Mul, C1, C2);
> }
> -Constant *ConstantExpr::getDiv(Constant *C1, Constant *C2) {
> - return get(Instruction::Div, C1, C2);
> +Constant *ConstantExpr::getUDiv(Constant *C1, Constant *C2) {
> + return get(Instruction::UDiv, C1, C2);
> +}
> +Constant *ConstantExpr::getSDiv(Constant *C1, Constant *C2) {
> + return get(Instruction::SDiv, C1, C2);
> +}
> +Constant *ConstantExpr::getFDiv(Constant *C1, Constant *C2) {
> + return get(Instruction::FDiv, C1, C2);
> }
> Constant *ConstantExpr::getRem(Constant *C1, Constant *C2) {
> return get(Instruction::Rem, C1, C2);
> }
> Constant *ConstantExpr::getAnd(Constant *C1, Constant *C2) {
>
>
> *** This would be an excellent place to assert that the arguments are
> integer or fp (or vectors of) as appropriate.
All of these cases call ConstantExpr::get(Opcode, C1, C2). That function
provides copious asserts. I didn't think it was reasonable to double
them up, especially since the asserts in ConstantExpr::get are ifdef'd
for debug only. I took that to mean that they were performance sensitive
for a release+asserts build. Let me know if that's not the case (i.e.
if I should remove the #ifndef DEBUG code in ConstantExpr::get).
I looked at ConstantExpr::get and tightened up the asserts there. It was
allowing FP for UDiv and SDiv and integer for FDiv. Now it doesn't.
> ===================================================================
> RCS file: /var/cvs/llvm/llvm/lib/VMCore/Instructions.cpp,v
> retrieving revision 1.43
> diff -t -d -u -p -5 -r1.43 Instructions.cpp
> --- lib/VMCore/Instructions.cpp 20 Oct 2006 07:07:24 -0000 1.43
> +++ lib/VMCore/Instructions.cpp 23 Oct 2006 02:43:36 -0000
> @@ -1020,11 +1020,11 @@ void BinaryOperator::init(BinaryOps iTyp
> assert(LHS->getType() == RHS->getType() &&
> "Binary operator operand types must match!");
> #ifndef NDEBUG
> switch (iType) {
> case Add: case Sub:
> - case Mul: case Div:
> + case Mul: case UDiv: case SDiv: case FDiv:
> case Rem:
> assert(getType() == LHS->getType() &&
> "Arithmetic operation should return same type as
> operands!");
> assert((getType()->isInteger() || getType()->isFloatingPoint() ||
> isa<PackedType>(getType())) &&
>
>
> *** Likewise, this would be a good place to assert that the operands
> are int/fp(or vectors of) as appropriate.
Yes. Done.
Thanks Chris. Your comments are always useful and instructive.
Reid.
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
