Basic Work Plan:

Each item below will be considered an iteration. An iteration consists of making
a small(ish) change across llvm and llvm-gcc4 and testing it with llvm-test and
deja-gnu. Development of new test cases will also occur as the instructions are
modified.

The iterations planned are the following (in roughly this order):

1. Write an IntType class that is a subclass of Type and add it to
   include/llvm/Type.h.
   This class will represent the BATs and must have at least the following
   methods:
   IntType* get(uint16_t numbits); // Returns an IntType for "numbits" bits
   unsigned getNumBits() const; // Returns the number of bits in the type
2. Convert the static type instances in the Type class (BoolTy, ByteTy, IntTy,
   ShortTy,
   LongTy) into corresponding instances of IntType, like:
   static Type *BoolTy; -> static IntType *Int1Ty;
3. Revise the Bytecode reader and writer to handle integer types of any bit
   width. The
   common cases (8,16,32,and 64 bits) will retain their (low-order) values in
   the type
   index. Non-byte-width BATs will be assigned unique type identifiers based
   on their
   bit width. This retains the compaction of the common case values.
4. Update the bytecode documentation to reflect the new bytecode layout.
5. Revise the LLVM Assembly parser to handle integer types of any bit width.
   The assembler will support a new notation for specifying integer types
   using a regex
   pattern of i[0­9]+ so that i4, i7, i32, i64 will all be recognized as
   integer type
   names.
6. Revise the LLVM Assembly writer to use only the new notation for integers it
   prints.
   That is, an input using the short type will generate an output of i16.
   Similarly for
   the other keywords.
7. Update the LLVM Language Reference document to describe the new syntax.
8. Adjust lib/VMCore/ConstantFolding.{h,cpp} to fold integers of any bit width and
   perform correct integer arithmetic computations in constant expressions
   regardless
   of integer bit width.
9. Update all the LLVM Feature and Regression tests, as needed, to fix broken tests
   (e.g. those that look for keywords like short or int in the output) and
   ensure that
   there are no regressions.
10. Write new LLVM Feature tests for non-standard bit widths to ensure that
    assembly,
    bytecode and constant folding can work with these types. Use these tests
    to verify
    correctness of the BAT implementation.

Related to #​8, you'll have to change ConstantInt to be able to hold arbitrary bitwidth constants. Before
you do that, you probably want to merge ConstantBool and ConstantIntegral into ConstantInt.

To specifically implement #​8 and ConstantInt, you probably want to make a very simple library for
representing and manipulating arbitrary bit-width values. This will be important when changing things
that do arithmetic on constants (like instcombine). Currently we usually do stuff like:

int64_t X = V->getZExtValue();
X = (X << 1) & 47;
Y = ConstantInt::get(SomeType, X);

The random arithmetic will have to be done with the library instead of with inline C types and math.

-Chris

For this PR, i'd like to just handle bit width between 1 and 64bits. This means
arbitrary bit-width will be like i13, i47 which <= 64 bits.
For > 64 bits case, we can open a new PR for it. In that PR, we can add a new
Constant subclass, say LargeConstantInt as Reid suggested. i think we can still
keep ConstantBool, and let LargeConstantInt handle all the manipulation stuff of
the arbitrary bit-width values.

I think that handling <= 64 bits before arbitrary width integers makes sense.

You'll still need a basic constant manipulation library to handle constant folding of arbitrary width
integers, even if the widths are limited to 64-bits. Also, please consider merging ConstantBool and
ConstantIntegral into ConstantInt first, as a separate step. It will make things simpler in the long-run.

-Chris

As Chris suggested, ConstantIntegral and ConstantBool will be merged into
ConstantInt after #​2 has completed.

The inital design of BitSet is as following:

