initial dyninstAPI commit for code coverage
[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  * $Id: inst-x86.C,v 1.91 2001/09/07 21:15:08 tikir Exp $
45  */
46
47 #include <iomanip.h>
48
49 #include <limits.h>
50 #include "common/h/headers.h"
51
52 #ifndef BPATCH_LIBRARY
53 #include "rtinst/h/rtinst.h"
54 #endif
55 #include "common/h/Dictionary.h"
56 #include "dyninstAPI/src/symtab.h"
57 #include "dyninstAPI/src/process.h"
58 #include "dyninstAPI/src/inst.h"
59 #include "dyninstAPI/src/instP.h"
60 #include "dyninstAPI/src/ast.h"
61 #include "dyninstAPI/src/util.h"
62 #include "dyninstAPI/src/stats.h"
63 #include "dyninstAPI/src/os.h"
64 #include "dyninstAPI/src/showerror.h"
65
66 #include "dyninstAPI/src/arch-x86.h"
67 #include "dyninstAPI/src/inst-x86.h"
68 #include "dyninstAPI/src/instPoint.h" // includes instPoint-x86.h
69 #include "dyninstAPI/src/instP.h" // class returnInstance
70
71 // for function relocation
72 #include "dyninstAPI/src/func-reloc.h" 
73 #include "dyninstAPI/src/LocalAlteration.h"
74
75 class ExpandInstruction;
76 class InsertNops;
77
78 extern bool relocateFunction(process *proc, instPoint *&location);
79 extern void modifyInstPoint(instPoint *&location,process *proc);
80
81 extern bool isPowerOf2(int value, int &result);
82 void BaseTrampTrapHandler(int); //siginfo_t*, ucontext_t*);
83
84
85 // The general machine registers. 
86 // These values are taken from the Pentium manual and CANNOT be changed.
87 #undef EAX 
88 #define EAX (0)
89 #undef ECX
90 #define ECX (1)
91 #undef EDX
92 #define EDX (2)
93 #undef EBX
94 #define EBX (3)
95 #undef ESP
96 #define ESP (4)
97 #undef EBP
98 #define EBP (5)
99 #undef ESI
100 #define ESI (6)
101 #undef EDI
102 #define EDI (7)
103
104 // Size of a jump rel32 instruction
105 #define JUMP_REL32_SZ (5)
106 #define JUMP_SZ (5)
107 // Size of a call rel32 instruction
108 #define CALL_REL32_SZ (5)
109
110 #define PUSH_RM_OPC1 (0xFF)
111 #define PUSH_RM_OPC2 (6)
112 #define CALL_RM_OPC1 (0xFF)
113 #define CALL_RM_OPC2 (2)
114 #define PUSH_EBP (0x50+EBP)
115 #define SUB_REG_IMM32 (5)
116 #define LEAVE (0xC9)
117
118 /*
119    Function arguments are in the stack and are addressed with a displacement
120    from EBP. EBP points to the saved EBP, EBP+4 is the saved return address,
121    EBP+8 is the first parameter.
122    TODO: what about far calls?
123  */
124
125 #define PARAM_OFFSET (8)
126
127
128 // number of virtual registers
129 #define NUM_VIRTUAL_REGISTERS (32)
130
131 // offset from EBP of the saved EAX for a tramp
132 #define SAVED_EAX_OFFSET (-NUM_VIRTUAL_REGISTERS*4-4)
133
134 /****************************************************************************/
135 /****************************************************************************/
136 /****************************************************************************/
137
138 class NonRecursiveTrampTemplate : public trampTemplate
139 {
140
141 public:
142
143   int guardOnPre_beginOffset;
144   int guardOnPre_endOffset;
145
146   int guardOffPre_beginOffset;
147   int guardOffPre_endOffset;
148
149   int guardOnPost_beginOffset;
150   int guardOnPost_endOffset;
151
152   int guardOffPost_beginOffset;
153   int guardOffPost_endOffset;
154
155 };
156
157 /****************************************************************************/
158 /****************************************************************************/
159 /****************************************************************************/
160
161 void emitOpRMImm8( unsigned opcode1, unsigned opcode2, Register base, int disp, char imm,
162                    unsigned char * & insn );
163 void emitMovImmToMem( Address maddr, int imm,
164                       unsigned char * & insn );
165
166 /****************************************************************************/
167 /****************************************************************************/
168 /****************************************************************************/
169
170 /*
171    checkInstructions: check that there are no known jumps to the instructions
172    before and after the point.
173 */
174 void instPoint::checkInstructions() {
175   Address currAddr = addr_;
176   unsigned OKinsns = 0;
177
178   // if jumpAddr_ is not zero, this point has been checked already
179   if (jumpAddr_) 
180     return;
181
182   unsigned tSize;
183   unsigned maxSize = JUMP_SZ;
184   if (address() == func()->getAddress(0)) // entry point
185     maxSize = 2*JUMP_SZ;
186   tSize = insnAtPoint_.size();
187
188   if (!owner()->isJumpTarget(currAddr)) {
189     // check instructions before point
190     unsigned insnsBefore_ = insnsBefore();
191     for (unsigned u = 0; u < insnsBefore_; u++) {
192       OKinsns++;
193       tSize += (*insnBeforePt_)[u].size();
194       currAddr -= (*insnBeforePt_)[u].size();
195       if (owner()->isJumpTarget(currAddr)) {
196         // must remove instruction from point
197         // fprintf(stderr, "check instructions point 0x%lx, jmp to 0x%lx\n",
198         //                addr,currAddr);
199         break;
200       }
201     }
202   }
203   if (insnBeforePt_)
204     (*insnBeforePt_).resize(OKinsns);
205
206   // this is the address where we insert the jump
207   jumpAddr_ = currAddr;
208
209   // check instructions after point
210   currAddr = addr_ + insnAtPoint_.size();
211   OKinsns = 0;
212   unsigned insnsAfter_ = insnsAfter();
213   for (unsigned u = 0; tSize < maxSize && u < insnsAfter_; u++) {
214     if (owner()->isJumpTarget(currAddr))
215       break;
216     OKinsns++;
217     unsigned size = (*insnAfterPt_)[u].size();
218     currAddr += size;
219     tSize += size;
220   }
221   if (insnAfterPt_)
222     (*insnAfterPt_).resize(OKinsns);
223   
224 #ifdef notdef
225   if (tSize < maxSize) {
226     tSize = insnAtPoint_.size();
227     jumpAddr_ = addr_;
228     if (insnBeforePt_) (*insnBeforePt_).resize(0);
229     if (insnAfterPt_) (*insnAfterPt_).resize(0);
230   }
231 #endif
232 }
233
234 /* PT is an instrumentation point.  ENTRY is the entry point for the
235    same function, and EXITS are the exit instrumentation points for
236    the function.  Returns true if this function supports an extra slot
237    and PT can use it. */
238 static bool
239 _canUseExtraSlot(const instPoint *pt, const instPoint *entry,
240                  const vector<instPoint*> &exits)
241 {
242      if (entry->size() < 2*JUMP_SZ)
243           return false;
244
245      // We get 10 bytes for the entry points, instead of the usual five,
246      // so that we have space for an extra jump. We can then insert a
247      // jump to the basetramp in the second slot of the base tramp
248      // and use a short 2-byte jump from the point to the second jump.
249      // We adopt the following rule: Only one point in the function
250      // can use the indirect jump, and this is the first return point
251      // with a size that is less than five bytes
252      bool canUse = false;
253      for (unsigned u = 0; u < exits.size(); u++)
254           if (exits[u] == pt) {
255                canUse = true;
256                break;
257           } else if (exits[u]->size() < JUMP_SZ)
258                return false;
259      if (!canUse)
260           return false;
261
262      /* The entry has a slot, the point can be used for a slot,
263         now see if the point can reach the slot. */
264      int displacement = entry->jumpAddr() + 5 - pt->jumpAddr();
265      assert(displacement < 0);
266      if (pt->size() >= 2 && (displacement-2) > SCHAR_MIN)
267           return true;
268      else
269           return false;
270 }
271
272 /*
273    Returns true if we can use the extra slot for a jump at the entry point
274    to insert a jump to a base tramp at this point.  */
275 bool instPoint::canUseExtraSlot(process *proc) const
276 {
277      return _canUseExtraSlot(this,
278                              func()->funcEntry(proc),
279                              func()->funcExits(proc));
280 }
281
282 /* ENTRY and EXITS are the entry and exit points of a function.  PT
283    must be a point in the same function.  Return true if PT requires a
284    trap to instrument. */
285 static bool
286 _usesTrap(const instPoint *pt,
287           const instPoint *entry,
288           const vector<instPoint*> &exits)
289 {
290      /* If this point is big enough to hold a 32-bit jump to any
291         basetramp, it doesn't need a trap. */
292      if (pt->size() >= JUMP_REL32_SZ)
293           return false;
294
295      /* If it can use the extra slot, it doesn't need a trap. */
296      if (_canUseExtraSlot(pt, entry, exits)) {
297           return false;
298      }
299      /* Otherwise it needs a trap. */
300      return true;
301 }
302
303 bool instPoint::usesTrap(process *proc) const
304 {
305      return _usesTrap(this, func()->funcEntry(proc), func()->funcExits(proc));
306 }
307
308 /**************************************************************
309  *
310  *  machine dependent methods of pdFunction
311  *
312  **************************************************************/
313
314 // Determine if the called function is a "library" function or a "user" function
315 // This cannot be done until all of the functions have been seen, verified, and
316 // classified
317 //
318 void pd_Function::checkCallPoints() {
319   unsigned int i;
320   instPoint *p;
321   Address loc_addr;
322
323   vector<instPoint*> non_lib;
324
325   for (i=0; i<calls.size(); ++i) {
326     /* check to see where we are calling */
327     p = calls[i];
328     assert(p);
329
330     if (!p->insnAtPoint().isCallIndir()) {
331       loc_addr = p->insnAtPoint().getTarget(p->address());
332       file()->exec()->addJumpTarget(loc_addr);
333       pd_Function *pdf = (file_->exec())->findFuncByAddr(loc_addr);
334
335       if (pdf) {
336         p->set_callee(pdf);
337         non_lib.push_back(p);
338       } else {
339            // if this is a call outside the fuction, keep it
340            if((loc_addr < getAddress(0))||(loc_addr > (getAddress(0)+size()))){
341                 non_lib.push_back(p);
342            }
343            else {
344                delete p;
345            }
346       } 
347     } else {
348       // Indirect call -- be conservative, assume it is a call to
349       // an unnamed user function
350       //assert(!p->callee());
351       p->set_callee(NULL);
352       non_lib.push_back(p);
353     }
354   }
355   calls = non_lib;
356
357 }
358
359 // this function is not needed
360 Address pd_Function::newCallPoint(Address, const instruction,
361                                  const image *, bool &)
362 { assert(0); return 0; }
363
364
365 // see if we can recognize a jump table and skip it
366 // return the size of the table in tableSz.
367 bool checkJumpTable(image *im, instruction insn, Address addr, 
368                     Address funcBegin, 
369                     Address &funcEnd,
370                     unsigned &tableSz) {
371
372   const unsigned char *instr = insn.ptr();
373   tableSz = 0;
374   /*
375      the instruction usually used for jump tables is 
376        jmp dword ptr [REG*4 + ADDR]
377      where ADDR is an immediate following the SIB byte.
378      The opcode is 0xFF and the MOD/RM byte is 0x24. 
379      The SS field (bits 7 and 6) of SIB is 2, and the
380      base ( bits 2, 1, 0) is 5. The index bits (5,4,3) 
381      select the register.
382   */
383   if (instr[0] == 0xFF && instr[1] == 0x24 &&
384       ((instr[2] & 0xC0)>>6) == 2 && (instr[2] & 0x7) == 5) {
385     const Address tableBase = *(const Address *)(instr+3);
386     //fprintf(stderr, "Found jump table at 0x%lx 0x%lx\n",addr, tableBase);
387     // check if the table is right after the jump and inside the current function
388     if (tableBase > funcBegin && tableBase < funcEnd) {
389       // table is within function code
390       if (tableBase < addr+insn.size()) {
391         fprintf(stderr, "bad indirect jump at 0x%lx\n", addr);
392         return false;
393       } else if (tableBase > addr+insn.size()) {
394         // jump table may be at the end of the function code - adjust funcEnd
395         funcEnd = tableBase;
396         return true;
397       }
398       // skip the jump table
399       for (const unsigned *ptr = (const unsigned *)im->getPtrToInstruction(tableBase);
400            *ptr >= funcBegin && *ptr <= funcEnd; ptr++) {
401         //fprintf(stderr, " jump table entry = 0x%lx\n", *(unsigned *)ptr);
402         tableSz += sizeof(int);
403       }
404     }
405     else {
406         // fprintf(stderr, "Ignoring external jump table at 0x%lx.\n", tableBase);
407     }
408   }
409   return true;
410 }
411
412 void checkIfRelocatable(instruction insn, bool &canBeRelocated) {
413   const unsigned char *instr = insn.ptr();
414
415   // Check if REG bits of ModR/M byte are 100 or 101 (Possible jump 
416   // to jump table).
417   if (instr[0] == 0xFF && 
418      ( ((instr[1] & 0x38)>>3) == 4 || ((instr[1] & 0x38)>>3) == 5 )) {
419
420     // function should not be relocated
421     canBeRelocated = false;
422   }
423 }
424
425 /* auxiliary data structures for function findInstPoints */
426 enum { EntryPt, CallPt, ReturnPt };
427 class point_ {
428   public:
429      point_(): point(0), index(0), type(0) {};
430      point_(instPoint *p, unsigned i, unsigned t): point(p), index(i), type(t) {};
431      instPoint *point;
432      unsigned index;
433      unsigned type;
434 };
435
436
437 bool pd_Function::findInstPoints(const image *i_owner) {
438    // sorry this this hack, but this routine can modify the image passed in,
439    // which doesn't occur on other platforms --ari
440    image *owner = const_cast<image *>(i_owner); // const cast
441
442    if (size() == 0) {
443      //fprintf(stderr,"Function %s, size = %d\n", prettyName().string_of(), size());
444      return false;
445    }
446
447 #if defined(i386_unknown_solaris2_5)
448    /* On Solaris, this function is called when a signal handler
449       returns.  If it requires trap-based instrumentation, it can foul
450       the handler return mechanism.  So, better exclude it.  */
451    if (prettyName() == "_setcontext" || prettyName() == "setcontext")
452         return false;
453 #endif /* i386_unknown_solaris2_5 */
454
455 // XXXXX kludge: these functions are called by DYNINSTgetCPUtime, 
456 // they can't be instrumented or we would have an infinite loop
457 if (prettyName() == "gethrvtime" || prettyName() == "_divdi3"
458     || prettyName() == "GetProcessTimes")
459   return false;
460
461    point_ *points = new point_[size()];
462    //point_ *points = (point_ *)alloca(size()*sizeof(point));
463    unsigned npoints = 0;
464
465    const unsigned char *instr = (const unsigned char *)owner->getPtrToInstruction(getAddress(0));
466    Address adr = getAddress(0);
467    unsigned numInsns = 0;
468
469    instruction insn;
470    unsigned insnSize;
471
472    // keep a buffer with all the instructions in this function
473    instruction *allInstr = new instruction[size()+5];
474    //instruction *allInstr = (instruction *)alloca((size()+5)*sizeof(instruction));
475
476    // define the entry point
477    insnSize = insn.getNextInstruction(instr);
478    instPoint *p = new instPoint(this, owner, adr, insn);
479    funcEntry_ = p;
480    points[npoints++] = point_(p, numInsns, EntryPt);
481
482    // check if the entry point contains another point
483    if (insn.isJumpDir()) {
484      Address target = insn.getTarget(adr);
485      owner->addJumpTarget(target);
486      if (target < getAddress(0) || target >= getAddress(0) + size()) {
487        // jump out of function
488        // this is an empty function
489        delete [] points;
490        delete [] allInstr;
491        return false;
492      }
493    } else if (insn.isReturn()) {
494      // this is an empty function
495      delete [] points;
496      delete [] allInstr;
497      return false;
498    } else if (insn.isCall()) {
499      // TODO: handle calls at entry point
500      // call at entry point
501      //instPoint *p = new instPoint(this, owner, adr, insn);
502      //calls += p;
503      //points[npoints++] = point_(p, numInsns, CallPt);
504      //fprintf(stderr,"Function %s, call at entry point\n", prettyName().string_of());
505
506      delete [] points;
507      delete [] allInstr;
508      return false;
509    }
510
511    allInstr[numInsns] = insn;
512    numInsns++;
513    instr += insnSize;
514    adr += insnSize;
515
516    // get all the instructions for this function, and define the instrumentation
517    // points. For now, we only add one instruction to each point.
518    // Additional instructions, for the points that need them, will be added later.
519
520 #ifdef BPATCH_LIBRARY
521    if (BPatch::bpatch->hasForcedRelocation_NP()) {
522      relocatable_ = true;
523    }
524 #endif
525
526    // checkJumpTable will set canBeRelocated = false if their is a jump to a 
527    // jump table inside this function. 
528    bool canBeRelocated = true;
529
530    Address funcEnd = getAddress(0) + size();
531    for ( ; adr < funcEnd; instr += insnSize, adr += insnSize) {
532      insnSize = insn.getNextInstruction(instr);
533      assert(insnSize > 0);
534
535      if (adr + insnSize > funcEnd) {
536        break;
537      }
538
539      if (insn.isJumpIndir()) {
540        unsigned jumpTableSz;
541
542        // check if function should be allowed to be relocated
543        checkIfRelocatable(insn, canBeRelocated);
544
545        // check for jump table. This may update funcEnd
546        if (!checkJumpTable(owner, insn, adr, getAddress(0), funcEnd, jumpTableSz)) {
547          delete points;
548          delete allInstr;
549          //fprintf(stderr,"Function %s, size = %d, bad jump table\n", 
550          //          prettyName().string_of(), size());
551          return false;
552        }
553
554        // process the jump instruction
555        allInstr[numInsns] = insn;
556        numInsns++;
557
558        if (jumpTableSz > 0) {
559          // skip the jump table
560          // insert an illegal instruction with the size of the jump table
561          insn = instruction(instr, ILLEGAL, jumpTableSz);
562          allInstr[numInsns] = insn;
563          numInsns++;
564          insnSize += jumpTableSz;
565        }
566      } else if (insn.isJumpDir()) {
567        // check for jumps out of this function
568        Address target = insn.getTarget(adr);
569        owner->addJumpTarget(target);
570        if (target < getAddress(0) || target >= getAddress(0) + size()) {
571          // jump out of function
572          instPoint *p = new instPoint(this, owner, adr, insn);
573          funcReturns.push_back(p);
574          points[npoints++] = point_(p, numInsns, ReturnPt);
575        } 
576      } else if (insn.isReturn()) {
577        instPoint *p = new instPoint(this, owner, adr, insn);
578        funcReturns.push_back(p);
579        points[npoints++] = point_(p, numInsns, ReturnPt);
580
581      } else if (insn.isCall()) {
582        // calls to adr+5 are not really calls, they are used in dynamically linked
583        // libraries to get the address of the code.
584        // We skip them here.
585        if (insn.getTarget(adr) != adr + 5) {
586          instPoint *p = new instPoint(this, owner, adr, insn);
587          calls.push_back(p);
588          points[npoints++] = point_(p, numInsns, CallPt);
589        } else {
590            // Temporary: Currently we can't relocate a function if it
591            // contains a call to adr+5  
592            //canBeRelocated = false;
593        }
594      }
595
596      allInstr[numInsns] = insn;
597      numInsns++;
598      assert(npoints < size());
599      assert(numInsns <= size());
600    }
601
602    unsigned u;
603    // there are often nops after the end of the function. We get them here,
604    // since they may be usefull to instrument the return point
605    for (u = 0; u < 4; u++) {
606      if (owner->isValidAddress(adr)) {
607        insnSize = insn.getNextInstruction(instr);
608        if (insn.isNop()) {
609          allInstr[numInsns] = insn;
610          numInsns++;
611          assert(numInsns < size()+5);
612          instr += insnSize;
613          adr += insnSize;
614        }
615        else
616          break;
617      }
618    }
619
620
621    // add extra instructions to the points that need it.
622    unsigned lastPointEnd = 0;
623    unsigned thisPointEnd = 0;
624    for (u = 0; u < npoints; u++) {
625      instPoint *p = points[u].point;
626      unsigned index = points[u].index;
627      unsigned type = points[u].type;
628      lastPointEnd = thisPointEnd;
629      thisPointEnd = index;
630
631      // add instructions before the point
632      unsigned size = p->size();
633      for (int u1 = index-1; size < JUMP_SZ && u1 >= 0 && u1 > (int)lastPointEnd; u1--) {
634        if (!allInstr[u1].isCall()) {
635          p->addInstrBeforePt(allInstr[u1]);
636          size += allInstr[u1].size();
637        } else
638          break;
639      }
640
641      lastPointEnd = index;
642
643      // add instructions after the point
644      if (type == ReturnPt && p->address() == funcEnd-1) {
645
646        /* If an instrumentation point at the end of the function does
647           not end on a 4-byte boundary, we claim the bytes up to the
648           next 4-byte boundary as "bonus bytes" for the point, since
649           the next function will (should) begin at or past the
650           boundary.  We tried 8 byte boundaries and found some
651           functions did not begin on 8-byte aligned addresses, so 8 is
652           unsafe. */
653        unsigned bonus;
654 #ifndef i386_unknown_nt4_0
655        bonus = (funcEnd % 4) ? (4 - (funcEnd % 4)) : 0;
656 #else
657        /* Unfortunately, the Visual C++ compiler generates functions
658           that begin at unaligned boundaries, so forget this scheme on
659           NT. */
660        bonus = 0;
661 #endif /* i386_unknown_nt4_0 */
662        //p->setBonusBytes(bonus);
663        unsigned u1;
664        for (u1 = index+1 + bonus; u1 < index+JUMP_SZ-1 && u1 < numInsns; u1++) {
665          if (allInstr[u1].isNop() || *(allInstr[u1].ptr()) == 0xCC) {
666            //p->addInstrAfterPt(allInstr[u1]);
667            bonus++;
668            thisPointEnd = u1;
669          }
670          else 
671            break;
672        }
673        p->setBonusBytes(bonus);
674      } else if (type == ReturnPt) {
675        // normally, we would not add instructions after the return, but the 
676        // compilers often add nops after the return, and we can use them if necessary
677        for (unsigned u1 = index+1; u1 < index+JUMP_SZ-1 && u1 < numInsns; u1++) {
678          if (allInstr[u1].isNop() || *(allInstr[u1].ptr()) == 0xCC) {
679            p->addInstrAfterPt(allInstr[u1]);
680            thisPointEnd = u1;
681          }
682          else 
683            break;
684        }
685      } else {
686        size = p->size();
687        unsigned maxSize = JUMP_SZ;
688        if (type == EntryPt) maxSize = 2*JUMP_SZ;
689        for (unsigned u1 = index+1; size < maxSize && u1 <= numInsns; u1++) {
690          if (((u+1 == npoints) || (u+1 < npoints && points[u+1].index > u1))
691              && !allInstr[u1].isCall()) {
692            p->addInstrAfterPt(allInstr[u1]);
693            size += allInstr[u1].size();
694            thisPointEnd = u1;
695          }
696          else 
697            break;
698        }
699      }
700    }
701
702
703    for (u = 0; u < npoints; u++)
704         points[u].point->checkInstructions();
705
706    // create and sort vector of instPoints
707    vector<instPoint*> foo;
708    sorted_ips_vector(foo);
709
710    for (unsigned i=0;i<foo.size();i++) {
711
712      if (_usesTrap(foo[i], funcEntry_, funcReturns) && size() >= 5) {
713        relocatable_ = true;
714      }
715    }
716
717    // if the function contains a jump to a jump table, we can't relocate
718    // the function 
719    if ( !canBeRelocated ) {
720
721      // Function would have needed relocation 
722      if (relocatable_ == true) {
723
724 #ifdef DEBUG_FUNC_RELOC      
725        cerr << prettyName() << endl;
726        cerr << "Jump Table: Can't relocate function" << endl;
727 #endif
728
729        relocatable_ = false;
730      }
731    }
732
733    delete [] points;
734    delete [] allInstr;
735
736    return true;
737 }
738
739
740 /*
741  * Given an instruction, relocate it to a new address, patching up
742  *   any relative addressing that is present.
743  * The instruction may need to be replaced with a different size instruction
744  * or with multiple instructions.
745  * Return the size of the new instruction(s)
746  */
747 unsigned relocateInstruction(instruction insn,
748                          int origAddr, int newAddr,
749                          unsigned char *&newInsn)
750 {
751   /* 
752      Relative address instructions need to be modified. The relative address
753      can be a 8, 16, or 32-byte displacement relative to the next instruction.
754      Since we are relocating the instruction to a different area, we have
755      to replace 8 and 16-byte displacements with 32-byte displacements.
756
757      All relative address instructions are one or two-byte opcode followed
758      by a displacement relative to the next instruction:
759
760        CALL rel16 / CALL rel32
761        Jcc rel8 / Jcc rel16 / Jcc rel32
762        JMP rel8 / JMP rel16 / JMP rel32
763
764      The only two-byte opcode instructions are the Jcc rel16/rel32,
765      all others have one byte opcode.
766
767      The instruction JCXZ/JECXZ rel8 does not have an equivalent with rel32
768      displacement. We must generate code to emulate this instruction:
769      
770        JCXZ rel8
771
772      becomes
773
774        A0: JCXZ 2 (jump to A4)
775        A2: JMP 5  (jump to A9)
776        A4: JMP rel32 (relocated displacement)
777        A9: ...
778
779   */
780
781   const unsigned char *origInsn = insn.ptr();
782   unsigned insnType = insn.type();
783   unsigned insnSz = insn.size();
784   unsigned char *first = newInsn;
785
786   int oldDisp;
787   int newDisp;
788
789   if (insnType & REL_B) {
790     /* replace with rel32 instruction, opcode is one byte. */
791     if (*origInsn == JCXZ) {
792       oldDisp = (int)*(const char *)(origInsn+1);
793       newDisp = (origAddr + 2) + oldDisp - (newAddr + 9);
794       *newInsn++ = *origInsn; *(newInsn++) = 2; // jcxz 2
795       *newInsn++ = 0xEB; *newInsn++ = 5;        // jmp 5
796       *newInsn++ = 0xE9;                        // jmp rel32
797       *((int *)newInsn) = newDisp;
798       newInsn += sizeof(int);
799     }
800     else {
801       unsigned newSz=UINT_MAX;
802       if (insnType & IS_JCC) {
803         /* Change a Jcc rel8 to Jcc rel32. 
804            Must generate a new opcode: a 0x0F followed by (old opcode + 16) */
805         unsigned char opcode = *origInsn++;
806         *newInsn++ = 0x0F;
807         *newInsn++ = opcode + 0x10;
808         newSz = 6;
809       }
810       else if (insnType & IS_JUMP) {
811         /* change opcode to 0xE9 */
812         origInsn++;
813         *newInsn++ = 0xE9;
814         newSz = 5;
815       }
816       assert(newSz!=UINT_MAX);
817       oldDisp = (int)*(const char *)origInsn;
818       newDisp = (origAddr + 2) + oldDisp - (newAddr + newSz);
819       *((int *)newInsn) = newDisp;
820       newInsn += sizeof(int);
821     }
822   }
823   else if (insnType & REL_W) {
824     /* Skip prefixes */
825     if (insnType & PREFIX_OPR)
826       origInsn++;
827     if (insnType & PREFIX_SEG)
828       origInsn++;
829     /* opcode is unchanged, just relocate the displacement */
830     if (*origInsn == (unsigned char)0x0F)
831       *newInsn++ = *origInsn++;
832     *newInsn++ = *origInsn++;
833     oldDisp = *((const short *)origInsn);
834     newDisp = (origAddr + 5) + oldDisp - (newAddr + 3);
835     *((int *)newInsn) = newDisp;
836     newInsn += sizeof(int);
837   } else if (insnType & REL_D) {
838     // Skip prefixes
839     unsigned nPrefixes = 0;
840     if (insnType & PREFIX_OPR)
841       nPrefixes++;
842     if (insnType & PREFIX_SEG)
843       nPrefixes++;
844     for (unsigned u = 0; u < nPrefixes; u++)
845       *newInsn++ = *origInsn++;
846
847     /* opcode is unchanged, just relocate the displacement */
848     if (*origInsn == 0x0F)
849       *newInsn++ = *origInsn++;
850     *newInsn++ = *origInsn++;
851     oldDisp = *((const int *)origInsn);
852     newDisp = (origAddr + insnSz) + oldDisp - (newAddr + insnSz);
853     *((int *)newInsn) = newDisp;
854     newInsn += sizeof(int);
855   }
856   else {
857     /* instruction is unchanged */
858     for (unsigned u = 0; u < insnSz; u++)
859       *newInsn++ = *origInsn++;
860   }
861
862   return (newInsn - first);
863 }
864
865
866 /*
867  * Relocate a conditional jump and change the target to newTarget.
868  * The new target must be within 128 bytes from the new address
869  * Size of instruction is unchanged.
870  * Returns the old target
871  */
872 unsigned changeConditionalJump(instruction insn,
873                          int origAddr, int newAddr, int newTargetAddr,
874                          unsigned char *&newInsn)
875 {
876
877   const unsigned char *origInsn = insn.ptr();
878   unsigned insnType = insn.type();
879   unsigned insnSz = insn.size();
880
881   int oldDisp=-1;
882   int newDisp;
883
884   if (insnType & REL_B) {
885     /* one byte opcode followed by displacement */
886     /* opcode is unchanged */
887     assert(insnSz==2);
888     *newInsn++ = *origInsn++;
889     oldDisp = (int)*(const char *)origInsn;
890     newDisp = newTargetAddr - (newAddr + insnSz);
891     *newInsn++ = (char)newDisp;
892   }
893   else if (insnType & REL_W) {
894     /* Skip prefixes */
895     if (insnType & PREFIX_OPR)
896       *newInsn++ = *origInsn++;
897     if (insnType & PREFIX_SEG)
898       *newInsn++ = *origInsn++;
899
900     assert(*origInsn==0x0F);
901     *newInsn++ = *origInsn++; // copy the 0x0F
902     *newInsn++ = *origInsn++; // second opcode byte
903
904     oldDisp = *((const short *)origInsn);
905     newDisp = newTargetAddr - (newAddr + insnSz);
906     *((short *)newInsn) = (short)newDisp;
907     newInsn += sizeof(short);
908   }
909   else if (insnType & REL_D) {
910     // Skip prefixes
911     if (insnType & PREFIX_OPR)
912       *newInsn++ = *origInsn++;
913     if (insnType & PREFIX_SEG)
914       *newInsn++ = *origInsn++;
915
916     assert(*origInsn==0x0F);
917     *newInsn++ = *origInsn++; // copy the 0x0F
918     *newInsn++ = *origInsn++; // second opcode byte
919
920     oldDisp = *((const int *)origInsn);
921     newDisp = newTargetAddr - (newAddr + insnSz);
922     *((int *)newInsn) = (int)newDisp;
923     newInsn += sizeof(int);
924   }
925
926   assert (oldDisp!=-1);
927   return (origAddr+insnSz+oldDisp);
928 }
929
930
931
932 unsigned getRelocatedInstructionSz(instruction insn)
933 {
934   const unsigned char *origInsn = insn.ptr();
935   unsigned insnType = insn.type();
936   unsigned insnSz = insn.size();
937
938   if (insnType & REL_B) {
939     if (*origInsn == JCXZ)
940       return 9;
941     else {
942       if (insnType & IS_JCC)
943         return 6;
944       else if (insnType & IS_JUMP) {
945         return 5;
946       }
947     }
948   }
949   else if (insnType & REL_W) {
950     return insnSz + 2;
951   }
952   return insnSz;
953 }
954
955
956 registerSpace *regSpace;
957
958
959 bool registerSpace::readOnlyRegister(Register) {
960   return false;
961 }
962
963 /*
964    We don't use the machine registers to store temporaries,
965    but "virtual registers" that are located on the stack.
966    The stack frame for a tramp is:
967
968      ebp->    saved ebp (4 bytes)
969      ebp-4:   128-byte space for 32 virtual registers (32*4 bytes)
970      ebp-132: saved registers (8*4 bytes)
971      ebp-164: saved flags registers (4 bytes)
972
973      The temporaries are assigned numbers from 1 so that it is easier
974      to refer to them: -(reg*4)[ebp]. So the first reg is -4[ebp].
975
976      We are using a fixed number of temporaries now (32), but we could 
977      change to using an arbitrary number.
978
979 */
980 Register deadList[NUM_VIRTUAL_REGISTERS];
981 int deadListSize = sizeof(deadList);
982
983 void initTramps()
984 {
985     static bool inited=false;
986
987     if (inited) return;
988     inited = true;
989
990 #if defined(SHM_SAMPLING) && defined(MT_THREAD)
991     for (unsigned u = 0; u < NUM_VIRTUAL_REGISTERS-1; u++) {
992 #else
993     for (unsigned u = 0; u < NUM_VIRTUAL_REGISTERS; u++) {
994 #endif
995       deadList[u] = u+1;
996     }
997
998     regSpace = new registerSpace(deadListSize/sizeof(Register), deadList,
999                                 0, NULL);
1000 }
1001
1002
1003 void emitJump(unsigned disp32, unsigned char *&insn);
1004 void emitSimpleInsn(unsigned opcode, unsigned char *&insn);
1005 void emitMovRegToReg(Register dest, Register src, unsigned char *&insn);
1006 void emitAddMemImm32(Address dest, int imm, unsigned char *&insn);
1007 void emitAddRegImm32(Register dest, int imm, unsigned char *&insn);
1008 void emitOpRegImm(int opcode, Register dest, int imm, unsigned char *&insn);
1009 void emitMovRegToRM(Register base, int disp, Register src, unsigned char *&insn);
1010 void emitMovRMToReg(Register dest, Register base, int disp, unsigned char *&insn);
1011 void emitCallRel32(unsigned disp32, unsigned char *&insn);
1012
1013
1014 /*
1015  * change the insn at addr to be a branch to newAddr.
1016  *   Used to add multiple tramps to a point.
1017  */
1018 void generateBranch(process *proc, Address fromAddr, Address newAddr)
1019 {
1020   unsigned char inst[JUMP_REL32_SZ+1];
1021   unsigned char *insn = inst;
1022   emitJump(newAddr - (fromAddr + JUMP_REL32_SZ), insn);
1023   proc->writeTextSpace((caddr_t)fromAddr, JUMP_REL32_SZ, (caddr_t)inst);
1024 }
1025
1026
1027 bool insertInTrampTable(process *proc, unsigned key, unsigned val) {
1028   unsigned u;
1029
1030   // check for overflow of the tramp table. 
1031   // stop at 95% capacicty to ensure good performance
1032   if (proc->trampTableItems == (TRAMPTABLESZ - TRAMPTABLESZ/20))
1033     return false;
1034   proc->trampTableItems++;
1035   for (u = HASH1(key); proc->trampTable[u].key != 0; 
1036        u = (u + HASH2(key)) % TRAMPTABLESZ)
1037     ;
1038   proc->trampTable[u].key = key;
1039   proc->trampTable[u].val = val;
1040
1041 #if !defined(i386_unknown_nt4_0)
1042   bool err = false;
1043   Address addr = proc->findInternalAddress("DYNINSTtrampTable",true, err);
1044   assert(err==false);
1045   return proc->writeDataSpace((caddr_t)addr+u*sizeof(trampTableEntry),
1046                        sizeof(trampTableEntry),
1047                        (caddr_t)&(proc->trampTable[u]));
1048 #else
1049   return true;
1050 #endif
1051 }
1052
1053 /* Generate a jump to a base tramp. Return the size of the instruction
1054    generated at the instrumentation point. */
1055 unsigned generateBranchToTramp(process *proc, const instPoint *point, 
1056                                Address baseAddr, Address imageBaseAddr,
1057                                unsigned char *insn, bool &deferred)
1058 {
1059      /* There are three ways to get to the base tramp:
1060         1. Ordinary 5-byte jump instruction.
1061         2. 2-byte jump to the extra slot in the entry point
1062         3. Trap instruction.
1063      */
1064
1065      /* Ordinary 5-byte jump */
1066      if (point->size() >= JUMP_REL32_SZ) {
1067           // replace instructions at point with jump to base tramp
1068           emitJump(baseAddr - (point->jumpAddr() + imageBaseAddr + JUMP_REL32_SZ), insn);
1069           return JUMP_REL32_SZ;
1070      } 
1071
1072      /* Extra slot */
1073      if (point->canUseExtraSlot(proc)) {
1074           pd_Function *f = point->func();
1075           const instPoint *the_entry = f->funcEntry(proc);
1076
1077           int displacement = the_entry->jumpAddr() + 5 - point->jumpAddr();
1078           assert(displacement < 0);
1079           assert((displacement-2) > SCHAR_MIN);
1080           assert(point->size() >= 2);
1081 #ifdef INST_TRAP_DEBUG
1082           cerr << "Using extra slot in entry of " << f->prettyName()
1083                << " to avoid need for trap @" << (void*)point->address() << endl;
1084 #endif
1085
1086           instPoint *nonConstEntry = const_cast<instPoint *>(the_entry);
1087           returnInstance *retInstance;
1088
1089           trampTemplate *entryBase =
1090               findAndInstallBaseTramp(proc, nonConstEntry,
1091                                       retInstance, false, false, deferred);
1092           assert(entryBase);
1093           if (retInstance) {
1094               retInstance->installReturnInstance(proc);
1095           }
1096           generateBranch(proc, the_entry->jumpAddr()+imageBaseAddr+5, baseAddr);
1097           *insn++ = 0xEB;
1098           *insn++ = (char)(displacement-2);
1099           return 2;
1100      } 
1101
1102      /* Trap */
1103 #ifdef INST_TRAP_DEBUG
1104      cerr << "Warning: unable to insert jump in function " 
1105           << point->func()->prettyName() << " @" << (void*)point->address()
1106           << ". Using trap!" << endl;
1107 #endif
1108      if (!insertInTrampTable(proc, point->jumpAddr()+imageBaseAddr, baseAddr))
1109           return 0;
1110      *insn++ = 0xCC;
1111      return 1;
1112 }
1113
1114 /****************************************************************************/
1115 /****************************************************************************/
1116 /****************************************************************************/
1117
1118 #if defined(i386_unknown_solaris2_5) || \
1119     defined(i386_unknown_linux2_0) || \
1120     defined(i386_unknown_nt4_0)
1121 int guard_code_before_pre_instr_size  = 19; /* size in bytes */
1122 int guard_code_after_pre_instr_size   = 10; /* size in bytes */
1123 int guard_code_before_post_instr_size = 19; /* size in bytes */
1124 int guard_code_after_post_instr_size  = 10; /* size in bytes */
1125 #else
1126 int guard_code_before_pre_instr_size  = 0; /* size in bytes */
1127 int guard_code_after_pre_instr_size   = 0; /* size in bytes */
1128 int guard_code_before_post_instr_size = 0; /* size in bytes */
1129 int guard_code_after_post_instr_size  = 0; /* size in bytes */
1130 #endif
1131
1132 /****************************************************************************/
1133 /****************************************************************************/
1134 /****************************************************************************/
1135
1136 unsigned int get_guard_code_size() /* total size in bytes of the four
1137                                       guard code fragments*/
1138 {
1139   return
1140     guard_code_before_pre_instr_size +
1141     guard_code_after_pre_instr_size +
1142     guard_code_before_post_instr_size +
1143     guard_code_after_post_instr_size;
1144 }
1145
1146 /****************************************************************************/
1147 /****************************************************************************/
1148 /****************************************************************************/
1149
1150 void emitJccR8( int condition_code,
1151                 char jump_offset,
1152                 unsigned char * & instruction )
1153 {
1154   *instruction++ = condition_code;
1155   *instruction++ = jump_offset;
1156 }
1157
1158 /****************************************************************************/
1159 /****************************************************************************/
1160 /****************************************************************************/
1161
1162 #if defined(i386_unknown_solaris2_5) || \
1163     defined(i386_unknown_linux2_0) || \
1164     defined(i386_unknown_nt4_0)
1165 void generate_guard_code( unsigned char * buffer,
1166                           const NonRecursiveTrampTemplate & base_template,
1167                           Address /* base_address */,
1168                           Address guard_flag_address )
1169 {
1170   unsigned char * instruction;
1171
1172   /* guard-on code before pre instr */
1173   /* Code generated:
1174    * --------------
1175    * cmpl   $0x0, (guard flag address)
1176    * je     <after guard-off code>
1177    * movl   $0x0, (guard flag address)
1178    */
1179   instruction = buffer + base_template.guardOnPre_beginOffset;
1180   /*            CMP_                       (memory address)__  0 */
1181   emitOpRMImm8( 0x83, 0x07, Null_Register, guard_flag_address, 0, instruction );
1182   emitJccR8( JE_R8, buffer + base_template.guardOffPre_endOffset - ( instruction + 2 ), instruction );
1183   emitMovImmToMem( guard_flag_address, 0, instruction );
1184
1185   /* guard-off code after pre instr */
1186   /* Code generated:
1187    * --------------
1188    * movl   $0x1, (guard flag address)
1189    */
1190   instruction = buffer + base_template.guardOffPre_beginOffset;
1191   emitMovImmToMem( guard_flag_address, 1, instruction );
1192
1193   /* guard-on code before post instr */
1194   instruction = buffer + base_template.guardOnPost_beginOffset;
1195   emitOpRMImm8( 0x83, 0x07, Null_Register, guard_flag_address, 0x00, instruction );
1196   emitJccR8( JE_R8, buffer + base_template.guardOffPost_endOffset - ( instruction + 2 ), instruction );
1197   emitMovImmToMem( guard_flag_address, 0, instruction );
1198
1199   /* guard-off code after post instr */
1200   instruction = buffer + base_template.guardOffPost_beginOffset;
1201   emitMovImmToMem( guard_flag_address, 1, instruction );
1202 }
1203 #else
1204 void generate_guard_code( unsigned char * /* buffer */,
1205                           const NonRecursiveTrampTemplate & /* base_template */,
1206                           Address /* base_address */,
1207                           Address /* guard_flag_address */ )
1208 {
1209 }
1210 #endif
1211
1212 /****************************************************************************/
1213 /****************************************************************************/
1214 /****************************************************************************/
1215
1216 /*
1217  * Install a base tramp, relocating the instructions at location
1218  * The pre and post jumps are filled with a 'jump 0'
1219  * Return a descriptor for the base tramp.
1220  *
1221  */
1222
1223 trampTemplate *installBaseTramp( const instPoint *location,
1224                                  process *proc,
1225                                  bool noCost,
1226                                  bool trampRecursiveDesired = true
1227                                  ) 
1228 {  
1229    bool aflag;
1230   
1231 /*
1232    The base tramp:
1233    addr   instruction             cost
1234    0:    <relocated instructions before point>
1235    a = size of relocated instructions before point
1236    a+0:   jmp a+30 <skip pre insn>  1
1237    a+5:   push ebp                  1
1238    a+6:   mov esp, ebp              1
1239    a+8:   subl esp, 0x80            1
1240    a+14:  pushad                    5
1241    a+15:  pushaf                    9
1242    a+16:  jmp <global pre inst>     1
1243    a+21:  jmp <local pre inst>      1
1244    a+26:  popaf                    14
1245    a+27:  popad                     5
1246    a+28:  leave                     3
1247    a+29:  add costAddr, cost        3
1248    a+39:  <relocated instructions at point>
1249
1250    b = a +30 + size of relocated instructions at point
1251    b+0:   jmp b+30 <skip post insn>
1252    b+5:   push ebp
1253    b+6:   mov esp, ebp
1254    b+8:   subl esp, 0x80
1255    b+14:  pushad
1256    b+15:  pushaf
1257    b+16:  jmp <global post inst>
1258    b+21:  jmp <local post inst>
1259    b+26:  popaf
1260    b+27:  popad
1261    b+28:  leave
1262    b+29:  <relocated instructions after point>
1263
1264    c:     jmp <return to user code>
1265
1266    tramp size = 2*23 + 10 + 5 + size of relocated instructions
1267    Make sure to update the size if the tramp is changed
1268
1269    cost of pre and post instrumentation is (1+1+1+5+9+1+1+15+5+3) = 42
1270    cost of rest of tramp is (1+3+1+1)
1271
1272    [mihai Wed Apr 12 00:22:03 CDT 2000]
1273      Additionally, if a guarded template is generated
1274      (i.e. trampRecursiveDesired = false), four more code fragments are inserted:
1275      - code to turn the guard on (19 bytes): between a+15 and a+16, and
1276                                              between b+15 and b+16
1277      - code to turn the guard off (10 bytes): between a+21 and a+26, and
1278                                               between b+21 and b+26
1279      A total of 58 bytes are added to the base tramp.
1280 */
1281
1282   unsigned u;
1283   trampTemplate *ret = 0;
1284   if( trampRecursiveDesired )
1285     {
1286       ret = new trampTemplate;
1287     }
1288   else
1289     {
1290       ret = new NonRecursiveTrampTemplate;
1291     }
1292   ret->trampTemp = 0;
1293
1294   unsigned jccTarget = 0; // used when the instruction at the point is a cond. jump
1295   unsigned auxJumpOffset = 0;
1296
1297   // compute the tramp size
1298   // if there are any changes to the tramp, the size must be updated.
1299 #if defined(SHM_SAMPLING) && defined(MT_THREAD)
1300   unsigned trampSize = 73+2*27 + 66;
1301 #else
1302   unsigned trampSize = 73;
1303 #endif
1304
1305   if( ! trampRecursiveDesired )
1306     {
1307       trampSize += get_guard_code_size();   // NOTE-131 with Relocation
1308     }
1309
1310   for (u = 0; u < location->insnsBefore(); u++) {
1311     trampSize += getRelocatedInstructionSz(location->insnBeforePt(u));
1312   }
1313   if (location->insnAtPoint().type() & IS_JCC)
1314     trampSize += location->insnAtPoint().size() + 2 * JUMP_SZ;
1315   else
1316     trampSize += getRelocatedInstructionSz(location->insnAtPoint());
1317   for (u = 0; u < location->insnsAfter(); u++) {
1318     trampSize += getRelocatedInstructionSz(location->insnAfterPt(u));
1319   }
1320
1321   Address imageBaseAddr;
1322   if (!proc->getBaseAddress(location->owner(), imageBaseAddr)) {
1323     abort();
1324   }
1325
1326   Address costAddr = 0; // for now...
1327   if (!noCost) {
1328 #ifdef SHM_SAMPLING
1329      costAddr = (Address)proc->getObsCostLowAddrInApplicSpace();
1330      assert(costAddr);
1331 #else
1332      // get address of DYNINSTobsCostLow to update observed cost
1333      bool err = false;
1334      costAddr = proc->findInternalAddress("DYNINSTobsCostLow",
1335                                           true, err);
1336      assert(costAddr && !err);
1337 #endif
1338   }
1339
1340   ret->size = trampSize;
1341   Address baseAddr = inferiorMalloc(proc, trampSize, textHeap);
1342   // cout << "installBaseTramp(): trampoline base address = 0x"
1343   //      << setw( 8 ) << setfill( '0' ) << hex << baseAddr << dec << endl;
1344   ret->baseAddr = baseAddr;
1345
1346   unsigned char *code = new unsigned char[2*trampSize];
1347   unsigned char *insn = code;
1348   Address currAddr = baseAddr;
1349
1350   // get the current instruction that is being executed. If the PC is at a
1351   // instruction that is being relocated, we must change the PC.
1352   Address currentPC = proc->currentPC();
1353
1354   // emulate the instructions before the point
1355   Address origAddr = location->jumpAddr() + imageBaseAddr;
1356   for (u = location->insnsBefore(); u > 0; ) {
1357     --u;
1358     if (currentPC == origAddr) {
1359       //fprintf(stderr, "changed PC: 0x%lx to 0x%lx\n", currentPC, currAddr);
1360       proc->setNewPC(currAddr);
1361     }
1362
1363     unsigned newSize = relocateInstruction(location->insnBeforePt(u), origAddr, currAddr, insn);
1364     aflag=(newSize == getRelocatedInstructionSz(location->insnBeforePt(u)));
1365     assert(aflag);
1366     currAddr += newSize;
1367     origAddr += location->insnBeforePt(u).size();
1368   }
1369
1370
1371   /***
1372     If the instruction at the point is a conditional jump, we relocate it to
1373     the top of the base tramp, and change the code so that the tramp is executed
1374     only if the branch is taken.
1375
1376     e.g.
1377      L1:  jne target
1378      L2:  ...
1379
1380     becomes
1381
1382           jne T1
1383           jmp T2
1384           jne
1385      T1:  ...
1386
1387      T2:  relocated instructions after point
1388
1389      then later at the base tramp, at the point where we relocate the instruction
1390      at the point, we insert a jump to target
1391   ***/
1392   if (location->insnAtPoint().type() & IS_JCC) {
1393      currAddr = baseAddr + (insn - code);
1394      assert(origAddr == location->address() + imageBaseAddr);
1395      origAddr = location->address() + imageBaseAddr;
1396      if (currentPC == origAddr &&
1397          currentPC != (location->jumpAddr() + imageBaseAddr)) {
1398        //fprintf(stderr, "changed PC: 0x%lx to 0x%lx\n", currentPC, currAddr);
1399        proc->setNewPC(currAddr);
1400      }
1401
1402      jccTarget = changeConditionalJump(location->insnAtPoint(), origAddr, currAddr,
1403                                        currAddr+location->insnAtPoint().size()+5, insn);
1404      currAddr += location->insnAtPoint().size();
1405      auxJumpOffset = insn-code;
1406      emitJump(0, insn);
1407      origAddr += location->insnAtPoint().size();
1408   }
1409
1410   // pre branches
1411   // skip pre instrumentation
1412   ret->skipPreInsOffset = insn-code;
1413   emitJump(0, insn);
1414
1415   // save registers and create a new stack frame for the tramp
1416   ret->savePreInsOffset = insn-code;
1417   emitSimpleInsn(PUSH_EBP, insn);  // push ebp
1418   emitMovRegToReg(EBP, ESP, insn); // mov ebp, esp  (2-byte instruction)
1419   // allocate space for temporaries (virtual registers)
1420   emitOpRegImm(5, ESP, 128, insn); // sub esp, 128
1421   emitSimpleInsn(PUSHAD, insn);    // pushad
1422   emitSimpleInsn(PUSHFD, insn);    // pushfd
1423
1424 #if defined(SHM_SAMPLING) && defined(MT_THREAD)
1425   // generate preamble for MT version
1426   Address base=0;
1427   generateMTpreamble((char *)insn, base, proc);
1428   insn += base;
1429 #endif
1430
1431   if( ! trampRecursiveDesired )
1432     {
1433       NonRecursiveTrampTemplate * temp_ret = ( NonRecursiveTrampTemplate * )ret;
1434       temp_ret->guardOnPre_beginOffset = insn - code;
1435       for( int i = 0; i < guard_code_before_pre_instr_size; i++ )
1436         emitSimpleInsn( 0x90, insn );
1437       temp_ret->guardOnPre_endOffset = insn - code;
1438     }
1439
1440   // global pre branch
1441   ret->globalPreOffset = insn-code;
1442   emitJump(0, insn);
1443
1444   // local pre branch
1445   ret->localPreOffset = insn-code;
1446   emitJump(0, insn);
1447
1448   ret->localPreReturnOffset = insn-code;
1449
1450   if( ! trampRecursiveDesired )
1451     {
1452       NonRecursiveTrampTemplate * temp_ret = ( NonRecursiveTrampTemplate * )ret;
1453       temp_ret->guardOffPre_beginOffset = insn - code;
1454       for( int i = 0; i < guard_code_after_pre_instr_size; i++ )
1455         emitSimpleInsn( 0x90, insn );
1456       temp_ret->guardOffPre_endOffset = insn - code;
1457     }
1458
1459   // restore registers
1460   emitSimpleInsn(POPFD, insn);     // popfd
1461   emitSimpleInsn(POPAD, insn);     // popad
1462   ret->restorePreInsOffset = insn-code;
1463   emitSimpleInsn(LEAVE, insn);     // leave
1464
1465   // update cost
1466   // update cost -- a 10-byte instruction
1467   ret->updateCostOffset = insn-code;
1468   currAddr = baseAddr + (insn-code);
1469   ret->costAddr = currAddr;
1470   if (!noCost) {
1471      emitAddMemImm32(costAddr, 88, insn);  // add (costAddr), cost
1472   }
1473   else {
1474      // minor hack: we still need to fill up the rest of the 10 bytes, since
1475      // assumptions are made about the positioning of instructions that follow.
1476      // (This could in theory be fixed)
1477      // So, 10 NOP instructions (each 1 byte)
1478      for (unsigned foo=0; foo < 10; foo++)
1479         emitSimpleInsn(0x90, insn); // NOP
1480   }
1481
1482    
1483   if (!(location->insnAtPoint().type() & IS_JCC)) {
1484     // emulate the instruction at the point 
1485     ret->emulateInsOffset = insn-code;
1486     currAddr = baseAddr + (insn - code);
1487     assert(origAddr == location->address() + imageBaseAddr);
1488     origAddr = location->address() + imageBaseAddr;
1489     if (currentPC == origAddr &&
1490         currentPC != (location->jumpAddr() + imageBaseAddr)) {
1491       //fprintf(stderr, "changed PC: 0x%lx to 0x%lx\n", currentPC, currAddr);
1492       proc->setNewPC(currAddr);
1493     }
1494
1495     unsigned newSize = relocateInstruction(location->insnAtPoint(), origAddr, currAddr, insn);
1496     aflag=(newSize == getRelocatedInstructionSz(location->insnAtPoint()));
1497     assert(aflag);
1498     currAddr += newSize;
1499     origAddr += location->insnAtPoint().size();
1500   } else {
1501     // instruction at point is a conditional jump. 
1502     // The instruction was relocated to the beggining of the tramp (see comments above)
1503     // We must generate a jump to the original target here
1504     assert(jccTarget > 0);
1505     currAddr = baseAddr + (insn - code);
1506     emitJump(jccTarget-(currAddr+JUMP_SZ), insn);
1507     currAddr += JUMP_SZ;
1508   }
1509
1510   // post branches
1511   // skip post instrumentation
1512   ret->skipPostInsOffset = insn-code;
1513   emitJump(0, insn);
1514
1515
1516   // save registers and create a new stack frame for the tramp
1517   ret->savePostInsOffset = insn-code;
1518   emitSimpleInsn(PUSH_EBP, insn);  // push ebp
1519   emitMovRegToReg(EBP, ESP, insn); // mov ebp, esp
1520   // allocate space for temporaries (virtual registers)
1521   emitOpRegImm(5, ESP, 128, insn); // sub esp, 128
1522   emitSimpleInsn(PUSHAD, insn);    // pushad
1523   emitSimpleInsn(PUSHFD, insn);    // pushfd
1524
1525 #if defined(SHM_SAMPLING) && defined(MT_THREAD)
1526   // generate preamble for MT version
1527   base=0;
1528   generateMTpreamble((char *)insn, base, proc);
1529   insn += base;
1530 #endif
1531
1532   if( ! trampRecursiveDesired )
1533     {
1534       NonRecursiveTrampTemplate * temp_ret = ( NonRecursiveTrampTemplate * )ret;
1535       temp_ret->guardOnPost_beginOffset = insn - code;
1536       for( int i = 0; i < guard_code_before_post_instr_size; i++ )
1537         emitSimpleInsn( 0x90, insn );
1538       temp_ret->guardOnPost_endOffset = insn - code;
1539     }
1540
1541   // global post branch
1542   ret->globalPostOffset = insn-code; 
1543   emitJump(0, insn);
1544
1545   // local post branch
1546   ret->localPostOffset = insn-code;
1547   emitJump(0, insn);
1548
1549   ret->localPostReturnOffset = insn-code;
1550
1551   if( ! trampRecursiveDesired )
1552     {
1553       NonRecursiveTrampTemplate * temp_ret = ( NonRecursiveTrampTemplate * )ret;
1554       temp_ret->guardOffPost_beginOffset = insn - code;
1555       for( int i = 0; i < guard_code_after_post_instr_size; i++ )
1556         emitSimpleInsn( 0x90, insn );
1557       temp_ret->guardOffPost_endOffset = insn - code;
1558     }
1559
1560   // restore registers
1561   emitSimpleInsn(POPFD, insn);     // popfd
1562   emitSimpleInsn(POPAD, insn);     // popad
1563   ret->restorePostInsOffset = insn-code;
1564   emitSimpleInsn(LEAVE, insn);     // leave
1565   
1566   // emulate the instructions after the point
1567   ret->returnInsOffset = insn-code;
1568   currAddr = baseAddr + (insn - code);
1569   assert(origAddr == location->address() + imageBaseAddr + location->insnAtPoint().size());
1570   origAddr = location->address() + imageBaseAddr + location->insnAtPoint().size();
1571   for (u = 0; u < location->insnsAfter(); u++) {
1572     if (currentPC == origAddr) {
1573       //fprintf(stderr, "changed PC: 0x%lx to 0x%lx\n", currentPC, currAddr);
1574       proc->setNewPC(currAddr);
1575     }
1576     unsigned newSize = relocateInstruction(location->insnAfterPt(u), origAddr, currAddr, insn);
1577     aflag=(newSize == getRelocatedInstructionSz(location->insnAfterPt(u)));
1578     assert(aflag);
1579     currAddr += newSize;
1580     origAddr += location->insnAfterPt(u).size();
1581   }
1582
1583   // return to user code
1584   currAddr = baseAddr + (insn - code);
1585   emitJump(location->returnAddr()+imageBaseAddr - (currAddr+JUMP_SZ), insn);
1586 #ifdef INST_TRAP_DEBUG
1587   cerr << "installBaseTramp jump back to " <<
1588           (void*)( location->returnAddr() + imageBaseAddr ) << endl;
1589 #endif
1590
1591   assert((unsigned)(insn-code) == trampSize);
1592
1593   // update the jumps to skip pre and post instrumentation
1594   unsigned char *ip = code + ret->skipPreInsOffset;
1595   emitJump(ret->updateCostOffset - (ret->skipPreInsOffset+JUMP_SZ), ip);
1596   ip = code + ret->skipPostInsOffset;
1597   emitJump(ret->returnInsOffset - (ret->skipPostInsOffset+JUMP_SZ), ip);
1598
1599   if (auxJumpOffset > 0) {
1600     ip = code + auxJumpOffset;
1601     emitJump(ret->returnInsOffset - (auxJumpOffset+JUMP_SZ), ip);
1602   }
1603
1604   if( ! trampRecursiveDesired )
1605     {
1606       /* prepare guard flag memory, if needed */
1607       Address guardFlagAddress = proc->getTrampGuardFlagAddr();
1608       if( guardFlagAddress == 0 )
1609         {
1610           int initial_value = 1;
1611
1612           guardFlagAddress = inferiorMalloc( proc, sizeof( int ), dataHeap );
1613           // cout << "installBaseTramp(): flag address = 0x"
1614           //      << setw( 8 ) << setfill( '0' ) << hex << guardFlagAddress << dec << endl;
1615
1616           /* Initialize the new value */
1617           proc->writeDataSpace( ( void * )guardFlagAddress, sizeof( int ), & initial_value );
1618
1619           proc->setTrampGuardFlagAddr( guardFlagAddress );
1620         }
1621
1622       NonRecursiveTrampTemplate * temp_ret = ( NonRecursiveTrampTemplate * )ret;
1623       generate_guard_code( code, * temp_ret, baseAddr, guardFlagAddress );
1624     }
1625   
1626   // put the tramp in the application space
1627   proc->writeDataSpace((caddr_t)baseAddr, insn-code, (caddr_t) code);
1628
1629   delete [] code;
1630
1631   ret->cost = 6;
1632   //
1633   // The cost for generateMTpreamble is 25 for pre and post instrumentation:
1634   // movl   $0x80570ec,%eax                1
1635   // call   *%ea                           5
1636   // movl   %eax,0xfffffffc(%ebp)          1
1637   // shll   $0x2,0xfffffffc(%ebp)         12
1638   // addl   $0x84ac670,0xfffffffc(%ebp)    4
1639   // movl   0xfffffffc(%ebp),%eax          1
1640   // movl   %eax,0xffffff80(%ebp)          1
1641   //
1642   ret->prevBaseCost = 42+25;
1643   ret->postBaseCost = 42+25;
1644   ret->prevInstru = false;
1645   ret->postInstru = false;
1646   return ret;
1647 }
1648
1649
1650 // This function is used to clear a jump from base to minitramps
1651 // For the x86 platform, we generate a jump to the next instruction
1652 void generateNoOp(process *proc, Address addr) 
1653 {
1654   static unsigned char jump0[5] = { 0xE9, 0, 0, 0, 0 };
1655   proc->writeDataSpace((caddr_t) addr, 5, (caddr_t)jump0);
1656 }
1657
1658
1659 trampTemplate* findAndInstallBaseTramp(process *proc, 
1660                                        instPoint *&location, 
1661                                        returnInstance *&retInstance,
1662                                        bool trampRecursiveDesired,
1663                                        bool noCost,
1664                                        bool &deferred)
1665 {
1666     trampTemplate *ret;
1667     retInstance = NULL;
1668
1669     pd_Function *f = location->func();
1670
1671     // location may not have been updated since relocation of function
1672     if (f->needsRelocation() && f->isInstalled(proc)) {
1673       f->modifyInstPoint(const_cast<const instPoint *&>(location), proc);
1674     }
1675
1676     if (!proc->baseMap.defines(location)) {
1677
1678         // if function needs relocation  
1679         if (f->needsRelocation()) {
1680         
1681           // if function has not already been relocated
1682           if (!f->isInstalled(proc)) {
1683             bool relocated = f->relocateFunction(proc, location, deferred);
1684      
1685             // Silence warnings
1686             assert(relocated || true);
1687
1688 #ifndef BPATCH_LIBRARY
1689             if (!relocated) return NULL;
1690 #endif
1691           }
1692         }
1693
1694         ret = installBaseTramp(location, proc, noCost, trampRecursiveDesired);
1695         proc->baseMap[location] = ret;
1696
1697         // generate branch from instrumentation point to base tramp
1698         Address imageBaseAddr;
1699         if (!proc->getBaseAddress(location->owner(), imageBaseAddr))
1700           abort();
1701         unsigned char *insn = new unsigned char[JUMP_REL32_SZ];
1702         unsigned size = generateBranchToTramp(proc, location, ret->baseAddr, 
1703                                               imageBaseAddr, insn, deferred);
1704         if (size == 0)
1705           return NULL;
1706         retInstance = new returnInstance(location->insns(), 
1707                                          new instruction(insn, 0, size), size,
1708                                          location->jumpAddr() + imageBaseAddr, 
1709                                          size);
1710
1711     } else {
1712         ret = proc->baseMap[location];
1713     }
1714     return(ret);
1715 }
1716
1717
1718 /*
1719  * Install a single mini-tramp.
1720  *
1721  */
1722 void installTramp(instInstance *inst, char *code, int codeSize) 
1723 {
1724     totalMiniTramps++;
1725     //insnGenerated += codeSize/sizeof(int);
1726     (inst->proc)->writeDataSpace((caddr_t)inst->trampBase, codeSize, code);
1727     Address atAddr;
1728     if (inst->when == callPreInsn) {
1729         if (inst->baseInstance->prevInstru == false) {
1730             atAddr = inst->baseInstance->baseAddr+inst->baseInstance->skipPreInsOffset;
1731             inst->baseInstance->cost += inst->baseInstance->prevBaseCost;
1732             inst->baseInstance->prevInstru = true;
1733             generateNoOp(inst->proc, atAddr);
1734         }
1735     }
1736     else {
1737         if (inst->baseInstance->postInstru == false) {
1738             atAddr = inst->baseInstance->baseAddr+inst->baseInstance->skipPostInsOffset; 
1739             inst->baseInstance->cost += inst->baseInstance->postBaseCost;
1740             inst->baseInstance->postInstru = true;
1741             generateNoOp(inst->proc, atAddr);
1742         }
1743     }
1744 }
1745
1746
1747 /**************************************************************
1748  *
1749  *  code generator for x86
1750  *
1751  **************************************************************/
1752
1753
1754
1755
1756 #define MAX_BRANCH      (0x1<<31)
1757
1758 Address getMaxBranch() {
1759   return (Address)MAX_BRANCH;
1760 }
1761
1762
1763 bool doNotOverflow(int)
1764 {
1765   //
1766   // this should be changed by the correct code. If there isn't any case to
1767   // be checked here, then the function should return TRUE. If there isn't
1768   // any immediate code to be generated, then it should return FALSE - naim
1769   //
1770   // any int value can be an immediate on the pentium
1771   return(true);
1772 }
1773
1774
1775
1776 /* build the MOD/RM byte of an instruction */
1777 inline unsigned char makeModRMbyte(unsigned Mod, unsigned Reg, unsigned RM) {
1778   return ((Mod & 0x3) << 6) + ((Reg & 0x7) << 3) + (RM & 0x7);
1779 }
1780
1781 /* 
1782    Emit the ModRM byte and displacement for addressing modes.
1783    base is a register (EAX, ECX, EDX, EBX, EBP, ESI, EDI)
1784    disp is a displacement
1785    reg_opcode is either a register or an opcode
1786 */
1787 void emitAddressingMode(Register base, RegValue disp, int reg_opcode, 
1788                         unsigned char *&insn) {
1789   assert(base != ESP);
1790   if (base == Null_Register) {
1791     *insn++ = makeModRMbyte(0, reg_opcode, 5);
1792     *((int *)insn) = disp;
1793     insn += sizeof(int);
1794   } else if (disp == 0 && base != EBP) {
1795     *insn++ = makeModRMbyte(0, reg_opcode, base);
1796   } else if (disp >= -128 && disp <= 127) {
1797     *insn++ = makeModRMbyte(1, reg_opcode, base);
1798     *((char *)insn++) = (char) disp;
1799   } else {
1800     *insn++ = makeModRMbyte(2, reg_opcode, base);
1801     *((int *)insn) = disp;
1802     insn += sizeof(int);
1803   }
1804 }
1805
1806
1807 /* emit a simple one-byte instruction */
1808 void emitSimpleInsn(unsigned op, unsigned char *&insn) {
1809   *insn++ = op;
1810 }
1811
1812 // emit a simple register to register instruction: OP dest, src
1813 // opcode is one or two byte
1814 void emitOpRegReg(unsigned opcode, Register dest, Register src,
1815                   unsigned char *&insn) {
1816   if (opcode <= 0xFF)
1817     *insn++ = opcode;
1818   else {
1819     *insn++ = opcode >> 8;
1820     *insn++ = opcode & 0xFF;
1821   }
1822   // ModRM byte define the operands: Mod = 3, Reg = dest, RM = src
1823   *insn++ = makeModRMbyte(3, dest, src);
1824 }
1825
1826 // emit OP reg, r/m
1827 void emitOpRegRM(unsigned opcode, Register dest, Register base, int disp,
1828                  unsigned char *&insn) {
1829   if (opcode <= 0xff) {
1830     *insn++ = opcode;
1831   } else {
1832     *insn++ = opcode >> 8;
1833     *insn++ = opcode & 0xff;
1834   }
1835   emitAddressingMode(base, disp, dest, insn);
1836 }
1837
1838 // emit OP r/m, reg
1839 void emitOpRMReg(unsigned opcode, Register base, int disp, Register src,
1840                  unsigned char *&insn) {
1841   *insn++ = opcode;
1842   emitAddressingMode(base, disp, src, insn);
1843 }
1844
1845 // emit OP reg, imm32
1846 void emitOpRegImm(int opcode, Register dest, int imm, unsigned char *&insn) {
1847   *insn++ = 0x81;
1848   *insn++ = makeModRMbyte(3, opcode, dest);
1849   *((int *)insn) = imm;
1850   insn+= sizeof(int);
1851 }
1852
1853 /*
1854 // emit OP r/m, imm32
1855 void emitOpRMImm(unsigned opcode, Register base, int disp, int imm,
1856                  unsigned char *&insn) {
1857   *insn++ = 0x81;
1858   emitAddressingMode(base, disp, opcode, insn);
1859   *((int *)insn) = imm;
1860   insn += sizeof(int);
1861 }
1862 */
1863
1864 // emit OP r/m, imm32
1865 void emitOpRMImm(unsigned opcode1, unsigned opcode2,
1866                  Register base, int disp, int imm, unsigned char *&insn) {
1867   *insn++ = opcode1;
1868   emitAddressingMode(base, disp, opcode2, insn);
1869   *((int *)insn) = imm;
1870   insn += sizeof(int);
1871 }
1872
1873 // emit OP r/m, imm8
1874 void emitOpRMImm8(unsigned opcode1, unsigned opcode2,
1875                  Register base, int disp, char imm, unsigned char *&insn) {
1876   *insn++ = opcode1;
1877   emitAddressingMode(base, disp, opcode2, insn);
1878   *insn++ = imm;
1879 }
1880
1881 // emit OP reg, r/m, imm32
1882 void emitOpRegRMImm(unsigned opcode, Register dest,
1883                  Register base, int disp, int imm, unsigned char *&insn) {
1884   *insn++ = opcode;
1885   emitAddressingMode(base, disp, dest, insn);
1886   *((int *)insn) = imm;
1887   insn += sizeof(int);
1888 }
1889
1890 // emit MOV reg, reg
1891 void emitMovRegToReg(Register dest, Register src, unsigned char *&insn) {
1892   *insn++ = 0x8B;
1893   *insn++ = makeModRMbyte(3, dest, src);
1894 }
1895
1896 // emit MOV reg, r/m
1897 void emitMovRMToReg(Register dest, Register base, int disp, unsigned char *&insn) {
1898   *insn++ = 0x8B;
1899   emitAddressingMode(base, disp, dest, insn);
1900 }
1901
1902 // emit MOV r/m, reg
1903 void emitMovRegToRM(Register base, int disp, Register src, unsigned char *&insn) {
1904   *insn++ = 0x89;
1905   emitAddressingMode(base, disp, src, insn);
1906 }
1907
1908 // emit MOV m, reg
1909 void emitMovRegToM(int disp, Register src, unsigned char *&insn) {
1910   *insn++ = 0x89;
1911   emitAddressingMode(Null_Register, disp, src, insn);
1912 }
1913
1914 // emit MOV reg, m
1915 void emitMovMToReg(Register dest, int disp, unsigned char *&insn) {
1916   *insn++ = 0x8B;
1917   emitAddressingMode(Null_Register, disp, dest, insn);
1918 }
1919
1920 // emit MOV reg, imm32
1921 void emitMovImmToReg(Register dest, int imm, unsigned char *&insn) {
1922   *insn++ = 0xB8 + dest;
1923   *((int *)insn) = imm;
1924   insn += sizeof(int);
1925 }
1926
1927 // emit MOV r/m32, imm32
1928 void emitMovImmToRM(Register base, int disp, int imm, unsigned char *&insn) {
1929   *insn++ = 0xC7;
1930   emitAddressingMode(base, disp, 0, insn);
1931   *((int*)insn) = imm;
1932   insn += sizeof(int);
1933 }
1934
1935 // emit MOV mem32, imm32
1936 void emitMovImmToMem(Address maddr, int imm, unsigned char *&insn) {
1937   *insn++ = 0xC7;
1938   // emit the ModRM byte: we use a 32-bit displacement for the address,
1939   // the ModRM value is 0x05
1940   *insn++ = 0x05;
1941   *((unsigned *)insn) = maddr;
1942   insn += sizeof(unsigned);
1943   *((int*)insn) = imm;
1944   insn += sizeof(int);
1945 }
1946
1947
1948 // emit Add dword ptr DS:[addr], imm
1949 void emitAddMemImm32(Address addr, int imm, unsigned char *&insn) {
1950   *insn++ = 0x81;
1951   *insn++ = 0x05;
1952   *((unsigned *)insn) = addr;
1953   insn += sizeof(unsigned);
1954   *((int *)insn) = imm;
1955   insn += sizeof(int);
1956 }
1957
1958 // emit Add reg, imm32
1959 void emitAddRegImm32(Register reg, int imm, unsigned char *&insn) {
1960   *insn++ = 0x81;
1961   *insn++ = makeModRMbyte(3, 0, reg);
1962   *((int *)insn) = imm;
1963   insn += sizeof(int);
1964 }
1965
1966 // emit JUMP rel32
1967 void emitJump(unsigned disp32, unsigned char *&insn) {
1968   if ((signed)disp32 >= 0)
1969     assert (disp32 < unsigned(1<<31));
1970   else
1971     assert ((unsigned)(-(signed)disp32) < unsigned(1<<31));
1972   *insn++ = 0xE9;
1973   *((int *)insn) = disp32;
1974   insn += sizeof(int);
1975
1976
1977 // emit CALL rel32
1978 void emitCallRel32(unsigned disp32, unsigned char *&insn) {
1979   *insn++ = 0xE8;
1980   *((int *)insn) = disp32;
1981   insn += sizeof(int);
1982 }
1983
1984 // set dest=1 if src1 op src2, otherwise dest = 0
1985 void emitRelOp(unsigned op, Register dest, Register src1, Register src2,
1986                unsigned char *&insn) {
1987   //fprintf(stderr,"Relop dest = %d, src1 = %d, src2 = %d\n", dest, src1, src2);
1988   emitOpRegReg(0x29, ECX, ECX, insn);           // clear ECX
1989   emitMovRMToReg(EAX, EBP, -(src1*4), insn);    // mov eax, -(src1*4)[ebp]
1990   emitOpRegRM(0x3B, EAX, EBP, -(src2*4), insn); // cmp eax, -(src2*4)[ebp]
1991   unsigned char opcode;
1992   switch (op) {
1993     case eqOp: opcode = JNE_R8; break;
1994     case neOp: opcode = JE_R8; break;
1995     case lessOp: opcode = JGE_R8; break;
1996     case leOp: opcode = JG_R8; break;
1997     case greaterOp: opcode = JLE_R8; break;
1998     case geOp: opcode = JL_R8; break;
1999     default: assert(0);
2000   }
2001   *insn++ = opcode; *insn++ = 1;                // jcc 1
2002   emitSimpleInsn(0x40+ECX, insn);               // inc ECX
2003   emitMovRegToRM(EBP, -(dest*4), ECX, insn);    // mov -(dest*4)[ebp], ecx
2004
2005 }
2006
2007 // set dest=1 if src1 op src2imm, otherwise dest = 0
2008 void emitRelOpImm(unsigned op, Register dest, Register src1, int src2imm,
2009                   unsigned char *&insn) {
2010   //fprintf(stderr,"Relop dest = %d, src1 = %d, src2 = %d\n", dest, src1, src2);
2011   emitOpRegReg(0x29, ECX, ECX, insn);           // clear ECX
2012   emitMovRMToReg(EAX, EBP, -(src1*4), insn);    // mov eax, -(src1*4)[ebp]
2013   emitOpRegImm(0x3D, EAX, src2imm, insn);       // cmp eax, src2
2014   unsigned char opcode;
2015   switch (op) {
2016     case eqOp: opcode = JNE_R8; break;
2017     case neOp: opcode = JE_R8; break;
2018     case lessOp: opcode = JGE_R8; break;
2019     case leOp: opcode = JG_R8; break;
2020     case greaterOp: opcode = JLE_R8; break;
2021     case geOp: opcode = JL_R8; break;
2022     default: assert(0);
2023   }
2024   *insn++ = opcode; *insn++ = 1;                // jcc 1
2025   emitSimpleInsn(0x40+ECX, insn);               // inc ECX
2026   emitMovRegToRM(EBP, -(dest*4), ECX, insn);    // mov -(dest*4)[ebp], ecx
2027
2028 }
2029
2030 void emitEnter(short imm16, unsigned char *&insn) {
2031   *insn++ = 0xC8;
2032   *((short*)insn) = imm16;
2033   insn += sizeof(short);
2034   *insn++ = 0;
2035 }
2036
2037
2038
2039 Register emitFuncCall(opCode op, 
2040                       registerSpace *rs,
2041                       char *ibuf, Address &base,
2042                       const vector<AstNode *> &operands, 
2043                       const string &callee, process *proc,
2044                       bool noCost, const function_base *calleefunc)
2045 {
2046   assert(op == callOp);
2047   Address addr;
2048   bool err;
2049   vector <Register> srcs;
2050
2051   if (calleefunc)
2052        addr = calleefunc->getEffectiveAddress(proc);
2053   else {
2054        addr = proc->findInternalAddress(callee, false, err);
2055        if (err) {
2056             function_base *func = proc->findOneFunction(callee);
2057             if (!func) {
2058                  ostrstream os(errorLine, 1024, ios::out);
2059                  os << "Internal error: unable to find addr of " << callee << endl;
2060                  logLine(errorLine);
2061                  showErrorCallback(80, (const char *) errorLine);
2062                  P_abort();
2063             }
2064             addr = func->getEffectiveAddress(proc);
2065        }
2066   }
2067   for (unsigned u = 0; u < operands.size(); u++)
2068     srcs.push_back((Register)operands[u]->generateCode(proc, rs, ibuf, base, noCost, false));
2069
2070   unsigned char *insn = (unsigned char *) ((void*)&ibuf[base]);
2071   unsigned char *first = insn;
2072
2073   // push arguments in reverse order, last argument first
2074   // must use int instead of unsigned to avoid nasty underflow problem:
2075   for (int i=srcs.size() - 1 ; i >= 0; i--) {
2076      emitOpRMReg(PUSH_RM_OPC1, EBP, -(srcs[i]*4), PUSH_RM_OPC2, insn);
2077      rs->freeRegister(srcs[i]);
2078   }
2079
2080   // make the call
2081   // we are using an indirect call here because we don't know the
2082   // address of this instruction, so we can't use a relative call.
2083   // TODO: change this to use a direct call
2084   emitMovImmToReg(EAX, addr, insn);       // mov eax, addr
2085   emitOpRegReg(CALL_RM_OPC1, CALL_RM_OPC2, EAX, insn);   // call *(eax)
2086
2087   // reset the stack pointer
2088   if (srcs.size() > 0)
2089      emitOpRegImm(0, ESP, srcs.size()*4, insn); // add esp, srcs.size()*4
2090
2091   // allocate a (virtual) register to store the return value
2092   Register ret = rs->allocateRegister((char *)insn, base, noCost);
2093   emitMovRegToRM(EBP, -(ret*4), EAX, insn);
2094
2095   base += insn - first;
2096   return ret;
2097 }
2098
2099
2100
2101 /*
2102  * emit code for op(src1,src2, dest)
2103  * ibuf is an instruction buffer where instructions are generated
2104  * base is the next free position on ibuf where code is to be generated
2105  */
2106
2107 Address emitA(opCode op, Register src1, Register /*src2*/, Register dest,
2108              char *ibuf, Address &base, bool /*noCost*/)
2109 {
2110     //fprintf(stderr,"emitA(op=%d,src1=%d,src2=XX,dest=%d)\n",op,src1,dest);
2111
2112     unsigned char *insn = (unsigned char *) (&ibuf[base]);
2113     unsigned char *first = insn;
2114
2115     switch (op) {
2116     case ifOp: {
2117       // if src1 == 0 jump to dest
2118       // src1 is a temporary
2119       // dest is a target address
2120       emitOpRegReg(0x29, EAX, EAX, insn);           // sub EAX, EAX ; clear EAX
2121       emitOpRegRM(0x3B, EAX, EBP, -(src1*4), insn); // cmp -(src1*4)[EBP], EAX
2122       // je dest
2123       *insn++ = 0x0F;
2124       *insn++ = 0x84;
2125       *((int *)insn) = dest;
2126       insn += sizeof(int);
2127       base += insn-first;
2128       return base;
2129       }
2130     case branchOp: { 
2131         emitJump(dest - JUMP_REL32_SZ, insn); 
2132         base += JUMP_REL32_SZ;
2133         return(base - JUMP_REL32_SZ);
2134       }
2135     case trampTrailer: {
2136       // generate the template for a jump -- actual jump is generated elsewhere
2137       emitJump(0, insn); // jump xxxx
2138       // return the offset of the previous jump
2139       base += insn - first;
2140       return(base - JUMP_REL32_SZ);
2141       }
2142     case trampPreamble: {
2143         base += insn - first;
2144         return(0);      // let's hope this is expected!
2145       }
2146     default:
2147         abort();        // unexpected op for this emit!
2148     }
2149   return(0);            // should never reach here!
2150 }
2151
2152 Register emitR(opCode op, Register src1, Register /*src2*/, Register dest,
2153              char *ibuf, Address &base, bool /*noCost*/)
2154 {
2155     //fprintf(stderr,"emitR(op=%d,src1=%d,src2=XX,dest=%d)\n",op,src1,dest);
2156
2157     unsigned char *insn = (unsigned char *) (&ibuf[base]);
2158     unsigned char *first = insn;
2159
2160     switch (op) {
2161     case getRetValOp: {
2162       // dest is a register where we can store the value
2163       // the return value is in the saved EAX
2164       emitMovRMToReg(EAX, EBP, SAVED_EAX_OFFSET, insn);
2165       emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2166       base += insn - first;
2167       return dest;
2168       }
2169     case getParamOp: {
2170       // src1 is the number of the argument
2171       // dest is a register where we can store the value
2172       // Parameters are addressed by a positive offset from ebp,
2173       // the first is PARAM_OFFSET[ebp]
2174       emitMovRMToReg(EAX, EBP, PARAM_OFFSET + src1*4, insn);
2175       emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2176       base += insn - first;
2177       return dest;
2178       }
2179     default:
2180       abort();                  // unexpected op for this emit!
2181     }
2182   return(Null_Register);        // should never be reached!
2183 }
2184
2185 void emitVload(opCode op, Address src1, Register /*src2*/, Register dest, 
2186              char *ibuf, Address &base, bool /*noCost*/, int /* size */)
2187 {
2188     unsigned char *insn = (unsigned char *) (&ibuf[base]);
2189     unsigned char *first = insn;
2190
2191     if (op == loadConstOp) {
2192       // dest is a temporary
2193       // src1 is an immediate value 
2194       // dest = src1:imm32
2195       emitMovImmToRM(EBP, -(dest*4), src1, insn);
2196       base += insn - first;
2197       return;
2198     } else if (op ==  loadOp) {
2199       // dest is a temporary
2200       // src1 is the address of the operand
2201       // dest = [src1]
2202       emitMovMToReg(EAX, src1, insn);               // mov eax, src1
2203       emitMovRegToRM(EBP, -(dest*4), EAX, insn);    // mov -(dest*4)[ebp], eax
2204       base += insn - first;
2205       return;
2206     } else if (op == loadFrameRelativeOp) {
2207       // dest is a temporary
2208       // src1 is the offset of the from the frame of the variable
2209       // eax = [eax]    - saved sp
2210       // dest = [eax](src1)
2211       emitMovRMToReg(EAX, EBP, 0, insn);       // mov (%ebp), %eax 
2212       emitMovRMToReg(EAX, EAX, src1, insn);    // mov <offset>(%eax), %eax 
2213       emitMovRegToRM(EBP, -(dest*4), EAX, insn);    // mov -(dest*4)[ebp], eax
2214       base += insn - first;
2215       return;
2216     } else if (op == loadFrameAddr) {
2217       emitMovRMToReg(EAX, EBP, 0, insn);       // mov (%ebp), %eax 
2218       emitAddRegImm32(EAX, src1, insn);        // add #<offset>, %eax
2219       emitMovRegToRM(EBP, -(dest*4), EAX, insn);    // mov -(dest*4)[ebp], eax
2220       base += insn - first;
2221       return;
2222     } else {
2223         abort();                // unexpected op for this emit!
2224     }
2225 }
2226
2227 void emitVstore(opCode op, Register src1, Register src2, Address dest,
2228              char *ibuf, Address &base, bool /*noCost*/, int /* size */)
2229 {
2230     unsigned char *insn = (unsigned char *) (&ibuf[base]);
2231     unsigned char *first = insn;
2232
2233     if (op ==  storeOp) {
2234       // [dest] = src1
2235       // dest has the address where src1 is to be stored
2236       // src1 is a temporary
2237       // src2 is a "scratch" register, we don't need it in this architecture
2238       emitMovRMToReg(EAX, EBP, -(src1*4), insn);    // mov eax, -(src1*4)[ebp]
2239       emitMovRegToM(dest, EAX, insn);               // mov dest, eax
2240       base += insn - first;
2241       return;
2242     } else if (op == storeFrameRelativeOp) {
2243       // src1 is a temporary
2244       // src2 is a "scratch" register, we don't need it in this architecture
2245       // dest is the frame offset 
2246       //
2247       // src2 = [ebp]   - saved sp
2248       // (dest)[src2] = src1
2249       emitMovRMToReg(src2, EBP, 0, insn);           // mov src2, (ebp)
2250       emitMovRMToReg(EAX, EBP, -(src1*4), insn);    // mov eax, -(src1*4)[ebp]
2251       emitMovRegToRM(src2, dest, EAX, insn);        // mov (dest)[src2], eax
2252       base += insn - first;
2253       return;
2254     } else {
2255         abort();                // unexpected op for this emit!
2256     }
2257 }
2258
2259 void emitVupdate(opCode op, RegValue src1, Register /*src2*/, Address dest, 
2260              char *ibuf, Address &base, bool noCost)
2261 {
2262     unsigned char *insn = (unsigned char *) (&ibuf[base]);
2263     unsigned char *first = insn;
2264
2265     if (op == updateCostOp) {
2266       // src1 is the cost value
2267       // src2 is not used
2268       // dest is the address of observed cost
2269
2270       if (!noCost) {
2271          // update observed cost
2272          // dest = address of DYNINSTobsCostLow
2273          // src1 = cost
2274          emitAddMemImm32(dest, src1, insn);  // ADD (dest), src1
2275       }
2276       base += insn-first;
2277       return;           //return base;    // never seem to ever need this
2278     } else {
2279         abort();                // unexpected op for this emit!
2280     }
2281 }
2282
2283 void emitV(opCode op, Register src1, Register src2, Register dest, 
2284              char *ibuf, Address &base, bool /*noCost*/, int /* size */)
2285 {
2286     //fprintf(stderr,"emitV(op=%d,src1=%d,src2=%d,dest=%d)\n",op,src1,src2,dest);
2287
2288     assert ((op!=branchOp) && (op!=ifOp) &&
2289             (op!=trampTrailer) && (op!=trampPreamble));         // !emitA
2290     assert ((op!=getRetValOp) && (op!=getParamOp));             // !emitR
2291     assert ((op!=loadOp) && (op!=loadConstOp));                 // !emitVload
2292     assert ((op!=storeOp));                                     // !emitVstore
2293     assert ((op!=updateCostOp));                                // !emitVupdate
2294
2295     unsigned char *insn = (unsigned char *) (&ibuf[base]);
2296     unsigned char *first = insn;
2297
2298     if (op ==  loadIndirOp) {
2299       // same as loadOp, but the value to load is already in a register
2300       emitMovRMToReg(EAX, EBP, -(src1*4), insn); // mov eax, -(src1*4)[ebp]
2301       emitMovRMToReg(EAX, EAX, 0, insn);         // mov eax, [eax]
2302       emitMovRegToRM(EBP, -(dest*4), EAX, insn); // mov -(dest*4)[ebp], eax
2303
2304     } 
2305     else if (op ==  storeIndirOp) {
2306       // same as storeOp, but the address where to store is already in a
2307       // register
2308       emitMovRMToReg(EAX, EBP, -(src1*4), insn);   // mov eax, -(src1*4)[ebp]
2309       emitMovRMToReg(ECX, EBP, -(dest*4), insn);   // mov ecx, -(dest*4)[ebp]
2310       emitMovRegToRM(ECX, 0, EAX, insn);           // mov [ecx], eax
2311
2312     } else if (op == noOp) {
2313        emitSimpleInsn(NOP, insn); // nop
2314
2315     } else if (op == saveRegOp) {
2316       // should not be used on this platform
2317       assert(0);
2318
2319     } else {
2320       unsigned opcode = 0;//initialize to placate gcc warnings
2321         switch (op) {
2322             // integer ops
2323             case plusOp:
2324                 // dest = src1 + src2
2325                 // mv eax, src1
2326                 // add eax, src2
2327                 // mov dest, eax
2328                 opcode = 0x03; // ADD
2329                 break;
2330
2331             case minusOp:
2332                 opcode = 0x2B; // SUB
2333                 break;
2334
2335             case timesOp:
2336                 opcode = 0x0FAF; // IMUL
2337                 break;
2338
2339             case divOp:
2340                 // dest = src1 div src2
2341                 // mov eax, src1
2342                 // cdq   ; edx = sign extend of eax
2343                 // idiv eax, src2 ; eax = edx:eax div src2, edx = edx:eax mod src2
2344                 // mov dest, eax
2345                 emitMovRMToReg(EAX, EBP, -(src1*4), insn);
2346                 emitSimpleInsn(0x99, insn);
2347                 emitOpRegRM(0xF7, 0x7 /*opcode extension*/, EBP, -(src2*4), insn);
2348                 emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2349                 base += insn-first;
2350                 return;
2351                 break;
2352
2353             // Bool ops
2354             case orOp:
2355                 opcode = 0x0B; // OR 
2356                 break;
2357
2358             case andOp:
2359                 opcode = 0x23; // AND
2360                 break;
2361
2362             // rel ops
2363             // dest = src1 relop src2
2364             case eqOp:
2365             case neOp:
2366             case lessOp:
2367             case leOp:
2368             case greaterOp:
2369             case geOp:
2370                 emitRelOp(op, dest, src1, src2, insn);
2371                 base += insn-first;
2372                 return;
2373                 break;
2374
2375             default:
2376                 abort();
2377                 break;
2378         }
2379
2380         emitMovRMToReg(EAX, EBP, -(src1*4), insn);
2381         emitOpRegRM(opcode, EAX, EBP, -(src2*4), insn);
2382         emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2383       }
2384     base += insn - first;
2385     return;
2386 }
2387
2388
2389 void emitImm(opCode op, Register src1, RegValue src2imm, Register dest, 
2390              char *ibuf, Address &base, bool)
2391 {
2392     unsigned char *insn = (unsigned char *) (&ibuf[base]);
2393     unsigned char *first = insn;
2394
2395     if (op ==  storeOp) {
2396       // [dest] = src1
2397       // dest has the address where src1 is to be stored
2398       // src1 is an immediate value
2399       // src2 is a "scratch" register, we don't need it in this architecture
2400       emitMovImmToReg(EAX, dest, insn);
2401       emitMovImmToRM(EAX, 0, src1, insn);
2402     } else {
2403         unsigned opcode1;
2404         unsigned opcode2;
2405         switch (op) {
2406             // integer ops
2407             case plusOp:
2408                 opcode1 = 0x81;
2409                 opcode2 = 0x0; // ADD
2410                 break;
2411
2412             case minusOp:
2413                 opcode1 = 0x81;
2414                 opcode2 = 0x5; // SUB
2415                 break;
2416
2417             case timesOp: {
2418                 int result=-1;
2419                 if (isPowerOf2(src2imm, result) && result <= MAX_IMM8) {
2420                   if (src1 != dest) {
2421                     emitMovRMToReg(EAX, EBP, -(src1*4), insn);
2422                     emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2423                   }
2424                   // sal dest, result
2425                   emitOpRMImm8(0xC1, 4, EBP, -(dest*4), result, insn);
2426                 }
2427                 else {
2428                   // imul EAX, -(src1*4)[ebp], src2imm
2429                   emitOpRegRMImm(0x69, EAX, EBP, -(src1*4), src2imm, insn);
2430                   emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2431                 } 
2432                 base += insn-first;
2433                 return;
2434               }
2435                 break;
2436
2437             case divOp: {
2438                 int result=-1;
2439                 if (isPowerOf2(src2imm, result) && result <= MAX_IMM8) {
2440                   if (src1 != dest) {
2441                     emitMovRMToReg(EAX, EBP, -(src1*4), insn);
2442                     emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2443                   }
2444                   // sar dest, result
2445                   emitOpRMImm8(0xC1, 7, EBP, -(dest*4), result, insn);
2446                 }
2447                 else {
2448                   // dest = src1 div src2imm
2449                   // mov eax, src1
2450                   // cdq   ; edx = sign extend of eax
2451                   // mov ebx, src2imm
2452                   // idiv eax, ebx ; eax = edx:eax div src2, edx = edx:eax mod src2
2453                   // mov dest, eax
2454                   emitMovRMToReg(EAX, EBP, -(src1*4), insn);
2455                   emitSimpleInsn(0x99, insn);
2456                   emitMovImmToReg(EBX, src2imm, insn);
2457                   // idiv eax, ebx
2458                   emitOpRegReg(0xF7, 0x7 /*opcode extension*/, EBX, insn); 
2459                   emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2460                 }
2461               }
2462                 base += insn-first;
2463                 return;
2464                 break;
2465
2466             // Bool ops
2467             case orOp:
2468                 opcode1 = 0x81;
2469                 opcode2 = 0x1; // OR 
2470                 break;
2471
2472             case andOp:
2473                 opcode1 = 0x81;
2474                 opcode2 = 0x4; // AND
2475                 break;
2476
2477             // rel ops
2478             // dest = src1 relop src2
2479             case eqOp:
2480             case neOp:
2481             case lessOp:
2482             case leOp:
2483             case greaterOp:
2484             case geOp:
2485                 emitRelOpImm(op, dest, src1, src2imm, insn);
2486                 base += insn-first;
2487                 return;
2488                 break;
2489
2490             default:
2491                 abort();
2492                 break;
2493         }
2494         if (src1 != dest) {
2495           emitMovRMToReg(EAX, EBP, -(src1*4), insn);
2496           emitMovRegToRM(EBP, -(dest*4), EAX, insn);
2497         }
2498         emitOpRMImm(opcode1, opcode2, EBP, -(dest*4), src2imm, insn);
2499       }
2500     base += insn - first;
2501     return;
2502 }
2503
2504
2505
2506 int getInsnCost(opCode op)
2507 {
2508     if (op == loadConstOp) {
2509         return(1);
2510     } else if (op ==  loadOp) {
2511         return(1+1);
2512     } else if (op ==  loadIndirOp) {
2513         return(3);
2514     } else if (op ==  storeOp) {
2515         return(1+1); 
2516     } else if (op ==  storeIndirOp) {
2517         return(3);
2518     } else if (op ==  ifOp) {
2519         return(1+2+1);
2520     } else if (op ==  whileOp) {
2521         return(1+2+1+1); /* Need to find out about this */
2522     } else if (op == branchOp) {
2523         return(1);      /* XXX Need to find out what value this should be. */
2524     } else if (op ==  callOp) {
2525         // cost of call only
2526         return(1+2+1+1);
2527     } else if (op == updateCostOp) {
2528         return(3);
2529     } else if (op ==  trampPreamble) {
2530         return(0);
2531     } else if (op ==  trampTrailer) {
2532         return(1);
2533     } else if (op == noOp) {
2534         return(1);
2535     } else if (op == getRetValOp) {
2536         return (1+1);
2537     } else if (op == getParamOp) {
2538         return(1+1);
2539     } else {
2540         switch (op) {
2541             // rel ops
2542             case eqOp:
2543             case neOp:
2544             case lessOp:
2545             case leOp:
2546             case greaterOp:
2547             case geOp:
2548                 return(1+1+2+1+1+1);
2549                 break;
2550             case divOp:
2551                 return(1+2+46+1);
2552             case timesOp:
2553                 return(1+10+1);
2554             case plusOp:
2555             case minusOp:
2556             case orOp:
2557             case andOp:
2558                 return(1+2+1);
2559             case getAddrOp:
2560                 return(0);      // doesn't add anything to operand
2561             default:
2562                 assert(0);
2563                 return 0;
2564                 break;
2565         }
2566     }
2567 }
2568
2569
2570
2571 bool process::heapIsOk(const vector<sym_data> &find_us) {
2572   Symbol sym;
2573   string str;
2574   Address baseAddr;
2575
2576   // find the main function
2577   // first look for main or _main
2578 #if !defined(i386_unknown_nt4_0)
2579   if (!((mainFunction = findOneFunction("main")) 
2580         || (mainFunction = findOneFunction("_main")))) {
2581      string msg = "Cannot find main. Exiting.";
2582      statusLine(msg.string_of());
2583      showErrorCallback(50, msg);
2584      return false;
2585   }
2586 #else
2587   if (!((mainFunction = findOneFunction("main")) 
2588         || (mainFunction = findOneFunction("_main"))
2589         || (mainFunction = findOneFunction("WinMain"))
2590         || (mainFunction = findOneFunction("_WinMain")))) {
2591      string msg = "Cannot find main or WinMain. Exiting.";
2592      statusLine(msg.string_of());
2593      showErrorCallback(50, msg);
2594      return false;
2595   }
2596 #endif
2597
2598   for (unsigned i=0; i<find_us.size(); i++) {
2599     str = find_us[i].name;
2600     if (!getSymbolInfo(str, sym, baseAddr)) {
2601       string str1 = string("_") + str.string_of();
2602       if (!getSymbolInfo(str1, sym, baseAddr) && find_us[i].must_find) {
2603         string msg;
2604         msg = string("Cannot find ") + str + string(". Exiting");
2605         statusLine(msg.string_of());
2606         showErrorCallback(50, msg);
2607         return false;
2608       }
2609     }
2610   }
2611
2612 //  string ghb = GLOBAL_HEAP_BASE;
2613 //  if (!getSymbolInfo(ghb, sym, baseAddr)) {
2614 //    ghb = U_GLOBAL_HEAP_BASE;
2615 //    if (!getSymbolInfo(ghb, symm baseAddr)) {
2616 //      string msg;
2617 //      msg = string("Cannot find ") + str + string(". Exiting");
2618 //      statusLine(msg.string_of());
2619 //      showErrorCallback(50, msg);
2620 //      return false;
2621 //    }
2622 //  }
2623 //  Address instHeapEnd = sym.addr()+baseAddr;
2624 //  addInternalSymbol(ghb, instHeapEnd);
2625
2626 #if !defined(i386_unknown_nt4_0)
2627   string tt = "DYNINSTtrampTable";
2628   if (!getSymbolInfo(tt, sym, baseAddr)) {
2629       string msg;
2630       msg = string("Cannot find ") + tt + string(". Cannot use this application");
2631       statusLine(msg.string_of());
2632       showErrorCallback(50, msg);
2633       return false;
2634   }
2635 #endif
2636
2637   return true;
2638 }
2639
2640
2641
2642 dictionary_hash<string, unsigned> funcFrequencyTable(string::hash);
2643
2644 //
2645 // initDefaultPointFrequencyTable - define the expected call frequency of
2646 //    procedures.  Currently we just define several one shots with a
2647 //    frequency of one, and provide a hook to read a file with more accurate
2648 //    information.
2649 //
2650 void initDefaultPointFrequencyTable()
2651 {
2652     FILE *fp;
2653     float value;
2654     char name[512];
2655
2656     funcFrequencyTable["main"] = 1;
2657     funcFrequencyTable["DYNINSTsampleValues"] = 1;
2658     funcFrequencyTable[EXIT_NAME] = 1;
2659
2660     // try to read file.
2661     fp = fopen("freq.input", "r");
2662     if (!fp) {
2663         return;
2664     } else {
2665         printf("found freq.input file\n");
2666     }
2667     while (!feof(fp)) {
2668         fscanf(fp, "%s %f\n", name, &value);
2669         funcFrequencyTable[name] = (int) value;
2670         printf("adding %s %f\n", name, value);
2671     }
2672     fclose(fp);
2673 }
2674
2675 /*
2676  * Get an estimate of the frequency for the passed instPoint.  
2677  *    This is not (always) the same as the function that contains the point.
2678  * 
2679  *  The function is selected as follows:
2680  *
2681  *  If the point is an entry or an exit return the function name.
2682  *  If the point is a call and the callee can be determined, return the called
2683  *     function.
2684  *  else return the funcation containing the point.
2685  *
2686  *  WARNING: This code contains arbitrary values for func frequency (both user 
2687  *     and system).  This should be refined over time.
2688  *
2689  * Using 1000 calls sec to be one SD from the mean for most FPSPEC apps.
2690  *      -- jkh 6/24/94
2691  *
2692  */
2693 float getPointFrequency(instPoint *point)
2694 {
2695
2696     pd_Function *func = point->callee();
2697
2698     if (!func)
2699       func = point->func();
2700
2701     if (!funcFrequencyTable.defines(func->prettyName())) {
2702       // Changing this value from 250 to 100 because predictedCost was
2703       // too high - naim 07/18/96
2704       return(100.0);       
2705     } else {
2706       return ((float)funcFrequencyTable[func->prettyName()]);
2707     }
2708 }
2709
2710 //
2711 // return cost in cycles of executing at this point.  This is the cost
2712 //   of the base tramp if it is the first at this point or 0 otherwise.
2713 //
2714 int getPointCost(process *proc, const instPoint *point)
2715 {
2716     if (proc->baseMap.defines(point)) {
2717         return(0);
2718     } else {
2719         if (point->usesTrap(proc))
2720           return 9000; // estimated number of cycles for traps
2721         else
2722           return(83);
2723     }
2724 }
2725
2726
2727
2728 bool returnInstance::checkReturnInstance(const vector<Address> &stack, u_int &index) {
2729         return true;
2730
2731     // If false (unsafe) is returned, then 'index' is set to the first unsafe call stack
2732     // index.
2733     for (u_int i=0; i < stack.size(); i++) {
2734         index = i;
2735
2736         if (stack[i] >= addr_ && stack[i] < addr_+size_)
2737             return false;
2738     }
2739
2740     return true;
2741 }
2742  
2743 void returnInstance::installReturnInstance(process *proc) {
2744     assert(instructionSeq);
2745     proc->writeTextSpace((void *)addr_, instSeqSize, instructionSeq->ptr());
2746     delete instructionSeq;
2747     instructionSeq = 0;
2748         installed = true;
2749 }
2750
2751 void returnInstance::addToReturnWaitingList(Address , process *) {
2752     //P_abort();
2753         assert(0);
2754 }
2755
2756 void generateBreakPoint(instruction &insn) {
2757   insn = instruction ((const unsigned char*)"\017\013", ILLEGAL, 2);
2758 }
2759
2760 void instWaitingList::cleanUp(process *, Address ) {
2761   P_abort();
2762 /*
2763   proc->writeTextSpace((caddr_t)pc, relocatedInstruction.size(),
2764             (caddr_t&)(relocatedInstruction.ptr()));
2765   proc->writeTextSpace((caddr_t)addr_, instSeqSize,
2766             (caddr_t)instructionSeq);
2767 */
2768 }
2769
2770 /* ***************************************************** */
2771
2772 bool process::emitInferiorRPCheader(void *void_insnPtr, Address &baseBytes) {
2773    unsigned char *insnPtr = (unsigned char *)void_insnPtr;
2774    unsigned char *origInsnPtr = insnPtr;
2775    insnPtr += baseBytes;
2776
2777    // We emit the following here (to set up a fresh stack frame):
2778    // pushl %ebp        (0x55)
2779    // movl  %esp, %ebp  (0x89 0xe5)
2780    // pushad
2781    // pushfd
2782
2783    emitSimpleInsn(PUSH_EBP, insnPtr);
2784    emitMovRegToReg(EBP, ESP, insnPtr);
2785    // allocate space for temporaries (virtual registers)
2786    emitOpRegImm(5, ESP, 128, insnPtr); // sub esp, 128
2787    emitSimpleInsn(PUSHAD, insnPtr);
2788    emitSimpleInsn(PUSHFD, insnPtr);
2789
2790    baseBytes += (insnPtr - origInsnPtr);
2791
2792    return true;
2793 }
2794
2795 bool process::emitInferiorRPCtrailer(void *void_insnPtr, Address &baseBytes,
2796                                      unsigned &breakOffset,
2797                                      bool shouldStopForResult,
2798                                      unsigned &stopForResultOffset,
2799                                      unsigned &justAfter_stopForResultOffset) {
2800    unsigned char *insnPtr = (unsigned char *)void_insnPtr;
2801       // unsigned char * is the most natural to work with on x86, since instructions
2802       // are always an integral # of bytes.  Besides, it makes the following line easy:
2803    insnPtr += baseBytes; // start off in the right spot
2804
2805    if (shouldStopForResult) {
2806       // illegal insn: 0x0f0b does the trick.
2807       stopForResultOffset = baseBytes;
2808       *insnPtr++ = 0x0f;
2809       *insnPtr++ = 0x0b;
2810       baseBytes += 2;
2811
2812       justAfter_stopForResultOffset = baseBytes;
2813    }
2814
2815    // Sequence: popfd, popad, leave (0xc9), call DYNINSTbreakPoint(), illegal
2816
2817    emitSimpleInsn(POPFD, insnPtr); // popfd
2818    emitSimpleInsn(POPAD, insnPtr); // popad
2819    emitSimpleInsn(LEAVE, insnPtr); // leave
2820    baseBytes += 3; // all simple insns are 1 byte
2821
2822    // We can't do a SIGTRAP since SIGTRAP is reserved in x86.
2823    // So we do a SIGILL instead.
2824    breakOffset = baseBytes;
2825    *insnPtr++ = 0x0f;
2826    *insnPtr++ = 0x0b;
2827    baseBytes += 2;
2828
2829    // Here, we should generate an illegal insn, or something.
2830    // A two-byte insn, 0x0f0b, should do the trick.  The idea is that
2831    // the code should never be executed.
2832    *insnPtr++ = 0x0f;
2833    *insnPtr++ = 0x0b;
2834    baseBytes += 2;
2835
2836    return true;
2837 }
2838
2839 // process::replaceFunctionCall
2840 //
2841 // Replace the function call at the given instrumentation point with a call to
2842 // a different function, or with a NOOP.  In order to replace the call with a
2843 // NOOP, pass NULL as the parameter "func."
2844 // Returns true if sucessful, false if not.  Fails if the site is not a call
2845 // site, or if the site has already been instrumented using a base tramp.
2846 //
2847 // Note that right now we can only replace a call instruction that is five
2848 // bytes long (like a call to a 32-bit relative address).
2849 bool process::replaceFunctionCall(const instPoint *point,
2850                                   const function_base *func) {
2851     // Must be a call site
2852     if (!point->insnAtPoint().isCall())
2853         return false;
2854
2855     // Cannot already be instrumented with a base tramp
2856     if (baseMap.defines(point))
2857         return false;
2858
2859     // Replace the call
2860     if (func == NULL) { // Replace with NOOPs
2861         unsigned char *newInsn = new unsigned char[point->insnAtPoint().size()];
2862         unsigned char *p = newInsn;
2863         for (unsigned i = 0; i < point->insnAtPoint().size(); i++)
2864             emitSimpleInsn(NOP, p);
2865         writeTextSpace((void *)point->iPgetAddress(),
2866                        point->insnAtPoint().size(), newInsn);
2867     } else { // Replace with a call to a different function
2868         // XXX Right only, call has to be 5 bytes -- sometime, we should make
2869         // it work for other calls as well.
2870         assert(point->insnAtPoint().size() == CALL_REL32_SZ);
2871         unsigned char *newInsn = new unsigned char[CALL_REL32_SZ];
2872         unsigned char *p = newInsn;
2873         emitCallRel32(func->addr() - (point->iPgetAddress()+CALL_REL32_SZ), p);
2874         writeTextSpace((void *)point->iPgetAddress(), CALL_REL32_SZ, newInsn);
2875     }
2876
2877     return true;
2878 }
2879
2880 // Emit code to jump to function CALLEE without linking.  (I.e., when
2881 // CALLEE returns, it returns to the current caller.)
2882 void emitFuncJump(opCode /*op*/, 
2883                   char * /*i*/, Address & /*base*/, 
2884                   const function_base * /*callee*/, process * /*proc*/)
2885 {
2886      /* Unimplemented on this platform! */
2887      assert(0);
2888 }
2889
2890 void emitLoadPreviousStackFrameRegister(Address register_num,
2891                                         Register dest,
2892                                         char *insn,
2893                                         Address &base,
2894                                         int,
2895                                         bool){
2896   //Previous stack frame register is stored on the stack,
2897   //it was stored there at the begining of the base tramp.
2898
2899   //Calculate the register's offset from the frame pointer in EBP
2900   unsigned offset = SAVED_EAX_OFFSET - (register_num * 4);
2901   
2902   unsigned char *in = (unsigned char *) (&insn[base]);
2903   unsigned char *first = in;
2904   
2905   emitMovRMToReg(EAX, EBP, offset, in); //mov eax, offset[ebp]
2906   emitMovRegToRM(EBP, -(dest*4), EAX, in); //mov dest, 0[eax]
2907   base += in - first;
2908 }
2909
2910
2911 #ifndef BPATCH_LIBRARY
2912 bool process::isDynamicCallSite(instPoint *callSite){
2913   function_base *temp;
2914   if(!findCallee(*(callSite),temp)){
2915     return true;
2916   }
2917   return false;
2918 }
2919
2920 bool process::MonitorCallSite(instPoint *callSite){
2921   Register base_reg, index_reg;
2922   int displacement;
2923   unsigned scale;
2924   int addr_mode;
2925   unsigned Mod;
2926
2927   AstNode *func;
2928   instruction i = callSite->insnAtPoint();
2929   vector<AstNode *> the_args(2);
2930   if(i.isCallIndir()){
2931     addr_mode = get_instruction_operand(i.ptr(), base_reg, index_reg,
2932                                          displacement, scale, Mod);
2933     switch(addr_mode){
2934       
2935     case REGISTER_DIRECT:
2936       the_args[0] = new AstNode(AstNode::PreviousStackFrameDataReg,
2937                                 (void *) base_reg);
2938       the_args[1] = new AstNode(AstNode::Constant,
2939                                 (void *) callSite->iPgetAddress());
2940       func = new AstNode("DYNINSTRegisterCallee", the_args);
2941       addInstFunc(this, callSite, func, callPreInsn,
2942                   orderFirstAtPoint, true,false);
2943       break;
2944     case REGISTER_INDIRECT:
2945       {
2946         AstNode *prevReg = new AstNode(AstNode::PreviousStackFrameDataReg,
2947                                        (void *) base_reg);
2948         the_args[0] = new AstNode(AstNode::DataIndir, prevReg);
2949         the_args[1] = new AstNode(AstNode::Constant,
2950                                   (void *) callSite->iPgetAddress());
2951         func = new AstNode("DYNINSTRegisterCallee", the_args);
2952         addInstFunc(this, callSite, func, callPreInsn,
2953                     orderFirstAtPoint, true,false);
2954         break;
2955       }
2956     case REGISTER_INDIRECT_DISPLACED:
2957       {
2958         AstNode *prevReg = new AstNode(AstNode::PreviousStackFrameDataReg,
2959                                        (void *) base_reg);
2960         AstNode *derefPrevReg = new AstNode(AstNode::DataIndir, prevReg );
2961
2962         AstNode *offset = new AstNode(AstNode::Constant, 
2963                                       (void *) displacement);
2964         AstNode *sum = new AstNode(plusOp, derefPrevReg, offset);
2965         
2966         the_args[0] = new AstNode(AstNode::DataIndir, sum);
2967         the_args[1] = new AstNode(AstNode::Constant,
2968                                   (void *) callSite->iPgetAddress());
2969         func = new AstNode("DYNINSTRegisterCallee", the_args);
2970         addInstFunc(this, callSite, func, callPreInsn,
2971                     orderFirstAtPoint, true,false);
2972         break;
2973       }
2974     case DISPLACED: 
2975       {
2976         AstNode *offset = new AstNode(AstNode::Constant, 
2977                                       (void *) displacement);
2978         the_args[0] = new AstNode(AstNode::DataIndir, offset);
2979         the_args[1] = new AstNode(AstNode::Constant,
2980                                   (void *) callSite->iPgetAddress());
2981         func = new AstNode("DYNINSTRegisterCallee", the_args);
2982         addInstFunc(this, callSite, func, callPreInsn,
2983                     orderFirstAtPoint, true, false);
2984         break;
2985       }
2986     case SIB:
2987       {
2988         AstNode *effective_address;
2989         if(index_reg != 4) { //We use a scaled index
2990           bool useBaseReg = true;
2991           if(Mod == 0 && base_reg == 5){
2992             cerr << "Inserting untested call site monitoring "
2993               "instrumentation at address " << hex << 
2994               callSite->iPgetAddress() << dec << endl;
2995             useBaseReg = false;
2996           }
2997           
2998           AstNode *index = new AstNode(AstNode::PreviousStackFrameDataReg,
2999                                        (void *) index_reg);
3000           AstNode *base = new AstNode(AstNode::PreviousStackFrameDataReg,
3001                                       (void *) base_reg);
3002           
3003           AstNode *disp = new AstNode(AstNode::Constant, 
3004                                       (void *) displacement);
3005           
3006           if(scale == 1){ //No need to do the multiplication
3007             if(useBaseReg){
3008               AstNode *base_index_sum = new AstNode(plusOp, index, base);
3009               effective_address = new AstNode(plusOp, base_index_sum,
3010                                               disp);
3011             }
3012             else 
3013               effective_address = new AstNode(plusOp, index, disp); 
3014             
3015             the_args[0] = new AstNode(AstNode::DataIndir, effective_address);
3016             
3017             the_args[1] = new AstNode(AstNode::Constant,
3018                                       (void *) callSite->iPgetAddress());
3019             func = new AstNode("DYNINSTRegisterCallee", the_args);
3020             addInstFunc(this, callSite, func, callPreInsn,
3021                         orderFirstAtPoint, true, false);
3022           }
3023           else {
3024             AstNode *scale_factor
3025               = new AstNode(AstNode::Constant, (void *) scale);
3026             AstNode *index_scale_product = new AstNode(timesOp, index, 
3027                                                        scale_factor);
3028             if(useBaseReg){
3029               AstNode *base_index_sum = new AstNode(plusOp, 
3030                                                     index_scale_product,
3031                                                     base);
3032               effective_address = new AstNode(plusOp, base_index_sum,
3033                                               disp);
3034             }
3035             else 
3036               effective_address = new AstNode(plusOp, 
3037                                                index_scale_product,
3038                                                disp);
3039             the_args[0] = new AstNode(AstNode::DataIndir, effective_address);
3040             
3041             the_args[1] = new AstNode(AstNode::Constant,
3042                                       (void *) callSite->iPgetAddress());
3043             func = new AstNode("DYNINSTRegisterCallee", the_args);
3044             addInstFunc(this, callSite, func, callPreInsn,
3045                         orderFirstAtPoint, true,false);
3046           }
3047         }
3048         else { //We do not use a scaled index. 
3049           cerr << "Inserting untested call site monitoring "
3050             "instrumentation at address " << hex <<
3051             callSite->iPgetAddress() << dec << endl;
3052           AstNode *base = new AstNode(AstNode::PreviousStackFrameDataReg,
3053                                       (void *) base_reg);
3054           AstNode *disp = new AstNode(AstNode::Constant, 
3055                                       (void *) displacement);
3056           AstNode *effective_address =  new AstNode(plusOp, base,
3057                                                     disp);
3058           the_args[0] = new AstNode(AstNode::DataIndir, effective_address);
3059           
3060           the_args[1] = new AstNode(AstNode::Constant,
3061                                     (void *) callSite->iPgetAddress());
3062           func = new AstNode("DYNINSTRegisterCallee", the_args);
3063           addInstFunc(this, callSite, func, callPreInsn,
3064                       orderFirstAtPoint, true, false);
3065         }
3066       }
3067       break;
3068       
3069     default:
3070       cerr << "Unexpected addressing type in MonitorCallSite at addr:" 
3071            << hex << callSite->iPgetAddress() << dec 
3072            << "The daemon declines the monitoring request of this call site." 
3073            << endl; 
3074       break;
3075     }
3076   }
3077   else if(i.isCall()){
3078     //Regular callees are statically determinable, so no need to 
3079     //instrument them
3080     return true;
3081   }
3082   else {
3083     cerr << "Unexpected instruction in MonitorCallSite()!!!\n";
3084   }
3085   return true;
3086 }
3087 #endif
3088
3089 #if (defined(i386_unknown_solaris2_5) || defined(i386_unknown_linux2_0))
3090 #include <sys/signal.h>
3091 //#include <sys/ucontext.h>
3092
3093 void
3094 BaseTrampTrapHandler (int)//, siginfo_t*, ucontext_t*)
3095 {
3096   cout << "In BaseTrampTrapHandler()" << endl;
3097   // unset trap handler, so that DYNINSTtrapHandler can take place
3098   if (sigaction(SIGTRAP, NULL, NULL) != 0) {
3099     perror("sigaction(SIGTRAP)");
3100     assert(0);
3101     abort();
3102   }
3103 }
3104 #endif
3105
3106 bool deleteBaseTramp(process *proc,instPoint* location,
3107                      instInstance* instance)
3108 {
3109         cerr << "WARNING : deleteBaseTramp is unimplemented "
3110              << "(after the last instrumentation deleted)" << endl;
3111         return false;
3112 }
3113
3114
3115 #ifdef BPATCH_LIBRARY
3116 /*
3117  * createInstructionInstPoint
3118  *
3119  * Create a BPatch_point instrumentation point at the given address, which
3120  * is guaranteed not be one of the "standard" inst points.
3121  *
3122  * proc         The process in which to create the inst point.
3123  * address      The address for which to create the point.
3124  */
3125 BPatch_point *createInstructionInstPoint(process* /* proc */, void *address,
3126                                          BPatch_point** alternative)
3127 {
3128     BPatch_reportError(BPatchSerious, 109,
3129         "BPatch_image::createInstPointAtAddr unimplemented on this platform");
3130     return NULL;
3131 }
3132
3133 /*
3134  * BPatch_point::getDisplacedInstructions
3135  *
3136  * Returns the instructions to be relocated when instrumentation is inserted
3137  * at this point.  Returns the number of bytes taken up by these instructions.
3138  *
3139  * maxSize      The maximum number of bytes of instructions to return.
3140  * insns        A pointer to a buffer in which to return the instructions.
3141  */
3142
3143 int BPatch_point::getDisplacedInstructions(int maxSize, void* insns)
3144 {
3145     void *code;
3146     char copyOut[1024];
3147     unsigned int count = 0;
3148
3149     if (point->insnsBefore()) {
3150         for (unsigned int i=0; i < point->insnsBefore(); i++) {
3151             code = const_cast<unsigned char *>(point->insnBeforePt(i).ptr());
3152             memcpy(&copyOut[count], code, point->insnBeforePt(i).size());
3153             count += point->insnBeforePt(i).size();
3154             assert(count < sizeof(copyOut));
3155         }
3156     }
3157
3158     code = const_cast<unsigned char *>(point->insnAtPoint().ptr());
3159     memcpy(&copyOut[count], code, point->insnAtPoint().size());
3160     count += point->insnAtPoint().size();
3161     assert(count < sizeof(copyOut));
3162
3163     if (point->insnsAfter()) {
3164         for (unsigned int i=0; i < point->insnsAfter(); i++) {
3165             code = const_cast<unsigned char *>(point->insnAfterPt(i).ptr());
3166             memcpy(&copyOut[count], code, point->insnAfterPt(i).size());
3167             count += point->insnAfterPt(i).size();
3168             assert(count < sizeof(copyOut));
3169         }
3170     }
3171
3172     if (count <= (unsigned) maxSize) {
3173         memcpy(insns, copyOut, count);
3174         return(count);
3175     } else {
3176         return -1;
3177     }
3178 }
3179
3180 #endif
3181
3182 /****************************************************************************/
3183 /****************************************************************************/
3184
3185 /* pd_Function Code for function relocation */
3186
3187 // Check if an instruction is a relative addressed jump instruction
3188
3189 bool pd_Function::isNearBranchInsn(const instruction insn) {
3190   if (insn.isJumpDir())
3191     return true;
3192   return false;
3193 }
3194
3195 // Check if an instruction is a relative addressed call instruction 
3196
3197 bool pd_Function::isTrueCallInsn(const instruction insn) {
3198   if (insn.isCall() && !insn.isCallIndir())
3199     return true;
3200   return false;
3201 }
3202
3203 /****************************************************************************/
3204 /****************************************************************************/
3205
3206 /* x86 */
3207
3208 // Create a buffer of x86 instructon objects. These x86 instructions will
3209 // contain pointers to the machine code 
3210
3211 bool pd_Function::loadCode(const image* /* owner */, process *proc, 
3212                            instruction *&oldCode, 
3213                            unsigned &numberOfInstructions, 
3214                            Address &firstAddress) {
3215
3216   vector<instruction> insnVec;
3217   unsigned type, insnSize, totalSize = 0; 
3218   instruction *insn = 0;
3219
3220 #ifdef DEBUG_FUNC_RELOC 
3221     cerr << "pd_Function::loadCode" << endl;
3222 #endif
3223
3224   originalCode = new unsigned char[size()];
3225
3226   // copy function to be relocated from application into instructions
3227   proc->readDataSpace((caddr_t)firstAddress, size(), originalCode, true);
3228
3229   // first address of function
3230   unsigned char *p = originalCode;
3231
3232   // last address of function
3233   unsigned end_of_function = (unsigned)(p + size());
3234
3235   // iterate over all instructions in function
3236   while ( (unsigned) p < end_of_function ) {
3237
3238     // new instruction object 
3239     insnSize = get_instruction(p, type);
3240     insn = new instruction(p, type, insnSize);   
3241     insnVec.push_back(*insn);
3242
3243     /*
3244     // check for the following instruction sequence:
3245     //
3246     //  call (0)       (PC relative address, where the target of call (0)
3247     //                  is the next instruction
3248     //  pop  %ebx      (pops return address of call instruction off of the
3249     //                  stack and places it in the ebx reg. The value in
3250     //                  ebx becomes the address of the pop instruction
3251     //
3252     // This sequence is used to get the address of the currently 
3253     // executing instruction. Presently we don't relocate a function 
3254     // with this sequence of instructions 
3255
3256     // A call instruction whose target is the next instruction, is generally
3257     // used to obtain the address of the next instruction. 
3258     // Presently we don't relocate a functions with such calls
3259     if ( isTrueCallInsn((const instruction)(*insn)) && 
3260          get_disp(insn) == 0 && *(p + insnSize) == 0x5b ) {
3261
3262          relocatable_ = false;
3263
3264          delete insn;
3265          return false;
3266     }
3267     */
3268
3269     // update p so it points to the next machine code instruction
3270     p = p + insnSize; 
3271     totalSize += insnSize;
3272
3273     delete insn;
3274   }
3275
3276   // Occasionally a function's size is not calculated correctly for 
3277   // pd_Function. In such cases, the last few bytes in the function
3278   // are "garbage", and the parsing done in the above while loop
3279   // interprets those bytes as an instruction. If the last byte of that 
3280   // "garbage" instruction is outside the bounds of the function, 
3281   // the sum of the insnSizes of the insn's that were parsed above will be 
3282   // greater than the size of the function being relocating. To keep the
3283   // sum of the insnSizes equal to the size of the pd_Function, we replace 
3284   // the "garbage" bytes with nop instructions, and ignore drop those bytes
3285   // that are outside of the function.   
3286
3287   // # bytes of "garbage" at the end of the function 
3288   int garbage = (unsigned)p - end_of_function;
3289
3290   // if "garbage" bytes are found
3291   if (garbage) { 
3292   
3293     // create a nop machine instruction
3294     unsigned char *nop = new unsigned char;
3295     emitSimpleInsn(0x90, nop);
3296     nop--;
3297
3298     // create an x86 instruction for a nop
3299     insn = new instruction(nop, 0, 1);
3300
3301     // replace "garbage" x86 instruction with a nop instruction
3302     insnVec[insnVec.size() - 1] = *insn;
3303
3304     // replace all "garbage" bytes up to the end of the function with nops
3305     for (int i = 0; i < garbage; i++) {   
3306       insnVec.push_back(*insn);
3307     }  
3308   }
3309
3310   // buffer of x86 instructions
3311   unsigned bufSize = insnVec.size();
3312   oldCode = new instruction[bufSize];
3313
3314   // if unable to allocate array, dump warn and return false.... 
3315   if (oldCode == NULL) {
3316     cerr << "WARN : unable to allocate array (" << insnVec.size() << " bytes) to read in " \
3317          << "instructions for function" << prettyName().string_of() << " unable to instrument" \
3318          << endl;
3319     return false;
3320   }
3321
3322   // copy vector of instructions into buffer of instructions
3323   for (unsigned i = 0; i < insnVec.size(); i++) {
3324     oldCode[i] = insnVec[i];
3325   }
3326
3327   numberOfInstructions = insnVec.size();
3328   setNumInstructions(numberOfInstructions);  
3329   
3330   return true;
3331
3332
3333 /****************************************************************************/
3334 /****************************************************************************/
3335
3336 // Copy machine code from one location (in mutator) to another location
3337 // (also in the mutator)
3338 // Also updates the corresponding buffer of x86 instructions 
3339
3340 void pd_Function::copyInstruction(instruction &newInsn, instruction &oldInsn, 
3341                                                       unsigned &codeOffset) {
3342  
3343   unsigned insnSize = oldInsn.size(); 
3344   const unsigned char *oldPtr = oldInsn.ptr();
3345   unsigned tmp = codeOffset;
3346
3347 #ifdef DEBUG_FUNC_RELOC 
3348       cerr << "pd_Function::copyInstruction" << endl;
3349 #endif 
3350
3351   // iterate over each byte of the machine instruction, copying it
3352   for (unsigned i = 0; i < insnSize; i++) {     
3353     relocatedCode[codeOffset] = *(oldPtr + i);
3354     codeOffset++;
3355   }
3356
3357   // update x86 instruction corresponding to machine code instruction
3358   newInsn = *(new instruction(&relocatedCode[tmp], oldInsn.type(), insnSize));
3359 }   
3360
3361 /****************************************************************************/
3362 /****************************************************************************/
3363
3364 // update displacement of expanded instruction
3365
3366 int pd_Function::expandInstructions(LocalAlterationSet &alteration_set, 
3367                                     instruction &insn, 
3368                                     Address offset,
3369                                     instruction &newCodeInsn) {
3370
3371  
3372   int oldDisp = 0, newDisp = 0, extra_offset = 0;
3373   unsigned char *oldInsn = 0, *newInsn = 0;
3374  
3375   unsigned insnType = insn.type(); 
3376
3377   // location (in mutator) instruction was originally located at
3378   oldInsn = const_cast<unsigned char *> (insn.ptr());
3379
3380   // location (in mutator) instruction is being relocated to (temporarily)
3381   newInsn = const_cast<unsigned char *> (newCodeInsn.ptr());
3382
3383   // old displacement from instruction to target
3384   oldDisp = get_disp(&insn);
3385
3386   // change in displacement of target  
3387   extra_offset = alteration_set.getShift(offset + oldDisp) - 
3388                  alteration_set.getShift(offset);
3389
3390   if (insnType & REL_B) {
3391     /* replace with rel32 instruction, opcode is one byte. */
3392     if (*oldInsn == JCXZ) {
3393       *newInsn++ = *oldInsn; *newInsn++ = 2; // jcxz 2
3394       *newInsn++ = 0xEB; *newInsn++ = 5;        // jmp 5
3395       *newInsn++ = 0xE9;                        // jmp rel32
3396       *((int *)newInsn) = oldDisp + extra_offset - 7; // change in insn size is 7
3397       newInsn += sizeof(int);
3398       return true;
3399     } else {
3400         unsigned newSz=UINT_MAX;
3401         if (insnType & IS_JCC) {
3402           /* Change a Jcc rel8 to Jcc rel32. 
3403              Must generate a new opcode: a 0x0F followed by (old opcode + 16) */
3404           unsigned char opcode = *oldInsn++;
3405           *newInsn++ = 0x0F;
3406           *newInsn++ = opcode + 0x10;
3407           newDisp = oldDisp + extra_offset - 4;   // change in insn size is 4
3408           newSz = 6;
3409         } else {
3410             if (insnType & IS_JUMP) {
3411               /* change opcode to 0xE9 */
3412               oldInsn++;
3413               *newInsn++ = 0xE9;
3414               newDisp = oldDisp + extra_offset - 3;  // change in insn size is 3
3415               newSz = 5;
3416             }
3417             assert(newSz!=UINT_MAX);
3418             *((int *)newInsn) = newDisp;
3419             newInsn += sizeof(int); 
3420             return true;
3421         }
3422     }
3423   } else {
3424       if (insnType & REL_W) {
3425         assert(insnType & PREFIX_OPR);
3426         if (insnType & PREFIX_SEG)
3427           *newInsn++ = *oldInsn++;
3428         
3429            /* opcode is unchanged, just relocate the displacement */
3430    
3431           if (*oldInsn == (unsigned char)0x0F)
3432             *newInsn++ = *oldInsn++;
3433           *newInsn++ = *oldInsn++;
3434           newDisp = oldDisp + extra_offset - 1;  // change in insn size is 1
3435           *((int *)newInsn) = newDisp;
3436           newInsn += sizeof(int);
3437           return true;
3438       } else {
3439           // should never get here
3440           assert (insnType & REL_D);
3441           assert (0); 
3442       }
3443   }
3444    return false;   
3445 }
3446
3447
3448 /****************************************************************************/
3449 /****************************************************************************/
3450
3451 // given the Address adr, calculate the offset in the buffer code[], 
3452 // of the x86 instruction that begins at adr. Return -1 if adr is 
3453 // a byte in the middle of an instruction and not the first byte of 
3454 // the instruction
3455
3456 int pd_Function::getArrayOffset(Address adr, instruction code[]) {
3457   
3458   unsigned i;
3459   Address insnAdr = addressOfMachineInsn(&code[0]);  
3460
3461 #ifdef DEBUG_FUNC_RELOC
3462       cerr << "pd_Function::getArrayOffset" << endl;
3463 #endif
3464
3465   assert(adr >= insnAdr && adr <= insnAdr + size()); 
3466
3467   // find the instruction that contains the byte at Address adr
3468   for (i = 0; insnAdr < adr; i++) {
3469     insnAdr += ((instruction)code[i]).size();
3470   }
3471
3472   // if adr is the first byte of the instruction, return the offset in
3473   // the buffer of the instruction
3474   if (insnAdr == adr) return i;
3475   else return -1;
3476 }
3477
3478 /****************************************************************************/
3479 /****************************************************************************/
3480
3481 // update the before and after insns of x86 instPoint p
3482
3483 void pd_Function::instrAroundPt(instPoint *p, instruction allInstr[], 
3484                                 int numBefore, int numAfter, 
3485                                 unsigned type, int index) {   
3486
3487   // add instructions before the point
3488   unsigned size = (p->insnAtPoint()).size();
3489   for (int u1 = index-1; size < JUMP_SZ && u1 >= 0 && 
3490                            u1 > (index - 1) - numBefore; u1--) {
3491     if (!allInstr[u1].isCall()) {
3492        p->addInstrBeforePt(allInstr[u1]);
3493        size += allInstr[u1].size();
3494     } else {
3495        break;
3496     }
3497   }
3498
3499   // add instructions after the point
3500   if (type == ReturnPt) {
3501
3502     for (int u1 = index+1; size < JUMP_SZ && u1 < (index + 1) + numAfter; u1++) {
3503
3504       if (allInstr[u1].isNop() || *(allInstr[u1].ptr()) == 0xCC) {
3505            p->addInstrAfterPt(allInstr[u1]);
3506            size += allInstr[u1].size();
3507       } else {
3508         break;
3509       }
3510     }
3511
3512   } else {
3513
3514       unsigned maxSize = JUMP_SZ;
3515       if (type == EntryPt) maxSize = 2*JUMP_SZ;
3516       for (int u1 = index+1; size < maxSize && u1 < (index + 1) + numAfter; u1++) {
3517         if (!allInstr[u1].isCall()) {
3518           p->addInstrAfterPt(allInstr[u1]);
3519           size += allInstr[u1].size();
3520         } else { 
3521           break;
3522         }
3523       }
3524   }
3525 }
3526
3527
3528 /****************************************************************************/
3529 /****************************************************************************/
3530 // originalOffset:      offset (in bytes) of the machine insn from the 
3531 //                      beginning of the original function
3532 //
3533 // newOffset:           offset (in bytes) of the machine insn from the 
3534 //                      beginning of the relocated and expanded function 
3535 //
3536 // originalArrayOffset: offset (in # of instructions) of the x86 instruction 
3537 //                      corresponding to the instPoint, from the beginning of 
3538 //                      the buffer corresponding to the original function.
3539 //
3540 // newArrayOffset:      offset (in # of instructions) of the x86 instruction 
3541 //                      corresponding to the instPoint, from the beginning of 
3542 //                      the buffer corresponding to the expanded and relocate
3543 //                      function.
3544 //
3545 // oldJumpOffset:       offset (in bytes) from the beginning of the original
3546 //                      function, at which the jump to the baseTramp would be
3547 //                      placed.
3548 //
3549 // newJumpOffset:       offset (in bytes) from the beginning of the expanded 
3550 //                      and relocated function, at which the jump to the 
3551 //                      baseTramp would be placed.
3552 //
3553 // newJumpAddr:         absolute Address of the jump to the baseTramp, 
3554 //                      in the expanded and relocated function would be placed.
3555 //
3556 // newJumpAddr:         absolute Address of the instruction in the expanded 
3557 //                      and relocated function.
3558
3559
3560 #define CALC_OFFSETS(ip)                                                      \
3561      originalOffset = ((ip->iPgetAddress() + imageBaseAddr) - mutatee);       \
3562      originalArrayOffset = getArrayOffset(originalOffset + mutator, oldCode); \
3563      if (originalArrayOffset < 0) return false;                               \
3564      newOffset = originalOffset + alteration_set.getShift(originalOffset);    \
3565      newArrayOffset = originalArrayOffset +                                   \
3566                       alteration_set.getInstPointShift(originalOffset);       \
3567      oldJumpOffset = (ip->jumpAddr() + imageBaseAddr) - mutatee;              \
3568      newJumpOffset = oldJumpOffset + alteration_set.getShift(oldJumpOffset);  \
3569      newJumpAddr = newAdr + newJumpOffset;                                    \
3570      adr = newAdr + newOffset;
3571  
3572 /****************************************************************************/
3573 /****************************************************************************/
3574
3575 // update info about instrumentation points
3576
3577 bool pd_Function::fillInRelocInstPoints(
3578                             const image *owner, process *proc,
3579                             instPoint *&location, 
3580                             relocatedFuncInfo *&reloc_info, Address mutatee, 
3581                             Address mutator,instruction oldCode[], 
3582                             Address newAdr,instruction newCode[],
3583                             LocalAlterationSet &alteration_set) {
3584    
3585   unsigned retId = 0, callId = 0,arbitraryId = 0;
3586   int originalOffset, newOffset, originalArrayOffset, newArrayOffset;
3587   int oldJumpOffset, newJumpOffset;
3588   Address adr, newJumpAddr;
3589
3590   instPoint *point = 0; 
3591
3592   assert(newAdr);
3593
3594 #ifdef DEBUG_FUNC_RELOC    
3595     cerr << "pd_Function::fillInRelocInstPoints called" <<endl;
3596     cerr << " mutator = " << mutator << " mutatee = " << mutatee 
3597          << " newAdr = " << hex << newAdr << endl;
3598 #endif
3599
3600   Address imageBaseAddr;
3601   if (!proc->getBaseAddress(owner, imageBaseAddr))
3602         abort();
3603
3604   alteration_set.Collapse();
3605
3606   //  Add inst point corresponding to func entry....
3607   //   Assumes function has single entry point  
3608   if (funcEntry_ != NULL) {
3609
3610     //  figure out how far entry inst point is from beginning of function..
3611     CALC_OFFSETS(funcEntry_)
3612
3613     point = new instPoint(this, owner, adr-imageBaseAddr, newCode[newArrayOffset]);
3614
3615 #ifdef DEBUG_FUNC_RELOC    
3616         cerr << " added entry point at originalOffset " << originalOffset
3617              << " newOffset " << newOffset << endl;
3618 #endif
3619
3620     assert(point != NULL);
3621
3622     point->setRelocated();
3623
3624     point->setJumpAddr(newJumpAddr-imageBaseAddr);
3625
3626     instrAroundPt(point, newCode, funcEntry_->insnsBefore(), 
3627                   funcEntry_->insnsAfter() + 
3628                   alteration_set.numInstrAddedAfter(originalOffset), 
3629                   EntryPt, newArrayOffset);  
3630
3631     if (location == funcEntry_) {
3632       location = point;
3633     }
3634
3635     // update reloc_info with new instPoint
3636     reloc_info->addFuncEntry(point);
3637     assert(reloc_info->f