One byte read can produce bound [0,255], but it is possible that an one byte read...
[dyninst.git] / parseAPI / src / BoundFactCalculator.C
1 #include "dyntypes.h"
2 #include "CodeObject.h"
3 #include "CodeSource.h"
4
5 #include "BoundFactCalculator.h"
6 #include "IndirectASTVisitor.h"
7 #include "debug_parse.h"
8 #include "JumpTablePred.h"
9 #include "Instruction.h"
10
11 using namespace Dyninst::InstructionAPI;
12
13 void BoundFactsCalculator::NaturalDFS(Node::Ptr cur) {
14     nodeColor[cur] = 1;
15     NodeIterator nbegin, nend;
16     cur->outs(nbegin, nend);
17
18     for (; nbegin != nend; ++nbegin) 
19         if (nodeColor.find(*nbegin) == nodeColor.end())
20             NaturalDFS(*nbegin);
21
22     reverseOrder.push_back(cur);
23    
24 }
25
26 void BoundFactsCalculator::ReverseDFS(Node::Ptr cur) {
27     nodeColor[cur] = 1;
28     analysisOrder[cur] = orderStamp;
29     NodeIterator nbegin, nend;
30     cur->ins(nbegin, nend);
31
32     for (; nbegin != nend; ++nbegin) 
33         if (nodeColor.find(*nbegin) == nodeColor.end())
34             ReverseDFS(*nbegin);
35 }
36
37 static void BuildEdgeFromVirtualEntry(SliceNode::Ptr virtualEntry,
38                                       ParseAPI::Block *curBlock,
39                                       map<ParseAPI::Block*, vector<SliceNode::Ptr> >&targetMap,
40                                       set<ParseAPI::Block*> &visit,
41                                       GraphPtr slice) {
42     if (targetMap.find(curBlock) != targetMap.end()) {
43         const vector<SliceNode::Ptr> &targets = targetMap[curBlock];
44         for (auto nit = targets.begin(); nit != targets.end(); ++nit) {
45             SliceNode::Ptr trgNode = *nit; 
46             slice->insertPair(virtualEntry, trgNode, TypedSliceEdge::create(virtualEntry, trgNode, FALLTHROUGH));
47         }
48         return;
49     }
50     if (visit.find(curBlock) != visit.end()) return;
51     visit.insert(curBlock);
52     for (auto eit = curBlock->targets().begin(); eit != curBlock->targets().end(); ++eit)
53         if ((*eit)->type() != CALL && (*eit)->type() != RET) {
54             BuildEdgeFromVirtualEntry(virtualEntry, (*eit)->trg(), targetMap, visit, slice);       
55         }
56 }                                     
57
58 void BoundFactsCalculator::DetermineAnalysisOrder() {
59     NodeIterator nbegin, nend;
60     slice->allNodes(nbegin, nend);
61
62     nodeColor.clear();
63     reverseOrder.clear();
64     analysisOrder.clear();
65     for (; nbegin != nend; ++nbegin) 
66         if (nodeColor.find(*nbegin) == nodeColor.end()) {
67             NaturalDFS(*nbegin);
68         }
69     nodeColor.clear();
70     orderStamp = 0;
71     for (auto nit = reverseOrder.rbegin(); nit != reverseOrder.rend(); ++nit)
72         if (nodeColor.find(*nit) == nodeColor.end()) {
73             ++orderStamp;
74             ReverseDFS(*nit);
75         }
76
77     // Create a virtual entry node that has
78     // edges into all entry SCCs
79     SliceNode::Ptr virtualEntry = SliceNode::create(Assignment::Ptr(), func->entry(), func);
80     analysisOrder[virtualEntry] = 0;
81     for (int curOrder = 1; curOrder <= orderStamp; ++curOrder) {
82         // First determine all nodes in this SCC
83         vector<Node::Ptr> curNodes;
84         NodeIterator nbegin, nend;
85         slice->allNodes(nbegin, nend);
86         for (; nbegin != nend; ++nbegin) {
87             if (analysisOrder[*nbegin] == curOrder) {
88                 curNodes.push_back(*nbegin);
89             } 
90         }
91
92         // If this SCC does not have any outside edge,
93         // it is an entry SCC and we need to connect
94         // the virtual entry to it
95         if (!HasIncomingEdgesFromLowerLevel(curOrder, curNodes)) {
96             if (curNodes.size() == 1) {
97                 // If the SCC has only one node,
98                 // we connect the virtual entry to this single node
99                 SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*(curNodes.begin()));
100                 slice->insertPair(virtualEntry, node, TypedSliceEdge::create(virtualEntry, node, FALLTHROUGH));
101             } else {
102                 // If there are more than one node in this SCC,
103                 // we do a DFS to see which nodes in the SCC can be
104                 // reached from the entry of the function without passing
105                 // through other nodes in the SCC.
106                 // Basically, we only connect edges from the virtual entry
107                 // to the entries of the SCC
108                 set<ParseAPI::Block*> visit;
109                 map<ParseAPI::Block*, vector<SliceNode::Ptr> >targetMap;
110                 for (auto nit = curNodes.begin(); nit != curNodes.end(); ++nit) {
111                     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*nit);
112                     ParseAPI::Block * b = node->block();
113                     Address addr = node->addr();
114                     if (targetMap.find(b) == targetMap.end()) {
115                         targetMap[b].push_back(node);
116                     } else if (targetMap[b][0]->addr() > addr) {
117                         targetMap[b].clear();
118                         targetMap[b].push_back(node);
119                     } else if (targetMap[b][0]->addr() == addr) {
120                         targetMap[b].push_back(node);
121                     }
122                 }
123                 BuildEdgeFromVirtualEntry(virtualEntry, virtualEntry->block(), targetMap, visit, slice); 
124             }
125         }
126     }
127     //fprintf(stderr, "%d\n", nodeColor.size());
128 //    if (nodeColor.size() > 100) slice->printDOT("slice.dot");
129
130     slice->clearEntryNodes();
131     slice->markAsEntryNode(virtualEntry);
132 //    if (nodeColor.size() == 24 && jumpAddr == 0x4305ff) {
133 //    if (jumpAddr == 0x41b8b1 && nodeColor.size() < 25) { 
134 //        dyn_debug_parsing=1;
135 //      slice->printDOT("slice.dot");
136 //    } else
137 //        dyn_debug_parsing=0;
138
139 }
140
141 bool BoundFactsCalculator::HasIncomingEdgesFromLowerLevel(int curOrder, vector<Node::Ptr>& curNodes) {
142     for (auto nit = curNodes.begin(); nit != curNodes.end(); ++nit) {
143         Node::Ptr cur = *nit;
144         NodeIterator nbegin, nend;
145         cur->ins(nbegin, nend);
146         for (; nbegin != nend; ++nbegin) 
147             if (analysisOrder[*nbegin] < curOrder) return true;
148     }
149     return false;
150
151 }
152
153 bool BoundFactsCalculator::CalculateBoundedFacts() {    
154     /* We use a dataflow analysis to calculate the value bound
155      * of each register and potentially some memory locations.
156      * The key steps of the dataflow analysis are 
157      * 1. Determine the analysis order:
158      *    First calculate all strongly connected components (SCC)
159      *    of the graph. The flow analysis inside a SCC is 
160      *    iterative. The flow analysis between several SCCs
161      *    is done topologically. 
162      * 2. For each node, need to calculate the meet and 
163      *    calculate the transfer function.
164      * 1. The meet should be simply an intersection of all the bounded facts 
165      * along all paths. 
166      * 2. To calculate the transfer function, we first get the symbolic expression
167      * of the instrution for the node. Then depending on the instruction operation
168      * and the meet result, we know what are still bounded. For example, loading 
169      * memory is always unbounded; doing and operation on a register with a constant
170      * makes the register bounded. 
171      */
172     
173     DetermineAnalysisOrder();
174     queue<Node::Ptr> workingList;
175     unordered_set<Node::Ptr, Node::NodePtrHasher> inQueue;
176     unordered_map<Node::Ptr, int, Node::NodePtrHasher> inQueueLimit;
177
178     for (int curOrder = 0; curOrder <= orderStamp; ++curOrder) {
179         // We first determine which nodes are
180         // in this SCC
181         vector<Node::Ptr> curNodes;
182         NodeIterator nbegin, nend;
183         slice->allNodes(nbegin, nend);
184         for (; nbegin != nend; ++nbegin) {
185             if (analysisOrder[*nbegin] == curOrder) {
186                 curNodes.push_back(*nbegin);
187                 workingList.push(*nbegin);
188                 inQueue.insert(*nbegin);
189             } 
190         }
191
192         if (!HasIncomingEdgesFromLowerLevel(curOrder, curNodes)) {
193             // If this SCC is an entry SCC,
194             // we choose a node inside the SCC
195             // and let it be top.
196             // This should only contain the virtual entry node
197             parsing_printf("This SCC does not incoming edges from outside\n");
198             boundFactsIn[curNodes[0]] = new BoundFact();
199             boundFactsOut[curNodes[0]] = new BoundFact();
200         }
201         parsing_printf("Starting analysis inside SCC %d\n", curOrder);
202         // We now start iterative analysis inside the SCC
203         while (!workingList.empty()) {
204             // We get the current node
205             Node::Ptr curNode = workingList.front();
206             workingList.pop();
207             inQueue.erase(curNode);
208             
209             SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);
210             ++inQueueLimit[curNode];
211             if (inQueueLimit[curNode] > IN_QUEUE_LIMIT) continue;
212             
213             BoundFact* oldFactIn = GetBoundFactIn(curNode);
214             parsing_printf("Calculate Meet for %lx", node->addr());
215             if (node->assign()) {
216                 parsing_printf(", insn: %s\n", node->assign()->insn()->format().c_str());
217             }
218             else {
219                 if (node->block() == NULL) 
220                     parsing_printf(", the VirtualExit node\n");
221                 else
222                     parsing_printf(", the VirtualEntry node\n");
223
224             }
225             parsing_printf("\tOld fact for %lx:\n", node->addr());
226             if (oldFactIn == NULL) parsing_printf("\t\t do not exist\n"); else oldFactIn->Print();
227
228             // We find all predecessors of the current node
229             // and calculates the meet of the analysis results
230             // from the predecessors
231             BoundFact* newFactIn = Meet(curNode);
232             parsing_printf("\tNew fact at %lx\n", node->addr());
233             if (newFactIn != NULL) newFactIn->Print(); else parsing_printf("\t\tNot calculated\n");
234
235             // If the current node has not been calcualted yet,
236             // or the new meet results are different from the 
237             // old ones, we keep the new results
238             if (newFactIn != NULL && (oldFactIn == NULL || *oldFactIn != *newFactIn)) {
239                 parsing_printf("\tFacts change!\n");
240                 if (oldFactIn != NULL) delete oldFactIn;
241                 boundFactsIn[curNode] = newFactIn;
242                 BoundFact* newFactOut = new BoundFact(*newFactIn);
243
244                 // The current node has a transfer function
245                 // that changes the analysis results
246                 CalcTransferFunction(curNode, newFactOut);
247         
248                 if (boundFactsOut.find(curNode) != boundFactsOut.end() && boundFactsOut[curNode] != NULL)
249                     delete boundFactsOut[curNode];                  
250                 boundFactsOut[curNode] = newFactOut;
251                 curNode->outs(nbegin, nend);
252                 for (; nbegin != nend; ++nbegin)
253                     // We only add node inside current SCC into the working list
254                     if (inQueue.find(*nbegin) == inQueue.end() && analysisOrder[*nbegin] == curOrder) {
255                         workingList.push(*nbegin);
256                         inQueue.insert(*nbegin);
257                     }
258             } else {
259                 if (newFactIn != NULL) delete newFactIn;
260                 parsing_printf("\tFacts do not change!\n");
261             }
262
263         }
264     }
265
266     return true;
267 }
268
269
270
271
272 void BoundFactsCalculator::ThunkBound( BoundFact*& curFact, Node::Ptr src, Node::Ptr trg, bool &newCopy) {
273
274     // This function checks whether any found thunk is between 
275     // the src node and the trg node. If there is any, then we have 
276     // extra bound information to be added.
277     ParseAPI::Block *srcBlock;
278     Address srcAddr = 0;
279     if (src == Node::Ptr()) 
280         srcBlock = func->entry();
281     else {
282         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(src);
283         srcBlock = srcNode->block();
284         srcAddr = srcNode->addr();
285
286     }
287     SliceNode::Ptr trgNode = boost::static_pointer_cast<SliceNode>(trg);                               
288     ParseAPI::Block *trgBlock = trgNode->block();
289     Address trgAddr = trgNode->addr();
290
291     bool first = true;
292     for (auto tit = thunks.begin(); tit != thunks.end(); ++tit) {
293         ParseAPI::Block* thunkBlock = tit->second.block;
294         parsing_printf("\t\tCheck srcAddr at %lx, trgAddr at %lx, thunk at %lx\n", srcAddr, trgAddr, tit->first);
295         if (src != Node::Ptr()) {
296             if (srcBlock == thunkBlock) {
297                 if (srcAddr > tit->first) continue;
298             } else {
299                 if (rf.thunk_ins[thunkBlock].find(srcBlock) == rf.thunk_ins[thunkBlock].end()) continue;
300             }
301         }
302         if (trgBlock == thunkBlock) {
303             if (trgAddr < tit->first) continue;
304         } else {
305             if (rf.thunk_outs[thunkBlock].find(trgBlock) == rf.thunk_outs[thunkBlock].end()) continue;
306         }
307
308         parsing_printf("\t\t\tfind thunk at %lx between the source and the target. Add fact", tit->first);
309         BoundValue *bv = new BoundValue(tit->second.value);
310         bv->Print();
311         if (first && !newCopy) {
312             newCopy = true;
313             curFact = new BoundFact(*curFact);
314         }
315         curFact->GenFact(VariableAST::create(Variable(AbsRegion(Absloc(tit->second.reg)))), bv, false);
316         first = false;
317     }
318
319
320 }
321
322
323 static bool IsConditionalJump(Instruction::Ptr insn) {
324     entryID id = insn->getOperation().getID();
325
326     if (id == e_jz || id == e_jnz ||
327         id == e_jb || id == e_jnb ||
328         id == e_jbe || id == e_jnbe ||
329         id == e_jb_jnaej_j || id == e_jnb_jae_j ||
330         id == e_jle || id == e_jl ||
331         id == e_jnl || id == e_jnle) return true;
332     return false;
333 }
334
335 BoundFact* BoundFactsCalculator::Meet(Node::Ptr curNode) {
336
337     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);     
338
339     EdgeIterator gbegin, gend;
340     curNode->ins(gbegin, gend);    
341     BoundFact* newFact = NULL;
342     
343     bool first = true;  
344     for (; gbegin != gend; ++gbegin) {
345         TypedSliceEdge::Ptr edge = boost::static_pointer_cast<TypedSliceEdge>(*gbegin); 
346         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(edge->source()); 
347         BoundFact *prevFact = GetBoundFactOut(srcNode);     
348         bool newCopy = false;
349         if (prevFact == NULL) {
350             parsing_printf("\t\tIncoming node %lx has not been calculated yet, ignore it\n", srcNode->addr());
351             continue;
352         } else {            
353             // Otherwise, create a new copy.
354             // We do not want to overwrite the bound fact
355             // of the predecessor
356             prevFact = new BoundFact(*prevFact);
357         }
358         parsing_printf("\t\tMeet incoming edge from %lx\n", srcNode->addr());
359         parsing_printf("\t\tThe fact from %lx before applying transfer function\n", srcNode->addr());
360         prevFact->Print();
361         if (!srcNode->assign()) {
362             prevFact = new BoundFact(*prevFact);
363             newCopy = true;
364             parsing_printf("\t\tThe predecessor node is the virtual entry ndoe\n");
365             if (firstBlock) {
366                 // If the indirect jump is in the entry block
367                 // of the function, we assume that rax is in
368                 // range [0,8] for analyzing the movaps table.
369                 // NEED TO HAVE A SAFE WAY TO DO THIS!!
370                 parsing_printf("\t\tApplying entry block rax assumption!\n");
371                 AST::Ptr axAST;
372                 if (func->entry()->obj()->cs()->getAddressWidth() == 8)
373                     axAST = VariableAST::create(Variable(AbsRegion(Absloc(x86_64::rax))));
374                 else
375                     // DOES THIS REALLY SHOW UP IN 32-BIT CODE???
376                     axAST = VariableAST::create(Variable(AbsRegion(Absloc(x86::eax))));
377                 prevFact->GenFact(axAST, new BoundValue(StridedInterval(1,0,8)), false);
378             }
379         } else if (srcNode->assign() && IsConditionalJump(srcNode->assign()->insn())) {
380             prevFact = new BoundFact(*prevFact);
381             newCopy = true;
382             // If the predecessor is a conditional jump,
383             // we can determine bound fact based on the predicate and the edge type
384             parsing_printf("\t\tThe predecessor node is a conditional jump!\n");
385             if (!prevFact->ConditionalJumpBound(srcNode->assign()->insn(), edge->type())) {
386                 fprintf(stderr, "From %lx to %lx\n", srcNode->addr(), node->addr());
387                 assert(0);
388             }
389         } 
390         ThunkBound(prevFact, srcNode, node, newCopy);
391         parsing_printf("\t\tFact from %lx after applying transfer function\n", srcNode->addr());
392         prevFact->Print();
393         if (first) {
394             // For the first incoming dataflow fact,
395             // we just copy it.
396             // We can do this because if an a-loc
397             // is missing in the fact map, we assume
398             // the a-loc is top. 
399             first = false;
400             if (newCopy) newFact = prevFact; else newFact = new BoundFact(*prevFact);
401         } else {
402             newFact->Meet(*prevFact);
403             if (newCopy) delete prevFact;
404         }
405     }
406     return newFact;
407 }
408
409 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode, BoundFact *newFact){
410     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);    
411     if (!node->assign()) return;
412     if (node->assign() && node->assign()->out().absloc().type() == Absloc::Register &&
413             (node->assign()->out().absloc().reg() == x86::zf || node->assign()->out().absloc().reg() == x86_64::zf)) {
414             // zf should be only predecessor of this node
415         parsing_printf("\t\tThe predecessor node is zf assignment!\n");
416         newFact->SetPredicate(node->assign(), ExpandAssignment(node->assign()) );           
417         return;
418     }
419     entryID id = node->assign()->insn()->getOperation().getID();
420     // The predecessor is not a conditional jump,
421     // then we can determine buond fact based on the src assignment
422     parsing_printf("\t\tThe predecessor node is normal node\n");
423     parsing_printf("\t\t\tentry id %d\n", id);
424
425     AbsRegion &ar = node->assign()->out();
426     Instruction::Ptr insn = node->assign()->insn();
427
428     pair<AST::Ptr, bool> expandRet = ExpandAssignment(node->assign());
429         
430     if (expandRet.first == NULL) {
431         // If the instruction is outside the set of instrutions we
432         // add instruction semantics. We assume this instruction
433         // kills all bound fact.
434 //      parsing_printf("\t\t\t No semantic support for this instruction. Kill all bound fact\n");
435 //      newFact->SetToBottom();
436         parsing_printf("\t\t\t No semantic support for this instruction. Assume it does not affect jump target calculation. Ignore it (Treat as identity function)\n"); 
437         return;
438     } else {
439         parsing_printf("\tAST: %s\n", expandRet.first->format().c_str());
440     }
441     
442     AST::Ptr calculation = expandRet.first;     
443     BoundCalcVisitor bcv(*newFact, node->block(), handleOneByteRead);
444     calculation->accept(&bcv);
445     AST::Ptr outAST;
446     // If the instruction writes memory,
447     // we need the AST that represents the memory access and the address.
448     // When the AbsRegion represents memory,
449     // the generator of the AbsRegion is set to be the AST that represents
450     // the memory address during symbolic expansion.
451     // In other cases, if the AbsRegion represents a register,
452     // the generator is not set.
453     if (ar.generator() != NULL) 
454         outAST = SimplifyAnAST(RoseAST::create(ROSEOperation(ROSEOperation::derefOp, ar.size()), ar.generator()), node->assign()->insn()->size());
455     else
456         outAST = VariableAST::create(Variable(ar));
457
458     if (id == e_bsf || id == e_bsr) {
459         int size = node->assign()->insn()->getOperand(0).getValue()->size();
460         newFact->GenFact(outAST, new BoundValue(StridedInterval(1,0, size * 8)), false);
461         parsing_printf("\t\t\tCalculating transfer function: Output facts\n");
462         newFact->Print();
463         return;
464
465     }
466
467     if (id == e_push) {
468          if (calculation->getID() == AST::V_ConstantAST) {
469              ConstantAST::Ptr c = boost::static_pointer_cast<ConstantAST>(calculation);
470              newFact->PushAConst(c->val().val);
471              parsing_printf("\t\t\tCalculating transfer function: Output facts\n");
472              newFact->Print();
473              return;
474          }
475     }
476
477     if (id == e_pop) {
478         if (newFact->PopAConst(outAST)) {
479              parsing_printf("\t\t\tCalculating transfer function: Output facts\n");
480              newFact->Print();
481              return;
482         }            
483     }
484
485     // Assume all SETxx entry ids are contiguous    
486     if (id >= e_setb && id <= e_setz) {
487         newFact->GenFact(outAST, new BoundValue(StridedInterval(1,0,1)), false);
488         parsing_printf("\t\t\tCalculating transfer function: Output facts\n");
489         newFact->Print();
490         return;
491     }
492
493
494     if (bcv.IsResultBounded(calculation)) { 
495         parsing_printf("\t\t\tGenerate bound fact for %s\n", outAST->format().c_str());
496         newFact->GenFact(outAST, new BoundValue(*bcv.GetResultBound(calculation)), false);
497     }
498     else {
499         parsing_printf("\t\t\tKill bound fact for %s\n", outAST->format().c_str());
500         newFact->KillFact(outAST, false);
501     }
502     if (calculation->getID() == AST::V_VariableAST) {
503         // We only track alising between registers
504         parsing_printf("\t\t\t%s and %s are equal\n", calculation->format().c_str(), outAST->format().c_str());
505         newFact->InsertRelation(calculation, outAST, BoundFact::Equal);
506     }
507     newFact->AdjustPredicate(outAST, calculation);
508
509     // Now try to track all aliasing
510     newFact->TrackAlias(DeepCopyAnAST(calculation), ar);
511
512     parsing_printf("\t\t\tCalculating transfer function: Output facts\n");
513     newFact->Print();
514
515 }                                               
516
517 BoundFact* BoundFactsCalculator::GetBoundFactIn(Node::Ptr node) {
518     auto fit = boundFactsIn.find(node);
519     if (fit == boundFactsIn.end())
520         return NULL;
521     else
522         return fit->second;
523 }
524 BoundFact* BoundFactsCalculator::GetBoundFactOut(Node::Ptr node) {
525     auto fit = boundFactsOut.find(node);
526     if (fit == boundFactsOut.end())
527         return NULL;
528     else
529         return fit->second;
530 }
531 BoundFactsCalculator::~BoundFactsCalculator() {
532     for (auto fit = boundFactsIn.begin(); fit != boundFactsIn.end(); ++fit)
533         if (fit->second != NULL)
534             delete fit->second;
535     boundFactsIn.clear();
536     for (auto fit = boundFactsOut.begin(); fit != boundFactsOut.end(); ++fit)
537         if (fit->second != NULL)
538             delete fit->second;
539     boundFactsOut.clear();
540
541 }
542
543 pair<AST::Ptr, bool> BoundFactsCalculator::ExpandAssignment(Assignment::Ptr assign) {
544     parsing_printf("Expand assignment : %s Instruction: %s\n", assign->format().c_str(), assign->insn()->format().c_str());
545     if (expandCache.find(assign) != expandCache.end()) {
546         AST::Ptr ast = expandCache[assign];
547 //      if (ast) return make_pair(DeepCopyAnAST(ast), true); else return make_pair(ast, false);
548         if (ast) return make_pair(ast, true); else return make_pair(ast, false);
549
550     } else {
551         pair<AST::Ptr, bool> expandRet = SymEval::expand(assign, false);
552         if (expandRet.second && expandRet.first) {
553             parsing_printf("Original expand: %s\n", expandRet.first->format().c_str());
554             AST::Ptr calculation = SimplifyAnAST(expandRet.first, assign->insn()->size());
555             //expandCache[assign] = DeepCopyAnAST(expandRet.first);
556             expandCache[assign] = calculation;
557         } else {
558             expandCache[assign] = AST::Ptr();
559         }
560         return make_pair( expandCache[assign], expandRet.second );
561     }
562 }
563