class BitSet {

private:

typedef uint64_t _WordTy;

std::vector<_WordTy> WordVec;

inline size_t BITSET_WORDS(uint16_t __n) {
return __n < 1 ? 0 : (__n + BITSET_BITS_PER_WORD - 1) /
BITSET_BITS_PER_WORD;
}

static size_t whichWord(size_t pos)
{ return pos / BITSET_BITS_PER_WORD; }

static size_t whichByte(size_t pos)
{ return (pos % BITSET_BITS_PER_WORD) / 8; }

static size_t whichBit(size_t pos)
{ return pos % BITSET_BITS_PER_WORD; }

static _WordTy maskBit(size_t pos)
{ return (static_cast<_WordTy>(1)) << whichBit(pos); }

_WordTy& getWord(size_t pos)
{ return WordVec[whichWord(pos)]; }

_WordTy getWord(size_t pos) const
{ return WordVec[whichWord(pos)]; }

public:

enum {
BITSET_BITS_PER_WORD = sizeof(uint64_t) * 8
};

/// Create a new BitSet of numbits bit-width, and initalized as all zeros.
///
BitSet(unsigned short numbits = 1) : WordVec(BITSET_WORDS(numbits), 0) {}

/// Create a new BitSet with Integer Value translated from a string.
/// Argument Radix helps the interpretation of the string. Radix can only be
/// 2, 8, 10, 16.
///
BitSet(std::string& Val, uint8_t radix = 10);

BitSet(const BitSet& BS) : WordVec(BS.WordVec) {}

/// Initial bits bitwise-copied from a single word.
BitSet(const _WordTy val) : WordVec(1, val) {}

BitSet& operator=(const BitSet& RHS)
{ WordVec.assign(RHS.WordVec.begin(), RHS.WordVec.end()); }

const BitSet operator++(int);
BitSet& operator++();

const BitSet operator--(int);
BitSet& operator--();

BitSet& operator&=(const BitSet& RHS);

BitSet& operator|=(const BitSet& RHS);

BitSet& operator^=(const BitSet& RHS);

BitSet& operator<<=(size_t shiftAmt);

BitSet& operator>>=(size_t shiftAmt);

BitSet& operator~() const;

BitSet& operator*=(const BitSet& RHS);
BitSet& operator/=(const BitSet& RHS);
BitSet& operator+=(const BitSet& RHS);
BitSet& operator-=(const BitSet& RHS);
BitSet& operator%=(const BitSet& RHS);

/// getMaxValue - This is only for bitwidth <= 64 and
/// returns a uint64_t.
/// @​brief Gets max value of the BitSet with bitwidth <= 64.
uint64_t getMaxValue();

/// getMinValue - This is only for bitwidth <= 64 and
/// returns a uint64_t.
/// @​brief Gets min value of the BitSet with bitwidth <= 64.
uint64_t getMinValue();

/// @​brief Set every bit to 1.
///
BitSet& setAll();

/// Set the given bit to 1 whose poition is given as "pos"
/// @​brief Set a given bit to 1.
///
BitSet& set(size_t pos);

/// @​brief Set every bit to 0.
///
BitSet& clearAll();

/// Set the given bit to 0 whose position is given as "pos"
/// @​brief Set a given bit to 0.
///
BitSet& clear(size_t pos);

/// @​brief Toggle every bit to its opposite value.
///
BitSet& flip();

/// Toggle a given bit to its opposite value whose position is given as "pos"
/// @​brief Toggles a given bit to its opposite value.
BitSet& flip(size_t pos);

/// @​brief Array-indexing support.
///
bool operator[](size_t pos);

/// Retuns a numerical interpretation of the BitSet if its bit-width <= 64
///
operator uint64_t() const;

/// Retuns a character interpretation of the BitSet.
///
std::string to_string(uint8_t radix = 10) const;

/// Returns the number of bits which are set.
size_t count() const;

/// Returns the total number of bits;
size_t getBitsNum() const;

/// Comparison of two BitSets.
bool operator==(const BitSet& RHS) const;
bool operator!=(const BitSet& RHS) const;

/// Return the index of the first "on" bit or BitsNum if all zero.
///
size_t findFirst() const;

BitSet operator<<(size_t shiftAmt) const;
BitSet operator>>(size_t shiftAmt) const;

};

