Hi Reid, thanks for replying.
> > > Please use APInt's to do the subtraction, instead of constant
> > > folding. Reid should be able to help you with this.
> >
> > I don't understand why. If APInt's are much more efficient, then
> > shouldn't ConstantExpr:getSub be improved to detect this case and
> > directly use APInts itself?
>
> Currently, ConstantInt is implemented in terms of APInt. So, if you
> subtract two ConstantInt (via ConstantExpr), you are in essence just
> doing an APInt subtraction. However, having just looked at the constant
> folding code again, here's what happens:
>
> 1. Call to ConstantExpr::get which calls ConstantExpr::getTy which
> calls ConstantFoldBinaryInstruction.
> 2. 5 if statements and a switch in ConstantFoldBinaryInstruction
> 3. Extraction of APInt values from the ConstantInt operands to the
> ConstantExpr object.
> 4. APInt subtraction.
> 5. Construction of a new ConstantInt which involves at least (a)
> construction of an IntegerMapKeyType and (b) std::map lookup to
> see if the value already exists; and, if the value doesn't
> exist, will also involve (c) instantiation of an integer value
> representation object and (d) insertion into two maps (one
> forward, one inverse)
>
> I think this is Chris' point. You could replace all of that with just
> "APInt subtraction". #5 can be really expensive because of the map
> traversals and insertions, especially in programs with lots of constant
> values.
In most of the switch code #5 cannot be avoided, since the final result
needs to be a ConstantInt. However Range only needs to be turned into
a ConstantInt if the range is wide, so indeed one instance of #5 can be
avoided in the common case.
> > > + if (Range->getZExtValue() < 2*HOST_BITS_PER_WIDE_INT) {
> > >
> > > This is bad because it means llvm-gcc will produce different code
> > > based on thevalue of HOST_BITS... Please just say " < 64" or something.
>
> Since you are working with numbers of bits here and not with values
> requiring that number of bits, the range of values possible will always
> fit in a uint32_t. Is it possible just to use that instead of a
> ConstantInt? uint32_t Range = X - Y is way cheaper than any of the
> foregoing :)
Range is the case range, which can be arbitrarily big, so I'm afraid not.
> FYI: I'm contemplating making llvm-gcc represent CONSTANT_INT nodes with
> APInt so that it can handle integer constants of any bit width. This is
> a requirement for the work I'm doing for AutoESL.
This would make it hard to merge with mainline.
I am testing the following patch. While I was there, I made it agnostic
as to the signedness of the switch expression and cases (in Ada they can
be unsigned).
Ciao,
Duncan.
Index: gcc.llvm.master/gcc/llvm-convert.cpp
===================================================================
--- gcc.llvm.master.orig/gcc/llvm-convert.cpp 2007-03-14 18:49:06.000000000 +0100
+++ gcc.llvm.master/gcc/llvm-convert.cpp 2007-03-14 19:03:58.000000000 +0100
@@ -1666,6 +1666,7 @@
// Emit the condition.
Value *SwitchExp = Emit(SWITCH_COND(exp), 0);
+ bool ExpIsSigned = !TYPE_UNSIGNED(TREE_TYPE(SWITCH_COND(exp)));
// Emit the switch instruction.
SwitchInst *SI = new SwitchInst(SwitchExp, CurBB,
@@ -1673,39 +1674,65 @@
EmitBlock(new BasicBlock(""));
SI->setSuccessor(0, CurBB); // Default location starts out as fall-through
- // Output the body of the switch.
- if (SWITCH_BODY(exp))
- Emit(SWITCH_BODY(exp), 0);
-
+ assert(!SWITCH_BODY(exp) && "not a gimple switch?");
+
+ BasicBlock *DefaultDest = NULL;
for (unsigned i = 0, e = TREE_VEC_LENGTH(Cases); i != e; ++i) {
BasicBlock *Dest = getLabelDeclBlock(CASE_LABEL(TREE_VEC_ELT(Cases, i)));
- if (CASE_LOW(TREE_VEC_ELT(Cases, i)) == 0) {
- SI->setSuccessor(0, Dest); // Change the default destination.
+
+ tree low = CASE_LOW(TREE_VEC_ELT(Cases, i));
+ if (!low) {
+ DefaultDest = Dest;
continue;
}
// Convert the integer to the right type.
- Value *Val = Emit(CASE_LOW(TREE_VEC_ELT(Cases, i)), 0);
- Val = CastToSIntType(Val, SwitchExp->getType());
- ConstantInt *ValC = cast<ConstantInt>(Val);
- if (CASE_HIGH(TREE_VEC_ELT(Cases, i)) == 0) {
- SI->addCase(ValC, Dest); // Single destination.
+ Value *Val = Emit(low, 0);
+ Val = CastToAnyType(Val, !TYPE_UNSIGNED(TREE_TYPE(low)),
+ SwitchExp->getType(), ExpIsSigned);
+ ConstantInt *LowC = cast<ConstantInt>(Val);
+
+ tree high = CASE_HIGH(TREE_VEC_ELT(Cases, i));
+ if (!high) {
+ SI->addCase(LowC, Dest); // Single destination.
continue;
}
- // Otherwise, we have a range, like 'case 1 ... 17'. Add all of the
- // necessary successors to the switch.
- Val = Emit(CASE_HIGH(TREE_VEC_ELT(Cases, i)), 0);
- // Make sure the case value is the same type as the switch expression (int)
- Val = CastToSIntType(Val, SwitchExp->getType());
- ConstantInt *HiC = cast<ConstantInt>(Val);
- Constant *OneC = ConstantInt::get(ValC->getType(), 1);
- while (1) {
- SI->addCase(ValC, Dest);
- if (ValC == HiC) break; // Emitted the last one.
- ValC = cast<ConstantInt>(ConstantExpr::getAdd(ValC, OneC));
+ // Otherwise, we have a range, like 'case 1 ... 17'.
+ Val = Emit(high, 0);
+ // Make sure the case value is the same type as the switch expression
+ Val = CastToAnyType(Val, !TYPE_UNSIGNED(TREE_TYPE(high)),
+ SwitchExp->getType(), ExpIsSigned);
+ ConstantInt *HighC = cast<ConstantInt>(Val);
+
+ APInt Range = HighC->getValue() - LowC->getValue();
+ if (Range.ult(APInt(Range.getBitWidth(), 64))) {
+ // Add all of the necessary successors to the switch.
+ APInt CurrentValue = LowC->getValue();
+ while (1) {
+ SI->addCase(LowC, Dest);
+ if (LowC == HighC) break; // Emitted the last one.
+ CurrentValue++;
+ LowC = ConstantInt::get(CurrentValue);
+ }
+ } else {
+ // The range is too big to add to the switch - emit an "if".
+ Value *Diff = BinaryOperator::create(Instruction::Sub, SwitchExp, LowC,
+ "tmp", CurBB);
+ Value *Cond = new ICmpInst(ICmpInst::ICMP_ULE, Diff,
+ ConstantInt::get(Range), "tmp", CurBB);
+ BasicBlock *False_Block = new BasicBlock("case_false");
+ new BranchInst(Dest, False_Block, Cond, CurBB);
+ EmitBlock(False_Block);
}
}
+
+ if (DefaultDest)
+ if (SI->getSuccessor(0) == CurBB)
+ SI->setSuccessor(0, DefaultDest);
+ else
+ new BranchInst(DefaultDest, CurBB);
+
return 0;
}
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
