changes made for CFG for alpha architecture and
[dyninst.git] / dyninstAPI / src / AddressHandle-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 "AddressHandle.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 isAReturnInstruction(const instruction i){
230     return isReturnInsn(i);
231 }
232
233 /** is the instruction an indirect jump instruction 
234   * @param i the instruction value 
235   */
236 bool isAIndirectJumpInstruction(const instruction i){
237     return isInsnType(i, JRmask, JRmatch) && !isReturnInsn(i);
238 }
239
240 /** is the instruction a conditional branch instruction 
241   * @param i the instruction value 
242   */ 
243 bool isACondBranchInstruction(const instruction i){
244     BranchInfo bi;
245
246     if (getBranchInfo(i, bi)) {
247         if (!bi.isCall && bi.isConditional)
248             return true;
249     }
250
251     return false;
252 }
253
254 /** is the instruction an unconditional branch instruction 
255   * @param i the instruction value 
256   */
257 bool isAJumpInstruction(const instruction i){
258     BranchInfo bi;
259
260     if (getBranchInfo(i, bi)) {
261         if (!bi.isCall && !bi.isIndirect && !bi.isConditional) {
262             return true;
263         }
264     }
265
266     return false;
267 }
268
269 /** is the instruction a call instruction 
270   * @param i the instruction value 
271   */
272 bool isACallInstruction(const instruction i){
273     if (isCallInsn(i)) {
274         return true;
275     } else if (i.decode.op == REGIMMop) {
276         if (i.regimm.opr == BGEZALopr ||
277             i.regimm.opr == BGEZALLopr ||
278             i.regimm.opr == BLTZALopr ||
279             i.regimm.opr == BLTZALLopr) {
280 fprintf(stderr, "Conditional branch and link found!!!\n");
281             return true;
282         }
283     }
284     return false;
285 }
286
287 /** function which returns the target address of control transfer instructions
288   * @param i the instruction value 
289   * @param pos the address of the instruction
290   */
291 Address getBranchTargetAddress(const instruction i,Address pos){
292     /* XXX Can we assume that the instruction is a branch or jump? */
293     Address delaySlot = pos + INSN_SIZE;
294     if (isInsnType(i, Jmask, Jmatch) ||
295         isInsnType(i, JALmask, JALmatch)) {
296         Address hi = delaySlot & REGION_NUM_MASK;
297         Address lo = (i.jtype.imm26 << 2) & REGION_OFF_MASK;
298         return hi | lo;
299     } else {
300         /* All others are branches. */
301         return delaySlot + (i.itype.simm16 << 2);
302     }
303 }
304
305 /* find branches starting at the given address
306  * @param ah the starting address for the search
307  */
308 void AddressHandle::getMultipleJumpTargets(BPatch_Set<Address>& result){
309     /*
310      * We need to look for series of instructions:
311      * 1. Calculate some offset into a table
312      * 2. lw R1, X(R2), or ld R1, X(R2)
313      * 3. jr R1 (this should be ah ah-1)
314      */
315     AddressHandle ah = *this;
316
317     Address origAddr = *ah;
318
319     assert(ah.hasPrev() && isInsnType(ah.getPrevInstruction(),JRmask,JRmatch));
320
321     ah--;
322
323 #ifdef DEBUG_FINDTARGET_2
324         printf("** Checking indirect jump at 0x%p.\n",
325                 (void *)origAddr);
326 #endif
327
328     /* Get register used in JR instruction. */
329     instruction i = ah.getInstruction();
330
331     int jumpReg = i.rtype.rs;
332
333 #ifdef DEBUG_FINDTARGET_2
334     printf("jumpReg = %s ($%d)\n", reg_names_book[jumpReg], jumpReg);
335 #endif
336
337     int jumpSrcReg    = -1;
338 #ifdef DEBUG_FINDTARGET
339     int jumpSrcOffset = 0;
340 #endif
341
342     /* Get table load. */
343     while (ah.hasPrev()) {
344         ah--;
345
346         i = ah.getInstruction();
347
348         if ((isInsnType(i, LWmask, LWmatch) || 
349              isInsnType(i, LDmask, LDmatch)) &&
350             i.itype.rt == jumpReg) {
351             jumpSrcReg = i.itype.rs;
352 #ifdef DEBUG_FINDTARGET
353             jumpSrcOffset = i.itype.simm16;
354 #endif
355             break;
356         }
357     }
358
359     if (jumpSrcReg == -1) {
360 #ifdef DEBUG_FINDTARGET
361         printf("** Can't find possible targets for indirect jump at 0x%p!\n",
362                 (void *)origAddr);
363         printf("   There was no lw or ld instruction before jump.\n");
364 #endif
365         return;
366     }
367
368 #ifdef DEBUG_FINDTARGET_2
369     printf("Jump source register: %s ($%d)\n",
370             reg_names_book[jumpSrcReg], jumpSrcReg);
371     printf("  Jump source offset: %d\n", jumpSrcOffset);
372 #endif
373
374     unsigned int regMask = 1 << jumpSrcReg;
375
376     int baseReg = -1;
377     int baseOffset;
378     Address baseLoadAddr;
379
380     int tmpReg;
381
382     BPatch_Set<int> stackLocations;
383
384     while (ah.hasPrev()) {
385         ah--;
386
387         i = ah.getInstruction();
388
389 #ifdef DEBUG_FINDTARGET_2
390         dis(&i, (void *)(*ah), 1,  "  ", stdout);
391 #endif
392
393         if ((isInsnType(i, LWmask, LWmatch) || 
394              isInsnType(i, LDmask, LDmatch)) &&
395             ((regMask & (1 << i.itype.rt)) != 0) &&
396             ((i.itype.rs == REG_GP) ||
397              (i.itype.rs == REG_AT && i.itype.rt != REG_AT))) {
398 #ifdef DEBUG_FINDTARGET_2
399             if (i.itype.rs == REG_GP)
400                 printf("Load from GP");
401             else if (i.itype.rs == REG_AT)
402                 printf("Load from AT");
403             else
404                 printf("Load from ??");
405             printf(" at 0x%p\n", *ah);
406 #endif
407             baseReg      = i.itype.rt;
408             baseOffset   = i.itype.simm16;
409             baseLoadAddr = *ah;
410
411             if (i.itype.rs == REG_GP)
412                 break;
413         } else if ((isInsnType(i, LWmask, LWmatch) || 
414                     isInsnType(i, LDmask, LDmatch)) &&
415                    ((regMask & (1 << i.itype.rt)) != 0) &&
416                    (i.itype.rs == REG_SP)) {
417 #ifdef DEBUG_FINDTARGET_2
418             printf("0x%08p: Removing %s ($%d) from set,\n",
419                     *ah, reg_names_book[i.itype.rt], i.itype.rt);
420             printf("  and adding stack location %d\n", (int)i.itype.simm16);
421 #endif
422             stackLocations.insert(i.itype.simm16);
423             regMask &= ~(1 << (i.itype.rt));
424         } else if ((isInsnType(i, SWmask, SWmatch) || 
425                     isInsnType(i, SDmask, SDmatch)) &&
426                    (i.itype.rs == REG_SP) &&
427                    (stackLocations.contains(i.itype.simm16))) {
428 #ifdef DEBUG_FINDTARGET_2
429             printf("0x%08p: Adding %s ($%d) to set,\n",
430                     *ah, reg_names_book[i.itype.rt], i.itype.rt);
431             printf("  and removing stack location %d\n", (int)i.itype.simm16);
432 #endif
433             stackLocations.remove(i.itype.simm16);
434             regMask |= 1 << i.rtype.rt;
435         } else if ((isInsnType(i, ADDmask, ADDmatch) ||
436                     isInsnType(i, ADDUmask, ADDUmatch) ||
437                     isInsnType(i, DADDmask, DADDmatch) ||
438                     isInsnType(i, DADDUmask, DADDUmatch)) &&
439                    ((regMask & (1 << i.rtype.rd)) != 0)) {
440 #ifdef DEBUG_FINDTARGET_2
441             printf("0x%08p: Adding %s ($%d) and %s ($%d) to set.\n",
442                     *ah,
443                     reg_names_book[i.itype.rs], i.itype.rs,
444                     reg_names_book[i.itype.rt], i.rtype.rt);
445 #endif
446             regMask |= (1 << i.rtype.rs) | (1 << i.rtype.rt);
447         } else if (modifies_greg(i, tmpReg) &&
448                    !isInsnType(i, ADDIUmask, ADDIUmatch) &&
449                    !isInsnType(i, DADDIUmask, DADDIUmatch)) {
450 #ifdef DEBUG_FINDTARGET_2
451             printf("0x%08p: Removing %s ($%d) from set.\n",
452                     *ah, reg_names_book[tmpReg], tmpReg);
453 #endif
454             regMask &= ~(1 << tmpReg);
455         }
456     }
457
458     if (baseReg == -1) {
459 #ifdef DEBUG_FINDTARGET
460         printf("** Can't find possible targets for indirect jump at 0x%p!\n",
461                 (void *)origAddr);
462         printf("   Couldn't find load relative to GP or AT.\n");
463 #endif
464 #ifdef DEBUG_FINDTARGET_2
465         exit(1);
466 #endif
467         return;
468     }
469
470 #ifdef DEBUG_FINDTARGET_2
471     printf("        Base register is: %s ($%d)\n", 
472             reg_names_book[baseReg], baseReg);
473 #endif
474
475     ah.setCurrentAddress(baseLoadAddr);
476
477     int offset = 0;
478
479     while (ah.hasMore() && (*ah) < origAddr) {
480         ah++;
481
482         i = ah.getInstruction();
483
484         if ((isInsnType(i, ADDIUmask, ADDIUmatch) || 
485              isInsnType(i, DADDIUmask, DADDIUmatch)) &&
486             i.itype.rs == baseReg) {
487             offset += i.itype.simm16;
488         }
489     }
490
491 #ifdef DEBUG_FINDTARGET_2
492     printf("               Offset is: %d\n", offset);
493 #endif
494
495     const Object &elf = ah.getImage()->getObject();
496     bool is_elf64 = elf.is_elf64();
497
498     Address addr = elf.get_gp_value() + baseOffset;
499
500     if (is_elf64) addr = get_dword(elf, addr);
501     else addr = get_word(elf, addr);
502
503     addr += offset;
504     addr += elf.get_base_addr();
505
506 #ifdef DEBUG_FINDTARGET_2
507     printf("Address of table is: 0x%p\n", (void *)addr);
508 #endif
509
510     for (;;) {
511         Address target;
512         if (is_elf64) {
513             target = get_dword(elf, addr);
514             addr += 8;
515         } else {
516             target = get_word(elf, addr);
517             addr += 4;
518         }
519         if (!ah.containsAddress(target)) {
520 #ifdef DEBUG_FINDTARGET_2
521             printf("Not an entry: 0x%p\n", (void *)target);
522 #endif
523             break;
524         }
525 #ifdef DEBUG_FINDTARGET_2
526         printf("Entry: 0x%p\n", (void *)target);
527 #endif
528         result += target;
529     }
530
531 #if DEBUG_FINDTARGET
532     if (result.size() == 0) {
533         printf("** Can't find possible targets for indirect jump at 0x%p!\n",
534                 (void *)origAddr);
535 #ifdef DEBUG_FINDTARGET_2
536         exit(1);
537 #endif
538     } else if (result.size() == 1) {
539         printf("** Found only one entry in table for indirect jump at 0x%p!\n",
540                 (void *)origAddr);
541 #ifdef DEBUG_FINDTARGET_2
542         exit(1);
543 #endif
544     }
545 #endif
546 }
547
548 //Address Handle used by flowGraph which wraps the instructions
549 //and supply enough operation to iterate over the instrcution sequence.
550
551 AddressHandle::AddressHandle(process* fProcess,
552                              Address bAddress,
553                              unsigned fSize)
554         : addressProc(fProcess),
555           addressImage(fProcess->getImage()),baseAddress(bAddress),
556           range(fSize),currentAddress(bAddress) {}
557
558 AddressHandle::AddressHandle(Address cAddress,process* fProcess,
559                              Address bAddress,
560                              unsigned fSize)
561         : addressProc(fProcess),
562           addressImage(fProcess->getImage()),baseAddress(bAddress),
563           range(fSize),currentAddress(cAddress) {}
564
565 AddressHandle::AddressHandle(const AddressHandle& ah){
566         addressImage = ah.addressImage;
567         addressProc = ah.addressProc;
568         baseAddress = ah.baseAddress;
569         currentAddress = ah.currentAddress;
570         range = ah.range;
571 }
572
573 bool AddressHandle::delayInstructionSupported(){
574     return true;
575 }
576 bool AddressHandle::hasMore(){
577     if((currentAddress < (baseAddress + range )) &&
578        (currentAddress >= baseAddress))
579         return true;
580     return false;
581 }
582 bool AddressHandle::hasPrev(){
583     if((currentAddress < (baseAddress + range )) &&
584        (currentAddress > baseAddress))
585         return true;
586     return false;
587 }
588 Address AddressHandle::prevAddress(){
589     Address ret = currentAddress-sizeof(instruction);
590     return ret;
591 }
592 Address AddressHandle::prevAddressOf(Address addr){
593     Address ret = addr - sizeof(instruction);
594     return ret;
595 }
596 Address AddressHandle::nextAddress(){
597     Address ret = currentAddress + sizeof(instruction);
598     return ret;
599 }
600 Address AddressHandle::nextAddressOf(Address addr){
601     Address ret = addr + sizeof(instruction);
602     return ret;
603 }
604 void AddressHandle::setCurrentAddress(Address addr){
605     currentAddress = addr;
606 }
607 unsigned AddressHandle::getInstructionCount(){
608     return range / sizeof(Word);
609 }
610 instruction AddressHandle::getInstruction(){
611     instruction ret;
612     ret.raw = addressImage->get_instruction(currentAddress);
613     return ret;
614 }
615 instruction AddressHandle::getNextInstruction(){
616     instruction ret;
617     ret.raw = addressImage->get_instruction(currentAddress+sizeof(instruction));
618     return ret;
619 }
620 instruction AddressHandle::getPrevInstruction(){
621     instruction ret;
622     ret.raw = addressImage->get_instruction(currentAddress-sizeof(instruction));
623     return ret;
624 }
625 Address AddressHandle::operator++(){
626     currentAddress += sizeof(instruction);
627     return currentAddress;
628 }
629 Address AddressHandle::operator--(){
630     currentAddress -= sizeof(instruction);
631     return currentAddress;
632 }
633 Address AddressHandle::operator++(int){
634     Address ret = currentAddress;
635     currentAddress += sizeof(instruction);
636     return ret;
637 }
638 Address AddressHandle::operator--(int){
639     Address ret = currentAddress;
640     currentAddress -= sizeof(instruction);
641     return ret;
642 }
643 Address AddressHandle::operator*(){
644     return currentAddress;
645 }