Added instruction iterator
[dyninst.git] / dyninstAPI / src / InstrucIter-mips.C
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <assert.h>
4 #include <string.h>
5
6 #include "common/h/Types.h"
7 #include "common/h/Vector.h"
8 #include "common/h/Dictionary.h"
9
10 #include "arch.h"
11 #include "util.h"
12 #include "process.h"
13 #include "symtab.h"
14 #include "instPoint.h"
15 #include "InstrucIter.h"
16
17 #include "BPatch_snippet.h"
18
19 // #define DEBUG_FINDTARGET 1
20 // #define DEBUG_FINDTARGET_2 1
21
22 /* From inst-mips.C & arch-mips.C: */
23 extern char *reg_names_book[];
24 extern uint32_t get_word(const Object &elf, Address addr);
25 extern uint64_t get_dword(const Object &elf, Address addr);
26 extern void dis(void *actual_, void *addr_, int ninsns,
27                 const char *pre, FILE *stream);
28
29 typedef struct {
30     bool isConditional;
31     bool isIndirect;
32     bool isCall;
33 } BranchInfo;
34
35 /** returns true if an instruction is a branch, false if not.  Also returns
36   * information about the branch: is it condition, is it indirect, and
37   * the target address.
38   * @param i the instruction value
39   */
40 static bool getBranchInfo(instruction i, BranchInfo &bi)
41 {
42     bi.isConditional = false;
43     bi.isIndirect    = false;
44     bi.isCall        = false;
45
46     switch (i.decode.op) {
47       case COP0op:
48       case COP1op:
49       case COP2op:
50       case COP1Xop:
51         if (i.itype.rs == 8) { /* BC */
52             /* XXX Actually, are all branch conditions (i.itype.rt values)
53                allowed?*/
54             bi.isConditional = true;
55             return true;
56         }
57         break;
58       case BEQop:
59       case BEQLop:
60       case BNEop:
61       case BNELop:
62         /* Branch if equal or not equal on comparison of a register with
63            itself is an unconditional branch (or a branch never). */
64         if (i.itype.rs != i.itype.rt) {
65             bi.isConditional = true;
66             return true;
67         }
68         return true;
69       case BGTZop:
70       case BGTZLop:
71       case BLEZop:
72       case BLEZLop:
73         bi.isConditional = true;
74         return true;
75       case Jop:
76         return true;
77       case JALop:
78         bi.isCall = true;
79         return true;
80       case REGIMMop:
81         switch (i.regimm.opr) {
82           case BGEZopr:
83           case BGEZLopr:
84           case BLTZopr:
85           case BLTZLopr:
86             bi.isConditional = true;
87             return true;
88           case BGEZALopr:
89           case BGEZALLopr:
90           case BLTZALopr:
91           case BLTZALLopr:
92             bi.isConditional = true;
93             bi.isCall = true;
94             return true;
95         };
96         break;
97       case SPECIALop:
98         switch (i.rtype.ops) {
99           case JALRops:
100             if (i.rtype.rt == 0 && i.rtype.sa == 0) {
101                 bi.isIndirect = true;
102                 bi.isCall = true;
103                 return true;
104             } else {
105                 /* Invalid -- throw assert for now. */
106                 assert(0);
107             }
108           case JRops:
109             if (i.rtype.rt == 0 && i.rtype.rd == 0 && i.rtype.sa == 0) {
110                 bi.isIndirect = true;
111                 return true;
112             } else {
113                 /* Invalid. */
114                 assert(0);
115             }
116         };
117         break;
118     };
119     return false;
120 }
121
122 bool modifies_greg(instruction i, int &regnum)
123 {
124     int cop;
125
126     switch (i.decode.op) {
127       case ADDIop:
128       case ADDIUop:
129       case ANDIop:
130       case DADDIop:
131       case DADDIUop:
132       case LBop:
133       case LBUop:
134       case LDop:
135       case LDLop:
136       case LDRop:
137       case LHop:
138       case LHUop:
139       case LLop:
140       case LLDop:
141       case LUIop:
142       case LWop:
143       case LWLop:
144       case LWRop:
145       case LWUop:
146       case ORIop:
147       case SLTIop:
148       case SLTIUop:
149       case XORIop:
150         regnum = i.itype.rt;
151         return true;
152       case COP0op:
153       case COP1op:
154       case COP2op:
155         if (i.rtype.sa == 0 && i.rtype.ops == 0) {
156             cop = i.rtype.op & 0x3;
157             if ((cop == 0 && i.rtype.rs == 1) ||
158                 ((cop == 1 || cop == 2) && i.rtype.rs == 2) ||
159                 ((cop == 0 || cop == 1 || cop == 2) && i.rtype.rs == 0)) {
160                 regnum = i.rtype.rt;
161                 return true;
162             }
163         }
164         break;
165       case SPECIALop:
166         switch (i.rtype.ops) {
167           case ADDops:
168           case ADDUops:
169           case ANDops:
170           case DADDops:
171           case DADDUops:
172           case DSLLVops:
173           case DSRAVops:
174           case DSRLVops:
175           case DSUBops:
176           case DSUBUops:
177           case NORops:
178           case ORops:
179           case SLLVops:
180           case SLTops:
181           case SLTUops:
182           case SRAVops:
183           case SUBops:
184           case SUBUops:
185           case XORops:
186             if (i.rtype.sa == 0) {
187                 regnum = i.rtype.rd;
188                 return true;
189             }
190             break;
191           case DSLLops:
192           case DSLL32ops:
193           case DSRAops:
194           case DSRA32ops:
195           case DSRLops:
196           case DSRL32ops:
197           case SLLops:
198           case SRAops:
199           case SRLops:
200           case SRLVops:
201             if (i.rtype.rs == 0) {
202                 regnum = i.rtype.rd;
203                 return true;
204             }
205             break;
206           case MFHIops:
207           case MFLOops:
208             if (i.rtype.rs == 0 && i.rtype.rt == 0 && i.rtype.sa == 0) {
209                 regnum = i.rtype.rd;
210                 return true;
211             }
212             break;
213           case JALRops:
214             if (i.rtype.rt == 0 && i.rtype.sa == 0) {
215                 regnum = i.rtype.rd;
216                 return true;
217             }
218             break;
219         }
220     }
221
222     return false;
223 }
224
225 //some more function used to identify the properties of the instruction
226 /** is the instruction used to return from the functions
227   * @param i the instruction value 
228   */
229 bool InstrucIter::isAReturnInstruction()
230 {
231   const instruction i = getInstruction();
232   return isReturnInsn(i);
233 }
234
235 /** is the instruction an indirect jump instruction 
236   * @param i the instruction value 
237   */
238 bool InstrucIter::isAIndirectJumpInstruction()
239 {
240   const instruction i = getInstruction();
241   return isInsnType(i, JRmask, JRmatch) && !isReturnInsn(i);
242 }
243
244 /** is the instruction a conditional branch instruction 
245   * @param i the instruction value 
246   */ 
247 bool InstrucIter::isACondBranchInstruction()
248 {
249   const instruction i = getInstruction();
250
251   BranchInfo bi;
252
253   if (getBranchInfo(i, bi)) {
254     if (!bi.isCall && bi.isConditional)
255       return true;
256   }
257   
258   return false;
259 }
260
261 /** is the instruction an unconditional branch instruction 
262   * @param i the instruction value 
263   */
264 bool InstrucIter::isAJumpInstruction()
265 {
266   const instruction i = getInstruction();
267
268   BranchInfo bi;
269
270   if (getBranchInfo(i, bi)) {
271     if (!bi.isCall && !bi.isIndirect && !bi.isConditional) {
272       return true;
273     }
274   }
275   
276   return false;
277 }
278
279 /** is the instruction a call instruction 
280   * @param i the instruction value 
281   */
282 bool InstrucIter::isACallInstruction()
283 {
284   const instruction i = getInstruction();
285
286   if (isCallInsn(i)) {
287     return true;
288   } else if (i.decode.op == REGIMMop) {
289     if (i.regimm.opr == BGEZALopr ||
290         i.regimm.opr == BGEZALLopr ||
291         i.regimm.opr == BLTZALopr ||
292         i.regimm.opr == BLTZALLopr) {
293       fprintf(stderr, "Conditional branch and link found!!!\n");
294       return true;
295     }
296   }
297   return false;
298 }
299
300 bool InstrucIter::isAnneal()
301 {
302   return false;
303 }
304
305 /** function which returns the target address of control transfer instructions
306   * @param i the instruction value 
307   * @param pos the address of the instruction
308   */
309 Address InstrucIter::getBranchTargetAddress(Address pos)
310 {
311   const instruction i = getInstruction();
312
313   /* XXX Can we assume that the instruction is a branch or jump? */
314   Address delaySlot = pos + INSN_SIZE;
315   if (isInsnType(i, Jmask, Jmatch) ||
316       isInsnType(i, JALmask, JALmatch)) {
317     Address hi = delaySlot & REGION_NUM_MASK;
318     Address lo = (i.jtype.imm26 << 2) & REGION_OFF_MASK;
319     return hi | lo;
320   } else {
321     /* All others are branches. */
322     return delaySlot + (i.itype.simm16 << 2);
323   }
324 }
325
326 void initOpCodeInfo()
327 {
328 }
329
330 /* NOT yet implemented. */
331 BPatch_memoryAccess InstrucIter::isLoadOrStore()
332 {
333   return BPatch_memoryAccess::none;
334 }
335
336 /* find branches starting at the given address
337  * @param ah the starting address for the search
338  */
339 void InstrucIter::getMultipleJumpTargets(BPatch_Set<Address>& result){
340     /*
341      * We need to look for series of instructions:
342      * 1. Calculate some offset into a table
343      * 2. lw R1, X(R2), or ld R1, X(R2)
344      * 3. jr R1 (this should be ah ah-1)
345      */
346     InstrucIter ah = *this;
347
348     Address origAddr = *ah;
349
350     assert(ah.hasPrev() && isInsnType(ah.getPrevInstruction(),JRmask,JRmatch));
351
352     ah--;
353
354 #ifdef DEBUG_FINDTARGET_2
355         printf("** Checking indirect jump at 0x%p.\n",
356                 (void *)origAddr);
357 #endif
358
359     /* Get register used in JR instruction. */
360     instruction i = ah.getInstruction();
361
362     int jumpReg = i.rtype.rs;
363
364 #ifdef DEBUG_FINDTARGET_2
365     printf("jumpReg = %s ($%d)\n", reg_names_book[jumpReg], jumpReg);
366 #endif
367
368     int jumpSrcReg    = -1;
369 #ifdef DEBUG_FINDTARGET
370     int jumpSrcOffset = 0;
371 #endif
372
373     /* Get table load. */
374     while (ah.hasPrev()) {
375         ah--;
376
377         i = ah.getInstruction();
378
379         if ((isInsnType(i, LWmask, LWmatch) || 
380              isInsnType(i, LDmask, LDmatch)) &&
381             i.itype.rt == jumpReg) {
382             jumpSrcReg = i.itype.rs;
383 #ifdef DEBUG_FINDTARGET
384             jumpSrcOffset = i.itype.simm16;
385 #endif
386             break;
387         }
388     }
389
390     if (jumpSrcReg == -1) {
391 #ifdef DEBUG_FINDTARGET
392         printf("** Can't find possible targets for indirect jump at 0x%p!\n",
393                 (void *)origAddr);
394         printf("   There was no lw or ld instruction before jump.\n");
395 #endif
396         return;
397     }
398
399 #ifdef DEBUG_FINDTARGET_2
400     printf("Jump source register: %s ($%d)\n",
401             reg_names_book[jumpSrcReg], jumpSrcReg);
402     printf("  Jump source offset: %d\n", jumpSrcOffset);
403 #endif
404
405     unsigned int regMask = 1 << jumpSrcReg;
406
407     int baseReg = -1;
408     int baseOffset;
409     Address baseLoadAddr;
410
411     int tmpReg;
412
413     BPatch_Set<int> stackLocations;
414
415     while (ah.hasPrev()) {
416         ah--;
417
418         i = ah.getInstruction();
419
420 #ifdef DEBUG_FINDTARGET_2
421         dis(&i, (void *)(*ah), 1,  "  ", stdout);
422 #endif
423
424         if ((isInsnType(i, LWmask, LWmatch) || 
425              isInsnType(i, LDmask, LDmatch)) &&
426             ((regMask & (1 << i.itype.rt)) != 0) &&
427             ((i.itype.rs == REG_GP) ||
428              (i.itype.rs == REG_AT && i.itype.rt != REG_AT))) {
429 #ifdef DEBUG_FINDTARGET_2
430             if (i.itype.rs == REG_GP)
431                 printf("Load from GP");
432             else if (i.itype.rs == REG_AT)
433                 printf("Load from AT");
434             else
435                 printf("Load from ??");
436             printf(" at 0x%p\n", *ah);
437 #endif
438             baseReg      = i.itype.rt;
439             baseOffset   = i.itype.simm16;
440             baseLoadAddr = *ah;
441
442             if (i.itype.rs == REG_GP)
443                 break;
444         } else if ((isInsnType(i, LWmask, LWmatch) || 
445                     isInsnType(i, LDmask, LDmatch)) &&
446                    ((regMask & (1 << i.itype.rt)) != 0) &&
447                    (i.itype.rs == REG_SP)) {
448 #ifdef DEBUG_FINDTARGET_2
449             printf("0x%08p: Removing %s ($%d) from set,\n",
450                     *ah, reg_names_book[i.itype.rt], i.itype.rt);
451             printf("  and adding stack location %d\n", (int)i.itype.simm16);
452 #endif
453             stackLocations.insert(i.itype.simm16);
454             regMask &= ~(1 << (i.itype.rt));
455         } else if ((isInsnType(i, SWmask, SWmatch) || 
456                     isInsnType(i, SDmask, SDmatch)) &&
457                    (i.itype.rs == REG_SP) &&
458                    (stackLocations.contains(i.itype.simm16))) {
459 #ifdef DEBUG_FINDTARGET_2
460             printf("0x%08p: Adding %s ($%d) to set,\n",
461                     *ah, reg_names_book[i.itype.rt], i.itype.rt);
462             printf("  and removing stack location %d\n", (int)i.itype.simm16);
463 #endif
464             stackLocations.remove(i.itype.simm16);
465             regMask |= 1 << i.rtype.rt;
466         } else if ((isInsnType(i, ADDmask, ADDmatch) ||
467                     isInsnType(i, ADDUmask, ADDUmatch) ||
468                     isInsnType(i, DADDmask, DADDmatch) ||
469                     isInsnType(i, DADDUmask, DADDUmatch)) &&
470                    ((regMask & (1 << i.rtype.rd)) != 0)) {
471 #ifdef DEBUG_FINDTARGET_2
472             printf("0x%08p: Adding %s ($%d) and %s ($%d) to set.\n",
473                     *ah,
474                     reg_names_book[i.itype.rs], i.itype.rs,
475                     reg_names_book[i.itype.rt], i.rtype.rt);
476 #endif
477             regMask |= (1 << i.rtype.rs) | (1 << i.rtype.rt);
478         } else if (modifies_greg(i, tmpReg) &&
479                    !isInsnType(i, ADDIUmask, ADDIUmatch) &&
480                    !isInsnType(i, DADDIUmask, DADDIUmatch)) {
481 #ifdef DEBUG_FINDTARGET_2
482             printf("0x%08p: Removing %s ($%d) from set.\n",
483                     *ah, reg_names_book[tmpReg], tmpReg);
484 #endif
485             regMask &= ~(1 << tmpReg);
486         }
487     }
488
489     if (baseReg == -1) {
490 #ifdef DEBUG_FINDTARGET
491         printf("** Can't find possible targets for indirect jump at 0x%p!\n",
492                 (void *)origAddr);
493         printf("   Couldn't find load relative to GP or AT.\n");
494 #endif
495 #ifdef DEBUG_FINDTARGET_2
496         exit(1);
497 #endif
498         return;
499     }
500
501 #ifdef DEBUG_FINDTARGET_2
502     printf("        Base register is: %s ($%d)\n", 
503             reg_names_book[baseReg], baseReg);
504 #endif
505
506     ah.setCurrentAddress(baseLoadAddr);
507
508     int offset = 0;
509
510     while (ah.hasMore() && (*ah) < origAddr) {
511         ah++;
512
513         i = ah.getInstruction();
514
515         if ((isInsnType(i, ADDIUmask, ADDIUmatch) || 
516              isInsnType(i, DADDIUmask, DADDIUmatch)) &&
517             i.itype.rs == baseReg) {
518             offset += i.itype.simm16;
519         }
520     }
521
522 #ifdef DEBUG_FINDTARGET_2
523     printf("               Offset is: %d\n", offset);
524 #endif
525
526     const Object &elf = ah.getImage()->getObject();
527     bool is_elf64 = 
528 #ifndef mips_unknown_ce2_11 //ccw 10 apr 2001
529         elf.is_elf64();
530 #else
531         false;
532 #endif
533
534     Address addr = elf.get_gp_value() + baseOffset;
535
536     if (is_elf64) addr = get_dword(elf, addr);
537     else addr = get_word(elf, addr);
538
539     addr += offset;
540     addr += elf.get_base_addr();
541
542 #ifdef DEBUG_FINDTARGET_2
543     printf("Address of table is: 0x%p\n", (void *)addr);
544 #endif
545
546     for (;;) {
547         Address target;
548         if (is_elf64) {
549             target = get_dword(elf, addr);
550             addr += 8;
551         } else {
552             target = get_word(elf, addr);
553             addr += 4;
554         }
555         if (!ah.containsAddress(target)) {
556 #ifdef DEBUG_FINDTARGET_2
557             printf("Not an entry: 0x%p\n", (void *)target);
558 #endif
559             break;
560         }
561 #ifdef DEBUG_FINDTARGET_2
562         printf("Entry: 0x%p\n", (void *)target);
563 #endif
564         result += target;
565     }
566
567 #if DEBUG_FINDTARGET
568     if (result.size() == 0) {
569         printf("** Can't find possible targets for indirect jump at 0x%p!\n",
570                 (void *)origAddr);
571 #ifdef DEBUG_FINDTARGET_2
572         exit(1);
573 #endif
574     } else if (result.size() == 1) {
575         printf("** Found only one entry in table for indirect jump at 0x%p!\n",
576                 (void *)origAddr);
577 #ifdef DEBUG_FINDTARGET_2
578         exit(1);
579 #endif
580     }
581 #endif
582 }
583
584
585 bool InstrucIter::delayInstructionSupported(){
586     return true;
587 }
588 bool InstrucIter::hasMore(){
589     if((currentAddress < (baseAddress + range )) &&
590        (currentAddress >= baseAddress))
591         return true;
592     return false;
593 }
594 bool InstrucIter::hasPrev(){
595     if((currentAddress < (baseAddress + range )) &&
596        (currentAddress > baseAddress))
597         return true;
598     return false;
599 }
600 Address InstrucIter::prevAddress(){
601     Address ret = currentAddress-sizeof(instruction);
602     return ret;
603 }
604 Address InstrucIter::nextAddress(){
605     Address ret = currentAddress + sizeof(instruction);
606     return ret;
607 }
608 void InstrucIter::setCurrentAddress(Address addr){
609     currentAddress = addr;
610 }
611 instruction InstrucIter::getInstruction(){
612     instruction ret;
613     ret.raw = addressImage->get_instruction(currentAddress);
614     return ret;
615 }
616 instruction InstrucIter::getNextInstruction(){
617     instruction ret;
618     ret.raw = addressImage->get_instruction(currentAddress+sizeof(instruction));
619     return ret;
620 }
621 instruction InstrucIter::getPrevInstruction(){
622     instruction ret;
623     ret.raw = addressImage->get_instruction(currentAddress-sizeof(instruction));
624     return ret;
625 }
626 Address InstrucIter::operator++(){
627     currentAddress += sizeof(instruction);
628     return currentAddress;
629 }
630 Address InstrucIter::operator--(){
631     currentAddress -= sizeof(instruction);
632     return currentAddress;
633 }
634 Address InstrucIter::operator++(int){
635     Address ret = currentAddress;
636     currentAddress += sizeof(instruction);
637     return ret;
638 }
639 Address InstrucIter::operator--(int){
640     Address ret = currentAddress;
641     currentAddress -= sizeof(instruction);
642     return ret;
643 }
644 Address InstrucIter::operator*(){
645     return currentAddress;
646 }