Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / ast.C
1 /*
2  * Copyright (c) 1996-2009 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  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 // $Id: ast.C,v 1.209 2008/09/15 18:37:49 jaw Exp $
33
34 #include "dyninstAPI/src/symtab.h"
35 #include "dyninstAPI/src/process.h"
36 #include "dyninstAPI/src/inst.h"
37 #include "dyninstAPI/src/instP.h"
38 #include "dyninstAPI/src/instPoint.h"
39 #include "dyninstAPI/src/ast.h"
40 #include "dyninstAPI/src/util.h"
41 #include "dyninstAPI/src/debug.h"
42
43 #if defined(cap_instruction_api)
44 #include "Instruction.h"
45 using namespace Dyninst::InstructionAPI;
46 #else
47 #include "dyninstAPI/src/InstrucIter.h"
48 #endif
49
50 #include "dyninstAPI/h/BPatch.h"
51 #include "dyninstAPI/src/BPatch_collections.h"
52 #include "dyninstAPI/h/BPatch_type.h"
53 #include "dyninstAPI/src/BPatch_libInfo.h" // For instPoint->BPatch_point mapping
54
55 #include "dyninstAPI/h/BPatch_point.h"
56 #include "dyninstAPI/h/BPatch_memoryAccess_NP.h"
57 #include "dyninstAPI/h/BPatch_type.h"
58
59 #include "dyninstAPI/src/addressSpace.h"
60 #include "dyninstAPI/src/binaryEdit.h"
61
62 #if defined(arch_sparc)
63 #include "dyninstAPI/src/inst-sparc.h"
64 #elif defined(arch_power)
65 #include "dyninstAPI/src/inst-power.h"
66 #elif defined(arch_x86) || defined (arch_x86_64)
67 #include "dyninstAPI/src/inst-x86.h"
68 extern int tramp_pre_frame_size_32;
69 extern int tramp_pre_frame_size_64;
70 #elif defined(arch_ia64)
71 #include "dyninstAPI/src/inst-ia64.h"
72 #else
73 #error "Unknown architecture in ast.h"
74 #endif
75
76 #include "emitter.h"
77
78 #include "registerSpace.h"
79 #include "mapped_module.h"
80
81 using namespace Dyninst;
82
83 extern bool doNotOverflow(int value);
84
85 AstNodePtr AstNode::originalAddrNode_ = AstNodePtr();
86 AstNodePtr AstNode::actualAddrNode_ = AstNodePtr();
87 AstNodePtr AstNode::dynamicTargetNode_ = AstNodePtr();
88
89 AstNode::AstNode() {
90 #if defined(ASTDEBUG)
91    ASTcounter();
92 #endif
93    referenceCount = 0;
94    useCount = 0;
95    // "operands" is left as an empty vector
96    size = 4;
97    bptype = NULL;
98    doTypeCheck = true;
99
100 }
101
102 AstNodePtr AstNode::nullNode() {
103     return AstNodePtr(new AstNullNode());
104 }
105
106 AstNodePtr AstNode::labelNode(std::string &label) {
107     return AstNodePtr (new AstLabelNode(label));
108 }
109
110 AstNodePtr AstNode::operandNode(operandType ot, void *arg) {
111     return AstNodePtr(new AstOperandNode(ot, arg));
112 }
113
114 // TODO: this is an indirect load; should be an operator.
115 AstNodePtr AstNode::operandNode(operandType ot, AstNodePtr ast) {
116     return AstNodePtr(new AstOperandNode(ot, ast));
117 }
118
119 AstNodePtr AstNode::operandNode(operandType ot, const image_variable* iv) {
120     return AstNodePtr(new AstOperandNode(ot, iv));
121 }
122
123 AstNodePtr AstNode::sequenceNode(pdvector<AstNodePtr > &sequence) {
124     return AstNodePtr(new AstSequenceNode(sequence));
125 }
126
127 AstNodePtr AstNode::variableNode(vector<AstNodePtr> &ast_wrappers, 
128                                  vector<pair<Offset, Offset> >*ranges) {
129     return AstNodePtr(new AstVariableNode(ast_wrappers, ranges));
130 }
131
132 AstNodePtr AstNode::operatorNode(opCode ot, AstNodePtr l, AstNodePtr r, AstNodePtr e) {
133     return AstNodePtr(new AstOperatorNode(ot, l, r, e));
134 }
135
136 AstNodePtr AstNode::funcCallNode(const std::string &func, pdvector<AstNodePtr > &args,
137       AddressSpace *addrSpace) 
138 {
139    if (addrSpace) 
140    {
141       int_function *ifunc = addrSpace->findOnlyOneFunction(func.c_str());
142
143       if (ifunc == NULL) 
144       {
145          fprintf(stderr, "Bitch whine moan\n");
146          fprintf(stderr, "%s[%d]: Can't find function %s\n", FILE__, __LINE__, func.c_str());
147          return AstNodePtr();
148       }
149
150       return AstNodePtr(new AstCallNode(ifunc, args));
151    }
152    else
153       return AstNodePtr(new AstCallNode(func, args));
154 }
155
156 AstNodePtr AstNode::funcCallNode(int_function *func, pdvector<AstNodePtr > &args) {
157     if (func == NULL) return AstNodePtr();
158     return AstNodePtr(new AstCallNode(func, args));
159 }
160
161 AstNodePtr AstNode::funcCallNode(int_function *func) {
162     if (func == NULL) return AstNodePtr();
163     return AstNodePtr(new AstCallNode(func));
164 }
165
166 AstNodePtr AstNode::funcCallNode(Address addr, pdvector<AstNodePtr > &args) {
167     return AstNodePtr(new AstCallNode(addr, args));
168 }
169
170 AstNodePtr AstNode::funcReplacementNode(int_function *func) {
171     if (func == NULL) return AstNodePtr();
172     return AstNodePtr(new AstReplacementNode(func));
173 }
174
175 AstNodePtr AstNode::memoryNode(memoryType ma, int which) {
176     return AstNodePtr(new AstMemoryNode(ma, which));
177 }
178
179 AstNodePtr AstNode::miniTrampNode(AstNodePtr tramp) {
180     if (tramp == NULL) return AstNodePtr();
181     return AstNodePtr(new AstMiniTrampNode(tramp));
182 }
183
184 AstNodePtr AstNode::insnNode(BPatch_instruction *insn) {
185     // Figure out what kind of instruction we've got...
186     if (dynamic_cast<BPatch_memoryAccess *>(insn)) {
187         return AstNodePtr(new AstInsnMemoryNode(insn->insn(), (Address) insn->getAddress()));
188     } 
189     
190     return AstNodePtr(new AstInsnNode(insn->insn(), (Address) insn->getAddress()));
191 }
192
193 AstNodePtr AstNode::originalAddrNode() {
194     if (originalAddrNode_ == NULL) {
195         originalAddrNode_ = AstNodePtr(new AstOriginalAddrNode());
196     }
197     return originalAddrNode_;
198 }
199
200 AstNodePtr AstNode::actualAddrNode() {
201     if (actualAddrNode_ == NULL) {
202         actualAddrNode_ = AstNodePtr(new AstActualAddrNode());
203     }
204     return actualAddrNode_;
205 }
206
207 AstNodePtr AstNode::dynamicTargetNode() {
208     if (dynamicTargetNode_ == NULL) {
209         dynamicTargetNode_ = AstNodePtr(new AstDynamicTargetNode());
210     }
211     return dynamicTargetNode_;
212 }
213
214
215 bool isPowerOf2(int value, int &result)
216 {
217   if (value<=0) return(false);
218   if (value==1) {
219     result=0;
220     return(true);
221   }
222   if ((value%2)!=0) return(false);
223   if (isPowerOf2(value/2,result)) {
224     result++;
225     return(true);
226   }
227   else return(false);
228 }
229
230 BPatch_type *AstNode::getType() { return bptype; }
231
232 void AstNode::setType(BPatch_type *t) { 
233     bptype = t;
234     if (t != NULL) { 
235         size = t->getSize(); 
236     }
237 }
238
239 AstOperatorNode::AstOperatorNode(opCode opC, AstNodePtr l, AstNodePtr r, AstNodePtr e) :
240     AstNode(),
241     op(opC),
242     loperand(l),
243     roperand(r),
244     eoperand(e)
245 {
246     // Optimization pass...
247     
248     if (op == plusOp) {
249         if (loperand->getoType() == Constant) {
250             // Swap left and right...
251             AstNodePtr temp = loperand;
252             loperand = roperand;
253             roperand = temp;
254         }
255     }
256     if (op == timesOp) {
257         if (roperand->getoType() == undefOperandType) {
258             // ...
259         }
260         else if (roperand->getoType() != Constant) {
261             AstNodePtr temp = roperand;
262             roperand = loperand;
263             loperand = temp;
264         }
265         else {
266             int result;
267             if (!isPowerOf2((Address)roperand->getOValue(),result) &&
268                 isPowerOf2((Address)loperand->getOValue(),result)) {
269                 AstNodePtr temp = roperand;
270                 roperand = loperand;
271                 loperand = temp;
272             }
273         }
274     }
275     if (l != AstNodePtr())
276     {
277        //Unfortunate hack.  storeOp with a loperand of DataIndir
278        // don't actually reference their loperand--they reference
279        // the child of the loperand.  Handle that here to keep
280        // reference counts sane.
281        if (op == storeOp && loperand->getoType() == DataIndir)
282           l->operand()->referenceCount++;
283        else
284           l->referenceCount++;
285     }
286     if (r != AstNodePtr())
287        r->referenceCount++;
288     if (e != AstNodePtr())
289        e->referenceCount++;
290 };
291
292     // Direct operand
293 AstOperandNode::AstOperandNode(operandType ot, void *arg) :
294     AstNode(),
295     oType(ot),
296     oVar(NULL),
297     operand_()
298 {
299     
300     if (ot == ConstantString)
301         oValue = (void *)P_strdup((char *)arg);
302     else
303         oValue = (void *) arg;
304 }
305
306 // And an indirect (say, a load)
307 AstOperandNode::AstOperandNode(operandType ot, AstNodePtr l) :
308     AstNode(),
309     oType(ot),
310     oValue(NULL),
311     oVar(NULL),
312     operand_(l)
313 {
314    l->referenceCount++;
315 }
316
317 AstOperandNode::AstOperandNode(operandType ot, const image_variable* iv) :
318   AstNode(),
319   oType(ot),
320   oValue(NULL),
321   oVar(iv),
322   operand_()
323 {
324   assert(oVar);
325 }
326
327
328 AstCallNode::AstCallNode(int_function *func,
329                          pdvector<AstNodePtr > &args) :
330     AstNode(),
331     func_addr_(0),
332     func_(func),
333     callReplace_(false),
334     constFunc_(false)
335 {
336     for (unsigned i = 0; i < args.size(); i++) {
337         args[i]->referenceCount++; 
338         args_.push_back(args[i]);
339     }
340 }
341
342 AstCallNode::AstCallNode(int_function *func) :
343     AstNode(),
344     func_addr_(0),
345     func_(func),
346     callReplace_(true),
347     constFunc_(false)
348 {
349 }
350
351 AstCallNode::AstCallNode(const std::string &func,
352                          pdvector<AstNodePtr > &args) :
353     AstNode(),
354     func_name_(func),
355     func_addr_(0),
356     func_(NULL),
357     callReplace_(false),
358     constFunc_(false)
359 {
360     for (unsigned i = 0; i < args.size(); i++) {
361         args[i]->referenceCount++; 
362         args_.push_back(args[i]);
363     }
364 }
365
366 AstCallNode::AstCallNode(Address addr,
367                          pdvector<AstNodePtr > &args) :
368     AstNode(),
369     func_addr_(addr),
370     func_(NULL),
371     callReplace_(false),
372     constFunc_(false)
373 {
374     for (unsigned i = 0; i < args.size(); i++) {
375         args[i]->referenceCount++; 
376         args_.push_back(args[i]);
377     }
378 }
379  
380 AstSequenceNode::AstSequenceNode(pdvector<AstNodePtr > &sequence) :
381     AstNode()
382 {
383     for (unsigned i = 0; i < sequence.size(); i++) {
384         sequence[i]->referenceCount++;
385         sequence_.push_back(sequence[i]);
386     }
387 }
388
389 AstVariableNode::AstVariableNode(vector<AstNodePtr>&ast_wrappers, vector<pair<Offset, Offset> > *ranges) :
390     ast_wrappers_(ast_wrappers), ranges_(ranges), index(0)
391 {
392    vector<AstNodePtr>::iterator i;
393    for (i = ast_wrappers.begin(); i != ast_wrappers.end(); i++) {
394       (*i)->referenceCount++;
395    }
396 }
397
398 AstInsnNode::AstInsnNode(instruction *insn, Address addr) :
399     AstNode(),
400     insn_(insn),
401     origAddr_(addr) {
402 }
403
404 AstMemoryNode::AstMemoryNode(memoryType mem,
405                              unsigned which) :
406     AstNode(),
407     mem_(mem),
408     which_(which) {
409     
410     assert(BPatch::bpatch != NULL);
411     assert(BPatch::bpatch->stdTypes != NULL);
412
413     
414     switch(mem_) {
415     case EffectiveAddr:
416         bptype = BPatch::bpatch->stdTypes->findType("void *");
417         break;
418     case BytesAccessed:
419         bptype = BPatch::bpatch->stdTypes->findType("int");
420         break;
421     default:
422         assert(!"Naah...");
423     }
424     size = bptype->getSize();
425     doTypeCheck = BPatch::bpatch->isTypeChecked();
426 };
427
428 AstNodePtr AstNode::threadIndexNode() {
429     // We use one of these across all platforms, since it
430     // devolves into a process-specific function node. 
431     // However, this lets us delay that until code generation
432     // when we have the process pointer.
433     static AstNodePtr indexNode_;
434
435     // Since we only ever have one, keep a static copy around. If
436     // we get multiples, we'll screw up our pointer-based common subexpression
437     // elimination.
438
439     if (indexNode_ != AstNodePtr()) return indexNode_;
440     pdvector<AstNodePtr > args;
441     // By not including a process we'll specialize at code generation.
442     indexNode_ = AstNode::funcCallNode("DYNINSTthreadIndex", args);
443     assert(indexNode_);
444     indexNode_->setConstFunc(true);
445
446     return indexNode_;
447 }
448
449
450 #if defined(ASTDEBUG)
451 #define AST_PRINT
452 #endif
453
454 #if defined(AST_PRINT)
455 void AstNode::printRC()
456 {
457     sprintf(errorLine,"RC referenceCount=%d\n",referenceCount);
458     logLine(errorLine);
459     if (loperand) {
460       logLine("RC loperand\n");
461       loperand->printRC();
462     }
463     if (roperand) {
464       logLine("RC roperand\n");
465       roperand->printRC();
466     }
467     if (eoperand) {
468       logLine("RC eoperand\n");
469       eoperand->printRC();
470     }
471 }
472 #endif
473
474 AstNode::~AstNode() {
475     //printf("at ~AstNode()  count=%d\n", referenceCount);
476 }
477
478 Address AstMiniTrampNode::generateTramp(codeGen &gen,
479                                         int &trampCost, 
480                                         bool noCost) {
481     static AstNodePtr costAst;
482     static AstNodePtr preamble;
483
484     if (costAst == AstNodePtr())
485         costAst = AstNode::operandNode(AstNode::Constant, (void *)0);
486
487     if (preamble == AstNodePtr())
488         preamble = AstNode::operatorNode(trampPreamble, costAst);
489
490     // private constructor; assumes NULL for right child
491     
492     // we only want to use the cost of the minimum statements that will
493     // be executed.  Statements, such as the body of an if statement,
494     // will have their costs added to the observed cost global variable
495     // only if they are indeed called.  The code to do this in the minitramp
496     // right after the body of the if.
497     trampCost = preamble->maxCost() + minCost();
498
499     costAst->setOValue((void *) (long) trampCost);
500     
501
502 //#if defined( ia64_unknown_linux2_4 )
503 //    extern Register deadRegisterList[];
504 //    defineBaseTrampRegisterSpaceFor( gen.point(), gen.rs(), deadRegisterList);
505 //#endif
506
507     if (!preamble->generateCode(gen, noCost)) {
508         fprintf(stderr, "[%s:%d] WARNING: failure to generate miniTramp preamble\n", __FILE__, __LINE__);
509     }
510     
511     if (!ast_->generateCode(gen, noCost)) {
512         fprintf(stderr, "[%s:%d] WARNING: failure to generate miniTramp body\n", __FILE__, __LINE__);
513     }
514
515     return 0;
516 }
517
518 // This name is a bit of a misnomer. It's not the strict use count; it's the
519 // use count modified by whether a node can be kept or not. We can treat
520 // un-keepable nodes (AKA those that don't strictly depend on their AST inputs)
521 // as multiple different nodes that happen to have the same children; keepable
522 // nodes are the "same". If that makes any sense. 
523 //
524 // In any case, we use the following algorithm to set use counts:
525 //
526 //DFS through the AST graph. 
527 //If an AST can be kept:
528 //  Increase its use count;
529 //  Return.
530 //If an AST cannot be kept:
531 //  Recurse to each child;
532 //  Return
533 //
534 // The result is all nodes having counts of 0, 1, or >1. These mean:
535 // 0: node cannot be kept, or is only reached via a keepable node.
536 // 1: Node can be kept, but doesn't matter as it's only used once.
537 // >1: keep result in a register.
538
539 void AstNode::setUseCount() 
540 {
541     // This code fails on IA-64. Until I can ask Todd about it, 
542     // it's just getting commented out...
543     //#if defined(arch_ia64)
544     //return;
545     //#endif
546         if (useCount) {
547                 // If the useCount is 1, then it means this node can
548                 // be shared, and there is a copy. In that case, we assume
549                 // that when this particular incarnation is generated, the
550                 // result will already be calculated and sitting in a register.
551                 // Since that's the case, just up the useCount so we know when
552                 // we can free said register.
553                 useCount++;
554                 return; 
555         }
556         if (canBeKept()) {
557                 useCount++;
558                 // We purposefully fall through... if our use count
559                 // is 1, we'll have to calculate this node instead of
560                 // keeping it around. In that case, see if any of the 
561                 // children are shared (because we can reuse them when
562                 // calculating this guy)
563         }
564         // We can't be kept, but maybe our children can.
565         pdvector<AstNodePtr> children;
566         getChildren(children);
567         for (unsigned i=0; i<children.size(); i++) {
568             children[i]->setUseCount();
569     }
570 }
571
572 void AstNode::cleanUseCount(void)
573 {
574     useCount = 0;
575
576     pdvector<AstNodePtr> children;
577     getChildren(children);
578     for (unsigned i=0; i<children.size(); i++) {
579                 children[i]->cleanUseCount();
580     }
581 }
582
583 // Allocate a register and make it available for sharing if our
584 // node is shared
585 Register AstNode::allocateAndKeep(codeGen &gen, bool noCost)
586 {
587     ast_printf("Allocating register for node %p, useCount %d\n", this, useCount);
588     // Allocate a register
589     Register dest = gen.rs()->allocateRegister(gen, noCost);
590     
591     if (useCount > 1) {
592         ast_printf("Adding kept register %d for node %p: useCount %d\n", dest, this, useCount);
593         // If use count is 0 or 1, we don't want to keep
594         // it around. If it's > 1, then we can keep the node
595         // (by construction) and want to since there's another
596         // use later.
597         gen.tracker()->addKeptRegister(gen, this, dest);
598     }
599     return dest;
600 }
601
602 //
603 // This procedure generates code for an AST DAG. If there is a sub-graph
604 // being shared between more than 1 node, then the code is generated only
605 // once for this sub-graph and the register where the return value of the
606 // sub-graph is stored, is kept allocated until the last node sharing the
607 // sub-graph has used it (freeing it afterwards). A count called "useCount"
608 // is used to determine whether a particular node or sub-graph is being
609 // shared. At the end of the call to generate code, this count must be 0
610 // for every node. Another important issue to notice is that we have to make
611 // sure that if a node is not calling generate code recursively for either
612 // its left or right operands, we then need to make sure that we update the
613 // "useCount" for these nodes (otherwise we might be keeping registers
614 // allocated without reason). 
615 //
616 // This code was modified in order to set the proper "useCount" for every
617 // node in the DAG before calling the original generateCode procedure (now
618 // generateCode_phase2). This means that we are traversing the DAG twice,
619 // but with the advantage of potencially generating more efficient code.
620 //
621 // Note: a complex Ast DAG might require more registers than the ones 
622 // currently available. In order to fix this problem, we will need to 
623 // implement a "virtual" register allocator - naim 11/06/96
624 //
625 bool AstNode::generateCode(codeGen &gen, 
626                            bool noCost, 
627                            Address &retAddr,
628                            Register &retReg) {
629     static bool entered = false;
630
631
632     bool ret = true;
633
634     bool top_level;
635     if (entered) {
636         top_level = false;
637     }
638     else {
639         entered = true;
640         top_level = true;
641         stats_codegen.startTimer(CODEGEN_AST_TIMER);
642         stats_codegen.incrementCounter(CODEGEN_AST_COUNTER);
643     }
644
645     entered = true;
646
647     cleanUseCount();
648     setUseCount();
649     setVariableAST(gen);
650     ast_printf("====== Code Generation Start ===== \n");
651     debugPrint();
652     ast_printf("\n\n\n\n");
653
654     // We can enter this guy recursively... inst-ia64 goes through
655     // emitV and calls generateCode on the frame pointer AST. Now, it
656     // really shouldn't, but them's the breaks. So we only want
657     // to build a regTracker if there isn't one already...
658     if (top_level) {
659         gen.setRegTracker(new regTracker_t);
660     }
661     
662     // note: this could return the value "(Address)(-1)" -- csserra
663     if (!generateCode_phase2(gen, noCost, retAddr, retReg)) {
664         fprintf(stderr, "WARNING: failed in generateCode internals!\n");
665         ret = false;
666     }
667     
668     if (top_level) {
669         delete gen.tracker();
670         gen.setRegTracker(NULL);
671     }
672     
673     ast_printf("====== Code Generation End ===== \n");
674     debugPrint();
675     ast_printf("\n\n\n\n");
676
677     if (top_level) {
678         entered = false;
679         stats_codegen.stopTimer(CODEGEN_AST_TIMER);
680     }
681
682     return ret;
683 }
684
685 bool AstNode::generateCode(codeGen &gen, 
686                            bool noCost) {
687     Address unused = ADDR_NULL;
688     Register unusedReg = REG_NULL;
689     bool ret = generateCode(gen, noCost, unused, unusedReg);
690     gen.rs()->freeRegister(unusedReg);
691
692     return ret;
693 }
694
695 bool AstNode::previousComputationValid(Register &reg,
696                                        codeGen &gen) {
697         Register keptReg = gen.tracker()->hasKeptRegister(this);
698         if (keptReg != REG_NULL) {
699                 reg = keptReg;
700                 ast_printf("Returning previously used register %d for node %p\n", reg, this);
701                 return true;
702         }
703    return false;
704 }
705
706 // We're going to use this fragment over and over and over...
707 #define RETURN_KEPT_REG(r) { if (previousComputationValid(r, gen)) { decUseCount(gen); gen.rs()->incRefCount(r); return true;} }
708 #define ERROR_RETURN { fprintf(stderr, "[%s:%d] ERROR: failure to generate operand\n", __FILE__, __LINE__); return false; }
709 #define REGISTER_CHECK(r) if (r == REG_NULL) { fprintf(stderr, "[%s: %d] ERROR: returned register invalid\n", __FILE__, __LINE__); return false; }
710
711
712 bool AstNode::initRegisters(codeGen &g) {
713     bool ret = true;
714     pdvector<AstNodePtr> kids;
715     getChildren(kids);
716     for (unsigned i = 0; i < kids.size(); i++) {
717         if (!kids[i]->initRegisters(g))
718             ret = false;
719     }
720     return ret;
721 }
722
723 bool AstNode::generateCode_phase2(codeGen &, bool,
724                                   Address &,
725                                   Register &) {
726     fprintf(stderr, "ERROR: call to AstNode generateCode_phase2; should be handled by subclass\n");
727     fprintf(stderr, "Undefined phase2 for:\n");
728     if (dynamic_cast<AstNullNode *>(this)) fprintf(stderr, "nullNode\n");
729     if (dynamic_cast<AstOperatorNode *>(this)) fprintf(stderr, "operatorNode\n");
730     if (dynamic_cast<AstOperandNode *>(this)) fprintf(stderr, "operandNode\n");
731     if (dynamic_cast<AstCallNode *>(this)) fprintf(stderr, "callNode\n");
732     if (dynamic_cast<AstReplacementNode *>(this)) fprintf(stderr, "replacementNode\n");
733     if (dynamic_cast<AstSequenceNode *>(this)) fprintf(stderr, "seqNode\n");
734     if (dynamic_cast<AstVariableNode *>(this)) fprintf(stderr, "varNode\n");
735     if (dynamic_cast<AstInsnNode *>(this)) fprintf(stderr, "insnNode\n");
736     if (dynamic_cast<AstMiniTrampNode *>(this)) fprintf(stderr, "miniTrampNode\n");
737     if (dynamic_cast<AstMemoryNode *>(this)) fprintf(stderr, "memoryNode\n");
738     assert(0);
739         return 0;
740 }
741
742
743 bool AstNullNode::generateCode_phase2(codeGen &gen, bool,
744                                       Address &retAddr,
745                                       Register &retReg) {
746     retAddr = ADDR_NULL;
747     retReg = REG_NULL;
748
749     decUseCount(gen);
750    
751     return true;
752 }
753
754 bool AstLabelNode::generateCode_phase2(codeGen &gen, bool,
755                                        Address &retAddr,
756                                        Register &retReg) {
757         assert(generatedAddr_ == 0);
758     // Pick up the address we were added at
759     generatedAddr_ = gen.currAddr();
760
761     retAddr = ADDR_NULL;
762     retReg = REG_NULL;
763
764         decUseCount(gen);
765
766     return true;
767 }
768
769 bool AstReplacementNode::generateCode_phase2(codeGen &gen, bool noCost,
770                                              Address &retAddr,
771                                              Register &retReg) {
772     retAddr = ADDR_NULL;
773     retReg = REG_NULL;
774     
775     assert(replacement);
776     
777     emitFuncJump(funcJumpOp, gen, replacement, gen.addrSpace(),
778                  gen.point(), noCost);
779     
780     decUseCount(gen);
781     return true;
782 }
783
784 bool AstOperatorNode::initRegisters(codeGen &g) {
785     bool ret = true;
786     pdvector<AstNodePtr> kids;
787     getChildren(kids);
788     for (unsigned i = 0; i < kids.size(); i++) {
789         if (!kids[i]->initRegisters(g))
790             ret = false;
791     }
792
793 #if !defined(arch_x86)
794     // Override: if we're trying to save to an original
795     // register, make sure it's saved on the stack.
796     if (op == storeOp) {
797         if (loperand->getoType() == origRegister) {
798             Address origReg = (Address) loperand->getOValue();
799             // Mark that register as live so we are sure to save it.
800             registerSlot *r = (*(g.rs()))[origReg];
801             r->liveState = registerSlot::live;
802         }
803     }
804 #endif
805     return ret;
806 }
807
808
809 #if defined(arch_x86) || defined(arch_x86_64)
810 bool AstOperatorNode::generateOptimizedAssignment(codeGen &gen, bool noCost) 
811 {
812    //Recognize the common case of 'a = a op constant' and try to 
813    // generate optimized code for this case.
814    Address laddr;
815   
816    if (loperand->getoType() == DataAddr)
817    {
818       laddr = (Address) loperand->getOValue();
819    }
820    else
821    {
822       if(loperand->getoType() == variableValue)
823       {
824          dyn_detail::boost::shared_ptr<AstOperandNode> lnode = 
825             dyn_detail::boost::dynamic_pointer_cast<AstOperandNode>(loperand);
826        
827          int_variable* var = lnode->lookUpVar(gen.addrSpace());
828          if (!var || gen.addrSpace()->needsPIC(var))
829             return false;
830          laddr = var->getAddress();
831       }
832       else
833       {
834          //Deal with global writes for now.
835          return false;
836       }
837      
838    }
839
840    if (roperand->getoType() == Constant) {
841       //Looks like 'global = constant'
842 #if defined(arch_x86_64)
843       if (laddr >> 32 || ((Address) roperand->getOValue()) >> 32) {
844          // Make sure value and address are 32-bit values.
845          return false;
846       }
847 #endif
848       int imm = (int) (long) roperand->getOValue();
849       emitStoreConst(laddr, (int) imm, gen, noCost);
850       loperand->decUseCount(gen);
851       roperand->decUseCount(gen);
852       return true;
853    }
854
855    AstOperatorNode *roper = dynamic_cast<AstOperatorNode *>(roperand.get());
856    if (!roper)
857       return false;
858    
859    if (roper->op != plusOp && roper->op != minusOp)
860       return false;
861    
862    AstOperandNode *arithl = dynamic_cast<AstOperandNode *>(roper->loperand.get());
863    AstOperandNode *arithr = dynamic_cast<AstOperandNode *>(roper->roperand.get());
864    if (!arithl || !arithr)
865       return false;
866    
867    AstNode *data_oper = NULL, *const_oper = NULL;
868    if (arithl->getoType() == DataAddr && arithr->getoType() == Constant &&
869        laddr == (Address) arithl->getOValue())
870    {
871       data_oper = arithl;
872       const_oper = arithr;
873    }
874    else if (arithl->getoType() == variableValue && arithr->getoType() == Constant)
875    {
876       Address addr = 0;
877       int_variable* var = arithl->lookUpVar(gen.addrSpace());
878       if (!var || gen.addrSpace()->needsPIC(var))
879          return false;
880       addr = var->getAddress();
881       if (addr == laddr) {
882          data_oper = arithl;
883          const_oper = arithr;
884       }
885    }
886    else if (arithr->getoType() == DataAddr && arithl->getoType() == Constant &&
887             laddr == (Address) arithr->getOValue() && roper->op == plusOp)
888    {
889       data_oper = arithr;
890       const_oper = arithl;
891    }
892    else if (arithl->getoType() == variableValue && arithr->getoType() == Constant)
893    {
894       Address addr = 0;
895       int_variable* var = arithl->lookUpVar(gen.addrSpace());
896       if(!var || gen.addrSpace()->needsPIC(var))
897          return false;
898       addr = var->getAddress();
899       if (addr == laddr) {
900          data_oper = arithr;
901          const_oper = arithl;
902       }
903    }
904    else
905    {
906       return false;
907    }
908
909    long int imm = (long int) const_oper->getOValue();
910    if (roper->op == plusOp) {
911       emitAddSignedImm(laddr, imm, gen, noCost);
912    }
913    else {
914       emitSubSignedImm(laddr, imm, gen, noCost);
915    }
916    
917    loperand->decUseCount(gen);
918    roper->roperand->decUseCount(gen);
919    roper->loperand->decUseCount(gen);
920    roper->decUseCount(gen);
921
922    return true;
923 }
924 #else
925 bool AstOperatorNode::generateOptimizedAssignment(codeGen &, bool) 
926 {
927    return false;   
928 }
929 #endif
930
931 bool AstOperatorNode::generateCode_phase2(codeGen &gen, bool noCost,
932                                           Address &retAddr,
933                                           Register &retReg) {
934
935    retAddr = ADDR_NULL; // We won't be setting this...
936    // retReg may have a value or be the (register) equivalent of NULL.
937    // In either case, we don't touch it...
938
939         RETURN_KEPT_REG(retReg);
940
941     
942    Address addr = ADDR_NULL;
943  
944    Register src1 = Null_Register;
945    Register src2 = Null_Register;
946
947    Register right_dest = Null_Register;
948    Register tmp = Null_Register;
949     
950    switch(op) {
951       case branchOp: {
952          assert(loperand->getoType() == Constant);
953          unsigned offset = (Register) (long) loperand->getOValue();
954          // We are not calling loperand->generateCode_phase2,
955          // so we decrement its useCount by hand.
956          // Would be nice to allow register branches...
957          loperand->decUseCount(gen);
958          (void)emitA(branchOp, 0, 0, (Register)offset, gen, rc_no_control, noCost);
959          retReg = REG_NULL; // No return register
960          break;
961       }
962       case ifOp: {
963          // This ast cannot be shared because it doesn't return a register
964          if (!loperand->generateCode_phase2(gen, noCost, addr, src1)) ERROR_RETURN;
965         
966          REGISTER_CHECK(src1);
967          codeBufIndex_t ifIndex= gen.getIndex();
968
969          size_t preif_patches_size = gen.allPatches().size();
970          codeBufIndex_t thenSkipStart = emitA(op, src1, 0, 0, gen, rc_before_jump, noCost);
971          size_t postif_patches_size = gen.allPatches().size();
972          // DO NOT FREE THE REGISTER HERE!!! we use it later to regenerate the
973          // jump once code has been generated. This is annoying, since we
974          // don't really need the register... we just want it allocated.
975         
976          // I'm ignoring the above; we'll keep the _value_ of src1, but free it
977          // for internal code.
978          Register src1_copy = src1;
979          if (loperand->decRefCount())
980             gen.rs()->freeRegister(src1);
981         
982          // The flow of control forks. We need to add the forked node to 
983          // the path
984          gen.tracker()->increaseConditionalLevel();
985          if (!roperand->generateCode_phase2(gen, noCost, addr, src2)) ERROR_RETURN;
986          if (roperand->decRefCount())
987             gen.rs()->freeRegister(src2);
988          gen.tracker()->decreaseAndClean(gen);
989          gen.rs()->unifyTopRegStates(gen); //Join the registerState for the if
990         
991          // Is there an else clause?  If yes, generate branch over it
992          codeBufIndex_t elseSkipStart = 0;
993          codeBufIndex_t elseSkipIndex = gen.getIndex();
994          size_t preelse_patches_size = 0, postelse_patches_size = 0;
995          if (eoperand) {
996             gen.rs()->pushNewRegState(); //Create registerState for else
997             preelse_patches_size = gen.allPatches().size();
998             elseSkipStart = emitA(branchOp, 0, 0, 0,
999                                   gen, rc_no_control, noCost);
1000             postelse_patches_size = gen.allPatches().size();
1001          }
1002
1003          // Now that we've generated the "then" section, rewrite the if
1004          // conditional branch.
1005          codeBufIndex_t elseStartIndex = gen.getIndex();
1006
1007          if (preif_patches_size != postif_patches_size) {
1008             assert(postif_patches_size > preif_patches_size);
1009             ifTargetPatch if_targ(elseStartIndex + gen.startAddr());
1010             for (unsigned i=preif_patches_size; i < postif_patches_size; i++) {
1011                gen.allPatches()[i].setTarget(&if_targ);
1012             }
1013             for (unsigned i=preif_patches_size; i < postif_patches_size; i++) {
1014                gen.allPatches()[i].applyPatch();
1015             }
1016          }
1017          else {
1018             gen.setIndex(ifIndex);
1019             // call emit again now with correct offset.
1020             // This backtracks over current code.
1021             // If/when we vectorize, we can do this in a two-pass arrangement
1022             (void) emitA(op, src1_copy, 0, 
1023                          (Register) codeGen::getDisplacement(thenSkipStart, elseStartIndex),
1024                          gen, rc_no_control, noCost);
1025             // Now we can free the register
1026             // Register has already been freed; we're just re-using it.
1027             //gen.rs()->freeRegister(src1);
1028         
1029             gen.setIndex(elseStartIndex);
1030          }
1031
1032          if (eoperand) {
1033             // If there's an else clause, we need to generate code for it.
1034             gen.tracker()->increaseConditionalLevel();
1035             if (!eoperand->generateCode_phase2(gen,
1036                                                noCost, 
1037                                                addr,
1038                                                src2)) ERROR_RETURN;
1039             if (eoperand->decRefCount())
1040                gen.rs()->freeRegister(src2);
1041             gen.tracker()->decreaseAndClean(gen);
1042             gen.rs()->unifyTopRegStates(gen); //Join the registerState for the else
1043             
1044             // We also need to fix up the branch at the end of the "true"
1045             // clause to jump around the "else" clause.
1046             codeBufIndex_t endIndex = gen.getIndex();
1047             if (preelse_patches_size != postelse_patches_size) {
1048                assert(postif_patches_size > preif_patches_size);
1049                ifTargetPatch else_targ(endIndex + gen.startAddr());
1050                for (unsigned i=preelse_patches_size; i < postelse_patches_size; i++) {
1051                   gen.allPatches()[i].setTarget(&else_targ);
1052                }
1053                for (unsigned i=preelse_patches_size; i < postelse_patches_size; i++) {
1054                   gen.allPatches()[i].applyPatch();
1055                }
1056             }
1057             else {        
1058                gen.setIndex(elseSkipIndex);
1059                emitA(branchOp, 0, 0, 
1060                      (Register) codeGen::getDisplacement(elseSkipStart, endIndex),
1061                      gen, rc_no_control, noCost);
1062                gen.setIndex(endIndex);
1063             }
1064          }
1065          retReg = REG_NULL; 
1066          break;
1067       }
1068       case ifMCOp: {
1069          assert(gen.point());
1070         
1071          // TODO: Right now we get the condition from the memory access info,
1072          // because scanning for memory accesses is the only way to detect these
1073          // conditional instructions. The right way(TM) would be to attach that
1074          // info directly to the point...
1075          // Okay. The info we need is stored in the BPatch_point. We have the instPoint. 
1076          // Yay.
1077         
1078          BPatch_addressSpace *bproc = (BPatch_addressSpace *) gen.addrSpace()->up_ptr();
1079          BPatch_point *bpoint = bproc->findOrCreateBPPoint(NULL, gen.point());
1080         
1081          const BPatch_memoryAccess* ma = bpoint->getMemoryAccess();
1082          assert(ma);
1083          int cond = ma->conditionCode_NP();
1084          if(cond > -1) {
1085             codeBufIndex_t startIndex = gen.getIndex();
1086             emitJmpMC(cond, 0 /* target, changed later */, gen);
1087             codeBufIndex_t fromIndex = gen.getIndex();
1088             // Add the snippet to the tracker, as AM has indicated...
1089             gen.tracker()->increaseConditionalLevel();
1090             // generate code with the right path
1091             if (!loperand->generateCode_phase2(gen,
1092                                                noCost,
1093                                                addr,
1094                                                src1)) ERROR_RETURN;
1095             if (loperand->decRefCount())
1096                gen.rs()->freeRegister(src1);
1097             gen.tracker()->decreaseAndClean(gen);
1098             codeBufIndex_t endIndex = gen.getIndex();
1099             // call emit again now with correct offset.
1100             gen.setIndex(startIndex);
1101             emitJmpMC(cond, codeGen::getDisplacement(fromIndex, endIndex), gen);
1102             gen.setIndex(endIndex);
1103          }
1104          else {
1105             if (!loperand->generateCode_phase2(gen,
1106                                                noCost,
1107                                                addr, 
1108                                                src1)) ERROR_RETURN;
1109             if (loperand->decRefCount())
1110                gen.rs()->freeRegister(src1);
1111          }
1112
1113          break;
1114       }
1115       case whileOp: {
1116          codeBufIndex_t top = gen.getIndex();
1117          if (!loperand->generateCode_phase2(gen, noCost, addr, src1)) ERROR_RETURN;
1118          REGISTER_CHECK(src1);
1119          codeBufIndex_t startIndex = gen.getIndex();
1120          codeBufIndex_t fromIndex = emitA(ifOp, src1, 0, 0, gen, rc_no_control, noCost);
1121          if (loperand->decRefCount())
1122             gen.rs()->freeRegister(src1);
1123          if (roperand) {
1124             gen.tracker()->increaseConditionalLevel();
1125             if (!roperand->generateCode_phase2(gen, noCost,
1126                                                addr,
1127                                                src1)) ERROR_RETURN;
1128             if (roperand->decRefCount())
1129                gen.rs()->freeRegister(src1);
1130             gen.tracker()->decreaseAndClean(gen);
1131          }
1132          //jump back
1133          (void) emitA(branchOp, 0, 0, codeGen::getDisplacement(top, gen.getIndex()),
1134                       gen, rc_no_control, noCost);
1135         
1136          // Rewind and replace the skip jump
1137          codeBufIndex_t endIndex = gen.getIndex();
1138          gen.setIndex(startIndex);
1139          (void) emitA(ifOp, src1, 0, (Register) codeGen::getDisplacement(fromIndex, endIndex), 
1140                       gen, rc_no_control, noCost);
1141          gen.setIndex(endIndex);
1142          // sprintf(errorLine,"branch forward %d\n", base - fromAddr);
1143          break;
1144       }
1145       case doOp: {
1146          fprintf(stderr, "[%s:%d] WARNING: do AST node unimplemented!\n", __FILE__, __LINE__);
1147          return false;
1148       }
1149       case getAddrOp: {
1150          switch(loperand->getoType()) {
1151             case variableAddr:
1152                if (retReg == REG_NULL) {
1153                   retReg = allocateAndKeep(gen, noCost);
1154                }
1155                assert (loperand->getOVar());
1156                loperand->emitVariableLoad(loadConstOp, retReg, retReg, gen, noCost, gen.rs(), size,
1157                                           gen.point(), gen.addrSpace());
1158                break;
1159             case variableValue:
1160                if (retReg == REG_NULL) {
1161                   retReg = allocateAndKeep(gen, noCost);
1162                }
1163                assert (loperand->getOVar());
1164                loperand->emitVariableLoad(loadOp, retReg, retReg, gen, noCost, gen.rs(), size,
1165                                           gen.point(), gen.addrSpace());
1166                break;
1167             case DataAddr:
1168                {
1169                   addr = reinterpret_cast<Address>(loperand->getOValue());
1170                   if (retReg == REG_NULL) {
1171                      retReg = allocateAndKeep(gen, noCost);
1172                   }
1173                   assert(!loperand->getOVar());
1174                   emitVload(loadConstOp, addr, retReg, retReg, gen,
1175                             noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1176                }
1177                break;
1178             case FrameAddr: {
1179                // load the address fp + addr into dest
1180                if (retReg == REG_NULL)
1181                   retReg = allocateAndKeep(gen, noCost);
1182                Register temp = gen.rs()->getScratchRegister(gen, noCost);
1183                addr = (Address) loperand->getOValue();
1184             
1185                emitVload(loadFrameAddr, addr, temp, retReg, gen,
1186                          noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1187                break;
1188             }
1189             case RegOffset: {
1190                assert(loperand);
1191                assert(loperand->operand());
1192             
1193                // load the address reg + addr into dest
1194                if (retReg == REG_NULL) {
1195                   retReg = allocateAndKeep(gen, noCost);
1196                }
1197                addr = (Address) loperand->operand()->getOValue();
1198             
1199                emitVload(loadRegRelativeAddr, addr, (long)loperand->getOValue(), retReg, gen,
1200                          noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1201                break;
1202             }
1203             case DataIndir:
1204                // taking address of pointer de-ref returns the original
1205                //    expression, so we simple generate the left child's 
1206                //    code to get the address 
1207                if (!loperand->operand()->generateCode_phase2(gen,
1208                                                              noCost, 
1209                                                              addr,
1210                                                              retReg)) ERROR_RETURN;
1211                // Broken refCounts?
1212                break;
1213             default:
1214                assert(0);
1215          }
1216          break;
1217       }
1218       case storeOp: {
1219          bool result = generateOptimizedAssignment(gen, noCost);
1220          if (result)
1221             break;
1222        
1223          // This ast cannot be shared because it doesn't return a register
1224          if (!roperand->generateCode_phase2(gen,
1225                                             noCost,
1226                                             addr,
1227                                             src1))  { 
1228             fprintf(stderr, "ERROR: failure generating roperand\n"); 
1229             ERROR_RETURN; 
1230          }
1231          REGISTER_CHECK(src1);
1232          // We will access loperand's children directly. They do not expect
1233          // it, so we need to bump up their useCounts
1234          loperand->fixChildrenCounts();
1235
1236          src2 = gen.rs()->allocateRegister(gen, noCost);
1237          switch (loperand->getoType()) {
1238             case variableValue:
1239                loperand->emitVariableStore(storeOp, src1, src2, gen,
1240                                            noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1241                loperand->decUseCount(gen);
1242                break;
1243             case DataAddr:
1244                addr = (Address) loperand->getOValue();
1245                assert(loperand->getOVar() == NULL);
1246                emitVstore(storeOp, src1, src2, addr, gen,
1247                           noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1248                // We are not calling generateCode for the left branch,
1249                // so need to decrement the refcount by hand
1250                loperand->decUseCount(gen);
1251                break;
1252             case FrameAddr:
1253                addr = (Address) loperand->getOValue();
1254                emitVstore(storeFrameRelativeOp, src1, src2, addr, gen, 
1255                           noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1256                loperand->decUseCount(gen);
1257                break;
1258             case RegOffset: {
1259                assert(loperand->operand());
1260                addr = (Address) loperand->operand()->getOValue();
1261             
1262                // This is cheating, but I need to pass 4 data values into emitVstore, and
1263                // it only allows for 3.  Prepare the dest address in scratch register src2.
1264             
1265                emitVload(loadRegRelativeAddr, addr, (long)loperand->getOValue(), src2,
1266                          gen, noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1267             
1268                // Same as DataIndir at this point.
1269                emitV(storeIndirOp, src1, 0, src2, gen, noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1270                loperand->decUseCount(gen);
1271                break;
1272             }
1273             case DataIndir: {
1274                // store to a an expression (e.g. an array or field use)
1275                // *(+ base offset) = src1
1276                if (!loperand->operand()->generateCode_phase2(gen,
1277                                                              noCost,
1278                                                              addr,
1279                                                              tmp)) ERROR_RETURN;
1280                REGISTER_CHECK(tmp);
1281
1282                // tmp now contains address to store into
1283                emitV(storeIndirOp, src1, 0, tmp, gen, noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1284                if (loperand->operand()->decRefCount())
1285                   gen.rs()->freeRegister(tmp);
1286                loperand->decUseCount(gen);
1287                break;
1288             }
1289             case origRegister:
1290                gen.rs()->writeProgramRegister(gen, (Register)(long)loperand->getOValue(),
1291                                               src1, getSize());
1292                //emitStorePreviousStackFrameRegister((Address) loperand->getOValue(),
1293                //src1, gen, getSize(), noCost);
1294                loperand->decUseCount(gen);
1295                break;
1296             case Param: {
1297                dyn_detail::boost::shared_ptr<AstOperandNode> lnode = 
1298                   dyn_detail::boost::dynamic_pointer_cast<AstOperandNode>(loperand);
1299                emitR(getParamOp, (Address)lnode->oValue,
1300                      src1, src2, gen, noCost, gen.point(),
1301                      gen.addrSpace()->multithread_capable());
1302                loperand->decUseCount(gen);
1303                break;
1304             }
1305             case ReturnVal:
1306                emitR(getRetValOp, Null_Register,
1307                      src1, src2, gen, noCost, gen.point(),
1308                      gen.addrSpace()->multithread_capable());
1309                loperand->decUseCount(gen);
1310                break;
1311             default: {
1312                // Could be an error, could be an attempt to load based on an arithmetic expression
1313                // Generate the left hand side, store the right to that address
1314                if (!loperand->generateCode_phase2(gen, noCost, addr, tmp)) ERROR_RETURN;
1315                REGISTER_CHECK(tmp);
1316
1317                emitV(storeIndirOp, src1, 0, tmp, gen, noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1318                if (loperand->decRefCount())
1319                   gen.rs()->freeRegister(tmp);
1320                break;
1321             }
1322          }
1323          if (roperand->decRefCount())
1324             gen.rs()->freeRegister(src1);
1325          gen.rs()->freeRegister(src2);
1326          retReg = REG_NULL;
1327          break;
1328       }
1329       case storeIndirOp: {
1330         
1331          if (!roperand->generateCode_phase2(gen, noCost, addr, src1)) ERROR_RETURN;
1332          if (!loperand->generateCode_phase2(gen, noCost, addr, src2)) ERROR_RETURN;
1333          REGISTER_CHECK(src1);
1334          REGISTER_CHECK(src2);
1335          emitV(op, src1, 0, src2, gen, noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1336          if (roperand->decRefCount())
1337             gen.rs()->freeRegister(src1);
1338          if (loperand->decRefCount())
1339             gen.rs()->freeRegister(src2);
1340          retReg = REG_NULL;
1341          break;
1342       }
1343       case trampPreamble: {
1344          // This ast cannot be shared because it doesn't return a register
1345 #if defined(i386_unknown_solaris2_5)            \
1346    || defined(sparc_sun_solaris2_4)
1347          // loperand is a constant AST node with the cost, in cycles.
1348          //int cost = noCost ? 0 : (int) loperand->getOValue();
1349          Address costAddr = 0; // for now... (won't change if noCost is set)
1350          loperand->decUseCount(gen);
1351          costAddr = gen.addrSpace()->getObservedCostAddr();
1352          retAddr = emitA(op, 0, 0, 0, gen, rc_no_control, noCost);
1353 #endif
1354          retReg = REG_NULL;
1355          break;
1356       }
1357       case plusOp:
1358       case minusOp:
1359       case timesOp:
1360       case divOp:
1361       case orOp:
1362       case andOp:
1363       case eqOp:
1364       case neOp:
1365       case lessOp:
1366       case leOp:
1367       case greaterOp:
1368       case geOp:
1369       default: 
1370       {
1371          src1 = Null_Register;
1372          right_dest = Null_Register;
1373          if (loperand) {
1374             if (!loperand->generateCode_phase2(gen,
1375                                                noCost, addr, src1)) ERROR_RETURN;
1376             REGISTER_CHECK(src1);
1377          }
1378          
1379          if (roperand &&
1380              (roperand->getoType() == Constant) &&
1381              doNotOverflow((Register) (long) roperand->getOValue())) {
1382             if (retReg == REG_NULL) {
1383                retReg = allocateAndKeep(gen, noCost);
1384                ast_printf("Operator node, const RHS, allocated register %d\n", retReg);
1385             }
1386             else
1387                ast_printf("Operator node, const RHS, keeping register %d\n", retReg);
1388                                 
1389             emitImm(op, src1, (Register) (long) roperand->getOValue(), retReg, gen, noCost, gen.rs());
1390
1391             if (src1 != Null_Register && loperand->decRefCount())
1392                gen.rs()->freeRegister(src1); 
1393
1394             // We do not .generateCode for roperand, so need to update its
1395             // refcounts manually
1396             roperand->decUseCount(gen);
1397          }
1398          else {
1399             if (roperand) {
1400                if (!roperand->generateCode_phase2(gen, noCost, addr, right_dest)) ERROR_RETURN;
1401                REGISTER_CHECK(right_dest);
1402             }
1403             if (retReg == REG_NULL) {
1404                retReg = allocateAndKeep(gen, noCost);
1405             }
1406             emitV(op, src1, right_dest, retReg, gen, noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1407             if (src1 != Null_Register && loperand->decRefCount()) {
1408                // Don't free inputs until afterwards; we have _no_ idea
1409                gen.rs()->freeRegister(src1); 
1410             }
1411             // what the underlying code might do with a temporary register.
1412             if (right_dest != Null_Register && roperand->decRefCount())
1413                gen.rs()->freeRegister(right_dest); 
1414          }
1415       }
1416    }
1417         decUseCount(gen);
1418    return true;
1419 }
1420
1421 bool AstOperandNode::generateCode_phase2(codeGen &gen, bool noCost,
1422                                          Address &,
1423                                          Register &retReg) {
1424         RETURN_KEPT_REG(retReg);
1425     
1426
1427     Address addr = ADDR_NULL;
1428     Register src = Null_Register;
1429
1430 #if defined(ASTDEBUG)
1431    sprintf(errorLine,"### location: %p ###\n", gen.point());
1432    logLine(errorLine);
1433 #endif
1434    // Allocate a register to return
1435    if (oType != DataReg) {
1436        if (retReg == REG_NULL) {
1437            retReg = allocateAndKeep(gen, noCost);
1438        }
1439    }
1440    Register temp;
1441    int tSize;
1442    int len;
1443    BPatch_type *Type;
1444    switch (oType) {
1445    case Constant:
1446      assert(oVar == NULL);
1447      emitVload(loadConstOp, (Address)oValue, retReg, retReg, gen,
1448                  noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1449      break;
1450    case DataIndir:
1451       if (!operand_->generateCode_phase2(gen, noCost, addr, src)) ERROR_RETURN;
1452       REGISTER_CHECK(src);
1453       Type = const_cast<BPatch_type *> (getType());
1454       // Internally generated calls will not have type information set
1455       if(Type)
1456          tSize = Type->getSize();
1457       else
1458          tSize = sizeof(long);
1459       emitV(loadIndirOp, src, 0, retReg, gen, noCost, gen.rs(), tSize, gen.point(), gen.addrSpace()); 
1460       if (operand_->decRefCount())
1461          gen.rs()->freeRegister(src);
1462       break;
1463    case DataReg:
1464        retReg = (Register) (long) oValue;
1465        break;
1466    case origRegister:
1467       gen.rs()->readProgramRegister(gen, (Register)(long)oValue, retReg, size);
1468        //emitLoadPreviousStackFrameRegister((Address) oValue, retReg, gen,
1469        //size, noCost);
1470        break;
1471    case variableAddr:
1472      assert(oVar);
1473      emitVariableLoad(loadConstOp, retReg, retReg, gen,
1474                  noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1475      break;
1476    case variableValue:
1477      assert(oVar);
1478      emitVariableLoad(loadOp, retReg, retReg, gen,
1479         noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1480      break;
1481    case ReturnVal:
1482        src = emitR(getRetValOp, 0, Null_Register, retReg, gen, noCost, gen.point(),
1483                    gen.addrSpace()->multithread_capable());
1484        REGISTER_CHECK(src);
1485        if (src != retReg) {
1486            // Move src to retReg. Can't simply return src, since it was not
1487            // allocated properly
1488            emitImm(orOp, src, 0, retReg, gen, noCost, gen.rs());
1489        }
1490        break;
1491    case Param:
1492        src = emitR(getParamOp, (Address)oValue, Null_Register,
1493                    retReg, gen, noCost, gen.point(),
1494                    gen.addrSpace()->multithread_capable());
1495        REGISTER_CHECK(src);
1496        if (src != retReg) {
1497            // Move src to retReg. Can't simply return src, since it was not
1498            // allocated properly
1499            emitImm(orOp, src, 0, retReg, gen, noCost, gen.rs());
1500        }
1501        break;
1502    case DataAddr:
1503      {
1504        assert(oVar == NULL);
1505        Address addr = reinterpret_cast<Address>(oValue);
1506        emitVload(loadOp, addr, retReg, retReg, gen, noCost, NULL, size, gen.point(), gen.addrSpace());
1507      }
1508      
1509        break;
1510    case FrameAddr:
1511        addr = (Address) oValue;
1512        temp = gen.rs()->allocateRegister(gen, noCost);
1513        
1514        emitVload(loadFrameRelativeOp, addr, temp, retReg, gen, noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1515        gen.rs()->freeRegister(temp);
1516        break;
1517    case RegOffset:
1518        // Prepare offset from value in any general register (not just fp).
1519        // This AstNode holds the register number, and loperand holds offset.
1520        assert(operand_);
1521        addr = (Address) operand_->getOValue();
1522        emitVload(loadRegRelativeOp, addr, (long)oValue, retReg, gen, noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1523        break;
1524    case ConstantString:
1525        // XXX This is for the std::string type.  If/when we fix the std::string type
1526        // to make it less of a hack, we'll need to change this.
1527        len = strlen((char *)oValue) + 1;
1528        
1529        addr = (Address) gen.addrSpace()->inferiorMalloc(len, dataHeap); //dataheap
1530        
1531        if (!gen.addrSpace()->writeDataSpace((char *)addr, len, (char *)oValue))
1532            perror("ast.C(1351): writing string value");
1533        if(!gen.addrSpace()->needsPIC())
1534        {
1535           emitVload(loadConstOp, addr, retReg, retReg, gen, noCost, gen.rs(), size, gen.point(), gen.addrSpace());
1536        }
1537        else
1538        {
1539           gen.codeEmitter()->emitLoadShared(loadConstOp, retReg, NULL, true, size, gen, addr);
1540        }
1541        break;
1542    default:
1543        fprintf(stderr, "[%s:%d] ERROR: Unknown operand type %d in AstOperandNode generation\n",
1544                __FILE__, __LINE__, oType);
1545        return false;
1546        break;
1547    }
1548         decUseCount(gen);
1549    return true;
1550 }
1551
1552 bool AstMemoryNode::generateCode_phase2(codeGen &gen, bool noCost,
1553                                         Address &,
1554                                         Register &retReg) {
1555         RETURN_KEPT_REG(retReg);
1556         
1557     const BPatch_memoryAccess* ma;
1558     const BPatch_addrSpec_NP *start;
1559     const BPatch_countSpec_NP *count;
1560     if (retReg == REG_NULL)
1561         retReg = allocateAndKeep(gen, noCost);    
1562     switch(mem_) {
1563     case EffectiveAddr: {
1564         
1565         // VG(11/05/01): get effective address
1566         // VG(07/31/02): take care which one
1567         // 1. get the point being instrumented & memory access info
1568         assert(gen.point());
1569         
1570         BPatch_addressSpace *bproc = (BPatch_addressSpace *)gen.addrSpace()->up_ptr();
1571         BPatch_point *bpoint = bproc->findOrCreateBPPoint(NULL, gen.point());
1572         if (bpoint == NULL) {
1573             fprintf(stderr, "ERROR: Unable to find BPatch point for internal point %p/0x%lx\n",
1574                     gen.point(), gen.point()->addr());
1575         }
1576         assert(bpoint);
1577         ma = bpoint->getMemoryAccess();
1578         if(!ma) {
1579             bpfatal( "Memory access information not available at this point.\n");
1580             bpfatal( "Make sure you create the point in a way that generates it.\n");
1581             bpfatal( "E.g.: find*Point(const BPatch_Set<BPatch_opCode>& ops).\n");
1582             assert(0);
1583         }
1584         if(which_ >= ma->getNumberOfAccesses()) {
1585             bpfatal( "Attempt to instrument non-existent memory access number.\n");
1586             bpfatal( "Consider using filterPoints()...\n");
1587             assert(0);
1588         }
1589         start = ma->getStartAddr(which_);
1590         emitASload(start, retReg, gen, noCost);
1591         break;
1592     }
1593     case BytesAccessed: {
1594         // 1. get the point being instrumented & memory access info
1595         assert(gen.point());
1596         
1597         BPatch_addressSpace *bproc = (BPatch_addressSpace *)gen.addrSpace()->up_ptr();
1598         BPatch_point *bpoint = bproc->findOrCreateBPPoint(NULL, gen.point());
1599         ma = bpoint->getMemoryAccess();
1600         if(!ma) {
1601             bpfatal( "Memory access information not available at this point.\n");
1602             bpfatal("Make sure you create the point in a way that generates it.\n");
1603             bpfatal( "E.g.: find*Point(const BPatch_Set<BPatch_opCode>& ops).\n");
1604             assert(0);
1605         }
1606         if(which_ >= ma->getNumberOfAccesses()) {
1607             bpfatal( "Attempt to instrument non-existent memory access number.\n");
1608             bpfatal( "Consider using filterPoints()...\n");
1609             assert(0);
1610         }
1611         count = ma->getByteCount(which_);
1612         emitCSload(count, retReg, gen, noCost);
1613         break;
1614     }
1615     default:
1616         assert(0);
1617     }
1618         decUseCount(gen);
1619     return true;
1620 }
1621
1622 bool AstCallNode::initRegisters(codeGen &gen) {
1623     // For now, we only care if we should save everything. "Everything", of course, 
1624     // is platform dependent. This is the new location of the clobberAllFuncCalls
1625     // that had previously been in emitCall.
1626
1627     bool ret = true;
1628
1629     // First, check kids
1630     pdvector<AstNodePtr > kids;
1631     getChildren(kids);
1632     for (unsigned i = 0; i < kids.size(); i++) {
1633         if (!kids[i]->initRegisters(gen))
1634             ret = false;
1635     }
1636
1637     // Platform-specific...
1638 #if defined(arch_x86) || defined(arch_x86_64)
1639     // Our "everything" is "floating point registers".
1640     // We also need a function object.
1641     int_function *callee = func_;
1642     if (!callee) {
1643         // Painful lookup time
1644         callee = gen.addrSpace()->findOnlyOneFunction(func_name_.c_str());
1645     }
1646     assert(callee);
1647
1648     // Marks registers as used based on the callee's behavior
1649     // This means we'll save them if necessary (also, lets us use
1650     // them in our generated code because we've saved, instead
1651     // of saving others).
1652     gen.codeEmitter()->clobberAllFuncCall(gen.rs(), callee);
1653
1654
1655 #endif
1656 #if defined(arch_power)
1657     if (callReplace_) return true;
1658
1659     // This code really doesn't work right now...
1660     int_function *callee = func_;
1661     if (!callee) {
1662         // Painful lookup time
1663         callee = gen.addrSpace()->findOnlyOneFunction(func_name_.c_str());
1664         assert(callee);
1665     }
1666     gen.codeEmitter()->clobberAllFuncCall(gen.rs(), callee);
1667     // We clobber in clobberAllFuncCall...
1668
1669     // Monotonically increasing...
1670 #endif
1671     return ret;
1672     
1673 }
1674
1675 bool AstCallNode::generateCode_phase2(codeGen &gen, bool noCost,
1676                                       Address &, 
1677                                       Register &retReg) {
1678         // We call this anyway... not that we'll ever be kept.
1679         // Well... if we can somehow know a function is entirely
1680         // dependent on arguments (a flag?) we can keep it around.
1681         RETURN_KEPT_REG(retReg);
1682
1683     // VG(11/06/01): This platform independent fn calls a platfrom
1684     // dependent fn which calls it back for each operand... Have to
1685     // fix those as well to pass location...
1686
1687     int_function *use_func = func_;
1688
1689     if (!use_func && !func_addr_) {
1690         // We purposefully don't cache the int_function object; the AST nodes
1691         // are process independent, and functions kinda are.
1692         use_func = gen.addrSpace()->findOnlyOneFunction(func_name_.c_str());
1693         if (!use_func) {
1694             fprintf(stderr, "ERROR: failed to find function %s, unable to create call\n",
1695                     func_name_.c_str());
1696         }
1697         assert(use_func); // Otherwise we've got trouble...
1698     }
1699
1700     Register tmp = 0;
1701
1702     if (use_func && !callReplace_) {
1703         tmp = emitFuncCall(callOp, gen, args_,  
1704                            noCost, use_func);
1705     }
1706     else if (use_func && callReplace_) {
1707         tmp = emitFuncCall(funcJumpOp, gen, args_,
1708                            noCost, use_func);
1709     }
1710     else if (func_addr_) {
1711         tmp = emitFuncCall(callOp, gen, args_,  
1712                            noCost, func_addr_);
1713     }
1714     else {
1715         char msg[256];
1716         sprintf(msg, "%s[%d]:  internal error:  unable to find %s",
1717                 __FILE__, __LINE__, func_name_.c_str());
1718         showErrorCallback(100, msg);
1719         assert(0);  // can probably be more graceful
1720     }
1721     
1722         // TODO: put register allocation here and have emitCall just
1723         // move the return result.
1724     if (tmp == REG_NULL) {
1725         // Happens in function replacement... didn't allocate
1726         // a return register.
1727     }
1728     else if (retReg == REG_NULL) {
1729         //emitFuncCall allocated tmp; we can use it, but let's see
1730         // if we should keep it around.
1731         retReg = tmp;
1732         // from allocateAndKeep:
1733         if (useCount > 1) {
1734             // If use count is 0 or 1, we don't want to keep
1735             // it around. If it's > 1, then we can keep the node
1736             // (by construction) and want to since there's another
1737             // use later.
1738             gen.tracker()->addKeptRegister(gen, this, retReg);
1739         }
1740     }           
1741     else if (retReg != tmp) {
1742         emitImm(orOp, tmp, 0, retReg, gen, noCost, gen.rs());
1743         gen.rs()->freeRegister(tmp);
1744     }
1745     decUseCount(gen);
1746     return true;
1747 }
1748
1749 bool AstSequenceNode::generateCode_phase2(codeGen &gen, bool noCost,
1750                                           Address &,
1751                                           Register &retReg) {
1752     RETURN_KEPT_REG(retReg);
1753     Register tmp = REG_NULL;
1754     Address unused = ADDR_NULL;
1755     
1756     for (unsigned i = 0; i < sequence_.size() - 1; i++) {
1757         if (!sequence_[i]->generateCode_phase2(gen,
1758                                                noCost, 
1759                                                unused,
1760                                                tmp)) ERROR_RETURN;
1761         if (sequence_[i]->decRefCount())
1762            gen.rs()->freeRegister(tmp);
1763         tmp = REG_NULL;
1764     }
1765
1766     // We keep the last one
1767     if (!sequence_.back()->generateCode_phase2(gen, noCost, unused, retReg)) ERROR_RETURN;
1768
1769         decUseCount(gen);
1770     
1771     return true;
1772 }
1773
1774 bool AstVariableNode::generateCode_phase2(codeGen &gen, bool noCost,
1775                                           Address &addr,
1776                                           Register &retReg) {
1777
1778     return ast_wrappers_[index]->generateCode_phase2(gen, noCost, addr, retReg);
1779 }
1780
1781 bool AstInsnNode::generateCode_phase2(codeGen &gen, bool,
1782                                       Address &, Register &) {
1783     assert(insn_);
1784     
1785     insn_->generate(gen, gen.addrSpace(), origAddr_, gen.currAddr());
1786     decUseCount(gen);
1787     
1788     return true;
1789 }
1790
1791 bool AstInsnBranchNode::generateCode_phase2(codeGen &gen, bool noCost,
1792                                             Address &, Register & ) {
1793     assert(insn_);
1794     
1795     // Generate side 2 and get the result...
1796     Address targetAddr = ADDR_NULL;
1797     Register targetReg = REG_NULL;
1798     if (target_) {
1799         // TODO: address vs. register...
1800         if (!target_->generateCode_phase2(gen, noCost, targetAddr, targetReg)) ERROR_RETURN;
1801     }
1802     // We'd now generate a fixed or register branch. But we don't. So there.
1803     assert(0 && "Unimplemented");
1804     insn_->generate(gen, gen.addrSpace(), origAddr_, gen.currAddr(), 0, 0);
1805         decUseCount(gen);
1806
1807     return true;
1808 }
1809
1810 bool AstInsnMemoryNode::generateCode_phase2(codeGen &gen, bool noCost,
1811                                             Address &, Register &) {
1812     Register loadReg = REG_NULL;
1813     Register storeReg = REG_NULL;
1814     Address loadAddr = ADDR_NULL;
1815     Address storeAddr = ADDR_NULL;
1816     assert(insn_);
1817
1818     // Step 1: save machine-specific state (AKA flags) and mark registers used in
1819     // the instruction itself as off-limits.
1820
1821     gen.rs()->saveVolatileRegisters(gen);
1822     pdvector<int> usedRegisters;
1823     if (insn_->getUsedRegs(usedRegisters)) {
1824         for (unsigned i = 0; i < usedRegisters.size(); i++) {
1825             gen.rs()->markReadOnly(usedRegisters[i]);
1826         }
1827     }
1828     else {
1829         // We don't know who to avoid... return false?
1830         fprintf(stderr, "WARNING: unknown \"off limits\" register set, returning false from memory modification\n");
1831         return false;
1832     }
1833
1834     // Step 2: generate code (this may spill registers)
1835
1836     if (load_)
1837         if (!load_->generateCode_phase2(gen, noCost, loadAddr, loadReg)) ERROR_RETURN;
1838     
1839     if (store_)
1840         if (!store_->generateCode_phase2(gen, noCost, storeAddr, storeReg)) ERROR_RETURN;
1841
1842     // Step 3: restore flags (before the original instruction)
1843
1844     gen.rs()->restoreVolatileRegisters(gen);
1845
1846     // Step 4: generate the memory instruction
1847     if (!insn_->generateMem(gen, origAddr_, gen.currAddr(), loadReg, storeReg)) {
1848         fprintf(stderr, "ERROR: generateMem call failed\n");
1849         return false;
1850     }
1851
1852     // Step 5: restore any registers that were st0mped. 
1853
1854
1855     gen.rs()->restoreAllRegisters(gen, true);
1856
1857     decUseCount(gen);
1858     return true;
1859 }
1860
1861 bool AstOriginalAddrNode::generateCode_phase2(codeGen &gen,
1862                                               bool noCost,
1863                                               Address &,
1864                                               Register &retReg) {
1865     RETURN_KEPT_REG(retReg);
1866     if (retReg == REG_NULL) {
1867         retReg = allocateAndKeep(gen, noCost);
1868     }
1869     if (retReg == REG_NULL) return false;
1870
1871     emitVload(loadConstOp, 
1872               (Address) gen.point()->addr(),
1873               retReg, retReg, gen, noCost);
1874     return true;
1875 }
1876
1877 bool AstActualAddrNode::generateCode_phase2(codeGen &gen,
1878                                             bool noCost,
1879                                             Address &,
1880                                             Register &retReg) {
1881     if (retReg == REG_NULL) {
1882         retReg = allocateAndKeep(gen, noCost);
1883     }
1884     if (retReg == REG_NULL) return false;
1885
1886     emitVload(loadConstOp, 
1887               (Address) gen.currAddr(),
1888               retReg, retReg, 
1889               gen, noCost);
1890
1891     return true;
1892 }
1893
1894 bool AstDynamicTargetNode::generateCode_phase2(codeGen &gen,
1895                                             bool noCost,
1896                                             Address & retAddr,
1897                                             Register &retReg) {
1898
1899 #if defined(cap_instruction_api)
1900     if(gen.point()->insn()->getCategory() == c_ReturnInsn) {
1901 #else
1902     InstrucIter instruc(gen.point()->addr(), gen.addrSpace());
1903     if (instruc.isAReturnInstruction()) {
1904 #endif        
1905     // if this is a return instruction our AST reads the top stack value
1906         if (retReg == REG_NULL) {
1907             retReg = allocateAndKeep(gen, noCost);
1908         }
1909         if (retReg == REG_NULL) return false;
1910
1911 #if defined (arch_x86)
1912         emitVload(loadRegRelativeOp, 
1913                   (Address) sizeof(Address), 
1914                   REGNUM_ESP, 
1915                   retReg, 
1916                   gen, noCost);
1917 #elif defined (arch_x86_64) // KEVINTODO: untested
1918         emitVload(loadRegRelativeOp, 
1919                   (Address) sizeof(Address), 
1920                   REGNUM_RSP, 
1921                   retReg, 
1922                   gen, noCost);
1923 #elif defined (arch_sparc) // KEVINTODO: untested
1924         emitVload(loadRegRelativeOp, 
1925                   (Address) sizeof(Address), 
1926                   REG_SPTR, 
1927                   retReg, 
1928                   gen, noCost);
1929 #elif defined (arch_power) // KEVINTODO: untested
1930         emitVload(loadRegRelativeOp, 
1931                   (Address) sizeof(Address), 
1932                   REG_SP,
1933                   retReg, 
1934                   gen, noCost);
1935 #elif defined (arch_arch_ia64) // KEVINTODO: untested
1936         emitVload(loadRegRelativeOp, 
1937                   (Address) sizeof(Address), 
1938                   REGISTER_SP, 
1939                   retReg, 
1940                   gen, noCost);
1941 #else
1942         assert(0);
1943 #endif
1944         return true;
1945     }
1946     else {// this is a dynamic ctrl flow instruction, have
1947           // getDynamicCallSiteArgs generate the necessary AST
1948         pdvector<AstNodePtr> args;
1949         if (!gen.addrSpace()->getDynamicCallSiteArgs
1950             (const_cast<instPoint*>(gen.point()),args)) {
1951             return false;
1952         }
1953         return args[0]->generateCode_phase2(gen, noCost, retAddr, retReg);
1954     }
1955 }
1956
1957
1958 #if defined(AST_PRINT)
1959 std::string getOpString(opCode op)
1960 {
1961     switch (op) {
1962         case plusOp: return("+");
1963         case minusOp: return("-");
1964         case timesOp: return("*");
1965         case divOp: return("/");
1966         case lessOp: return("<");
1967         case leOp: return("<=");
1968         case greaterOp: return(">");
1969         case geOp: return(">=");
1970         case eqOp: return("==");
1971         case neOp: return("!=");
1972         case loadOp: return("lda");
1973         case loadConstOp: return("load");
1974         case storeOp: return("=");
1975         case ifOp: return("if");
1976         case ifMCOp: return("ifMC");
1977         case whileOp: return("while") ;
1978         case doOp: return("while") ;
1979         case trampPreamble: return("preTramp");
1980         case branchOp: return("goto");
1981         case noOp: return("nop");
1982         case andOp: return("and");
1983         case orOp: return("or");
1984         case loadIndirOp: return("load&");
1985         case storeIndirOp: return("=&");
1986         case loadFrameRelativeOp: return("load $fp");
1987         case loadRegRelativeOp: return("load $reg");
1988         case loadFrameAddr: return("$fp");
1989         case storeFrameRelativeOp: return("store $fp");
1990         case getAddrOp: return("&");
1991         default: return("ERROR");
1992     }
1993 }
1994 #endif
1995
1996 #undef MIN
1997 #define MIN(x,y) ((x)>(y) ? (y) : (x))
1998 #undef MAX
1999 #define MAX(x,y) ((x)>(y) ? (x) : (y))
2000 #undef AVG
2001 #define AVG(x,y) (((x)+(y))/2)
2002
2003 int AstOperatorNode::costHelper(enum CostStyleType costStyle) const {
2004     int total = 0;
2005     int getInsnCost(opCode t);
2006     
2007     if (op == ifOp) {
2008         // loperand is the conditional expression
2009         if (loperand) total += loperand->costHelper(costStyle);
2010         total += getInsnCost(op);
2011         int rcost = 0, ecost = 0;
2012         if (roperand) {
2013             rcost = roperand->costHelper(costStyle);
2014             if (eoperand)
2015                 rcost += getInsnCost(branchOp);
2016         }
2017         if (eoperand)
2018             ecost = eoperand->costHelper(costStyle);
2019         if(ecost == 0) { // ie. there's only the if body
2020             if(costStyle      == Min)  total += 0;
2021             //guess half time body not executed
2022             else if(costStyle == Avg)  total += rcost / 2;
2023             else if(costStyle == Max)  total += rcost;
2024         } else {  // ie. there's an else block also, for the statements
2025             if(costStyle      == Min)  total += MIN(rcost, ecost);
2026             else if(costStyle == Avg)  total += AVG(rcost, ecost);
2027             else if(costStyle == Max)  total += MAX(rcost, ecost);
2028         }
2029     } else if (op == storeOp) {
2030         if (roperand) total += roperand->costHelper(costStyle);
2031         total += getInsnCost(op);
2032     } else if (op == storeIndirOp) {
2033         if (loperand) total += loperand->costHelper(costStyle);
2034         if (roperand) total += roperand->costHelper(costStyle);
2035         total += getInsnCost(op);
2036     } else if (op == trampPreamble) {
2037         total = getInsnCost(op);
2038     } else {
2039         if (loperand) 
2040             total += loperand->costHelper(costStyle);
2041         if (roperand) 
2042             total += roperand->costHelper(costStyle);
2043         total += getInsnCost(op);
2044     }
2045     return total;
2046 }
2047
2048 int AstOperandNode::costHelper(enum CostStyleType costStyle) const {
2049     int total = 0;
2050     if (oType == Constant) {
2051         total = getInsnCost(loadConstOp);
2052     } else if (oType == DataIndir) {
2053         total = getInsnCost(loadIndirOp);
2054         total += operand()->costHelper(costStyle);
2055     } else if (oType == DataAddr) {
2056         total = getInsnCost(loadOp);
2057     } else if (oType == DataReg) {
2058         total = getInsnCost(loadIndirOp);
2059     } else if (oType == Param) {
2060         total = getInsnCost(getParamOp);
2061     }
2062     return total;
2063 }
2064
2065 int AstCallNode::costHelper(enum CostStyleType costStyle) const {
2066     int total = 0;
2067     if (func_) total += getPrimitiveCost(func_->prettyName().c_str());
2068     else total += getPrimitiveCost(func_name_);
2069
2070     for (unsigned u = 0; u < args_.size(); u++)
2071         if (args_[u]) total += args_[u]->costHelper(costStyle);
2072     return total;
2073 }
2074     
2075
2076 int AstSequenceNode::costHelper(enum CostStyleType costStyle) const {
2077     int total = 0;
2078     for (unsigned i = 0; i < sequence_.size(); i++) {
2079         total += sequence_[i]->costHelper(costStyle);
2080     }
2081
2082     return total;
2083 }
2084
2085 int AstVariableNode::costHelper(enum CostStyleType /*costStyle*/) const{
2086     int total = 0;
2087     return total;
2088 }
2089
2090 #if defined(AST_PRINT)
2091 void AstNode::print() const {
2092   if (this) {
2093 #if defined(ASTDEBUG)
2094     bpfatal("{%d}", referenceCount) ;
2095 #endif
2096     if (type == operandNode) {
2097       if (oType == Constant) {
2098         fprintf(stderr,"%d", (int)(Address) oValue);
2099       } else if (oType == ConstantString) {
2100         fprintf(stderr," %s", (char *)oValue);
2101       } else if (oType == DataIndir) {
2102         fprintf(stderr," @[");
2103         loperand->print();
2104         fprintf(stderr,"]");
2105       } else if (oType == DataReg) {
2106         fprintf(stderr," reg%d ",(int)(Address)oValue);
2107         loperand->print();
2108       } else if (oType == Param) {
2109         fprintf(stderr," param[%d]", (int)(Address) oValue);
2110       } else if (oType == ReturnVal) {
2111         fprintf(stderr,"retVal");
2112       } else if (oType == DataAddr)  {
2113         if(!oVar)
2114         {
2115           fprintf(stderr," [0x%lx]", (long) oValue);
2116         }
2117         else
2118         {
2119           fprintf(stderr," [%s]", oVar->symTabName().c_str());
2120         }
2121         
2122       } else if (oType == FrameAddr)  {
2123         fprintf(stderr," [$fp + %d]", (int)(Address) oValue);
2124       } else if (oType == RegOffset)  {
2125         fprintf(stderr," [$%d + %d]", (int)(Address) loperand->getOValue(), (int)(Address) oValue);
2126       } else if (oType == EffectiveAddr)  {
2127         fprintf(stderr," <<effective address>>");
2128       } else if (oType == BytesAccessed)  {
2129         fprintf(stderr," <<bytes accessed>>");
2130       } else {
2131         fprintf(stderr," <Unknown Operand>");
2132       }
2133     } else if (type == opCodeNode_t) {
2134       cerr << "(" << getOpString(op);
2135       if (loperand) loperand->print();
2136       if (roperand) roperand->print();
2137       if (eoperand) eoperand->print();
2138       fprintf(stderr,")\n");
2139     } else if (type == callNode) {
2140       cerr << "(" << callee;
2141       for (unsigned u = 0; u < operands.size(); u++)
2142         operands[u]->print();
2143       fprintf(stderr,")\n");
2144     } else if (type == sequenceNode_t) {
2145       if (loperand) loperand->print();
2146       fprintf(stderr,",");
2147       if (roperand) roperand->print();
2148       fprintf(stderr,"\n");
2149     }
2150   }
2151 }
2152 #endif
2153
2154 BPatch_type *AstNode::checkType() {
2155     return BPatch::bpatch->type_Untyped;
2156 }
2157
2158 BPatch_type *AstOperatorNode::checkType() {
2159     BPatch_type *ret = NULL;
2160     BPatch_type *lType = NULL, *rType = NULL, *eType = NULL;
2161     bool errorFlag = false;
2162
2163     assert(BPatch::bpatch != NULL);     /* We'll use this later. */
2164
2165     if ((loperand || roperand) && getType()) {
2166         // something has already set the type for us.
2167         // this is likely an expression for array access
2168         ret = const_cast<BPatch_type *>(getType());
2169         return ret;
2170     }
2171
2172     if (loperand) lType = loperand->checkType();
2173
2174     if (roperand) rType = roperand->checkType();
2175
2176     if (eoperand) eType = eoperand->checkType();
2177
2178     if (lType == BPatch::bpatch->type_Error ||
2179         rType == BPatch::bpatch->type_Error)
2180         errorFlag = true;
2181     
2182     switch (op) {
2183     case ifOp:
2184         // XXX No checking for now.  Should check that loperand
2185         // is boolean.
2186         ret = BPatch::bpatch->type_Untyped;
2187         break;
2188     case noOp:
2189         ret = BPatch::bpatch->type_Untyped;
2190         break;
2191     case funcJumpOp:
2192         ret = BPatch::bpatch->type_Untyped;
2193         break;
2194     case getAddrOp:
2195         // Should set type to the infered type not just void * 
2196         //  - jkh 7/99
2197         ret = BPatch::bpatch->stdTypes->findType("void *");
2198         assert(ret != NULL);
2199         break;
2200     default:
2201         // XXX The following line must change to decide based on the
2202         // types and operation involved what the return type of the
2203         // expression will be.
2204         ret = lType;
2205         if (lType != NULL && rType != NULL) {
2206             if (!lType->isCompatible(rType)) {
2207                 fprintf(stderr, "WARNING: LHS type %s not compatible with RHS type %s\n",
2208                         lType->getName(), rType->getName());
2209                 errorFlag = true;
2210             }
2211         }
2212         break;
2213     }
2214     assert (ret != NULL);
2215
2216     if (errorFlag && doTypeCheck) {
2217         ret = BPatch::bpatch->type_Error;
2218     } else if (errorFlag) {
2219         ret = BPatch::bpatch->type_Untyped;
2220     }
2221
2222 #if defined(ASTDEBUG)
2223     // it would be useful to have some indication of what the type applied to
2224     // (currently it appears to be copious amounts of contextless junk)
2225     if (ret) {
2226         logLine(" type is ");
2227         if (ret->getName()) 
2228              logLine(ret->getName());
2229         else
2230              logLine(" <NULL Name String>");
2231         logLine("\n");
2232     }
2233 #endif
2234
2235     // remember what type we are
2236     setType(ret);
2237
2238     return ret;
2239 }
2240
2241 BPatch_type *AstOperandNode::checkType()
2242 {
2243     BPatch_type *ret = NULL;
2244     BPatch_type *type = NULL;
2245     bool errorFlag = false;
2246     
2247     assert(BPatch::bpatch != NULL);     /* We'll use this later. */
2248
2249     if (operand_ && getType()) {
2250         // something has already set the type for us.
2251         // this is likely an expression for array access
2252         ret = const_cast<BPatch_type *>(getType());
2253         return ret;
2254     }
2255     
2256     if (operand_) type = operand_->checkType();
2257
2258     if (type == BPatch::bpatch->type_Error)
2259         errorFlag = true;
2260     
2261     if (oType == DataIndir) {
2262         // XXX Should really be pointer to lType -- jkh 7/23/99
2263         ret = BPatch::bpatch->type_Untyped;
2264     } 
2265     else if ((oType == Param) || (oType == ReturnVal)) {
2266             // XXX Params and ReturnVals untyped for now
2267         ret = BPatch::bpatch->type_Untyped; 
2268     }
2269     else if ((oType == origRegister)) {
2270         ret = BPatch::bpatch->stdTypes->findType("int");
2271     }
2272     else {
2273         ret = const_cast<BPatch_type *>(getType());
2274     }
2275     assert(ret != NULL);
2276
2277     if (errorFlag && doTypeCheck) {
2278         ret = BPatch::bpatch->type_Error;
2279     } else if (errorFlag) {
2280         ret = BPatch::bpatch->type_Untyped;
2281     }
2282
2283 #if defined(ASTDEBUG)
2284     // it would be useful to have some indication of what the type applied to
2285     // (currently it appears to be copious amounts of contextless junk)
2286     if (ret) {
2287         logLine(" type is ");
2288         if (ret->getName()) 
2289              logLine(ret->getName());
2290         else
2291              logLine(" <NULL Name String>");
2292         logLine("\n");
2293     }
2294 #endif
2295
2296     // remember what type we are
2297     setType(ret);
2298
2299     return ret;
2300
2301 }
2302
2303
2304 BPatch_type *AstCallNode::checkType() {
2305     BPatch_type *ret = NULL;
2306     bool errorFlag = false;
2307     
2308     assert(BPatch::bpatch != NULL);     /* We'll use this later. */
2309     
2310     unsigned i;
2311     for (i = 0; i < args_.size(); i++) {
2312         BPatch_type *operandType = args_[i]->checkType();
2313         /* XXX Check operands for compatibility */
2314         if (operandType == BPatch::bpatch->type_Error) {
2315             errorFlag = true;
2316         }
2317     }
2318     /* XXX Should set to return type of function. */
2319     ret = BPatch::bpatch->type_Untyped;
2320
2321     assert(ret != NULL);
2322
2323     if (errorFlag && doTypeCheck) {
2324         ret = BPatch::bpatch->type_Error;
2325     } else if (errorFlag) {
2326         ret = BPatch::bpatch->type_Untyped;
2327     }
2328
2329 #if defined(ASTDEBUG)
2330     // it would be useful to have some indication of what the type applied to
2331     // (currently it appears to be copious amounts of contextless junk)
2332     if (ret) {
2333         logLine(" type is ");
2334         if (ret->getName()) 
2335              logLine(ret->getName());
2336         else
2337              logLine(" <NULL Name String>");
2338         logLine("\n");
2339     }
2340 #endif
2341
2342     // remember what type we are
2343     setType(ret);
2344
2345     return ret;
2346 }
2347
2348 BPatch_type *AstSequenceNode::checkType() {
2349     BPatch_type *ret = NULL;
2350     BPatch_type *sType = NULL;
2351     bool errorFlag = false;
2352     
2353     assert(BPatch::bpatch != NULL);     /* We'll use this later. */
2354
2355     if (getType()) {
2356         // something has already set the type for us.
2357         // this is likely an expression for array access
2358         ret = const_cast<BPatch_type *>(getType());
2359         return ret;
2360     }
2361
2362     for (unsigned i = 0; i < sequence_.size(); i++) {
2363         sType = sequence_[i]->checkType();
2364         if (sType == BPatch::bpatch->type_Error)
2365             errorFlag = true;
2366     }
2367
2368     ret = sType;
2369
2370     assert(ret != NULL);
2371     
2372     if (errorFlag && doTypeCheck) {
2373         ret = BPatch::bpatch->type_Error;
2374     } else if (errorFlag) {
2375         ret = BPatch::bpatch->type_Untyped;
2376     }
2377     
2378 #if defined(ASTDEBUG)
2379     // it would be useful to have some indication of what the type applied to
2380     // (currently it appears to be copious amounts of contextless junk)
2381     if (ret) {
2382         logLine(" type is ");
2383         if (ret->getName()) 
2384              logLine(ret->getName());
2385         else
2386              logLine(" <NULL Name String>");
2387         logLine("\n");
2388     }
2389 #endif
2390
2391     // remember what type we are
2392     setType(ret);
2393
2394     return ret;
2395 }
2396
2397 bool AstNode::accessesParam() {
2398 #if 0
2399     fprintf(stderr, "Undefined call to getChildren for type: ");
2400     if (dynamic_cast<AstNullNode *>(this)) fprintf(stderr, "nullNode\n");
2401     else if (dynamic_cast<AstOperatorNode *>(this)) fprintf(stderr, "operatorNode\n");
2402     else if (dynamic_cast<AstOperandNode *>(this)) fprintf(stderr, "operandNode\n");
2403     else if (dynamic_cast<AstCallNode *>(this)) fprintf(stderr, "callNode\n");
2404     else if (dynamic_cast<AstReplacementNode *>(this)) fprintf(stderr, "replacementNode\n");
2405     else if (dynamic_cast<AstSequenceNode *>(this)) fprintf(stderr, "seqNode\n");
2406     else if (dynamic_cast<AstVariableNode *>(this)) fprintf(stderr, "varNode\n");
2407     else if (dynamic_cast<AstInsnNode *>(this)) fprintf(stderr, "insnNode\n");
2408     else if (dynamic_cast<AstMiniTrampNode *>(this)) fprintf(stderr, "miniTrampNode\n");
2409     else if (dynamic_cast<AstMemoryNode *>(this)) fprintf(stderr, "memoryNode\n");
2410     else fprintf(stderr, "unknownNode\n");
2411 #endif
2412     return false;
2413 }
2414
2415
2416 // This is not the most efficient way to traverse a DAG
2417 bool AstOperatorNode::accessesParam()
2418 {
2419     bool ret = false;
2420     if (loperand)
2421         ret |= loperand->accessesParam();
2422     if (roperand)
2423         ret |= roperand->accessesParam();
2424     if (eoperand)
2425         ret |= eoperand->accessesParam();
2426     return ret;
2427 }
2428
2429
2430 bool AstCallNode::accessesParam() {
2431     for (unsigned i = 0; i < args_.size(); i++) {
2432         if (args_[i]->accessesParam())
2433             return true;
2434     }
2435     return false;
2436 }
2437
2438 bool AstSequenceNode::accessesParam() {
2439     for (unsigned i = 0; i < sequence_.size(); i++) {
2440         if (sequence_[i]->accessesParam())
2441             return true;
2442     }
2443     return false;
2444 }
2445
2446 bool AstVariableNode::accessesParam() {
2447     return ast_wrappers_[index]->accessesParam();
2448 }
2449
2450 // Our children may have incorrect useCounts (most likely they 
2451 // assume that we will not bother them again, which is wrong)
2452 void AstNode::fixChildrenCounts()
2453 {
2454     pdvector<AstNodePtr> children;
2455     getChildren(children);
2456     for (unsigned i=0; i<children.size(); i++) {
2457                 children[i]->setUseCount();
2458     }
2459 }
2460
2461
2462 // Check if the node can be kept at all. Some nodes (e.g., storeOp)
2463 // can not be cached. In fact, there are fewer nodes that can be cached.
2464 bool AstOperatorNode::canBeKept() const {
2465     switch (op) {
2466     case plusOp:
2467     case minusOp:
2468     case timesOp:
2469     case divOp:
2470     case neOp:
2471     case noOp:
2472     case orOp:
2473     case andOp:
2474                 break;
2475     default:
2476         return false;
2477     }
2478
2479     // The switch statement is a little odd, but hey. 
2480     if (loperand && !loperand->canBeKept()) return false;
2481     if (roperand && !roperand->canBeKept()) return false;
2482     if (eoperand && !eoperand->canBeKept()) return false;
2483     
2484     return true;
2485 }
2486
2487 bool AstOperandNode::canBeKept() const {
2488     
2489     switch (oType) {
2490     case DataReg:
2491     case DataIndir:
2492     case RegOffset:
2493     case origRegister:
2494     case DataAddr:
2495     case variableValue:
2496         return false;
2497     default:
2498                 break;
2499     }
2500     if (operand_ && !operand_->canBeKept()) return false;
2501     return true;
2502 }
2503
2504 bool AstCallNode::canBeKept() const {
2505     if (constFunc_) {
2506         for (unsigned i = 0; i < args_.size(); i++) {
2507             if (!args_[i]->canBeKept()) {
2508                 fprintf(stderr, "AST %p: labelled const func but argument %d cannot be kept!\n",
2509                         this, i);
2510                 return false;
2511             }
2512         }
2513         return true;
2514     }
2515     return false;
2516     
2517 }
2518
2519 bool AstSequenceNode::canBeKept() const {
2520         // Theoretically we could keep the entire thing, but... not sure
2521         // that's a terrific idea. For now, don't keep a sequence node around.
2522     return false;
2523 }
2524
2525 bool AstVariableNode::canBeKept() const {
2526     return ast_wrappers_[index]->canBeKept();
2527 }
2528
2529 bool AstMiniTrampNode::canBeKept() const {
2530         // Well... depends on the actual AST, doesn't it.
2531         assert(ast_);
2532         
2533         return ast_->canBeKept();
2534 }
2535
2536 bool AstReplacementNode::canBeKept() const { 
2537     return false;
2538 }
2539
2540 bool AstMemoryNode::canBeKept() const {
2541         // Despite our memory loads, we can be kept;
2542         // we're loading off process state, which is defined
2543         // to be invariant during the instrumentation phase.
2544         return true;
2545 }
2546
2547 // Occasionally, we do not call .generateCode_phase2 for the referenced node, 
2548 // but generate code by hand. This routine decrements its use count properly
2549 void AstNode::decUseCount(codeGen &gen)
2550 {
2551     if (useCount == 0) return;
2552     
2553     useCount--;
2554     
2555     if (useCount == 0) {
2556         gen.tracker()->removeKeptRegister(gen, this);
2557     }
2558 }
2559
2560 // Return all children of this node ([lre]operand, ..., operands[])
2561
2562 void AstNode::getChildren(pdvector<AstNodePtr > &) {
2563 #if 0
2564     fprintf(stderr, "Undefined call to getChildren for type: ");
2565     if (dynamic_cast<AstNullNode *>(this)) fprintf(stderr, "nullNode\n");
2566     else if (dynamic_cast<AstOperatorNode *>(this)) fprintf(stderr, "operatorNode\n");
2567     else if (dynamic_cast<AstOperandNode *>(this)) fprintf(stderr, "operandNode\n");
2568     else if (dynamic_cast<AstCallNode *>(this)) fprintf(stderr, "callNode\n");
2569     else if (dynamic_cast<AstReplacementNode *>(this)) fprintf(stderr, "replacementNode\n");
2570     else if (dynamic_cast<AstSequenceNode *>(this)) fprintf(stderr, "seqNode\n");
2571     else if (dynamic_cast<AstInsnNode *>(this)) fprintf(stderr, "insnNode\n");
2572     else if (dynamic_cast<AstMiniTrampNode *>(this)) fprintf(stderr, "miniTrampNode\n");
2573     else if (dynamic_cast<AstMemoryNode *>(this)) fprintf(stderr, "memoryNode\n");
2574     else fprintf(stderr, "unknownNode\n");
2575 #endif
2576 }
2577
2578
2579 void AstOperatorNode::getChildren(pdvector<AstNodePtr > &children) {
2580     if (loperand) children.push_back(loperand);
2581     if (roperand) children.push_back(roperand);
2582     if (eoperand) children.push_back(eoperand);
2583 }
2584
2585 void AstOperandNode::getChildren(pdvector<AstNodePtr > &children) {
2586     if (operand_) children.push_back(operand_);
2587 }
2588
2589 void AstCallNode::getChildren(pdvector<AstNodePtr > &children) {
2590     for (unsigned i = 0; i < args_.size(); i++)
2591         children.push_back(args_[i]);
2592 }
2593
2594 void AstSequenceNode::getChildren(pdvector<AstNodePtr > &children) {
2595     for (unsigned i = 0; i < sequence_.size(); i++)
2596         children.push_back(sequence_[i]);
2597 }
2598
2599 void AstVariableNode::getChildren(pdvector<AstNodePtr > &children) {
2600     ast_wrappers_[index]->getChildren(children);
2601 }
2602
2603 void AstMiniTrampNode::getChildren(pdvector<AstNodePtr > &children) {
2604     children.push_back(ast_);
2605 }
2606
2607 void AstOperatorNode::setVariableAST(codeGen &g) {
2608     if(loperand) loperand->setVariableAST(g);
2609     if(roperand) roperand->setVariableAST(g);
2610     if(eoperand) eoperand->setVariableAST(g);
2611 }
2612
2613 void AstOperandNode::setVariableAST(codeGen &g){
2614     if(operand_) operand_->setVariableAST(g);
2615 }
2616
2617 void AstCallNode::setVariableAST(codeGen &g){
2618     for (unsigned i = 0; i < args_.size(); i++)
2619         args_[i]->setVariableAST(g);
2620 }
2621
2622 void AstSequenceNode::setVariableAST(codeGen &g) {
2623     for (unsigned i = 0; i < sequence_.size(); i++)
2624         sequence_[i]->setVariableAST(g);
2625 }
2626
2627 void AstVariableNode::setVariableAST(codeGen &gen){
2628     //fprintf(stderr, "Generating code for variable in function %s with start address 0x%lx at address 0x%lx\n",gen.func()->prettyName().c_str(), gen.func()->getAddress(),gen.point()->addr());
2629     if(!ranges_)
2630         return;
2631     if(!gen.point())    //oneTimeCode. Set the AST at the beginning of the function??
2632     {
2633         index = 0;
2634         return;
2635     }
2636     Address addr = gen.point()->addr();     //Offset of inst point from function base address
2637     for(unsigned i=0; i< ranges_->size();i++){
2638         if((*ranges_)[i].first<=addr && addr<(*ranges_)[i].second)
2639             index = i;
2640     }
2641 }
2642
2643 void AstInsnBranchNode::setVariableAST(codeGen &g){
2644     if(target_) target_->setVariableAST(g);
2645 }
2646
2647 void AstInsnMemoryNode::setVariableAST(codeGen &g){
2648     if(load_) load_->setVariableAST(g);
2649     if(store_) store_->setVariableAST(g);
2650 }
2651
2652 void AstMiniTrampNode::setVariableAST(codeGen &g){
2653     if(ast_) ast_->setVariableAST(g);
2654 }
2655
2656 bool AstCallNode::containsFuncCall() const {
2657    return true;
2658 }
2659
2660 bool AstReplacementNode::containsFuncCall() const {
2661    return true;
2662 }
2663
2664 bool AstOperatorNode::containsFuncCall() const {
2665         if (loperand && loperand->containsFuncCall()) return true;
2666         if (roperand && roperand->containsFuncCall()) return true;
2667         if (eoperand && eoperand->containsFuncCall()) return true;
2668         return false;
2669 }
2670
2671 bool AstOperandNode::containsFuncCall() const {
2672         if (operand_ && operand_->containsFuncCall()) return true;
2673         return false;
2674 }
2675
2676 bool AstMiniTrampNode::containsFuncCall() const {
2677         if (ast_ && ast_->containsFuncCall()) return true;
2678         return false;
2679 }
2680
2681 bool AstSequenceNode::containsFuncCall() const {
2682         for (unsigned i = 0; i < sequence_.size(); i++) {
2683                 if (sequence_[i]->containsFuncCall()) return true;
2684         }
2685         return false;
2686 }
2687
2688 bool AstVariableNode::containsFuncCall() const 
2689 {
2690     return ast_wrappers_[index]->containsFuncCall();
2691 }
2692
2693 bool AstInsnMemoryNode::containsFuncCall() const {
2694     if (load_ && load_->containsFuncCall()) return true;
2695     if (store_ && store_->containsFuncCall()) return true;
2696     return false;
2697 }
2698
2699 bool AstNullNode::containsFuncCall() const
2700 {
2701    return false;
2702 }
2703
2704 bool AstLabelNode::containsFuncCall() const
2705 {
2706    return false;
2707 }
2708
2709 bool AstMemoryNode::containsFuncCall() const
2710 {
2711    return false;
2712 }
2713
2714 bool AstInsnNode::containsFuncCall() const
2715 {
2716    return false;
2717 }
2718
2719 bool AstOriginalAddrNode::containsFuncCall() const
2720 {
2721    return false;
2722 }
2723
2724 bool AstActualAddrNode::containsFuncCall() const
2725 {
2726    return false;
2727 }
2728
2729 bool AstDynamicTargetNode::containsFuncCall() const
2730 {
2731    return false;
2732 }
2733
2734 bool AstCallNode::containsFuncJump() const {
2735    return false;
2736 }
2737
2738 bool AstReplacementNode::containsFuncJump() const {
2739    return true;
2740 }
2741
2742 bool AstOperatorNode::containsFuncJump() const {
2743         if (loperand && loperand->containsFuncJump()) return true;
2744         if (roperand && roperand->containsFuncJump()) return true;
2745         if (eoperand && eoperand->containsFuncJump()) return true;
2746         return false;
2747 }
2748
2749 bool AstOperandNode::containsFuncJump() const {
2750         if (operand_ && operand_->containsFuncJump()) return true;
2751         return false;
2752 }
2753
2754 bool AstMiniTrampNode::containsFuncJump() const {
2755         if (ast_ && ast_->containsFuncJump()) return true;
2756         return false;
2757 }
2758
2759 bool AstSequenceNode::containsFuncJump() const {
2760         for (unsigned i = 0; i < sequence_.size(); i++) {
2761                 if (sequence_[i]->containsFuncJump()) return true;
2762         }
2763         return false;
2764 }
2765
2766 bool AstVariableNode::containsFuncJump() const 
2767 {
2768     return ast_wrappers_[index]->containsFuncJump();
2769 }
2770
2771 bool AstInsnMemoryNode::containsFuncJump() const {
2772     if (load_ && load_->containsFuncJump()) return true;
2773     if (store_ && store_->containsFuncJump()) return true;
2774     return false;
2775 }
2776
2777 bool AstNullNode::containsFuncJump() const
2778 {
2779    return false;
2780 }
2781
2782 bool AstLabelNode::containsFuncJump() const
2783 {
2784    return false;
2785 }
2786
2787 bool AstMemoryNode::containsFuncJump() const
2788 {
2789    return false;
2790 }
2791
2792 bool AstInsnNode::containsFuncJump() const
2793 {
2794    return false;
2795 }
2796
2797 bool AstOriginalAddrNode::containsFuncJump() const
2798 {
2799    return false;
2800 }
2801
2802 bool AstActualAddrNode::containsFuncJump() const
2803 {
2804    return false;
2805 }
2806
2807 bool AstDynamicTargetNode::containsFuncJump() const
2808 {
2809    return false;
2810 }
2811
2812 bool AstCallNode::usesAppRegister() const {
2813    for (unsigned i=0; i<args_.size(); i++) {
2814       if (args_[i] && args_[i]->usesAppRegister()) return true;
2815    }
2816    return false;
2817 }
2818
2819 bool AstReplacementNode::usesAppRegister() const {
2820    return false;
2821 }
2822
2823 bool AstOperatorNode::usesAppRegister() const {
2824         if (loperand && loperand->usesAppRegister()) return true;
2825         if (roperand && roperand->usesAppRegister()) return true;
2826         if (eoperand && eoperand->usesAppRegister()) return true;
2827         return false;
2828 }
2829
2830 bool AstOperandNode::usesAppRegister() const {
2831    if (oType == AstNode::FrameAddr ||
2832        oType == AstNode::RegOffset ||
2833        oType == AstNode::origRegister ||
2834        oType == AstNode::Param ||
2835        oType == AstNode::ReturnVal)
2836    {
2837       return true;
2838    }
2839
2840         if (operand_ && operand_->usesAppRegister()) return true;
2841         return false;
2842 }
2843
2844 bool AstMiniTrampNode::usesAppRegister() const {
2845         if (ast_ && ast_->usesAppRegister()) return true;
2846         return false;
2847 }
2848
2849 bool AstSequenceNode::usesAppRegister() const {
2850         for (unsigned i = 0; i < sequence_.size(); i++) {
2851                 if (sequence_[i]->usesAppRegister()) return true;
2852         }
2853         return false;
2854 }
2855
2856 bool AstVariableNode::usesAppRegister() const 
2857 {
2858     return ast_wrappers_[index]->usesAppRegister();
2859 }
2860
2861 bool AstInsnMemoryNode::usesAppRegister() const {
2862     if (load_ && load_->usesAppRegister()) return true;
2863     if (store_ && store_->usesAppRegister()) return true;
2864     return false;
2865 }
2866
2867 bool AstNullNode::usesAppRegister() const
2868 {
2869    return false;
2870 }
2871
2872 bool AstLabelNode::usesAppRegister() const
2873 {
2874    return false;
2875 }
2876
2877 bool AstDynamicTargetNode::usesAppRegister() const
2878 {
2879    return false;
2880 }
2881
2882 bool AstActualAddrNode::usesAppRegister() const
2883 {
2884    return false;
2885 }
2886
2887 bool AstOriginalAddrNode::usesAppRegister() const
2888 {
2889    return false;
2890 }
2891
2892 bool AstMemoryNode::usesAppRegister() const
2893 {
2894    return true;
2895 }
2896
2897 bool AstInsnNode::usesAppRegister() const
2898 {
2899    return true;
2900 }
2901
2902 void regTracker_t::addKeptRegister(codeGen &gen, AstNode *n, Register reg) {
2903         assert(n);
2904         if (tracker.find(n)) {
2905                 assert(tracker[n].keptRegister == reg);
2906                 return;
2907         }
2908         commonExpressionTracker t;
2909         t.keptRegister = reg;
2910         t.keptLevel = condLevel;
2911         tracker[n] = t;
2912         gen.rs()->markKeptRegister(reg);
2913 }
2914
2915 void regTracker_t::removeKeptRegister(codeGen &gen, AstNode *n) {
2916         if (!tracker.find(n)) {
2917                 return;
2918         }
2919         gen.rs()->unKeepRegister(tracker[n].keptRegister);
2920         tracker.undef(n);
2921 }
2922
2923 Register regTracker_t::hasKeptRegister(AstNode *n) {
2924         if (tracker.find(n))
2925                 return tracker[n].keptRegister;
2926         return REG_NULL;        
2927 }
2928
2929 // Find if the given register is "owned" by an AST node,
2930 // and if so nuke it.
2931
2932 bool regTracker_t::stealKeptRegister(Register r) {
2933         AstNode *a;
2934         commonExpressionTracker c;
2935         ast_printf("STEALING kept register %d for someone else\n", r);
2936         dictionary_hash_iter<AstNode *, commonExpressionTracker> reg_iter(tracker);
2937         while (reg_iter.next(a, c)) {
2938             if (c.keptRegister == r) {
2939                 tracker.undef(a);
2940                 return true;
2941             }
2942         }
2943         fprintf(stderr, "Odd - couldn't find kept register %d\n", r);
2944         return true;
2945 }
2946
2947 void regTracker_t::reset() {
2948         condLevel = 0;
2949         tracker.clear();
2950 }
2951
2952 void regTracker_t::increaseConditionalLevel() {
2953         condLevel++;
2954         ast_printf("Entering conditional branch, level now %d\n", condLevel);
2955 }
2956
2957 void regTracker_t::decreaseAndClean(codeGen &gen) {
2958     AstNode *a;
2959     commonExpressionTracker c;
2960     assert(condLevel > 0);
2961     
2962     ast_printf("Exiting from conditional branch, level currently %d\n", condLevel);
2963     
2964     dictionary_hash_iter<AstNode *, commonExpressionTracker> reg_iter(tracker);
2965     while (reg_iter.next(a, c)) {
2966         if (c.keptLevel == condLevel) {
2967             tracker.undef(a);
2968             gen.rs()->unKeepRegister(c.keptRegister);
2969             ast_printf("Removing kept register %d, level %d, for AST %p\n", 
2970                        c.keptRegister, c.keptLevel, a);
2971         }
2972     }
2973     
2974     condLevel--;
2975 }
2976
2977 unsigned regTracker_t::astHash(AstNode* const &ast) {
2978         return addrHash4((Address) ast);
2979 }
2980
2981 void AstNode::debugPrint(unsigned level) {
2982     if (!dyn_debug_ast) return;
2983     
2984     for (unsigned i = 0; i < level; i++) fprintf(stderr, "%s", " ");
2985     
2986     std::string type;
2987     if (dynamic_cast<AstNullNode *>(this)) type = "nullNode";
2988     else if (dynamic_cast<AstOperatorNode *>(this)) type = "operatorNode";
2989     else if (dynamic_cast<AstOperandNode *>(this)) type = "operandNode";
2990     else if (dynamic_cast<AstCallNode *>(this)) type = "callNode";
2991     else if (dynamic_cast<AstReplacementNode *>(this)) type = "replacementNode";
2992     else if (dynamic_cast<AstSequenceNode *>(this)) type = "sequenceNode";
2993     else if (dynamic_cast<AstVariableNode *>(this)) type = "variableNode";
2994     else if (dynamic_cast<AstInsnNode *>(this)) type = "insnNode";
2995     else if (dynamic_cast<AstMiniTrampNode *>(this)) type = "miniTrampNode";
2996     else if (dynamic_cast<AstMemoryNode *>(this)) type = "memoryNode";
2997     else type = "unknownNode";
2998     
2999     ast_printf("Node %s: ptr %p, useCount is %d, canBeKept %d, type %s\n", type.c_str(), this, useCount, canBeKept(), getType() ? getType()->getName() : "<NULL TYPE>");
3000
3001     pdvector<AstNodePtr> children;
3002     getChildren(children);
3003     for (unsigned i=0; i<children.size(); i++) {
3004         children[i]->debugPrint(level+1);
3005     }
3006 }
3007
3008 void regTracker_t::debugPrint() {
3009     if (!dyn_debug_ast) return;
3010     
3011     fprintf(stderr, "==== Begin debug dump of register tracker ====\n");
3012     
3013     fprintf(stderr, "Condition level: %d\n", condLevel);
3014     
3015     AstNode *a;
3016     commonExpressionTracker c;
3017     
3018     dictionary_hash_iter<AstNode *, commonExpressionTracker> reg_iter(tracker);
3019     while (reg_iter.next(a, c)) {
3020         fprintf(stderr, "AstNode %p: register %d, condition level %d\n",
3021                 a, c.keptRegister, c.keptLevel);
3022     }   
3023     fprintf(stderr, "==== End debug dump of register tracker ====\n");
3024 }
3025
3026 unsigned AstNode::getTreeSize() {
3027         pdvector<AstNodePtr > children;
3028         getChildren(children);
3029
3030         unsigned size = 1; // Us
3031         for (unsigned i = 0; i < children.size(); i++)
3032                 size += children[i]->getTreeSize();
3033         return size;
3034         
3035 }
3036
3037 int_variable* AstOperandNode::lookUpVar(AddressSpace* as)
3038 {
3039   mapped_module *mod = as->findModule(oVar->pdmod()->fileName());
3040   if(mod && (oVar->pdmod() == mod->pmod()))
3041   {
3042     int_variable* tmp = mod->obj()->findVariable(const_cast<image_variable*>(oVar));
3043     return tmp;
3044   }
3045   return NULL;
3046 }
3047
3048 void AstOperandNode::emitVariableLoad(opCode op, Register src2, Register dest, codeGen& gen, 
3049                                       bool noCost, registerSpace* rs, 
3050                                       int size, const instPoint* point, AddressSpace* as)
3051 {
3052   int_variable* var = lookUpVar(as);
3053   if(var && !as->needsPIC(var))
3054   {
3055     emitVload(op, var->getAddress(), src2, dest, gen, noCost, rs, size, point, as);
3056   }
3057   else
3058   {
3059     gen.codeEmitter()->emitLoadShared(op, dest, oVar, (var!=NULL),size, gen, 0);
3060   }  
3061 }
3062
3063 void AstOperandNode::emitVariableStore(opCode op, Register src1, Register src2, codeGen& gen, 
3064                                       bool noCost, registerSpace* rs, 
3065                                       int size, const instPoint* point, AddressSpace* as)
3066 {
3067   int_variable* var = lookUpVar(as);
3068   if (var && !as->needsPIC(var))
3069   {
3070     emitVstore(op, src1, src2, var->getAddress(), gen, noCost, rs, size, point, as);
3071   }
3072   else
3073   {
3074     gen.codeEmitter()->emitStoreShared(src1, oVar, (var!=NULL), size, gen);
3075   }  
3076 }
3077
3078 bool AstNode::decRefCount()
3079 {
3080    referenceCount--;
3081    //return referenceCount <= 0;
3082    return true;
3083 }