-static Init *getBit(Record *R, unsigned BitNo) {
- const std::vector<RecordVal> &V = R->getValues();
- for (unsigned i = 0, e = V.size(); i != e; ++i)
- if (V[i].getPrefix()) {
- assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
- "Can only handle fields of bits<> type!");
- BitsInit *I = (BitsInit*)V[i].getValue();
- if (BitNo < I->getNumBits())
- return I->getBit(BitNo);
- BitNo -= I->getNumBits();
- }
-
- std::cerr << "Cannot find requested bit!\n";
- exit(1);
- return 0;
-}
-
-static unsigned getNumBits(Record *R) {
- const std::vector<RecordVal> &V = R->getValues();
- unsigned Num = 0;
- for (unsigned i = 0, e = V.size(); i != e; ++i)
- if (V[i].getPrefix()) {
- assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
- "Can only handle fields of bits<> type!");
- Num += ((BitsInit*)V[i].getValue())->getNumBits();
- }
- return Num;
-}
-
-static bool BitsAreFixed(Record *I1, Record *I2, unsigned BitNo) {
- return dynamic_cast<BitInit*>(getBit(I1, BitNo)) &&
- dynamic_cast<BitInit*>(getBit(I2, BitNo));
-}
-
-static bool BitsAreEqual(Record *I1, Record *I2, unsigned BitNo) {
- BitInit *Bit1 = dynamic_cast<BitInit*>(getBit(I1, BitNo));
- BitInit *Bit2 = dynamic_cast<BitInit*>(getBit(I2, BitNo));
-
- return Bit1 && Bit2 && Bit1->getValue() == Bit2->getValue();
-}
-
-static bool BitRangesEqual(Record *I1, Record *I2,
- unsigned Start, unsigned End) {
- for (unsigned i = Start; i != End; ++i)
- if (!BitsAreEqual(I1, I2, i))
- return false;
- return true;
-}
-
-static unsigned getFirstFixedBit(Record *R, unsigned FirstFixedBit) {
- // Look for the first bit of the pair that are required to be 0 or 1.
- while (!dynamic_cast<BitInit*>(getBit(R, FirstFixedBit)))
- ++FirstFixedBit;
- return FirstFixedBit;
-}
-
-static void FindInstDifferences(Record *I1, Record *I2,
- unsigned FirstFixedBit, unsigned MaxBits,
- unsigned &FirstVaryingBitOverall,
- unsigned &LastFixedBitOverall) {
- // Compare the first instruction to the rest of the instructions, looking for
- // fields that differ.
- //
- unsigned FirstVaryingBit = FirstFixedBit;
- while (FirstVaryingBit < MaxBits && BitsAreEqual(I1, I2, FirstVaryingBit))
- ++FirstVaryingBit;
-
- unsigned LastFixedBit = FirstVaryingBit;
- while (LastFixedBit < MaxBits && BitsAreFixed(I1, I2, LastFixedBit))
- ++LastFixedBit;
-
- if (FirstVaryingBit < FirstVaryingBitOverall)
- FirstVaryingBitOverall = FirstVaryingBit;
- if (LastFixedBit < LastFixedBitOverall)
- LastFixedBitOverall = LastFixedBit;
-}
-
-static bool getBitValue(Record *R, unsigned BitNo) {
- Init *I = getBit(R, BitNo);
- assert(dynamic_cast<BitInit*>(I) && "Bit should be fixed!");
- return ((BitInit*)I)->getValue();
-}
-
-struct BitComparator {
- unsigned BitBegin, BitEnd;
- BitComparator(unsigned B, unsigned E) : BitBegin(B), BitEnd(E) {}
-
- bool operator()(Record *R1, Record *R2) { // Return true if R1 is less than R2
- for (unsigned i = BitBegin; i != BitEnd; ++i) {
- bool V1 = getBitValue(R1, i), V2 = getBitValue(R2, i);
- if (V1 < V2)
- return true;
- else if (V2 < V1)
- return false;
- }
- return false;
- }
-};
-
-static void PrintRange(std::vector<Record*>::iterator I,
- std::vector<Record*>::iterator E) {
- while (I != E) std::cerr << **I++;
-}
-
-static bool getMemoryBit(unsigned char *M, unsigned i) {
- return (M[i/8] & (1 << (i&7))) != 0;
-}
-
-static unsigned getFirstFixedBitInSequence(std::vector<Record*>::iterator IB,
- std::vector<Record*>::iterator IE,
- unsigned StartBit) {
- unsigned FirstFixedBit = 0;
- for (std::vector<Record*>::iterator I = IB; I != IE; ++I)
- FirstFixedBit = std::max(FirstFixedBit, getFirstFixedBit(*I, StartBit));
- return FirstFixedBit;
-}
-
-// ParseMachineCode - Try to split the vector of instructions (which is
-// intentionally taken by-copy) in half, narrowing down the possible
-// instructions that we may have found. Eventually, this list will get pared
-// down to zero or one instruction, in which case we have a match or failure.
-//
-static Record *ParseMachineCode(std::vector<Record*>::iterator InstsB,
- std::vector<Record*>::iterator InstsE,
- unsigned char *M) {
- assert(InstsB != InstsE && "Empty range?");
- if (InstsB+1 == InstsE) {
- // Only a single instruction, see if we match it...
- Record *Inst = *InstsB;
- for (unsigned i = 0, e = getNumBits(Inst); i != e; ++i)
- if (BitInit *BI = dynamic_cast<BitInit*>(getBit(Inst, i)))
- if (getMemoryBit(M, i) != BI->getValue())
- throw std::string("Parse failed!\n");
- return Inst;
- }
-
- unsigned MaxBits = ~0;
- for (std::vector<Record*>::iterator I = InstsB; I != InstsE; ++I)
- MaxBits = std::min(MaxBits, getNumBits(*I));
-
- unsigned FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, 0);
- unsigned FirstVaryingBit, LastFixedBit;
- do {
- FirstVaryingBit = ~0;
- LastFixedBit = ~0;
- for (std::vector<Record*>::iterator I = InstsB+1; I != InstsE; ++I)
- FindInstDifferences(*InstsB, *I, FirstFixedBit, MaxBits,
- FirstVaryingBit, LastFixedBit);
- if (FirstVaryingBit == MaxBits) {
- std::cerr << "ERROR: Could not find bit to distinguish between "
- << "the following entries!\n";
- PrintRange(InstsB, InstsE);
- }
-
-#if 0
- std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
- << ": " << InstsE-InstsB << "\n";
-#endif
-
- FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, FirstVaryingBit);
- } while (FirstVaryingBit != FirstFixedBit);
-
- //std::cerr << "\n\nXXXXXXXXXXXXXXXXX\n\n";
- //PrintRange(InstsB, InstsE);
-
- // Sort the Insts list so that the entries have all of the bits in the range
- // [FirstVaryingBit,LastFixedBit) sorted. These bits are all guaranteed to be
- // set to either 0 or 1 (BitInit values), which simplifies things.
- //
- std::sort(InstsB, InstsE, BitComparator(FirstVaryingBit, LastFixedBit));
-
- // Once the list is sorted by these bits, split the bit list into smaller
- // lists, and recurse on each one.
- //
- std::vector<Record*>::iterator RangeBegin = InstsB;
- Record *Match = 0;
- while (RangeBegin != InstsE) {
- std::vector<Record*>::iterator RangeEnd = RangeBegin+1;
- while (RangeEnd != InstsE &&
- BitRangesEqual(*RangeBegin, *RangeEnd, FirstVaryingBit, LastFixedBit))
- ++RangeEnd;
-
- // We just identified a range of equal instructions. If this range is the
- // input range, we were not able to distinguish between the instructions in
- // the set. Print an error and exit!
- //
- if (RangeBegin == InstsB && RangeEnd == InstsE) {
- std::cerr << "Error: Could not distinguish among the following insts!:\n";
- PrintRange(InstsB, InstsE);
- exit(1);
- }
-
-#if 0
- std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
- << ": [" << RangeEnd-RangeBegin << "] - ";
- for (int i = LastFixedBit-1; i >= (int)FirstVaryingBit; --i)
- std::cerr << (int)((BitInit*)getBit(*RangeBegin, i))->getValue() << " ";
- std::cerr << "\n";
-#endif
-
- if (Record *R = ParseMachineCode(RangeBegin, RangeEnd, M)) {
- if (Match) {
- std::cerr << "Error: Multiple matches found:\n";
- PrintRange(InstsB, InstsE);
- }
-
- assert(Match == 0 && "Multiple matches??");
- Match = R;
- }
- RangeBegin = RangeEnd;