*** empty log message ***
[dyninst.git] / dyninstAPI / src / inst-x86.C
1 /*
2  * Copyright (c) 1996 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 /*
43  * inst-x86.C - x86 dependent functions and code generator
44  *
45  * $Log: inst-x86.C,v $
46  * Revision 1.29  1997/11/26 21:44:48  mcheyney
47  * *** empty log message ***
48  *
49  * Revision 1.28  1997/10/28 20:24:16  tamches
50  * changed entry to the_entry to avoid a conflict
51  *
52  * Revision 1.27  1997/09/28 22:22:31  buck
53  * Added some more #ifdef BPATCH_LIBRARYs to eliminate some Dyninst API
54  * library dependencies on files in rtinst.
55  *
56  * Revision 1.26  1997/08/19 19:50:38  naim
57  * Adding support to dynamically link libdyninstRT by using dlopen on sparc-
58  * solaris - naim
59  *
60  * Revision 1.25  1997/08/18 01:34:23  buck
61  * Ported the Dyninst API to Windows NT.
62  *
63  * Revision 1.1.1.5  1997/07/08 20:02:44  buck
64  * Bring latest changes from Wisconsin over to Maryland repository.
65  *
66  * Revision 1.24  1997/07/08 19:15:13  buck
67  * Added support for the x86 Solaris platform and dynamically linked
68  * executables to the dyninst API library.
69  *
70  * Revision 1.23  1997/06/23 17:09:29  tamches
71  * include of instPoint.h is new
72  *
73  * Revision 1.22  1997/06/14 18:27:48  ssuen
74  * Moved class instPoint from inst-x86.C to inst-x86.h and added/moved the following
75  * standard definitions to the public section
76  *
77  *   Address addr_;
78  *   pd_Function *func_;
79  *   pd_Function *callee_;
80  *
81  *   function_base *iPgetFunction() const { ... }
82  *   function_base *iPgetCallee()   const { ... }
83  *   const image   *iPgetOwner()    const { ... }
84  *   Address        iPgetAddress()  const { ... }
85  *
86  * Revision 1.21  1997/06/06 18:27:15  mjrg
87  * Changed checkCallPoints to keep calls to shared object functions in the
88  * list of calls for a function
89  *
90  * Revision 1.20  1997/06/04 13:24:24  naim
91  * Removing debugging info - naim
92  *
93  * Revision 1.19  1997/05/23 23:01:26  mjrg
94  * Windows NT port
95  * bug fix to inst-x86.C
96  *
97  * Revision 1.18  1997/05/16 22:02:27  mjrg
98  * Fixed problem with instrumentation of conditional jumps
99  *
100  * Revision 1.17  1997/05/07 19:03:12  naim
101  * Getting rid of old support for threads and turning it off until the new
102  * version is finished. Additionally, new superTable, baseTable and superVector
103  * classes for future support of multiple threads. The fastInferiorHeap class has
104  * also changed - naim
105  *
106  * Revision 1.16  1997/05/02 18:25:36  mjrg
107  * Changes for allowing different main functions on different platforms
108  *
109  * Revision 1.15  1997/04/29 23:16:02  mjrg
110  * Changes for WindowsNT port
111  * Delayed check for DYNINST symbols to allow linking libdyninst dynamically
112  * Changed way paradyn and paradynd generate resource ids
113  * Changes to instPoint class in inst-x86.C to reduce size of objects
114  * Added initialization for process->threads to fork and attach constructors
115  *
116  * Revision 1.14  1997/04/14 00:22:07  newhall
117  * removed class pdFunction and replaced it with base class function_base and
118  * derived class pd_Function
119  *
120  * Revision 1.13  1997/02/26 23:42:52  mjrg
121  * First part on WindowsNT port: changes for compiling with Visual C++;
122  * moved unix specific code to unix.C
123  *
124  * Revision 1.12  1997/02/21 20:13:38  naim
125  * Moving files from paradynd to dyninstAPI + moving references to dataReqNode
126  * out of the ast class. The is the first pre-dyninstAPI commit! - naim
127  *
128  * Revision 1.11  1997/02/03 17:20:55  lzheng
129  * Changes made for combining the long jump and short jump on solaris platform
130  *
131  * Revision 1.10  1997/01/30 18:19:27  tamches
132  * emitInferiorRPCtrailer revamped; can now stop to read the result value of
133  * an inferiorRPC
134  *
135  * Revision 1.9  1997/01/27 19:40:57  naim
136  * Part of the base instrumentation for supporting multithreaded applications
137  * (vectors of counter/timers) implemented for all current platforms +
138  * different bug fixes - naim
139  *
140  * Revision 1.8  1997/01/21 23:58:53  mjrg
141  * Moved allocation of virtual registers to basetramp and fix to
142  * emitInferiorRPCheader to allocate virtual registers
143  *
144  * Revision 1.7  1997/01/21 00:27:58  tamches
145  * removed uses of DYNINSTglobalData
146  *
147  * Revision 1.6  1996/11/26 16:08:08  naim
148  * Fixing asserts - naim
149  *
150  * Revision 1.5  1996/11/19 16:28:04  newhall
151  * Fix to stack walking on Solaris: find leaf functions in stack (these can occur
152  * on top of stack or in middle of stack if the signal handler is on the stack)
153  * Fix to relocated functions: new instrumentation points are kept on a per
154  * process basis.  Cleaned up some of the code.
155  *
156  * Revision 1.4  1996/11/14 14:27:09  naim
157  * Changing AstNodes back to pointers to improve performance - naim
158  *
159  * Revision 1.3  1996/11/12 17:48:28  mjrg
160  * Moved the computation of cost to the basetramp in the x86 platform,
161  * and changed other platform to keep code consistent.
162  * Removed warnings, and made changes for compiling with Visual C++
163  *
164  * Revision 1.2  1996/10/31 08:51:09  tamches
165  * the shm-sampling commit; routines to implement inferiorRPC; removed some
166  * warnings; added noCost param to some fns.
167  *
168  * Revision 1.1  1996/10/18 23:54:14  mjrg
169  * Solaris/X86 port
170  *
171  *
172  *
173  */
174
175 #include <limits.h>
176 #include "util/h/headers.h"
177
178 #ifndef BPATCH_LIBRARY
179 #include "rtinst/h/rtinst.h"
180 #endif
181 #include "util/h/Dictionary.h"
182 #include "dyninstAPI/src/symtab.h"
183 #include "dyninstAPI/src/process.h"
184 #include "dyninstAPI/src/inst.h"
185 #include "dyninstAPI/src/instP.h"
186 #include "dyninstAPI/src/ast.h"
187 #include "dyninstAPI/src/util.h"
188 #include "dyninstAPI/src/stats.h"
189 #include "dyninstAPI/src/os.h"
190 #include "paradynd/src/showerror.h"
191
192 #include "dyninstAPI/src/arch-x86.h"
193 #include "dyninstAPI/src/inst-x86.h"
194 #include "dyninstAPI/src/instPoint.h" // includes instPoint-x86.h
195 #include "dyninstAPI/src/instP.h" // class returnInstance
196
197 extern bool isPowerOf2(int value, int &result);
198
199 // The general machine registers. 
200 // These values are taken from the Pentium manual and CANNOT be changed.
201 #define EAX (0)
202 #define ECX (1)
203 #define EDX (2)
204 #define EBX (3)
205 #define ESP (4)
206 #define EBP (5)
207 #define ESI (6)
208 #define EDI (7)
209
210 // Size of a jump rel32 instruction
211 #define JUMP_REL32_SZ (5)
212 #define JUMP_SZ (5)
213 // Size of a call rel32 instruction
214 #define CALL_REL32_SZ (5)
215
216 #define PUSH_RM_OPC1 (0xFF)
217 #define PUSH_RM_OPC2 (6)
218 #define CALL_RM_OPC1 (0xFF)
219 #define CALL_RM_OPC2 (2)
220 #define PUSH_EBP (0x50+EBP)
221 #define SUB_REG_IMM32 (5)
222 #define LEAVE (0xC9)
223
224 /*
225    Function arguments are in the stack and are addressed with a displacement
226    from EBP. EBP points to the saved EBP, EBP+4 is the saved return address,
227    EBP+8 is the first parameter.
228    TODO: what about far calls?
229  */
230
231 #define PARAM_OFFSET (8)
232
233
234 // number of virtual registers
235 #define NUM_VIRTUAL_REGISTERS (32)
236
237 // offset from EBP of the saved EAX for a tramp
238 #define SAVED_EAX_OFFSET (-NUM_VIRTUAL_REGISTERS*4-4)
239
240
241
242
243 /*
244    checkInstructions: check that there are no known jumps to the instructions
245    before and after the point.
246 */
247 void instPoint::checkInstructions() {
248   unsigned currAddr = addr_;
249   unsigned OKinsns = 0;
250
251   // if jumpAddr_ is not zero, this point has been checked already
252   if (jumpAddr_) 
253     return;
254
255   unsigned tSize;
256   unsigned maxSize = JUMP_SZ;
257   if (address() == func()->getAddress(0)) // entry point
258     maxSize = 2*JUMP_SZ;
259   tSize = insnAtPoint_.size();
260
261   if (!owner()->isJumpTarget(currAddr)) {
262     // check instructions before point
263     unsigned insnsBefore_ = insnsBefore();
264     for (unsigned u = 0; u < insnsBefore_; u++) {
265       OKinsns++;
266       tSize += (*insnBeforePt_)[u].size();
267       currAddr -= (*insnBeforePt_)[u].size();
268       if (owner()->isJumpTarget(currAddr)) {
269         // must remove instruction from point
270         // fprintf(stderr, "check instructions point %x, jmp to %x\n", addr,currAddr);
271         break;
272       }
273     }
274   }
275   if (insnBeforePt_)
276     (*insnBeforePt_).resize(OKinsns);
277
278   // this is the address where we insert the jump
279   jumpAddr_ = currAddr;
280
281   // check instructions after point
282   currAddr = addr_ + insnAtPoint_.size();
283   OKinsns = 0;
284   unsigned insnsAfter_ = insnsAfter();
285   for (unsigned u = 0; tSize < maxSize && u < insnsAfter_; u++) {
286     if (owner()->isJumpTarget(currAddr))
287       break;
288     OKinsns++;
289     unsigned size = (*insnAfterPt_)[u].size();
290     currAddr += size;
291     tSize += size;
292   }
293   if (insnAfterPt_)
294     (*insnAfterPt_).resize(OKinsns);
295   
296 #ifdef notdef
297   if (tSize < maxSize) {
298     tSize = insnAtPoint_.size();
299     jumpAddr_ = addr_;
300     if (insnBeforePt_) (*insnBeforePt_).resize(0);
301     if (insnAfterPt_) (*insnAfterPt_).resize(0);
302   }
303 #endif
304 }
305
306
307 /**************************************************************
308  *
309  *  machine dependent methods of pdFunction
310  *
311  **************************************************************/
312
313 // Determine if the called function is a "library" function or a "user" function
314 // This cannot be done until all of the functions have been seen, verified, and
315 // classified
316 //
317 void pd_Function::checkCallPoints() {
318   unsigned int i;
319   instPoint *p;
320   Address loc_addr;
321
322   vector<instPoint*> non_lib;
323
324   for (i=0; i<calls.size(); ++i) {
325     /* check to see where we are calling */
326     p = calls[i];
327     assert(p);
328
329     if (!p->insnAtPoint().isCallIndir()) {
330       loc_addr = p->insnAtPoint().getTarget(p->address());
331       file()->exec()->addJumpTarget(loc_addr);
332       pd_Function *pdf = (file_->exec())->findFunction(loc_addr);
333
334       if (pdf) {
335         p->set_callee(pdf);
336         non_lib += p;
337       } else {
338            // if this is a call outside the fuction, keep it
339            if((loc_addr < getAddress(0))||(loc_addr > (getAddress(0)+size()))){
340                 non_lib += p;
341            }
342            else {
343                delete p;
344            }
345       } 
346     } else {
347       // Indirect call -- be conservative, assume it is a call to
348       // an unnamed user function
349       //assert(!p->callee());
350       p->set_callee(NULL);
351       non_lib += p;
352     }
353   }
354   calls = non_lib;
355
356 }
357
358 // this function is not needed
359 Address pd_Function::newCallPoint(Address, const instruction,
360                                  const image *, bool &)
361 { assert(0); return 0; }
362
363
364 // see if we can recognize a jump table and skip it
365 // return the size of the table in tableSz.
366 bool checkJumpTable(image *im, instruction insn, Address addr, 
367                     Address funcBegin, 
368                     Address &funcEnd,
369                     unsigned &tableSz) {
370
371   const unsigned char *instr = insn.ptr();
372   tableSz = 0;
373   /*
374      the instruction usually used for jump tables is 
375        jmp dword ptr [REG*4 + ADDR]
376      where ADDR is an immediate following the SIB byte.
377      The opcode is 0xFF and the MOD/RM byte is 0x24. 
378      The SS field (bits 7 and 6) of SIB is 2, and the
379      base ( bits 2, 1, 0) is 5. The index bits (5,4,3) 
380      select the register.
381   */
382   if (instr[0] == 0xFF && instr[1] == 0x24 &&
383       ((instr[2] & 0xC0)>>6) == 2 && (instr[2] & 0x7) == 5) {
384     const unsigned tableBase = *(const int *)(instr+3);
385     //fprintf(stderr, "Found jump table at %x %x\n",addr, tableBase);
386     // check if the table is right after the jump and inside the current function
387     if (tableBase > funcBegin && tableBase < funcEnd) {
388       // table is within function code
389       if (tableBase < addr+insn.size()) {
390         fprintf(stderr, "bad indirect jump at %x\n", addr);
391         return false;
392       } else if (tableBase > addr+insn.size()) {
393         // jump table may be at the end of the function code - adjust funcEnd
394         funcEnd = tableBase;
395         return true;
396       }
397       // skip the jump table
398       for (const unsigned *ptr = (unsigned *)tableBase; 
399            *ptr >= funcBegin && *ptr <= funcEnd; ptr++) {
400         //fprintf(stderr, " jump table entry = %x\n", *(unsigned *)ptr);
401         tableSz += sizeof(int);
402       }
403     }
404     else {
405       const unsigned char *ptr = im->getPtrToInstruction(tableBase);
406       for ( ; *(const unsigned *)ptr >= funcBegin && *(const unsigned *)ptr <= funcEnd; 
407            ptr += sizeof(unsigned)) {
408         //fprintf(stderr, " jump table entry = %x\n", *(unsigned *)ptr);
409       }
410     }
411   }
412   return true;
413 }
414
415
416 /* auxiliary data structures for function findInstPoints */
417 enum { EntryPt, CallPt, ReturnPt };
418 class point_ {
419   public:
420      point_(): point(0), index(0), type(0) {};
421      point_(instPoint *p, unsigned i, unsigned t): point(p), index(i), type(t) {};
422      instPoint *point;
423      unsigned index;
424      unsigned type;
425 };
426
427
428 bool pd_Function::findInstPoints(const image *i_owner) {
429    // sorry this this hack, but this routine can modify the image passed in,
430    // which doesn't occur on other platforms --ari
431    image *owner = (image *)i_owner; // const cast
432
433    if (size() == 0) {
434      //fprintf(stderr,"Function %s, size = %d\n", prettyName().string_of(), size());
435      return false;
436    }
437
438 // XXXXX kludge: these functions are called by DYNINSTgetCPUtime, 
439 // they can't be instrumented or we would have an infinite loop
440 if (prettyName() == "gethrvtime" || prettyName() == "_divdi3"
441     || prettyName() == "GetProcessTimes")
442   return false;
443
444    point_ *points = new point_[size()];
445    //point_ *points = (point_ *)alloca(size()*sizeof(point));
446    unsigned npoints = 0;
447
448    const unsigned char *instr = (const unsigned char *)owner->getPtrToInstruction(getAddress(0));
449    Address adr = getAddress(0);
450    unsigned numInsns = 0;
451
452    instruction insn;
453    unsigned insnSize;
454
455    // keep a buffer with all the instructions in this function
456    instruction *allInstr = new instruction[size()+5];
457    //instruction *allInstr = (instruction *)alloca((size()+5)*sizeof(instruction));
458
459    // define the entry point
460    insnSize = insn.getNextInstruction(instr);
461    instPoint *p = new instPoint(this, owner, adr, insn);
462    funcEntry_ = p;
463    points[npoints++] = point_(p, numInsns, EntryPt);
464
465    // check if the entry point contains another point
466    if (insn.isJumpDir()) {
467      Address target = insn.getTarget(adr);
468      owner->addJumpTarget(target);
469      if (target < getAddress(0) || target >= getAddress(0) + size()) {
470        // jump out of function
471        // this is an empty function
472        delete points;
473        delete allInstr;
474        return false;
475      }
476    } else if (insn.isReturn()) {
477      // this is an empty function
478      delete points;
479      delete allInstr;
480      return false;
481    } else if (insn.isCall()) {
482      // TODO: handle calls at entry point
483      // call at entry point
484      //instPoint *p = new instPoint(this, owner, adr, insn);
485      //calls += p;
486      //points[npoints++] = point_(p, numInsns, CallPt);
487      //fprintf(stderr,"Function %s, call at entry point\n", prettyName().string_of());
488      delete points;
489      delete allInstr;
490      return false;
491    }
492
493    allInstr[numInsns] = insn;
494    numInsns++;
495    instr += insnSize;
496    adr += insnSize;
497
498    // get all the instructions for this function, and define the instrumentation
499    // points. For now, we only add one instruction to each point.
500    // Additional instructions, for the points that need them, will be added later.
501
502    Address funcEnd = getAddress(0) + size();
503    for ( ; adr < funcEnd; instr += insnSize, adr += insnSize) {
504      insnSize = insn.getNextInstruction(instr);
505      assert(insnSize > 0);
506
507      if (adr + insnSize > funcEnd) {
508        break;
509      }
510
511      if (insn.isJumpIndir()) {
512        unsigned jumpTableSz;
513        // check for jump table. This may update funcEnd
514        if (!checkJumpTable(owner, insn, adr, getAddress(0), funcEnd, jumpTableSz)) {
515          delete points;
516          delete allInstr;
517          //fprintf(stderr,"Function %s, size = %d, bad jump table\n", 
518          //          prettyName().string_of(), size());
519          return false;
520        }
521        // process the jump instruction
522        allInstr[numInsns] = insn;
523        numInsns++;
524
525        if (jumpTableSz > 0) {
526          // skip the jump table
527          // insert an illegal instruction with the size of the jump table
528          insn = instruction(instr, ILLEGAL, jumpTableSz);
529        }
530
531      } else if (insn.isJumpDir()) {
532        // check for jumps out of this function
533        Address target = insn.getTarget(adr);
534        owner->addJumpTarget(target);
535        if (target < getAddress(0) || target >= getAddress(0) + size()) {
536          // jump out of function
537          instPoint *p = new instPoint(this, owner, adr, insn);
538          funcReturns += p;
539          points[npoints++] = point_(p, numInsns, ReturnPt);
540        } 
541      } else if (insn.isReturn()) {
542        instPoint *p = new instPoint(this, owner, adr, insn);
543        funcReturns += p;
544        points[npoints++] = point_(p, numInsns, ReturnPt);
545
546      } else if (insn.isCall()) {
547        // calls to adr+5 are not really calls, they are used in dynamically linked
548        // libraries to get the address of the code.
549        // We skip them here.
550        if (insn.getTarget(adr) != adr + 5) {
551          instPoint *p = new instPoint(this, owner, adr, insn);
552          calls += p;
553          points[npoints++] = point_(p, numInsns, CallPt);
554        }
555      }
556
557      allInstr[numInsns] = insn;
558      numInsns++;
559      assert(npoints < size());
560      assert(numInsns <= size());
561    }
562
563    unsigned u;
564    // there are often nops after the end of the function. We get them here,
565    // since they may be usefull to instrument the return point
566    for (u = 0; u < 4; u++) {
567      if (owner->isValidAddress(adr)) {
568        insnSize = insn.getNextInstruction(instr);
569        if (insn.isNop()) {
570          allInstr[numInsns] = insn;
571          numInsns++;
572          assert(numInsns < size()+5);
573          instr += insnSize;
574          adr += insnSize;
575        }
576        else
577          break;
578      }
579    }
580
581
582    // add extra instructions to the points that need it.
583    unsigned lastPointEnd = 0;
584    unsigned thisPointEnd = 0;
585    for (u = 0; u < npoints; u++) {
586      instPoint *p = points[u].point;
587      unsigned index = points[u].index;
588      unsigned type = points[u].type;
589      lastPointEnd = thisPointEnd;
590      thisPointEnd = index;
591
592      // add instructions before the point
593      unsigned size = p->size();
594      for (int u1 = index-1; size < JUMP_SZ && u1 >= 0 && u1 > (int)lastPointEnd; u1--) {
595        if (!allInstr[u1].isCall()) {
596          p->addInstrBeforePt(allInstr[u1]);
597          size += allInstr[u1].size();
598        } else
599          break;
600      }
601
602      lastPointEnd = index;
603      // add instructions after the point
604      if (type == ReturnPt) {
605        // normally, we would not add instructions after the return, but the 
606        // compilers often add nops after the return, and we can use them if necessary
607        for (unsigned u1 = index+1; u1 < index+JUMP_SZ-1 && u1 < numInsns; u1++) {
608          if (allInstr[u1].isNop() || *(allInstr[u1].ptr()) == 0xCC) {
609            p->addInstrAfterPt(allInstr[u1]);
610            thisPointEnd = u1;
611          }
612          else 
613            break;
614        }
615      } else {
616        size = p->size();
617        unsigned maxSize = JUMP_SZ;
618        if (type == EntryPt) maxSize = 2*JUMP_SZ;
619        for (unsigned u1 = index+1; size < maxSize && u1 <= numInsns; u1++) {
620          if (u+1 < npoints && points[u+1].index > u1 && !allInstr[u1].isCall()) {
621            p->addInstrAfterPt(allInstr[u1]);
622            size += allInstr[u1].size();
623            thisPointEnd = u1;
624          }
625          else 
626            break;
627        }
628      }
629    }
630
631    delete points;
632    delete allInstr;
633
634    return true;
635 }
636
637
638 /*
639  * Given an instruction, relocate it to a new address, patching up
640  *   any relative addressing that is present.
641  * The instruction may need to be replaced with a different size instruction
642  * or with multiple instructions.
643  * Return the size of the new instruction(s)
644  */
645 unsigned relocateInstruction(instruction insn,
646                          int origAddr, int newAddr,
647                          unsigned char *&newInsn)
648 {
649   /* 
650      Relative address instructions need to be modified. The relative address
651      can be a 8, 16, or 32-byte displacement relative to the next instruction.
652      Since we are relocating the instruction to a different area, we have
653      to replace 8 and 16-byte displacements with 32-byte displacements.
654
655      All relative address instructions are one or two-byte opcode followed
656      by a displacement relative to the next instruction:
657
658        CALL rel16 / CALL rel32
659        Jcc rel8 / Jcc rel16 / Jcc rel32
660        JMP rel8 / JMP rel16 / JMP rel32
661
662      The only two-byte opcode instructions are the Jcc rel16/rel32,
663      all others have one byte opcode.
664
665      The instruction JCXZ/JECXZ rel8 does not have an equivalent with rel32
666      displacement. We must generate code to emulate this instruction:
667      
668        JCXZ rel8
669
670      becomes
671
672        A0: JCXZ 2 (jump to A4)
673        A2: JMP 5  (jump to A9)
674        A4: JMP rel32 (relocated displacement)
675        A9: ...
676
677   */
678
679   const unsigned char *origInsn = insn.ptr();
680   unsigned insnType = insn.type();
681   unsigned insnSz = insn.size();
682   unsigned char *first = newInsn;
683
684   int oldDisp;
685   int newDisp;
686
687   if (insnType & REL_B) {
688     /* replace with rel32 instruction, opcode is one byte. */
689     if (*origInsn == JCXZ) {
690       oldDisp = (int)*(const char *)(origInsn+1);
691       newDisp = (origAddr + 2) + oldDisp - (newAddr + 9);
692       *newInsn++ = *origInsn; *(newInsn++) = 2; // jcxz 2
693       *newInsn++ = 0xEB; *newInsn++ = 5;        // jmp 5
694       *newInsn++ = 0xE9;                        // jmp rel32
695       *((int *)newInsn) = newDisp;
696       newInsn += sizeof(int);
697     }
698     else {
699       unsigned newSz;
700       if (insnType & IS_JCC) {
701         /* Change a Jcc rel8 to Jcc rel32. 
702            Must generate a new opcode: a 0x0F followed by (old opcode + 16) */
703         unsigned char opcode = *origInsn++;
704         *newInsn++ = 0x0F;
705         *newInsn++ = opcode + 0x10;
706         newSz = 6;
707       }
708       else if (insnType & IS_JUMP) {
709         /* change opcode to 0xE9 */
710         origInsn++;
711         *newInsn++ = 0xE9;
712         newSz = 5;
713       }
714       oldDisp = (int)*(const char *)origInsn;
715       newDisp = (origAddr + 2) + oldDisp - (newAddr + newSz);
716       *((int *)newInsn) = newDisp;
717       newInsn += sizeof(int);
718     }
719   }
720   else if (insnType & REL_W) {
721     /* Skip prefixes */
722     if (insnType & PREFIX_OPR)
723       origInsn++;
724     if (insnType & PREFIX_SEG)
725       origInsn++;
726     /* opcode is unchanged, just relocate the displacement */
727     if (*origInsn == (unsigned char)0x0F)
728       *newInsn++ = *origInsn++;
729     *newInsn++ = *origInsn++;
730     oldDisp = *((const short *)origInsn);
731     newDisp = (origAddr + 5) + oldDisp - (newAddr + 3);
732     *((int *)newInsn) = newDisp;
733     newInsn += sizeof(int);
734   } else if (insnType & REL_D) {
735     // Skip prefixes
736     unsigned nPrefixes = 0;
737     if (insnType & PREFIX_OPR)
738       nPrefixes++;
739     if (insnType & PREFIX_SEG)
740       nPrefixes++;
741     for (unsigned u = 0; u < nPrefixes; u++)
742       *newInsn++ = *origInsn++;
743
744     /* opcode is unchanged, just relocate the displacement */
745     if (*origInsn == 0x0F)
746       *newInsn++ = *origInsn++;
747     *newInsn++ = *origInsn++;
748     oldDisp = *((const int *)origInsn);
749     newDisp = (origAddr + insnSz) + oldDisp - (newAddr + insnSz);
750     *((int *)newInsn) = newDisp;
751     newInsn += sizeof(int);
752   }
753   else {
754     /* instruction is unchanged */
755     for (unsigned u = 0; u < insnSz; u++)
756       *newInsn++ = *origInsn++;
757   }
758
759   return (newInsn - first);
760 }
761
762
763 /*
764  * Relocate a conditional jump and change the target to newTarget.
765  * The new target must be within 128 bytes from the new address
766  * Size of instruction is unchanged.
767  * Returns the old target
768  */
769 unsigned changeConditionalJump(instruction insn,
770                          int origAddr, int newAddr, int newTargetAddr,
771                          unsigned char *&newInsn)
772 {
773
774   const unsigned char *origInsn = insn.ptr();
775   unsigned insnType = insn.type();
776   unsigned insnSz = insn.size();
777
778   int oldDisp;
779   int newDisp;
780
781   if (insnType & REL_B) {
782     /* one byte opcode followed by displacement */
783     /* opcode is unchanged */
784     assert(insnSz==2);
785     *newInsn++ = *origInsn++;
786     oldDisp = (int)*(const char *)origInsn;
787     newDisp = newTargetAddr - (newAddr + insnSz);
788     *newInsn++ = (char)newDisp;
789   }
790   else if (insnType & REL_W) {
791     /* Skip prefixes */
792     if (insnType & PREFIX_OPR)
793       *newInsn++ = *origInsn++;
794     if (insnType & PREFIX_SEG)
795       *newInsn++ = *origInsn++;
796
797     assert(*origInsn==0x0F);
798     *newInsn++ = *origInsn++; // copy the 0x0F
799     *newInsn++ = *origInsn++; // second opcode byte
800
801     oldDisp = *((const short *)origInsn);
802     newDisp = newTargetAddr - (newAddr + insnSz);
803     *((short *)newInsn) = (short)newDisp;
804     newInsn += sizeof(short);
805   }
806   else if (insnType & REL_D) {
807     // Skip prefixes
808     if (insnType & PREFIX_OPR)
809       *newInsn++ = *origInsn++;
810     if (insnType & PREFIX_SEG)
811       *newInsn++ = *origInsn++;
812
813     assert(*origInsn==0x0F);
814     *newInsn++ = *origInsn++; // copy the 0x0F
815     *newInsn++ = *origInsn++; // second opcode byte
816
817     oldDisp = *((const int *)origInsn);
818     newDisp = newTargetAddr - (newAddr + insnSz);
819     *((int *)newInsn) = (int)newDisp;
820     newInsn += sizeof(int);
821   }
822
823   return (origAddr+insnSz+oldDisp);
824 }
825
826
827
828 unsigned getRelocatedInstructionSz(instruction insn)
829 {
830   const unsigned char *origInsn = insn.ptr();
831   unsigned insnType = insn.type();
832   unsigned insnSz = insn.size();
833
834   if (insnType & REL_B) {
835     if (*origInsn == JCXZ)
836       return 9;
837     else {
838       if (insnType & IS_JCC)
839         return 6;
840       else if (insnType & IS_JUMP) {
841         return 5;
842       }
843     }
844   }
845   else if (insnType & REL_W) {
846     return insnSz + 2;
847   }
848   return insnSz;
849 }
850
851
852 registerSpace *regSpace;
853
854
855 bool registerSpace::readOnlyRegister(reg) {
856   return false;
857 }
858
859 /*
860    We don't use the machine registers to store temporaries,
861    but "virtual registers" that are located on the stack.
862    The stack frame for a tramp is:
863
864      ebp->    saved ebp (4 bytes)
865      ebp-4:   128-byte space for 32 virtual registers (32*4 bytes)
866      ebp-132: saved registers (8*4 bytes)
867      ebp-164: saved flags registers (4 bytes)
868
869      The temporaries are assigned numbers from 1 so that it is easier
870      to refer to them: -(reg*4)[ebp]. So the first reg is -4[ebp].
871
872      We are using a fixed number of temporaries now (32), but we could 
873      change to using an arbitrary number.
874
875 */
876 int deadList[NUM_VIRTUAL_REGISTERS];
877 int deadListSize = sizeof(deadList);
878
879 void initTramps()
880 {
881     static bool inited=false;
882
883     if (inited) return;
884     inited = true;
885
886 #if defined(SHM_SAMPLING) && defined(MT_THREAD)
887     for (unsigned u = 0; u < NUM_VIRTUAL_REGISTERS-1; u++) {
888 #else
889     for (unsigned u = 0; u < NUM_VIRTUAL_REGISTERS; u++) {
890 #endif
891       deadList[u] = u+1;
892     }
893
894     regSpace = new registerSpace(sizeof(deadList)/sizeof(int), deadList,                                         0, NULL);
895 }
896
897
898 void emitJump(unsigned disp32, unsigned char *&insn);
899 void emitSimpleInsn(unsigned opcode, unsigned char *&insn);
900 void emitMovRegToReg(reg dest, reg src, unsigned char *&insn);
901 void emitAddMemImm32(Address dest, int imm, unsigned char *&insn);
902 void emitOpRegImm(int opcode, reg dest, int imm, unsigned char *&insn);
903 void emitMovRegToRM(reg base, int disp, reg src, unsigned char *&insn);
904 void emitMovRMToReg(reg dest, reg base, int disp, unsigned char *&insn);
905 void emitCallRel32(unsigned disp32, unsigned char *&insn);
906
907 void generateMTpreamble(char *insn, unsigned &base, process *proc)
908 {
909   AstNode *t1,*t2,*t3,*t4,*t5;;
910   vector<AstNode *> dummy;
911   unsigned tableAddr;
912   int value; 
913   bool err;
914   reg src = -1;
915
916   /* t3=DYNINSTthreadTable[thr_self()] */
917   t1 = new AstNode("DYNINSTthreadPos", dummy);
918   value = sizeof(unsigned);
919   t4 = new AstNode(AstNode::Constant,(void *)value);
920   t2 = new AstNode(timesOp, t1, t4);
921   removeAst(t1);
922   removeAst(t4);
923
924   tableAddr = proc->findInternalAddress("DYNINSTthreadTable",true,err);
925   assert(!err);
926   t5 = new AstNode(AstNode::Constant, (void *)tableAddr);
927   t3 = new AstNode(plusOp, t2, t5);
928   removeAst(t2);
929   removeAst(t5);
930   src = t3->generateCode(proc, regSpace, insn, base, false);
931   removeAst(t3);
932   // this instruction is different on every platform
933   unsigned char *tmp_insn = (unsigned char *) (&insn[base]);
934   emitMovRMToReg(EAX, EBP, -(src*4), tmp_insn);
935   emitMovRegToRM(EBP, -(REG_MT*4), EAX, tmp_insn); 
936   base += (unsigned)tmp_insn - (unsigned)(&insn[base]);
937   regSpace->freeRegister(src);
938 }
939
940 /*
941  * change the insn at addr to be a branch to newAddr.
942  *   Used to add multiple tramps to a point.
943  */
944 void generateBranch(process *proc, unsigned fromAddr, unsigned newAddr)
945 {
946   unsigned char inst[JUMP_REL32_SZ+1];
947   unsigned char *insn = inst;
948   emitJump(newAddr - (fromAddr + JUMP_REL32_SZ), insn);
949   proc->writeTextSpace((caddr_t)fromAddr, JUMP_REL32_SZ, (caddr_t)inst);
950 }
951
952
953 bool insertInTrampTable(process *proc, unsigned key, unsigned val) {
954   unsigned u;
955
956   // check for overflow of the tramp table. 
957   // stop at 95% capacicty to ensure good performance
958   if (proc->trampTableItems == (TRAMPTABLESZ - TRAMPTABLESZ/20))
959     return false;
960   proc->trampTableItems++;
961   for (u = HASH1(key); proc->trampTable[u].key != 0; 
962        u = (u + HASH2(key)) % TRAMPTABLESZ)
963     ;
964   proc->trampTable[u].key = key;
965   proc->trampTable[u].val = val;
966
967 #if !defined(i386_unknown_nt4_0)
968   bool err = false;
969   Address addr = proc->findInternalAddress("DYNINSTtrampTable",true, err);
970   assert(err==false);
971   return proc->writeTextSpace((caddr_t)addr+u*sizeof(trampTableEntry),
972                        sizeof(trampTableEntry),
973                        (caddr_t)&(proc->trampTable[u]));
974 #else
975   return true;
976 #endif
977 }
978
979 // generate a jump to a base tramp or a trap
980 // return the size of the instruction generated
981 unsigned generateBranchToTramp(process *proc, const instPoint *point, unsigned baseAddr, 
982                            Address imageBaseAddr, unsigned char *insn) {
983   if (point->size() < JUMP_REL32_SZ) {
984
985     // the point is not big enough for a jump
986     // First, check if we can use an indirection with the entry point
987     // if that is not possible, we must use a trap
988     // We get 10 bytes for the entry points, instead of the usual five,
989     // so that we have space for an extra jump. We can then insert a
990     // jump to the basetramp in the second slot of the base tramp
991     // and use a short 2-byte jump from the point to the second jump.
992     // We adopt the following rule: Only one point in the function
993     // can use the indirect jump, and this is the first return point
994     // with a size that is less than five bytes
995     pd_Function *f = point->func();
996     vector<instPoint *>fReturns = f->funcExits(proc);
997
998     // first check if this point can use the extra slot in the entry point
999     bool canUse = false;
1000     for (unsigned u = 0; u < fReturns.size(); u++) {
1001       if (fReturns[u] == point) {
1002         canUse = true;
1003         break;
1004       } else if (fReturns[u]->size() < JUMP_SZ)
1005         break;
1006     }
1007     if (canUse) {
1008       const instPoint *the_entry = f->funcEntry(proc);
1009       if (proc->baseMap.defines(the_entry) && the_entry->size() >= 2*JUMP_SZ) {
1010         assert(point->jumpAddr() > the_entry->address());
1011         // actual displacement needs to subtract size of instruction (2 bytes)
1012         int displacement = the_entry->address() + 5 - point->jumpAddr();
1013         assert(displacement < 0);
1014         if (point->size() >= 2 && (displacement-2) > SCHAR_MIN) {
1015           generateBranch(proc, the_entry->address()+5, baseAddr);
1016           *insn++ = 0xEB;
1017           *insn++ = (char)(displacement-2);
1018           return 2;
1019         }
1020       }
1021     }
1022
1023     // must use trap
1024     //sprintf(errorLine, "Warning: unable to insert jump in function %s, address %x. Using trap\n",point->func()->prettyName().string_of(),point->address());
1025     //logLine(errorLine);
1026
1027     if (!insertInTrampTable(proc, point->jumpAddr()+imageBaseAddr, baseAddr))
1028       return 0;
1029
1030     *insn = 0xCC;
1031     return 1;
1032   } else {
1033     // replace instructions at point with jump to base tramp
1034     emitJump(baseAddr - (point->jumpAddr() + imageBaseAddr + JUMP_REL32_SZ), insn);
1035     return JUMP_REL32_SZ;
1036   }
1037 }
1038
1039
1040 /*
1041  * Install a base tramp, relocating the instructions at location
1042  * The pre and post jumps are filled with a 'jump 0'
1043  * Return a descriptor for the base tramp.
1044  *
1045  */
1046
1047 trampTemplate *installBaseTramp(const instPoint *&location, process *proc, bool noCost) 
1048 {
1049    bool aflag;
1050 /*
1051    The base tramp:
1052    addr   instruction             cost
1053    0:    <relocated instructions before point>
1054    a = size of relocated instructions before point
1055    a+0:   jmp a+30 <skip pre insn>  1
1056    a+5:   push ebp                  1
1057    a+6:   mov esp, ebp              1
1058    a+8:   subl esp, 0x80            1
1059    a+14:  pushad                    5
1060    a+15:  pushaf                    9
1061    a+16:  jmp <global pre inst>     1
1062    a+21:  jmp <local pre inst>      1
1063    a+26:  popaf                    14
1064    a+27:  popad                     5
1065    a+28:  leave                     3
1066    a+29:  add costAddr, cost        3
1067    a+39:  <relocated instructions at point>
1068
1069    b = a +30 + size of relocated instructions at point
1070    b+0:   jmp b+30 <skip post insn>
1071    b+5:   push ebp
1072    b+6:   mov esp, ebp
1073    b+8:   subl esp, 0x80
1074    b+14:  pushad
1075    b+15:  pushaf
1076    b+16:  jmp <global post inst>
1077    b+21:  jmp <local post inst>
1078    b+26:  popaf
1079    b+27:  popad
1080    b+28:  leave
1081    b+29:  <relocated instructions after point>
1082
1083    c:     jmp <return to user code>
1084
1085    tramp size = 2*23 + 10 + 5 + size of relocated instructions
1086    Make sure to update the size if the tramp is changed
1087
1088    cost of pre and post instrumentation is (1+1+1+5+9+1+1+15+5+3) = 42
1089    cost of rest of tramp is (1+3+1+1)
1090
1091 */
1092
1093   unsigned u;
1094   trampTemplate *ret = new trampTemplate;
1095   ret->trampTemp = 0;
1096   unsigned jccTarget = 0; // used when the instruction at the point is a cond. jump
1097   unsigned auxJumpOffset = 0;
1098
1099   // check instructions at this point to find how many instructions 
1100   // we should relocate
1101   instPoint *temp = (instPoint *)location;
1102   temp->checkInstructions();
1103
1104   // compute the tramp size
1105   // if there are any changes to the tramp, the size must be updated.
1106 #if defined(SHM_SAMPLING) && defined(MT_THREAD)
1107   unsigned trampSize = 73+2*27;
1108 #else
1109   unsigned trampSize = 73;
1110 #endif
1111   for (u = 0; u < location->insnsBefore(); u++) {
1112     trampSize += getRelocatedInstructionSz(location->insnBeforePt(u));
1113   }
1114   if (location->insnAtPoint().type() & IS_JCC)
1115     trampSize += location->insnAtPoint().size() + 2 * JUMP_SZ;
1116   else
1117     trampSize += getRelocatedInstructionSz(location->insnAtPoint());
1118   for (u = 0; u < location->insnsAfter(); u++) {
1119     trampSize += getRelocatedInstructionSz(location->insnAfterPt(u));
1120   }
1121
1122   Address imageBaseAddr;
1123   if (!proc->getBaseAddress(location->owner(), imageBaseAddr)) {
1124     abort();
1125   }
1126
1127   Address costAddr = 0; // for now...
1128   if (!noCost) {
1129 #ifdef SHM_SAMPLING
1130      costAddr = (Address)proc->getObsCostLowAddrInApplicSpace();
1131      assert(costAddr);
1132 #else
1133      // get address of DYNINSTobsCostLow to update observed cost
1134      bool err = false;
1135      costAddr = proc->findInternalAddress("DYNINSTobsCostLow",
1136                                           true, err);
1137      assert(costAddr && !err);
1138 #endif
1139   }
1140
1141   ret->size = trampSize;
1142   unsigned baseAddr = inferiorMalloc(proc, trampSize, textHeap);
1143   ret->baseAddr = baseAddr;
1144
1145   unsigned char *code = new unsigned char[2*trampSize];
1146   unsigned char *insn = code;
1147   unsigned currAddr = baseAddr;
1148
1149   // get the current instruction that is being executed. If the PC is at a
1150   // instruction that is being relocated, we must change the PC.
1151   unsigned currentPC = proc->currentPC();
1152
1153   // emulate the instructions before the point
1154   unsigned origAddr = location->jumpAddr() + imageBaseAddr;
1155   for (u = location->insnsBefore(); u > 0; ) {
1156     --u;
1157     if (currentPC == origAddr) {
1158       //fprintf(stderr, "changed PC: %x to %x\n", currentPC, currAddr);
1159       proc->setNewPC(currAddr);
1160     }
1161
1162     unsigned newSize = relocateInstruction(location->insnBeforePt(u), origAddr, currAddr, insn);
1163     aflag=(newSize == getRelocatedInstructionSz(location->insnBeforePt(u)));
1164     assert(aflag);
1165     currAddr += newSize;
1166     origAddr += location->insnBeforePt(u).size();
1167   }
1168
1169
1170   /***
1171     If the instruction at the point is a conditional jump, we relocate it to
1172     the top of the base tramp, and change the code so that the tramp is executed
1173     only if the branch is taken.
1174
1175     e.g.
1176      L1:  jne target
1177      L2:  ...
1178
1179     becomes
1180
1181           jne T1
1182           jmp T2
1183           jne
1184      T1:  ...
1185
1186      T2:  relocated instructions after point
1187
1188      then later at the base tramp, at the point where we relocate the instruction
1189      at the point, we insert a jump to target
1190   ***/
1191   if (location->insnAtPoint().type() & IS_JCC) {
1192      currAddr = baseAddr + (insn - code);
1193      assert(origAddr == location->address() + imageBaseAddr);
1194      origAddr = location->address() + imageBaseAddr;
1195      if (currentPC == origAddr) {
1196        //fprintf(stderr, "changed PC: %x to %x\n", currentPC, currAddr);
1197        proc->setNewPC(currAddr);
1198      }
1199
1200      jccTarget = changeConditionalJump(location->insnAtPoint(), origAddr, currAddr,
1201                                        currAddr+location->insnAtPoint().size()+5, insn);
1202      currAddr += location->insnAtPoint().size();
1203      auxJumpOffset = insn-code;
1204      emitJump(0, insn);
1205      origAddr += location->insnAtPoint().size();
1206   }
1207
1208   // pre branches
1209   // skip pre instrumentation
1210   ret->skipPreInsOffset = insn-code;
1211   emitJump(0, insn);
1212
1213   // save registers and create a new stack frame for the tramp
1214   emitSimpleInsn(PUSH_EBP, insn);  // push ebp
1215   emitMovRegToReg(EBP, ESP, insn); // mov ebp, esp  (2-byte instruction)
1216   // allocate space for temporaries (virtual registers)
1217   emitOpRegImm(5, ESP, 128, insn); // sub esp, 128
1218   emitSimpleInsn(PUSHAD, insn);    // pushad
1219   emitSimpleInsn(PUSHFD, insn);    // pushfd
1220
1221 #if defined(SHM_SAMPLING) && defined(MT_THREAD)
1222   // generate preamble for MT version
1223   unsigned base=0;
1224   generateMTpreamble((char *)insn, base, proc);
1225   insn += base;
1226 #endif
1227
1228   // global pre branch
1229   ret->globalPreOffset = insn-code;
1230   emitJump(0, insn);
1231
1232   // local pre branch
1233   ret->localPreOffset = insn-code;
1234   emitJump(0, insn);
1235
1236   ret->localPreReturnOffset = insn-code;
1237
1238   // restore registers
1239   emitSimpleInsn(POPFD, insn);     // popfd
1240   emitSimpleInsn(POPAD, insn);     // popad
1241   emitSimpleInsn(LEAVE, insn);     // leave
1242
1243   // update cost
1244   // update cost -- a 10-byte instruction
1245   ret->updateCostOffset = insn-code;
1246   currAddr = baseAddr + (insn-code);
1247   ret->costAddr = currAddr;
1248   if (!noCost) {
1249      emitAddMemImm32(costAddr, 88, insn);  // add (costAddr), cost
1250   }
1251   else {
1252      // minor hack: we still need to fill up the rest of the 10 bytes, since
1253      // assumptions are made about the positioning of instructions that follow.
1254      // (This could in theory be fixed)
1255      // So, 10 NOP instructions (each 1 byte)
1256      for (unsigned foo=0; foo < 10; foo++)
1257         emitSimpleInsn(0x90, insn); // NOP
1258   }
1259
1260    
1261   if (!(location->insnAtPoint().type() & IS_JCC)) {
1262     // emulate the instruction at the point 
1263     ret->emulateInsOffset = insn-code;
1264     currAddr = baseAddr + (insn - code);
1265     assert(origAddr == location->address() + imageBaseAddr);
1266     origAddr = location->address() + imageBaseAddr;
1267     if (currentPC == origAddr) {
1268       //fprintf(stderr, "changed PC: %x to %x\n", currentPC, currAddr);
1269       proc->setNewPC(currAddr);
1270     }
1271
1272     unsigned newSize = relocateInstruction(location->insnAtPoint(), origAddr, currAddr, insn);
1273     aflag=(newSize == getRelocatedInstructionSz(location->insnAtPoint()));
1274     assert(aflag);
1275     currAddr += newSize;
1276     origAddr += location->insnAtPoint().size();
1277   } else {
1278     // instruction at point is a conditional jump. 
1279     // The instruction was relocated to the beggining of the tramp (see comments above)
1280     // We must generate a jump to the original target here
1281     assert(jccTarget > 0);
1282     currAddr = baseAddr + (insn - code);
1283     emitJump(jccTarget-(currAddr+JUMP_SZ), insn);
1284     currAddr += JUMP_SZ;
1285   }
1286
1287   // post branches
1288   // skip post instrumentation
1289   ret->skipPostInsOffset = insn-code;
1290   emitJump(0, insn);
1291
1292
1293   // save registers and create a new stack frame for the tramp
1294   emitSimpleInsn(PUSH_EBP, insn);  // push ebp
1295   emitMovRegToReg(EBP, ESP, insn); // mov ebp, esp
1296   // allocate space for temporaries (virtual registers)
1297   emitOpRegImm(5, ESP, 128, insn); // sub esp, 128
1298   emitSimpleInsn(PUSHAD, insn);    // pushad
1299   emitSimpleInsn(PUSHFD, insn);    // pushfd
1300
1301 #if defined(SHM_SAMPLING) && defined(MT_THREAD)
1302   // generate preamble for MT version
1303   base=0;
1304   generateMTpreamble((char *)insn, base, proc);
1305   insn += base;
1306 #endif
1307
1308   // global post branch
1309   ret->globalPostOffset = insn-code; 
1310   emitJump(0, insn);
1311
1312   // local post branch
1313   ret->localPostOffset = insn-code;
1314   emitJump(0, insn);
1315
1316   ret->localPostReturnOffset = insn-code;
1317
1318   // restore registers
1319   emitSimpleInsn(POPFD, insn);     // popfd
1320   emitSimpleInsn(POPAD, insn);     // popad
1321   emitSimpleInsn(LEAVE, insn);     // leave
1322   
1323   // emulate the instructions after the point
1324   ret->returnInsOffset = insn-code;
1325   currAddr = baseAddr + (insn - code);
1326   assert(origAddr == location->address() + imageBaseAddr + location->insnAtPoint().size());
1327   origAddr = location->address() + imageBaseAddr + location->insnAtPoint().size();
1328   for (u = 0; u < location->insnsAfter(); u++) {
1329     if (currentPC == origAddr) {
1330       //fprintf(stderr, "changed PC: %x to %x\n", currentPC, currAddr);
1331       proc->setNewPC(currAddr);
1332     }
1333     unsigned newSize = relocateInstruction(location->insnAfterPt(u), origAddr, currAddr, insn);
1334     aflag=(newSize == getRelocatedInstructionSz(location->insnAfterPt(u)));
1335     assert(aflag);
1336     currAddr += newSize;
1337     origAddr += location->insnAfterPt(u).size();
1338   }
1339
1340   // return to user code
1341   currAddr = baseAddr + (insn - code);
1342   emitJump((location->returnAddr() + imageBaseAddr) - (currAddr+JUMP_SZ), insn);
1343
1344   assert((unsigned)(insn-code) == trampSize);
1345
1346   // update the jumps to skip pre and post instrumentation
1347   unsigned char *ip = code + ret->skipPreInsOffset;
1348   emitJump(ret->updateCostOffset - (ret->skipPreInsOffset+JUMP_SZ), ip);
1349   ip = code + ret->skipPostInsOffset;
1350   emitJump(ret->returnInsOffset - (ret->skipPostInsOffset+JUMP_SZ), ip);
1351
1352   if (auxJumpOffset > 0) {
1353     ip = code + auxJumpOffset;
1354     emitJump(ret->returnInsOffset - (auxJumpOffset+JUMP_SZ), ip);
1355   }
1356   
1357   // put the tramp in the application space
1358   proc->writeDataSpace((caddr_t)baseAddr, insn-code, (caddr_t) code);
1359
1360   free(code);
1361
1362   ret->cost = 6;
1363   //
1364   // The cost for generateMTpreamble is 25 for pre and post instrumentation:
1365   // movl   $0x80570ec,%eax                1
1366   // call   *%ea                           5
1367   // movl   %eax,0xfffffffc(%ebp)          1
1368   // shll   $0x2,0xfffffffc(%ebp)         12
1369   // addl   $0x84ac670,0xfffffffc(%ebp)    4
1370   // movl   0xfffffffc(%ebp),%eax          1
1371   // movl   %eax,0xffffff80(%ebp)          1
1372   //
1373   ret->prevBaseCost = 42+25;
1374   ret->postBaseCost = 42+25;
1375   ret->prevInstru = false;
1376   ret->postInstru = false;
1377   return ret;
1378 }
1379
1380
1381 // This function is used to clear a jump from base to minitramps
1382 // For the x86 platform, we generate a jump to the next instruction
1383 void generateNoOp(process *proc, int addr) 
1384 {
1385   static unsigned char jump0[5] = { 0xE9, 0, 0, 0, 0 };
1386   proc->writeDataSpace((caddr_t) addr, 5, (caddr_t)jump0);
1387 }
1388
1389
1390 trampTemplate *findAndInstallBaseTramp(process *proc, 
1391                                        instPoint *&location, 
1392                                        returnInstance *&retInstance,
1393                                        bool noCost)
1394 {
1395     trampTemplate *ret;
1396     retInstance = NULL;
1397
1398     if (!proc->baseMap.defines(location)) {
1399         ret = installBaseTramp(location, proc, noCost);
1400         proc->baseMap[location] = ret;
1401         // generate branch from instrumentation point to base tramp
1402         unsigned imageBaseAddr;
1403         if (!proc->getBaseAddress(location->owner(), imageBaseAddr))
1404           abort();
1405         unsigned char *insn = new unsigned char[JUMP_REL32_SZ];
1406         unsigned size = generateBranchToTramp(proc, location, (int)ret->baseAddr, 
1407                                               imageBaseAddr, insn);
1408         if (size == 0)
1409           return NULL;
1410         retInstance = new returnInstance(new instruction(insn, 0, size), size,
1411                                          location->jumpAddr() + imageBaseAddr, size);
1412     } else {
1413         ret = proc->baseMap[location];
1414     }
1415     return(ret);
1416 }
1417
1418
1419 /*
1420  * Install a single mini-tramp.
1421  *
1422  */
1423 void installTramp(instInstance *inst, char *code, int codeSize) 
1424 {
1425     totalMiniTramps++;
1426     //insnGenerated += codeSize/sizeof(int);
1427     (inst->proc)->writeDataSpace((caddr_t)inst->trampBase, codeSize, code);
1428     unsigned atAddr;
1429     if (inst->when == callPreInsn) {
1430         if (inst->baseInstance->prevInstru == false) {
1431             atAddr = inst->baseInstance->baseAddr+inst->baseInstance->skipPreInsOffset;
1432             inst->baseInstance->cost += inst->baseInstance->prevBaseCost;
1433             inst->baseInstance->prevInstru = true;
1434             generateNoOp(inst->proc, atAddr);
1435         }
1436     }
1437     else {
1438         if (inst->baseInstance->postInstru == false) {
1439             atAddr = inst->baseInstance->baseAddr+inst->baseInstance->skipPostInsOffset; 
1440             inst->baseInstance->cost += inst->baseInstance->postBaseCost;
1441             inst->baseInstance->postInstru = true;
1442             generateNoOp(inst->proc, atAddr);
1443         }
1444     }
1445 }
1446
1447
1448 /**************************************************************
1449  *
1450  *  code generator for x86
1451  *
1452  **************************************************************/
1453
1454
1455
1456
1457 #define MAX_BRANCH      (0x1<<31)
1458
1459 unsigned getMaxBranch() {
1460   return (unsigned)MAX_BRANCH;
1461 }
1462
1463
1464 bool doNotOverflow(int)
1465 {
1466   //
1467   // this should be changed by the correct code. If there isn't any case to
1468   // be checked here, then the function should return TRUE. If there isn't
1469   // any immediate code to be generated, then it should return FALSE - naim
1470   //
1471   // any int value can be an immediate on the pentium
1472   return(true);
1473 }
1474
1475
1476
1477 /* build the MOD/RM byte of an instruction */
1478 inline unsigned char makeModRMbyte(unsigned Mod, unsigned Reg, unsigned RM) {
1479   return ((Mod & 0x3) << 6) + ((Reg & 0x7) << 3) + (RM & 0x7);
1480 }
1481
1482 /* 
1483    Emit the ModRM byte and displacement for addressing modes.
1484    base is a register (EAX, ECX, EDX, EBX, EBP, ESI, EDI)
1485    disp is a displacement
1486    reg_opcode is either a register or an opcode
1487  */
1488 void emitAddressingMode(int base, int disp, int reg_opcode, 
1489                         unsigned char *&insn) {
1490   assert(base != ESP);
1491   if (base == -1) {
1492     *insn++ = makeModRMbyte(0, reg_opcode, 5);
1493     *((int *)insn) = disp;
1494     insn += sizeof(int);
1495   } else if (disp == 0 && base != EBP) {
1496     *insn++ = makeModRMbyte(0, reg_opcode, base);
1497   } else if (disp >= -128 && disp <= 127) {
1498     *insn++ = makeModRMbyte(1, reg_opcode, base);
1499     *((char *)insn++) = (char) disp;
1500   } else {
1501     *insn++ = makeModRMbyte(2, reg_opcode, base);
1502     *((int *)insn) = disp;
1503     insn += sizeof(int);
1504   }
1505 }
1506
1507
1508 /* emit a simple one-byte instruction */
1509 void emitSimpleInsn(unsigned op, unsigned char *&insn) {
1510   *insn++ = op;
1511 }
1512
1513 // emit a simple register to register instruction: OP dest, src
1514 // opcode is one or two byte
1515 void emitOpRegReg(unsigned opcode, reg dest, reg src, unsigned char *&insn) {
1516   if (opcode <= 0xFF)
1517     *insn++ = opcode;
1518   else {
1519     *insn++ = opcode >> 8;
1520     *insn++ = opcode & 0xFF;
1521   }
1522   // ModRM byte define the operands: Mod = 3, Reg = dest, RM = src
1523   *insn++ = makeModRMbyte(3, dest, src);
1524 }
1525
1526 // emit OP reg, r/m
1527 void emitOpRegRM(unsigned opcode, reg dest, reg base, int disp, unsigned char *&insn) {
1528   *insn++ = opcode;
1529   emitAddressingMode(base, disp, dest, insn);
1530 }
1531
1532 // emit OP r/m, reg
1533 void emitOpRMReg(unsigned opcode, reg base, int disp, reg src, unsigned char *&insn) {
1534   *insn++ = opcode;
1535   emitAddressingMode(base, disp, src, insn);
1536 }
1537
1538 // emit OP reg, imm32
1539 void emitOpRegImm(int opcode, reg dest, int imm, unsigned char *&insn) {
1540   *insn++ = 0x81;
1541   *insn++ = makeModRMbyte(3, opcode, dest);
1542   *((int *)insn) = imm;
1543   insn+= sizeof(int);
1544 }
1545
1546 /*
1547 // emit OP r/m, imm32
1548 void emitOpRMImm(unsigned opcode, reg base, int disp, int imm, unsigned char *&insn) {
1549   *insn++ = 0x81;
1550   emitAddressingMode(base, disp, opcode, insn);
1551   *((int *)insn) = imm;
1552   insn += sizeof(int);
1553 }
1554 */
1555
1556 // emit OP r/m, imm32
1557 void emitOpRMImm(unsigned opcode1, unsigned opcode2,
1558                  reg base, int disp, int imm, unsigned char *&insn) {
1559   *insn++ = opcode1;
1560   emitAddressingMode(base, disp, opcode2, insn);
1561   *((int *)insn) = imm;
1562   insn += sizeof(int);
1563 }
1564
1565 // emit OP r/m, imm8
1566 void emitOpRMImm8(unsigned opcode1, unsigned opcode2,
1567                  reg base, int disp, char imm, unsigned char *&insn) {
1568   *insn++ = opcode1;
1569   emitAddressingMode(base, disp, opcode2, insn);
1570   *insn++ = imm;
1571 }
1572
1573 // emit OP reg, r/m, imm32
1574 void emitOpRegRMImm(unsigned opcode, reg dest,
1575                  reg base, int disp, int imm, unsigned char *&insn) {
1576   *insn++ = opcode;
1577   emitAddressingMode(base, disp, dest, insn);
1578   *((int *)insn) = imm;
1579   insn += sizeof(int);
1580 }
1581
1582 // emit MOV reg, reg
1583 void emitMovRegToReg(reg dest, reg src, unsigned char *&insn) {
1584   *insn++ = 0x8B;
1585   *insn++ = makeModRMbyte(3, dest, src);
1586 }
1587
1588 // emit MOV reg, r/m
1589 void emitMovRMToReg(reg dest, reg base, int disp, unsigned char *&insn) {
1590   *insn++ = 0x8B;
1591   emitAddressingMode(base, disp, dest, insn);
1592 }
1593
1594 // emit MOV r/m, reg
1595 void emitMovRegToRM(reg base, int disp, reg src, unsigned char *&insn) {
1596   *insn++ = 0x89;
1597   emitAddressingMode(base, disp, src, insn);
1598 }
1599
1600 // emit MOV m, reg
1601 void emitMovRegToM(int disp, reg src, unsigned char *&insn) {
1602   *insn++ = 0x89;
1603   emitAddressingMode(-1, disp, src, insn);
1604 }
1605
1606 // emit MOV reg, m
1607 void emitMovMToReg(reg dest, int disp, unsigned char *&insn) {
1608   *insn++ = 0x8B;
1609   emitAddressingMode(-1, disp, dest, insn);
1610 }
1611
1612 // emit MOV reg, imm32
1613 void emitMovImmToReg(reg dest, int imm, unsigned char *&insn) {
1614   *insn++ = 0xB8 + dest;
1615   *((int *)insn) = imm;
1616   insn += sizeof(int);
1617 }
1618
1619 // emit MOV r/m32, imm32
1620 void emitMovImmToRM(reg base, int disp, int imm, unsigned char *&insn) {
1621   *insn++ = 0xC7;
1622   emitAddressingMode(base, disp, 0, insn);
1623   *((int*)insn) = imm;
1624   insn += sizeof(int);
1625 }
1626
1627 // emit MOV mem32, imm32
1628 void emitMovImmToMem(unsigned maddr, int imm, unsigned char *&insn) {
1629   *insn++ = 0xC7;
1630   // emit the ModRM byte: we use a 32-bit displacement for the address,
1631   // the ModRM value is 0x05
1632   *insn++ = 0x05;
1633   *((unsigned *)insn) = maddr;
1634   insn += sizeof(unsigned);
1635   *((int*)insn) = imm;
1636   insn += sizeof(int);
1637 }
1638
1639
1640 // emit Add dword ptr DS:[addr], imm
1641 void emitAddMemImm32(Address addr, int imm, unsigned char *&insn) {
1642   *insn++ = 0x81;
1643   *insn++ = 0x05;
1644   *((unsigned *)insn) = addr;
1645   insn += sizeof(unsigned);
1646   *((int *)insn) = imm;
1647   insn += sizeof(int);
1648 }
1649
1650 // emit JUMP rel32
1651 void emitJump(unsigned disp32, unsigned char *&insn) {
1652   *insn++ = 0xE9;
1653   *((int *)insn) = disp32;
1654   insn += sizeof(int);
1655
1656
1657 // emit CALL rel32
1658 void emitCallRel32(unsigned disp32, unsigned char *&insn) {
1659   *insn++ = 0xE8;
1660   *((int *)insn) = disp32;
1661   insn += sizeof(int);
1662 }
1663
1664 // set dest=1 if src1 op src2, otherwise dest = 0
1665 void emitRelOp(unsigned op, reg dest, reg src1, reg src2, unsigned char *&insn) {
1666   //fprintf(stderr,"Relop dest = %d, src1 = %d, src2 = %d\n", dest, src1, src2);
1667   emitOpRegReg(0x29, ECX, ECX, insn);           // clear ECX
1668   emitMovRMToReg(EAX, EBP, -(src1*4), insn);    // mov eax, -(src1*4)[ebp]
1669   emitOpRegRM(0x3B, EAX, EBP, -(src2*4), insn); // cmp eax, -(src2*4)[ebp]
1670   unsigned char opcode;
1671   switch (op) {
1672     case eqOp: opcode = JNE_R8; break;
1673     case neOp: opcode = JE_R8; break;
1674     case lessOp: opcode = JGE_R8; break;
1675     case leOp: opcode = JG_R8; break;
1676     case greaterOp: opcode = JLE_R8; break;
1677     case geOp: opcode = JL_R8; break;
1678     default: assert(0);
1679   }
1680   *insn++ = opcode; *insn++ = 1;                // jcc 1
1681   emitSimpleInsn(0x40+ECX, insn);               // inc ECX
1682   emitMovRegToRM(EBP, -(dest*4), ECX, insn);    // mov -(dest*4)[ebp], ecx
1683
1684 }
1685
1686 // set dest=1 if src1 op src2imm, otherwise dest = 0
1687 void emitRelOpImm(unsigned op, reg dest, reg src1, int src2imm, unsigned char *&insn) {
1688   //fprintf(stderr,"Relop dest = %d, src1 = %d, src2 = %d\n", dest, src1, src2);
1689   emitOpRegReg(0x29, ECX, ECX, insn);           // clear ECX
1690   emitMovRMToReg(EAX, EBP, -(src1*4), insn);    // mov eax, -(src1*4)[ebp]
1691   emitOpRegImm(0x3D, EAX, src2imm, insn);       // cmp eax, src2
1692   unsigned char opcode;
1693   switch (op) {
1694     case eqOp: opcode = JNE_R8; break;
1695     case neOp: opcode = JE_R8; break;
1696     case lessOp: opcode = JGE_R8; break;
1697     case leOp: opcode = JG_R8; break;
1698     case greaterOp: opcode = JLE_R8; break;
1699     case geOp: opcode = JL_R8; break;
1700     default: assert(0);
1701   }
1702   *insn++ = opcode; *insn++ = 1;                // jcc 1
1703   emitSimpleInsn(0x40+ECX, insn);               // inc ECX
1704   emitMovRegToRM(EBP, -(dest*4), ECX, insn);    // mov -(dest*4)[ebp], ecx
1705
1706 }
1707
1708 void emitEnter(short imm16, unsigned char *&insn) {
1709   *insn++ = 0xC8;
1710   *((short*)insn) = imm16;
1711   insn += sizeof(short);
1712   *insn++ = 0;
1713 }
1714
1715
1716
1717 unsigned emitFuncCall(opCode op, 
1718                       registerSpace *rs,
1719                       char *ibuf, unsigned &base,
1720                       const vector<AstNode *> &operands, 
1721                       const string &callee, process *proc,
1722                       bool noCost)
1723 {
1724   assert(op == callOp);
1725   unsigned addr;
1726   bool err;
1727   vector <reg> srcs;
1728
1729   addr = proc->findInternalAddress(callee, false, err);
1730   if (err) {
1731     function_base *func = proc->findOneFunction(callee);
1732     if (!func) {
1733       ostrstream os(errorLine, 1024, ios::out);
1734       os << "Internal error: unable to find addr of " << callee << endl;
1735       logLine(errorLine);
1736       showErrorCallback(80, (const char *) errorLine);
1737       P_abort();
1738     }
1739     addr = func->getAddress(0);
1740   }
1741
1742   for (unsigned u = 0; u < operands.size(); u++)
1743     srcs += operands[u]->generateCode(proc, rs, ibuf, base, noCost);
1744
1745   unsigned char *insn = (unsigned char *) ((void*)&ibuf[base]);
1746   unsigned char *first = insn;
1747
1748   // push arguments in reverse order, last argument first
1749   // must use int instead of unsigned to avoid nasty underflow problem:
1750   for (int i=srcs.size() - 1 ; i >= 0; i--) {
1751      emitOpRMReg(PUSH_RM_OPC1, EBP, -(srcs[i]*4), PUSH_RM_OPC2, insn);
1752      rs->freeRegister(srcs[i]);
1753   }
1754
1755   // make the call
1756   // we are using an indirect call here because we don't know the
1757   // address of this instruction, so we can't use a relative call.
1758   // TODO: change this to use a direct call
1759   emitMovImmToReg(EAX, addr, insn);       // mov eax, addr
1760   emitOpRegReg(CALL_RM_OPC1, CALL_RM_OPC2, EAX, insn);   // call *(eax)
1761
1762   // reset the stack pointer
1763   if (srcs.size() > 0)
1764      emitOpRegImm(0, ESP, srcs.size()*4, insn); // add esp, srcs.size()*4
1765
1766   // allocate a (virtual) register to store the return value
1767   reg ret = rs->allocateRegister((char *)insn, base, noCost);
1768   emitMovRegToRM(EBP, -(ret*4), EAX, insn);
1769
1770   base += insn - first;
1771   return ret;
1772 }
1773
1774
1775
1776 /*
1777  * emit code for op(sr1,src2, dest)
1778  * ibuf is an instruction buffer where instructions are generated
1779  * base is the next free position on ibuf where code is to be generated
1780  */
1781 unsigned emit(opCode op, reg src1, reg src2, reg dest, char *ibuf, unsigned &base,
1782               bool noCost)
1783 {
1784     unsigned char *insn = (unsigned char *) (&ibuf[base]);
1785     unsigned char *first = insn;
1786
1787     if (op == updateCostOp) {
1788       // src1 is the cost value
1789       // src2 is not used
1790       // desc is the address of observed cost
1791
1792       if (!noCost) {
1793          // update observed cost
1794          // dest = address of DYNINSTobsCostLow
1795          // src1 = cost
1796          emitAddMemImm32(dest, src1, insn);  // ADD (dest), src1
1797       }
1798       base += insn-first;
1799       return base;
1800
1801     } else if (op == loadConstOp) {
1802       // dest is a temporary
1803       // src1 is an immediate value 
1804       // dest = src1:imm32
1805       emitMovImmToRM(EBP, -(dest*4), src1, insn);
1806
1807     } else if (op ==  loadOp) {
1808       // dest is a temporary
1809       // src1 is the address of the operand
1810       // dest = [src1]
1811       emitMovMToReg(EAX, src1, insn);               // mov eax, src1
1812       emitMovRegToRM(EBP, -(dest*4), EAX, insn);    // mov -(dest*4)[ebp], eax
1813
1814     } else if (op ==  loadIndirOp) {
1815       // same as loadOp, but the value to load is already in a register
1816       emitMovRMToReg(EAX, EBP, -(src1*4), insn); // mov eax, -(src1*4)[ebp]
1817       emitMovRMToReg(EAX, EAX, 0, insn);         // mov eax, [eax]
1818       emitMovRegToRM(EBP, -(dest*4), EAX, insn); // mov -(dest*4)[ebp], eax
1819
1820     } else if (op ==  storeOp) {
1821       // [dest] = src1
1822       // dest has the address where src1 is to be stored
1823       // src1 is a temporary
1824       // src2 is a "scratch" register, we don't need it in this architecture
1825       emitMovRMToReg(EAX, EBP, -(src1*4), insn);    // mov eax, -(src1*4)[ebp]
1826       emitMovRegToM(dest, EAX, insn);               // mov dest, eax
1827
1828     } else if (op ==  storeIndirOp) {
1829       // same as storeOp, but the address where to store is already in a
1830       // register
1831       emitMovRMToReg(EAX, EBP, -(src1*4), insn);   // mov eax, -(src1*4)[ebp]
1832       emitMovRMToReg(ECX, EBP, -(dest*4), insn);   // mov ecx, -(dest*4)[ebp]
1833       emitMovRegToRM(ECX, 0, EAX, insn);           // mov [ecx], eax
1834
1835     } else if (op ==  ifOp) {
1836       // if src1 == 0 jump to dest
1837       // src1 is a temporary
1838       // dest is a target address
1839       emitOpRegReg(0x29, EAX, EAX, insn);           // sub EAX, EAX ; clear EAX
1840       emitOpRegRM(0x3B, EAX, EBP, -(src1*4), insn); // cmp -(src1*4)[EBP], EAX
1841       // je dest
1842       *insn++ = 0x0F;
1843       *insn++ = 0x84;
1844       *((int *)insn) = dest;
1845       insn += sizeof(int);
1846       base += insn-first;
1847       return base;
1848
1849     } else if (op == branchOp) { 
1850         emitJump(dest - JUMP_REL32_SZ, insn); 
1851         base += JUMP_REL32_SZ;
1852         return(base - JUMP_REL32_SZ);
1853     } else if (op ==  trampPreamble) {
1854       // no code is needed here
1855       
1856     } else if (op ==  trampTrailer) {
1857
1858       // generate the template for a jump -- actual jump is generated elsewhere
1859       emitJump(0, insn); // jump xxxx
1860       // return the offset of the previous jump
1861       base += insn - first;
1862       return(base - JUMP_REL32_SZ);
1863
1864     } else if (op == noOp) {
1865        emitSimpleInsn(NOP, insn); // nop
1866
1867     } else if (op == getRetValOp) {
1868       // dest is a register were we can store the value
1869       // the return value is in the saved EAX
1870       emitMovRMToReg(EAX, EBP, SAVED_EAX_OFFSET, insn);
1871       emitMovRegToRM(EBP, -(dest*4), EAX, insn);
1872       base += insn - first;
1873       return dest;
1874
1875     } else if (op == getParamOp) {
1876       // src1 is the number of the argument
1877       // dest is a register were we can store the value
1878       // Parameters are addressed by a positive offset from ebp,
1879       // the first is PARAM_OFFSET[ebp]
1880       emitMovRMToReg(EAX, EBP, PARAM_OFFSET + src1*4, insn);
1881       emitMovRegToRM(EBP, -(dest*4), EAX, insn);
1882       base += insn - first;
1883       return dest;
1884
1885     } else if (op == saveRegOp) {
1886       // should not be used on this platform
1887       assert(0);
1888
1889     } else {
1890         unsigned opcode;
1891         switch (op) {
1892             // integer ops
1893             case plusOp:
1894                 // dest = src1 + src2
1895                 // mv eax, src1
1896                 // add eax, src2
1897                 // mov dest, eax
1898                 opcode = 0x03; // ADD
1899                 break;
1900
1901             case minusOp:
1902                 opcode = 0x2B; // SUB
1903                 break;
1904
1905             case timesOp:
1906                 opcode = 0x0FAF; // IMUL
1907                 break;
1908
1909             case divOp:
1910                 // dest = src1 div src2
1911                 // mov eax, src1
1912                 // cdq   ; edx = sign extend of eax
1913                 // idiv eax, src2 ; eax = edx:eax div src2, edx = edx:eax mod src2
1914                 // mov dest, eax
1915                 emitMovRMToReg(EAX, EBP, -(src1*4), insn);
1916                 emitSimpleInsn(0x99, insn);
1917                 emitOpRegRM(0xF7, 0x7 /*opcode extension*/, EBP, -(src2*4), insn);
1918                 emitMovRegToRM(EBP, -(dest*4), EAX, insn);
1919                 base += insn-first;
1920                 return 0;
1921                 break;
1922
1923             // Bool ops
1924             case orOp:
1925                 opcode = 0x0B; // OR 
1926                 break;
1927
1928             case andOp:
1929                 opcode = 0x23; // AND
1930                 break;
1931
1932             // rel ops
1933             // dest = src1 relop src2
1934             case eqOp:
1935             case neOp:
1936             case lessOp:
1937             case leOp:
1938             case greaterOp:
1939             case geOp:
1940                 emitRelOp(op, dest, src1, src2, insn);
1941                 base += insn-first;
1942                 return 0;
1943                 break;
1944
1945             default:
1946                 abort();
1947                 break;
1948         }
1949
1950         emitMovRMToReg(EAX, EBP, -(src1*4), insn);
1951         emitOpRegRM(opcode, EAX, EBP, -(src2*4), insn);
1952         emitMovRegToRM(EBP, -(dest*4), EAX, insn);
1953       }
1954     base += insn - first;
1955     return(0);
1956 }
1957
1958
1959 unsigned emitImm(opCode op, reg src1, int src2imm, reg dest, char *ibuf, unsigned &base, bool)
1960 {
1961     unsigned char *insn = (unsigned char *) (&ibuf[base]);
1962     unsigned char *first = insn;
1963
1964     if (op ==  storeOp) {
1965       // [dest] = src1
1966       // dest has the address where src1 is to be stored
1967       // src1 is an immediate value
1968       // src2 is a "scratch" register, we don't need it in this architecture
1969       emitMovImmToReg(EAX, dest, insn);
1970       emitMovImmToRM(EAX, 0, src1, insn);
1971     } else {
1972         unsigned opcode1;
1973         unsigned opcode2;
1974         switch (op) {
1975             // integer ops
1976             case plusOp:
1977                 opcode1 = 0x81;
1978                 opcode2 = 0x0; // ADD
1979                 break;
1980
1981             case minusOp:
1982                 opcode1 = 0x81;
1983                 opcode2 = 0x5; // SUB
1984                 break;
1985
1986             case timesOp: {
1987                 int result;
1988                 if (isPowerOf2(src2imm, result) && result <= MAX_IMM8) {
1989                   if (src1 != dest) {
1990                     emitMovRMToReg(EAX, EBP, -(src1*4), insn);
1991                     emitMovRegToRM(EBP, -(dest*4), EAX, insn);
1992                   }
1993                   // sal dest, result
1994                   emitOpRMImm8(0xC1, 4, EBP, -(dest*4), result, insn);
1995                 }
1996                 else {
1997                   // imul EAX, -(src1*4)[ebp], src2imm
1998                   emitOpRegRMImm(0x69, EAX, EBP, -(src1*4), src2imm, insn);
1999                   emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2000                 } 
2001                 base += insn-first;
2002                 return 0;
2003               }
2004                 break;
2005
2006             case divOp: {
2007                 int result;
2008                 if (isPowerOf2(src2imm, result) && result <= MAX_IMM8) {
2009                   if (src1 != dest) {
2010                     emitMovRMToReg(EAX, EBP, -(src1*4), insn);
2011                     emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2012                   }
2013                   // sar dest, result
2014                   emitOpRMImm8(0xC1, 7, EBP, -(dest*4), result, insn);
2015                 }
2016                 else {
2017                   // dest = src1 div src2imm
2018                   // mov eax, src1
2019                   // cdq   ; edx = sign extend of eax
2020                   // mov ebx, src2imm
2021                   // idiv eax, ebx ; eax = edx:eax div src2, edx = edx:eax mod src2
2022                   // mov dest, eax
2023                   emitMovRMToReg(EAX, EBP, -(src1*4), insn);
2024                   emitSimpleInsn(0x99, insn);
2025                   emitMovImmToReg(EBX, src2imm, insn);
2026                   // idiv eax, ebx
2027                   emitOpRegReg(0xF7, 0x7 /*opcode extension*/, EBX, insn); 
2028                   emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2029                 }
2030               }
2031                 base += insn-first;
2032                 return 0;
2033                 break;
2034
2035             // Bool ops
2036             case orOp:
2037                 opcode1 = 0x81;
2038                 opcode2 = 0x1; // OR 
2039                 break;
2040
2041             case andOp:
2042                 opcode1 = 0x81;
2043                 opcode2 = 0x4; // AND
2044                 break;
2045
2046             // rel ops
2047             // dest = src1 relop src2
2048             case eqOp:
2049             case neOp:
2050             case lessOp:
2051             case leOp:
2052             case greaterOp:
2053             case geOp:
2054                 emitRelOpImm(op, dest, src1, src2imm, insn);
2055                 base += insn-first;
2056                 return 0;
2057                 break;
2058
2059             default:
2060                 abort();
2061                 break;
2062         }
2063         if (src1 != dest) {
2064           emitMovRMToReg(EAX, EBP, -(src1*4), insn);
2065           emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2066         }
2067         emitOpRMImm(opcode1, opcode2, EBP, -(dest*4), src2imm, insn);
2068       }
2069     base += insn - first;
2070     return(0);
2071 }
2072
2073
2074
2075 int getInsnCost(opCode op)
2076 {
2077     if (op == loadConstOp) {
2078         return(1);
2079     } else if (op ==  loadOp) {
2080         return(1+1);
2081     } else if (op ==  loadIndirOp) {
2082         return(3);
2083     } else if (op ==  storeOp) {
2084         return(1+1); 
2085     } else if (op ==  storeIndirOp) {
2086         return(3);
2087     } else if (op ==  ifOp) {
2088         return(1+2+1);
2089     } else if (op == branchOp) {
2090         return(1);      /* XXX Need to find out what value this should be. */
2091     } else if (op ==  callOp) {
2092         // cost of call only
2093         return(1+2+1+1);
2094     } else if (op == updateCostOp) {
2095         return(3);
2096     } else if (op ==  trampPreamble) {
2097         return(0);
2098     } else if (op ==  trampTrailer) {
2099         return(1);
2100     } else if (op == noOp) {
2101         return(1);
2102     } else if (op == getRetValOp) {
2103         return (1+1);
2104     } else if (op == getParamOp) {
2105         return(1+1);
2106     } else {
2107         switch (op) {
2108             // rel ops
2109             case eqOp:
2110             case neOp:
2111             case lessOp:
2112             case leOp:
2113             case greaterOp:
2114             case geOp:
2115                 return(1+1+2+1+1+1);
2116                 break;
2117             case divOp:
2118                 return(1+2+46+1);
2119             case timesOp:
2120                 return(1+10+1);
2121             case plusOp:
2122             case minusOp:
2123             case orOp:
2124             case andOp:
2125                 return(1+2+1);
2126             default:
2127                 assert(0);
2128                 return 0;
2129                 break;
2130         }
2131     }
2132 }
2133
2134
2135
2136 bool process::heapIsOk(const vector<sym_data> &find_us) {
2137   Symbol sym;
2138   string str;
2139   Address baseAddr;
2140
2141   // find the main function
2142   // first look for main or _main
2143 #if !defined(i386_unknown_nt4_0)
2144   if (!((mainFunction = findOneFunction("main")) 
2145         || (mainFunction = findOneFunction("_main")))) {
2146      string msg = "Cannot find main. Exiting.";
2147      statusLine(msg.string_of());
2148      showErrorCallback(50, msg);
2149      return false;
2150   }
2151 #else
2152   if (!((mainFunction = findOneFunction("main")) 
2153         || (mainFunction = findOneFunction("_main"))
2154         || (mainFunction = findOneFunction("WinMain"))
2155         || (mainFunction = findOneFunction("_WinMain")))) {
2156      string msg = "Cannot find main or WinMain. Exiting.";
2157      statusLine(msg.string_of());
2158      showErrorCallback(50, msg);
2159      return false;
2160   }
2161 #endif
2162
2163   for (unsigned i=0; i<find_us.size(); i++) {
2164     str = find_us[i].name;
2165     if (!getSymbolInfo(str, sym, baseAddr)) {
2166       string str1 = string("_") + str.string_of();
2167       if (!getSymbolInfo(str1, sym, baseAddr) && find_us[i].must_find) {
2168         string msg;
2169         msg = string("Cannot find ") + str + string(". Exiting");
2170         statusLine(msg.string_of());
2171         showErrorCallback(50, msg);
2172         return false;
2173       }
2174     }
2175   }
2176
2177 //  string ghb = GLOBAL_HEAP_BASE;
2178 //  if (!getSymbolInfo(ghb, sym, baseAddr)) {
2179 //    ghb = U_GLOBAL_HEAP_BASE;
2180 //    if (!getSymbolInfo(ghb, symm baseAddr)) {
2181 //      string msg;
2182 //      msg = string("Cannot find ") + str + string(". Exiting");
2183 //      statusLine(msg.string_of());
2184 //      showErrorCallback(50, msg);
2185 //      return false;
2186 //    }
2187 //  }
2188 //  Address instHeapEnd = sym.addr()+baseAddr;
2189 //  addInternalSymbol(ghb, instHeapEnd);
2190
2191   string ghb = INFERIOR_HEAP_BASE;
2192   if (!getSymbolInfo(ghb, sym, baseAddr)) {
2193     ghb = UINFERIOR_HEAP_BASE;
2194     if (!getSymbolInfo(ghb, sym, baseAddr)) {
2195       string msg;
2196       msg = string("Cannot find ") + ghb + string(". Cannot use this application");
2197       statusLine(msg.string_of());
2198       showErrorCallback(50, msg);
2199       return false;
2200     }
2201   }
2202   Address curr = sym.addr()+baseAddr;
2203
2204 #if !defined(i386_unknown_nt4_0)
2205   string tt = "DYNINSTtrampTable";
2206   if (!getSymbolInfo(tt, sym, baseAddr)) {
2207       string msg;
2208       msg = string("Cannot find ") + tt + string(". Cannot use this application");
2209       statusLine(msg.string_of());
2210       showErrorCallback(50, msg);
2211       return false;
2212   }
2213 #endif
2214
2215   // Check that we can patch up user code to jump to our base trampolines:
2216   const Address instHeapStart = curr;
2217   const Address instHeapEnd = instHeapStart + SYN_INST_BUF_SIZE - 1;
2218
2219   if (instHeapEnd > getMaxBranch()) {
2220     logLine("*** FATAL ERROR: Program text + data too big for dyninst\n");
2221     sprintf(errorLine, "    heap starts at %x and ends at %x\n",
2222             instHeapStart, instHeapEnd);
2223     logLine(errorLine);
2224     return false;
2225   }
2226
2227   return true;
2228 }
2229
2230
2231
2232 dictionary_hash<string, unsigned> funcFrequencyTable(string::hash);
2233
2234 //
2235 // initDefaultPointFrequencyTable - define the expected call frequency of
2236 //    procedures.  Currently we just define several one shots with a
2237 //    frequency of one, and provide a hook to read a file with more accurate
2238 //    information.
2239 //
2240 void initDefaultPointFrequencyTable()
2241 {
2242     FILE *fp;
2243     float value;
2244     char name[512];
2245
2246     funcFrequencyTable["main"] = 1;
2247     funcFrequencyTable["DYNINSTsampleValues"] = 1;
2248     funcFrequencyTable[EXIT_NAME] = 1;
2249
2250     // try to read file.
2251     fp = fopen("freq.input", "r");
2252     if (!fp) {
2253         return;
2254     } else {
2255         printf("found freq.input file\n");
2256     }
2257     while (!feof(fp)) {
2258         fscanf(fp, "%s %f\n", name, &value);
2259         funcFrequencyTable[name] = (int) value;
2260         printf("adding %s %f\n", name, value);
2261     }
2262     fclose(fp);
2263 }
2264
2265 /*
2266  * Get an etimate of the frequency for the passed instPoint.  
2267  *    This is not (always) the same as the function that contains the point.
2268  * 
2269  *  The function is selected as follows:
2270  *
2271  *  If the point is an entry or an exit return the function name.
2272  *  If the point is a call and the callee can be determined, return the called
2273  *     function.
2274  *  else return the funcation containing the point.
2275  *
2276  *  WARNING: This code contins arbitray values for func frequency (both user 
2277  *     and system).  This should be refined over time.
2278  *
2279  * Using 1000 calls sec to be one SD from the mean for most FPSPEC apps.
2280  *      -- jkh 6/24/94
2281  *
2282  */
2283 float getPointFrequency(instPoint *point)
2284 {
2285
2286     pd_Function *func = point->callee();
2287
2288     if (!func)
2289       func = point->func();
2290
2291     if (!funcFrequencyTable.defines(func->prettyName())) {
2292       // Changing this value from 250 to 100 because predictedCost was
2293       // too high - naim 07/18/96
2294       return(100.0);       
2295     } else {
2296       return ((float)funcFrequencyTable[func->prettyName()]);
2297     }
2298 }
2299
2300 //
2301 // return cost in cycles of executing at this point.  This is the cost
2302 //   of the base tramp if it is the first at this point or 0 otherwise.
2303 //
2304 int getPointCost(process *proc, const instPoint *point)
2305 {
2306     instPoint *temp = (instPoint *)point;
2307     temp->checkInstructions();
2308
2309     if (proc->baseMap.defines(point)) {
2310         return(0);
2311     } else {
2312         if (point->size() == 1)
2313           return 9000; // estimated number of cycles for traps
2314         else
2315           return(83);
2316     }
2317 }
2318
2319
2320
2321 bool returnInstance::checkReturnInstance(const vector<Address> &, u_int &) {
2322     return true;
2323 }
2324  
2325 void returnInstance::installReturnInstance(process *proc) {
2326     assert(instructionSeq);
2327     proc->writeTextSpace((void *)addr_, instSeqSize, instructionSeq->ptr());
2328     delete instructionSeq;
2329     instructionSeq = 0;
2330 }
2331
2332 void returnInstance::addToReturnWaitingList(Address , process *) {
2333     P_abort();
2334 }
2335
2336 void generateBreakPoint(instruction &insn) {
2337   P_abort();
2338 }
2339
2340 void instWaitingList::cleanUp(process *, Address ) {
2341   P_abort();
2342 }
2343
2344 /* ***************************************************** */
2345
2346 bool process::emitInferiorRPCheader(void *void_insnPtr, unsigned &base) {
2347    unsigned char *insnPtr = (unsigned char *)void_insnPtr;
2348    unsigned char *origInsnPtr = insnPtr;
2349    insnPtr += base;
2350
2351    // We emit the following here (to set up a fresh stack frame):
2352    // pushl %ebp        (0x55)
2353    // movl  %esp, %ebp  (0x89 0xe5)
2354    // pushad
2355    // pushfd
2356
2357    emitSimpleInsn(PUSH_EBP, insnPtr);
2358    emitMovRegToReg(EBP, ESP, insnPtr);
2359    // allocate space for temporaries (virtual registers)
2360    emitOpRegImm(5, ESP, 128, insnPtr); // sub esp, 128
2361    emitSimpleInsn(PUSHAD, insnPtr);
2362    emitSimpleInsn(PUSHFD, insnPtr);
2363
2364    base += (insnPtr - origInsnPtr);
2365
2366    return true;
2367 }
2368
2369 bool process::emitInferiorRPCtrailer(void *void_insnPtr, unsigned &base,
2370                                      unsigned &breakOffset,
2371                                      bool shouldStopForResult,
2372                                      unsigned &stopForResultOffset,
2373                                      unsigned &justAfter_stopForResultOffset) {
2374    unsigned char *insnPtr = (unsigned char *)void_insnPtr;
2375       // unsigned char * is the most natural to work with on x86, since instructions
2376       // are always an integral # of bytes.  Besides, it makes the following line easy:
2377    insnPtr += base; // start off in the right spot
2378
2379    if (shouldStopForResult) {
2380       // illegal insn: 0x0f0b does the trick.
2381       stopForResultOffset = base;
2382       *insnPtr++ = 0x0f;
2383       *insnPtr++ = 0x0b;
2384       base += 2;
2385
2386       justAfter_stopForResultOffset = base;
2387    }
2388
2389    // Sequence: popfd, popad, leave (0xc9), call DYNINSTbreakPoint(), illegal
2390
2391    emitSimpleInsn(POPFD, insnPtr); // popfd
2392    emitSimpleInsn(POPAD, insnPtr); // popad
2393    emitSimpleInsn(LEAVE, insnPtr); // leave
2394    base += 3; // all simple insns are 1 byte
2395
2396    // We can't do a SIGTRAP since SIGTRAP is reserved in x86.
2397    // So we do a SIGILL instead.
2398    breakOffset = base;
2399    *insnPtr++ = 0x0f;
2400    *insnPtr++ = 0x0b;
2401    base += 2;
2402
2403    // Here, we should generate an illegal insn, or something.
2404    // A two-byte insn, 0x0f0b, should do the trick.  The idea is that
2405    // the code should never be executed.
2406    *insnPtr++ = 0x0f;
2407    *insnPtr++ = 0x0b;
2408    base += 2;
2409
2410    return true;
2411 }
2412
2413 // process::replaceFunctionCall
2414 //
2415 // Replace the function call at the given instrumentation point with a call to
2416 // a different function, or with a NOOP.  In order to replace the call with a
2417 // NOOP, pass NULL as the parameter "func."
2418 // Returns true if sucessful, false if not.  Fails if the site is not a call
2419 // site, or if the site has already been instrumented using a base tramp.
2420 //
2421 // Note that right now we can only replace a call instruction that is five
2422 // bytes long (like a call to a 32-bit relative address).
2423 bool process::replaceFunctionCall(const instPoint *point,
2424                                   const function_base *func) {
2425     // Must be a call site
2426     if (!point->insnAtPoint().isCall())
2427         return false;
2428
2429     // Cannot already be instrumented with a base tramp
2430     if (baseMap.defines(point))
2431         return false;
2432
2433     // Replace the call
2434     if (func == NULL) { // Replace with NOOPs
2435         unsigned char *newInsn = new unsigned char[point->insnAtPoint().size()];
2436         unsigned char *p = newInsn;
2437         for (int i = 0; i < point->insnAtPoint().size(); i++)
2438             emitSimpleInsn(NOP, p);
2439         writeTextSpace((void *)point->iPgetAddress(),
2440                        point->insnAtPoint().size(), newInsn);
2441     } else { // Replace with a call to a different function
2442         // XXX Right only, call has to be 5 bytes -- sometime, we should make
2443         // it work for other calls as well.
2444         assert(point->insnAtPoint().size() == CALL_REL32_SZ);
2445         unsigned char *newInsn = new unsigned char[CALL_REL32_SZ];
2446         unsigned char *p = newInsn;
2447         emitCallRel32(func->addr() - (point->iPgetAddress()+CALL_REL32_SZ), p);
2448         writeTextSpace((void *)point->iPgetAddress(), CALL_REL32_SZ, newInsn);
2449     }
2450
2451     return true;
2452 }