BitSet operator&(const BitSet& BS1, const BitSet& BS2);
BitSet operator|(const BitSet& BS1, const BitSet& BS2);
BitSet operator^(const BitSet& BS1, const BitSet& BS2);

BitSet operator*(const BitSet& BS1, const BitSet& BS2);
BitSet operator/(const BitSet& BS1, const BitSet& BS2);
BitSet operator+(const BitSet& BS1, const BitSet& BS2);
BitSet operator-(const BitSet& BS1, const BitSet& BS2);
BitSet operator%(const BitSet& BS1, const BitSet& BS2);

This looks right-minded, but I have concerns about efficiency. Instead, I'd like to see an approach that
looks like this:

1. ConstantInt should be modified to use the "variable sized array" trick from C to hold the integer data
   immediately after the ConstantInt instance. This allows each ConstantInt to stay a single allocation,
   and also allows them to be fully general (holding arbitrary width integers).

2. A new value class (AInt for arbitrary width integer?) like BitSet should be introduced to represent
   arbitrary width values when they need to be manipulated. This is the thing that should have the
   overloaded operators etc as your BitSet does. To implement this, I'd suggest having it contain three
   fields: a bit width, a pointer to uint64_t (the array of bits) and a single uint64_t value (the later two can
   be in a union if desired). ConstantInt::getValue() should be changed to return an instance of this class.

The basic design of #​2 permits AInt (or whatever) to be constructed on the stack with no additional
memory allocations as longs as the type is 64-bits or less. We can then slowly migrate all the
transformations over to use ConstantInt::getValue() instead of getZExtValue/getSExtValue.

-Chris

As a meta issue, please feel free to split this up into sub-bugs for each separate issue. For example,
you could file one for:

1. Merging ConstantInt ConstantIntegral ConstantBool.
2. Introduce "AInt" (or whatever it should be called), and adding getValue to constantint
3. Make ConstantInt be able to hold large values.
4. Migrate code to use AInt instead of uint64_t for various bit manipulations.
5. Update the .ll/.bc formats for variable width stuff,
   etc

These can all be marked as blocking this bug.

Current committed progress:

ConstantIntegral, ConstantBool and ConstantInt have been merged to a single
ConstantInt class.

BoolTy has been renamed Int1Ty

The arbitrary bitwidth integers have been implemented.

This is what's left for this enhancement

1. ConstantFolding (Sheng)
2. Full test suite (Leo)
3. Documentation updates (Reid)

4. Verifying that all the optimizations work with BATs, even if to just avoid breaking when confronted with
   one.

-Chris

That (#4) was intended to be convered under #​2. The test suite will consist of
both assembly and C/C++ programs.

There are now two remaining items, both being worked on by Sheng:

1. bug 1120 (which this one now depends on). This bug makes some cosmetic
   adjustments to use IntegerType as opposed to Type.
2. Double checking that constant folding works with various bit widths by
   reviewing Leo's test case for coverage.

Once these two items are done, Sheng, this bug can be resolved.

All tasks for this PR have been completed.

Should this really be closed even when simple things like constant folding are broken?

Actually, I retract that, constant folding may not be broken. Have you verified that it works though?

Yes, there's a test suite for it. It passes. Is there something you know that I
don't ?

Nope, I just wanted to make sure you tested it. You tried stuff like 'ashr i7 -1, 3' -> -1 etc?

Not that particular test case, but many similar ones. I just added that one to
test/Integer/a7.ll and it passed. If you're curious about the tests we've
developed, please see test/Integer .. its reasonably comprehensive. Leo developed
this test suite and Sheng reviewed it for completeness and accuracy. He found a
couple instructions that weren't tested well and updated the tests. He also found
a bug in the handling of i1 -1 and fixed it. At this point we don't know of any
constant folding bugs in the arbitrary precision integer arithmetic.

ok, sounds great!

mentioned in issue llvm/llvm-bugzilla-archive#1120