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