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