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