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