Merge branch 'arm64' into v9.1.x
[dyninst.git] / instructionAPI / aarch64_manual_pareser.py
1 #!/usr/bin/env python
2 # encoding: utf-8
3
4 """
5 Author: Steve Song
6 Email:  songxi.buaa@gmail.com
7 Date:   Sep 2015
8 """
9
10 import os, sys
11 from sets import Set
12 from array import *
13
14 #######################################
15 # a flag for vector and floating points
16 #######################################
17 #VEC_SIMD_SWITCH = False
18 VEC_SIMD_SWITCH = True
19
20 ####################################
21 # dir to store aarch64 ISA xml files
22 ####################################
23 #ISA_dir = "../../ISA_xml_v2_00rel11/"
24 ISA_dir = '/p/paradyn/arm/arm-download-1350222/AR100-DA-70000-r0p0-00rel10/AR100-DA-70000-r0p0-00rel10/ISA_xml/ISA_xml_v2_00rel11/'
25 files_dir = os.listdir(ISA_dir)
26
27 flagFieldsSet = set(['S', 'imm', 'option', 'opt', 'N', 'cond', 'sz', 'size', 'type'])
28 forwardFieldsSet = set([ ])
29
30 ##############################
31 # parse xml files
32 # get opcodes
33 ##############################
34 op_set = Set()
35 insn_set = Set()
36 fp_insn_set =Set()
37
38 # to get op IDs
39 def printP(op):
40     print '  aarch64_op_'+op+','
41
42 def getOpcodes():
43
44     # for general purpose instructions
45     base_insn_file = open(ISA_dir+'index.xml')
46     for lines in base_insn_file:
47         if lines.startswith("    <iform"):
48             op_set.add(lines.split('"')[1].split('.xml')[0].split('_')[0])
49             insn_set.add(lines.split('"')[1].split('.xml')[0])
50         # else do nothing
51
52     # for vector and fp instructions
53     if VEC_SIMD_SWITCH == True:
54         vec_FP_insn_file = open(ISA_dir+'fpsimdindex.xml')
55         for lines in vec_FP_insn_file:
56             if lines.startswith("    <iform"):
57                 op_set.add(lines.split('"')[1].split('.xml')[0].split('_')[0])
58                 insn_set.add(lines.split('"')[1].split('.xml')[0])
59                 fp_insn_set.add(lines.split('"')[1].split('.xml')[0])
60             # else do nothing
61
62
63     print('enum {')
64     printP('INVALID')
65     printP('extended')
66
67     for ele in sorted(insn_set):
68         printP(ele)
69
70     print('}')
71     print 'number of instructions: ', len(insn_set)
72
73 #################################
74 # to find all control field names
75 # discarded
76 #################################
77 '''
78 control_field_set = Set()
79 non_ctl_field_set = Set(['sf'] )
80
81 def getDecodeFieldNames():
82
83     decodeFile = open(ISA_dir + 'encodingindex.xml')
84
85     startReadDecodeField = False
86
87     for line in decodeFile:
88         if startReadDecodeField == True:
89             if line.find('\"bitfields\"') != -1:
90                 control_field_set.add(line.split('>')[1].split('<')[0])
91
92         if line.find('Decode fields') !=-1:
93             startReadDecodeField = True
94
95         if line.find('</thread>')!=-1 and startReadDecodeField == True:
96             startReadDecodeField = False
97
98         if line.find('funcgrouphearder') !=-1 and line.find('simd-dp')!=-1:
99             break
100
101     control_field_set.difference_update(non_ctl_field_set)
102     print sorted(control_field_set)
103     '''
104
105
106 def shifting(bitlist):
107     out = 0
108     for bit in bitlist:
109         out = (out<<1) | (bit=='1' )
110     return out
111
112 ##########################
113 # parse xml files and get
114 # opcodes and operands
115 ##########################
116
117 def getOperand_Insn(line):
118     '''
119     analyze one <box> line </box> to get operand
120     '''
121     for field in line.split(' '):
122         if field.find('name') != -1 and field.find('usename') == -1:
123             opname = field.split('\"')[1]
124             if opname.find('imm') !=-1:
125                 opname = 'imm'
126             return opname
127         # else continue do nothing
128
129 def isRnUpdated(line):
130     if line.find('post-idx') != -1 or line.find('pre-idx') !=-1:
131         return True;
132     return False;
133
134 def ifNeedToSetFlags(line):
135     if line.find('<iclass ') != -1 :
136         for field in line.split(' '):
137             if field.find('id=') !=-1:
138                 if field.split('\"')[1] == 's':
139                     return True
140
141     if line.find('<regdiagram') != -1:
142         if line.find('float/compare') != -1:
143             return True
144     return False
145
146
147 ###########################
148 # to store all masks
149 # to store all encodings
150 # to store all instructions
151 ###########################
152 masksArray = list()
153 encodingsArray = list()
154 insnArray = list()
155 operandsArray = list()
156 operandsSet = set()
157
158 # to get the encoding table
159 def getOpTable( filename = 'NULL' ):
160
161     global masksArray
162     global encodingsArray
163     global insnArray
164     global operandsSet
165
166     # some init #
167     insn_unallocated = (2**28+2**27)
168     masksArray.append(insn_unallocated)
169     encodingsArray.append(int(0))
170     insnArray.append('INVALID')
171     operandsArray.append('')
172     indexOfInsn = 1
173
174     print 0, '%22s'%'INVALID',  '%34s'%bin(insn_unallocated), '(', hex(insn_unallocated), ')'
175
176     for file in sorted(files_dir):
177
178         if file.endswith('.xml'):
179             instruction = file.split('.xml')[0]
180
181             if instruction in insn_set:
182                 #print file
183                 curFile = open(ISA_dir+file)
184
185                 startDiagram = False
186                 startBox = False
187                 maskBit = list('0'*32)
188                 encodingArray = list('0'*32)
189                 operands_pos_Insn = list()
190                 reserve_operand_pos = list()
191                 maskStartBit = 31
192                 isRnUp = False
193                 needToSetFlags = False
194
195                 # to analyze lines , do iterative passes#
196                 for line in curFile:
197
198                     if line.find('<iclass ') != -1 :
199                         needToSetFlags = ifNeedToSetFlags(line)
200
201                     # diagram starts #
202                     if line.find('<regdiagram')!=-1:
203                         isRnUp = isRnUpdated(line)
204                         if needToSetFlags == False:
205                             needToSetFlags = ifNeedToSetFlags(line)
206                         startDiagram = True
207                         continue
208
209                     # end of diagram #
210                     if line.find('</regdiagram')!=-1:
211                         if needToSetFlags == True:
212                             operands_pos_Insn.insert(0, ('setFlags',) )
213                         printInstnEntry(maskBit, encodingArray, indexOfInsn, instruction, operands_pos_Insn)
214
215                         startDiagram = False
216                         maskBit = list('0'*32)
217                         encodingArray = list('0'*32)
218                         operands_pos_Insn = list()
219
220                         indexOfInsn +=1
221                         continue
222
223                     # analyze each box #
224                     if startDiagram == True and line.find('<box') != -1:
225                         #name, start bit, length
226                         for x in line.split(' '):
227                             if x.find('hibit') != -1:
228                                 maskStartBit = int(x.split('\"')[1])
229                                 break
230
231                         # reserve the operand and position information
232                         # it only will be appended if the encoding fields are not defined unique
233                         reserve_operand_pos = getOperandValues(line, instruction, isRnUp)
234                         startBox = True
235
236                     # end of box #
237                     if line.find('</box') != -1:
238                         startBox = False
239                         continue
240
241                     # read box content #
242                     if startBox == True:
243                         # start of <c>
244                         if line.find('<c') != -1:
245                             encodeBit = line.split('>')[1].split('<')[0]
246
247                             # control field
248                             if encodeBit == '1' or encodeBit == '0':
249                                 maskBit[31-maskStartBit] = '1'
250                                 encodingArray[31-maskStartBit] = encodeBit
251                                 '''
252                                 if encodeBit == '1':
253                                     if reserve_operand_pos[0] == 'S':
254                                         operands_pos_Insn.append( ('setFlags',) )
255                                 '''
256
257                             elif encodeBit == '(1)':
258                                 maskBit[31-maskStartBit] = '1'
259                                 encodingArray[31-maskStartBit] = '1'
260
261                             elif encodeBit == '(0)':
262                                 maskBit[31-maskStartBit] = '1'
263                                 encodingArray[31-maskStartBit] = '0'
264
265                             # if it is 'x', we set it as not a control field
266                             # and append the reserved operand to the list
267                             elif encodeBit == 'x':
268                                 maskBit[31-maskStartBit] = '0'
269                                 encodingArray[31-maskStartBit] = '0'
270
271                                 if reserve_operand_pos[0] in forwardFieldsSet:
272                                     operands_pos_Insn.insert(0, reserve_operand_pos)
273                                 else:
274                                     operands_pos_Insn.append(reserve_operand_pos)
275
276                                 if reserve_operand_pos[0] not in operandsSet:
277                                     operandsSet.add(reserve_operand_pos[0])
278
279                             # if it is blank, same as 'x', do late operand appending
280                             elif encodeBit == '':
281                                 if reserve_operand_pos[0] in forwardFieldsSet:
282                                     operands_pos_Insn.insert(0, reserve_operand_pos)
283                                 else:
284                                     operands_pos_Insn.append(reserve_operand_pos)
285
286                                 if reserve_operand_pos[0] not in operandsSet:
287                                     operandsSet.add(reserve_operand_pos[0])
288
289                             elif encodeBit.startswith('!=') != -1:
290                                 if reserve_operand_pos[0] in forwardFieldsSet:
291                                     operands_pos_Insn.insert(0, reserve_operand_pos)
292                                 else:
293                                     operands_pos_Insn.append(reserve_operand_pos)
294
295                                 if reserve_operand_pos[0] not in operandsSet:
296                                     operandsSet.add(reserve_operand_pos[0])
297
298                             else:
299                                 #if not encodeBit.startswith('!='):
300                                 print '[WARN] something not has been analyzed:'+ encodeBit
301
302                             maskStartBit = maskStartBit - 1
303                     # end of <box line> #
304
305                 # end of each line #
306
307 ####################################
308 # generate instructions
309 ####################################
310 def printInstnEntry( maskBit, encodingArray, index, instruction, operands):
311     global masksArray
312     global encodingsArray
313     global insnArray
314     global operandsArray
315
316      # print instruction and encoding mask per file
317     maskBitInt = int(''.join(maskBit), 2)
318     encodingBitInt = int( ''.join(encodingArray),2)
319
320     masksArray.append(maskBitInt)
321     encodingsArray.append(encodingBitInt)
322     insnArray.append(instruction)
323     operandsArray.append(operands)
324
325     print index, "%22s"%instruction, '\t', ''.join(maskBit),'(', hex(maskBitInt),')', '\t', ''.join(encodingArray), '(', hex(encodingBitInt), ')', operands
326
327
328 def isLDST(insn):
329     if insn.startswith('ld') or insn.startswith('st'):
330         return True
331     return False
332
333 def getRegWidth(insn):
334
335     insnMnemonic = insn.split('_')[0]
336     # ld/st register, do nothing
337     if insnMnemonic.endswith('b') and not insnMnemonic.endswith('sb'):
338         return 32
339     elif insnMnemonic.endswith('h') and not insnMnemonic.endswith('sh'):
340         return 32
341     elif insnMnemonic.endswith('sb'):
342         return 64
343     elif insnMnemonic.endswith('sh'):
344         return 64
345     elif insnMnemonic.endswith('sw'):
346         return 64
347     elif insnMnemonic.endswith('r'):
348         return 64
349     elif insnMnemonic.endswith('p'):
350         return 64
351     else :
352         return 128
353         #print '[WARN] not recognized instruction:', insn
354     return 64
355
356 def isSIMD(insn):
357     if insn.find('simd') != -1:
358         return True
359     return False
360
361
362 ####################################
363 # generate the c++ code
364 # which builds the instruction table
365 ####################################
366 def buildInsnTable():
367     assert len(masksArray) == len(encodingsArray) ==len(insnArray)
368     print len(insnArray)
369     print '*** instruction table ***'
370
371     for i in range(0, len(insnArray)):
372         instruction = insnArray[i]
373
374         if len(operandsArray[i]) == 0:
375             operands = 'operandSpec()'
376         else:
377             operands = 'list_of'
378
379             # recognize FP and SIMD
380             if instruction in fp_insn_set:
381                 if isSIMD(instruction) == False:
382                     operands += '( fn(setFPMode) )'
383                 else:
384                     operands += '( fn(setSIMDMode) )'
385
386             if isLDST(instruction) == True:
387                 if getRegWidth(instruction) == 32 or getRegWidth(instruction) == 64:
388                     operands += '( fn(setRegWidth) )'
389                 else:
390                     if getRegWidth(instruction) != 128:
391                         print '[WARN] unknown width'
392
393             for operand in operandsArray[i]:
394                 operands += '( fn('
395
396                 if len(operand) != 1:
397                     operands += 'OPR'+operand[0]+'<'+ str(operand[1][0])+' COMMA ' + str(operand[1][1])+'>'
398                 else:
399                     curOperandName = operand[0]
400                     if curOperandName == 'setFlags':
401                         operands+= curOperandName
402                     else:
403                         operands += 'OPR'+ curOperandName
404
405                 operands += ') )'
406
407         print '\tmain_insn_table.push_back(aarch64_insn_entry(aarch64_op_'+insnArray[i]+', \t\"'+insnArray[i].split('_')[0]+'\",\t'+ operands +' ));'
408
409 ##########################
410 # generate decoding tree #
411 ##########################
412 numOfLeafNodes=0
413 processedIndex = Set()
414 notProcessedIndex = Set()
415 numNotProcNodes = 0
416 numNodes = 0
417
418 ##################
419 # a helper function
420 # clapse(1001, 1101) => (101 & 111) => 101 => 5
421 ##################
422 def clapseMask(encoding, curMask):
423     ret = 0
424     while curMask!=0:
425         if curMask & 0x80000000 != 0:
426             ret = (ret<<1)|((encoding & 0x80000000)>>31)
427         curMask = (curMask << 1)&0xffffffff
428         encoding = (encoding << 1)&0xffffffff
429     return ret
430
431
432 ####################################
433 # generate the c++ code
434 # which builds the decoding table
435 ####################################
436 def printDecodertable(entryToPlace, curMask=0, entryList=list(), index=-1 ):
437     entries = 'map_list_of'
438     if len(entryList) == 0:
439         entries = 'branchMap()'
440     else:
441         for ent in entryList:
442             entries += '('+str(ent[0])+','+str(ent[1])+')'
443
444     print '\tmain_decoder_table['+str(entryToPlace)+']=aarch64_mask_entry('+str(hex(curMask))+', '+entries+','+str(index)+');'
445
446
447
448 def num1sInMask(x):
449     mask = masksArray[x]
450     num = 0
451     while mask != 0:
452         if mask &1 == 1:
453             num +=1
454         mask = mask>>1
455     return int(num)
456
457 def alias_comparator( x, y ):
458     return num1sInMask(x) - num1sInMask(y)
459
460
461 ####################################
462 # this is the init value that the instruction
463 # entry should start from. 0 is reserved for
464 # invalid insn.
465 ####################################
466 entryAvailable = 1
467
468 ###########################################
469 # arg0 is the range of indexes in the instruction array
470 #   that you want to analyze
471 # arg1 is the bit mask that has been processed
472 # arg2 is the entry of the decoding table
473 #   where the current call should place for one decision node
474 ###########################################
475 def buildDecodeTable(inInsnIndex , processedMask, entryToPlace):
476     global numOfLeafNodes
477     global numNotProcNodes
478     global numNodes
479     global entryAvailable
480
481     # guards, redundant
482     if entryToPlace > 2**32:
483         print '*** [WARN] should not reach here ***'
484         return
485
486     # terminated condition 1
487     if len(inInsnIndex) < 1:
488         print '*** [WARN] should not reach here ***'
489         #numOfLeafNodes +=1
490         return
491
492     # size of inInsnIndex is 1. This means we should generate a leaf node
493     if len(inInsnIndex) ==1:
494         printDecodertable(entryToPlace, 0, list() , inInsnIndex[0]);
495         numNodes += 1
496         #print insnArray[inInsnIndex[0]]
497         if inInsnIndex[0] in processedIndex:
498             print '[WARN] index processed, repeated index is ', inInsnIndex[0]
499
500         processedIndex.add(inInsnIndex[0])
501         numOfLeafNodes +=1
502         return
503
504     validMaskBits = int(''.join('1'*32), 2)
505
506     # find the minimum common mask bit field
507     for i in inInsnIndex:
508         validMaskBits = validMaskBits & masksArray[i]
509
510     # eliminate the processed mask bit field
511     validMaskBits = validMaskBits&(~processedMask)
512     #print hex(validMaskBits), bin(validMaskBits)
513
514     # terminated condition 2
515     # if the mask we get is 0, this means we have a bunch of instructions
516     # sharing the same opcode. They are aliases actually.
517     # Group them together.
518     addMask = 0
519     if validMaskBits == 0:
520         # weak solution to aliases
521         numOfLeafNodes += len(inInsnIndex)
522
523         inInsnIndex.sort( cmp=alias_comparator )
524
525         for i in inInsnIndex:
526             processedIndex.add(i)
527             print insnArray[i], '\t', bin( masksArray[i] ), '\t', bin(encodingsArray[i])
528         printDecodertable(entryToPlace, 0, list(), inInsnIndex[0]);
529         numNodes += 1
530         return
531
532         '''
533         for i in inInsnIndex:
534             #print '%3d'%i+'%22s'%insnArray[i]+'%34s'%bin(masksArray[i])+'%34s'%bin(encodingsArray[i])
535             addMask |= masksArray[i] &(~processedMask)
536             #addMask ^= encodingsArray[i] &(~processedMask)
537
538         # handle alias, merge them into one node
539         if addMask == 0:
540             numOfLeafNodes += len(inInsnIndex)
541             for i in inInsnIndex:
542                 processedIndex.add(i)
543             printDecodertable(entryToPlace, 0, list(), inInsnIndex[0]);
544             numNodes += 1
545             return
546         # handle more mask bits
547         else:
548             validMaskBits = addMask
549             #print bin(addMask)
550             '''
551
552     # till here we should have got the mask bits
553     MSBmask = 0x80000000
554     curMask = 0
555     numCurMaskBit = 0
556
557     #print hex(validMaskBits)
558
559     # get currrent valid mask
560     # check bit one by one from MSB
561     for bit in range(0, 32):
562         if (MSBmask & validMaskBits) == 0 :
563             validMaskBits = (validMaskBits << 1)
564         else:
565             curMask |= 1<<(31-bit)
566             validMaskBits = (validMaskBits << 1)
567             numCurMaskBit += 1
568             #break
569
570     #print 'cur mask', hex(curMask)
571
572     # should not be 0
573     if curMask == 0:
574         print "[WARN] mask is 0"
575         #print '%25s'%'processed mask'+'%35s'%bin(processedMask)
576         for i in inInsnIndex:
577             print '%3d'%i+'%22s'%insnArray[i]+'%35s'%bin(masksArray[i])+'%35s'%bin(encodingsArray[i])
578         numOfLeafNodes+=len(inInsnIndex)
579         return
580
581
582     # update processed mask
583     processedMask = processedMask | curMask
584
585     indexList = [ ]
586     for i in range(0, 2**numCurMaskBit):
587         indexList.append([])
588
589     # generate the branches
590     # glue instructions to that branch
591     for index in inInsnIndex:
592         branchNo = clapseMask(encodingsArray[index] & curMask, curMask)
593         #print 'branchNo' ,branchNo
594         indexList[branchNo].append(index)
595
596     # get number of branches
597     # a trick to eliminate null branches
598     numBranch = 0
599     validIndexList = []
600     brNoinIndexList = 0
601     posToBrNo = list()
602     for i in indexList:
603         if len(i)!=0:
604             numBranch+=1
605             validIndexList.append(i)
606             posToBrNo.append(brNoinIndexList)
607         brNoinIndexList += 1
608
609     # typedef mask_table vector<mask_entry>;
610     # assign entry number to that branch
611     entryList = []
612     for i in range(0, numBranch):
613         entryList.append( (posToBrNo[i], entryAvailable + i) )
614
615     # reserve room
616     entryAvailable += numBranch
617
618     # TODO
619     printDecodertable(entryToPlace, curMask, entryList, -1);
620     numNodes += 1
621
622     """
623     print '%34s'%bin(curMask)
624     for i in zeroIndexes:
625         print '%34s'%bin(encodingsArray[i])
626
627     for i in oneIndexes:
628         print '%34s'%bin(encodingsArray[i])
629     """
630     #print validIndexList
631     for i in range(0, numBranch):
632         buildDecodeTable( validIndexList[i], processedMask, entryList[i][1])
633
634 ###############################################################
635 # the following section is for parsing and generating operands.
636 ###############################################################
637
638 def getOperandValues(line, instruction, isRnUp):
639     multiOperandSet = flagFieldsSet
640
641     if line.find(' name') != -1:
642         width = 1
643         tokens = line.split(' ')
644         for token in tokens:
645             if token.find('name')!=-1 and token.find('usename')== -1:
646                 name = token.split('\"')[1]
647                 if name.find('imm') != -1:
648                     name = 'imm'
649             if token.find('hibit')!=-1:
650                 bit = int(token.split('\"')[1])
651             if token.find('width') != -1:
652                 width = int(token.split('\"')[1])
653     else:
654         #print '*** [WARN] Blank operand field ***'
655         return ('', [0, 0])
656
657     if name.find('Rt') != -1 or name.find('Rt2') != -1 or name.find('Rn') !=-1:
658     #if name == 'Rt' or name == 'Rt2' or name == 'Rn':
659         if instruction.startswith('ld'):
660             name += 'L'
661
662         if instruction.startswith('st'):
663             name += 'S'
664
665     # ld/st class
666     if instruction.startswith('ld') or instruction.startswith('st'):
667         if name.startswith('Rn'):
668             if isRnUp == True:
669                 name += 'U'
670
671             # the following commented section is useless
672             '''
673             insnMnemonic = instruction.split('_')[0]
674             # ld/st register, do nothing
675             if insnMnemonic.endswith('b') and not insnMnemonic.endswith('sb'):
676                 name += '<u8>'
677             elif insnMnemonic.endswith('h') and not insnMnemonic.endswith('sh'):
678                 name += '<u16>'
679             elif insnMnemonic.endswith('w') and not insnMnemonic.endswith('sw'):
680                 name += '<u32>'
681             elif insnMnemonic.endswith('sb'):
682                 name += '<s8>'
683             elif insnMnemonic.endswith('sh'):
684                 name += '<s16>'
685             elif insnMnemonic.endswith('sw'):
686                 name += '<s32>'
687             # TODO: need to handle ld/st pair
688             #if instruction.endswith('p'):
689             else :
690                 if not insnMnemonic.endswith('r') and not insnMnemonic.endswith('p'):
691                     print '[WARN] not recognized instruction:', instruction
692                     '''
693
694
695     endbit = bit - (width-1)
696     #return (name, [bit, width])
697     if name in multiOperandSet:
698         return (name, [bit, endbit])
699     else:
700         return (name,)
701
702
703 def printOperandFuncs(operandsSet):
704     print 'operand function declares'
705     for operand in operandsSet:
706         print 'void '+ 'OPR'+operand + '(){ }'
707
708
709 ####### main ########
710 def main():
711
712     ######################################
713     # get opcodes of GP instructions
714     # and FP/VEC instructions respectively
715     ######################################
716     getOpcodes()
717
718     #################################################################
719     # get instructions, opcodes, lists of operands
720     # each set is stored in an array
721     # indexes in the arrays are used to find the instruction you want
722     #################################################################
723     getOpTable()
724
725     ###############################################
726     # instruction table
727     # generate C++ code to build instruction tables
728     ###############################################
729     buildInsnTable()
730
731     #########################################
732     # generate C++ code of operands functions
733     #########################################
734     print '*** operands ***'
735     print sorted(operandsSet)
736     printOperandFuncs(operandsSet)
737
738     ###########################################
739     # Decoder table.
740     # Generate C++ code to build decoding table.
741     # Basically, the generated stuff is a decision tree, which is represented in a map.
742     #
743     # Each entry stands for a decision node in the decision tree with a few or zero
744     #   branches. One branch contains a {Key, Value} pair. Key is used to index. Value is
745     #   the next entry number in the map, like a pointer.
746     #
747     # Binaries are passed to the root node first, and compared with the decision mask in
748     #   that node. Instrution binary does bit operation AND over the mask. The result of it
749     #   will be compared with the Key of the branches. Once matched to the Key, the instruction
750     #   will be passed to next decision node pointed by the branch.
751     #   Recursively do this, until to the leaf node.
752     #
753     # Each leaf node contains the index of the instruction array in the last field,
754     #   which holds the instruction entry.
755     ###########################################
756     print '*** decoder table ***'
757     validInsnIndex = list( range(0, len(insnArray) ) )
758     buildDecodeTable(validInsnIndex, 0 , 0)
759
760     ###############################
761     # some statistics for debugging
762     ###############################
763     print 'num of vaild leaves', numOfLeafNodes
764     allIndex = Set(range(0, len(insnArray)) )
765     print 'processed indexex: ', processedIndex, len(processedIndex)
766     print 'missing indexes:', sorted(allIndex - processedIndex), len(allIndex-processedIndex)
767     print 'number of total nodes in the tree:', numNodes
768
769 if __name__ == '__main__':
770     main()
771
772
773
774