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