parseAPI/src/BoundFactCalculator.C

   1 #include "IndirectControlFlow.h"
   2 #include "IndirectASTVisitor.h"
   3 #include "debug_parse.h"
   4
   5 bool BoundFactsCalculator::CalculateBoundedFacts() {
   6     /* We use a dataflow analysis to calculate what registers are bounded
   7      * at each node. The key points of the dataflow analysis are how
   8      * to calculate the meet and how to calculate the transfer function.
   9      * 1. The meet should be simply an intersection of all the bounded facts
  10      * along all paths.
  11      * 2. To calculate the transfer function, we first get the symbolic expression
  12      * of the instrution for the node. Then depending on the instruction operation
  13      * and the meet result, we know what are still bounded. For example, loading
  14      * memory is always unbounded; doing and operation on a register with a constant
  15      * makes the register bounded.
  16      */
  17
  18
  19     defined.clear();
  20     queue<Node::Ptr> workingList;
  21
  22     NodeIterator nbegin, nend;
  23     slice->allNodes(nbegin, nend);
  24
  25     for (; nbegin != nend; ++nbegin) {
  26         workingList.push(*nbegin);
  27     }
  28
  29
  30     while (!workingList.empty()) {
  31         Node::Ptr curNode = workingList.front();
  32         workingList.pop();
  33
  34         BoundFact oldFact = boundFacts[curNode.get()];
  35         Meet(curNode);
  36         CalcTransferFunction(curNode);
  37
  38         if (defined.find(curNode) == defined.end() || oldFact != boundFacts[curNode.get()]) {
  39             curNode->outs(nbegin, nend);
  40             for (; nbegin != nend; ++nbegin)
  41                 workingList.push(*nbegin);
  42         }
  43         defined.insert(curNode);
  44     }
  45
  46     return true;
  47 }
  48
  49
  50 void BoundFactsCalculator::ConditionalJumpBound(BoundFact& curFact, Node::Ptr src, Node::Ptr trg) {
  51
  52     /* This function checks whether any potential table guard is between the two nodes
  53      * that we are calculating the meet. Essentially, if there is a conditional jump
  54      * between the two nodes, we know extra bound information.
  55      */
  56
  57     ParseAPI::Block *srcBlock;
  58     if (src == Node::Ptr())
  59         srcBlock = func->entry();
  60     else {
  61         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(src);
  62         srcBlock = srcNode->block();
  63
  64     }
  65     SliceNode::Ptr trgNode = boost::static_pointer_cast<SliceNode>(trg);
  66     ParseAPI::Block *trgBlock = trgNode->block();
  67
  68     for (auto git = guards.begin(); git != guards.end(); ++git) {
  69         if (!git->constantBound) continue;
  70
  71         ParseAPI::Block *guardBlock = git->block;
  72         // Note that the guardBlock and the srcBlock can be the same,
  73         // but since the conditional jump will always be the last instruction
  74         // in the block, if they are in the same block, the src can reach the guard
  75         if (rf.incoming[guardBlock].find(srcBlock) == rf.incoming[guardBlock].end()) continue;
  76         bool pred_taken = rf.branch_taken[guardBlock].find(trgBlock) != rf.branch_taken[guardBlock].end();
  77         bool pred_ft = rf.branch_ft[guardBlock].find(trgBlock) != rf.branch_ft[guardBlock].end();
  78         parsing_printf("pred_taken : %d, pred_ft: %d\n", pred_taken, pred_ft);
  79         // If both branches reach the trg node, then this conditional jump
  80         // does not bound any variable for the trg node.
  81         if (pred_taken ^ pred_ft) {
  82             // Here I need to figure out which branch bounds the variable and
  83             // check it is the bounded path that reaches the trg node.
  84             AST::Ptr cmpAST;
  85             bool boundedOnTakenBranch = git->varSubtrahend ^ git->jumpWhenNoZF;
  86             if (   (boundedOnTakenBranch && pred_taken)
  87                 // In thic case, we jump when the variable is smaller than the constant.
  88                 // So the condition taken path is the path that bounds the value.
  89                 || (!boundedOnTakenBranch && pred_ft) ) {
  90                 // In thic case, we jump when the variable is larger than the constant.
  91                 // So the fallthrough path is the path that bounds the value.
  92
  93                 if (curFact.cmpBoundFactLive == false || git->cmpBound > curFact.cmpBound) {
  94                     curFact.cmpAST = git->cmpAST;
  95                     curFact.cmpBound = git->cmpBound;
  96                     curFact.cmpBoundFactLive = true;
  97                     curFact.cmpUsedRegs = git->usedRegs;
  98                 }
  99             }
 100         }
 101     }
 102     if (!curFact.cmpBoundFactLive && firstBlock) {
 103         // If this is indirect jump is in the first block,
 104         // it is possible that it is a jump table for a function
 105         // with variable number of arguments. Then the convention
 106         // is that al contains the number of argument.
 107         curFact.cmpAST = VariableAST::create(Variable(Absloc(x86_64::rax)));
 108         curFact.cmpBound = 8;
 109         curFact.cmpUsedRegs.insert(x86_64::rax);
 110         curFact.cmpBoundFactLive = true;
 111
 112
 113     }
 114 }
 115
 116 void BoundFactsCalculator::Meet(Node::Ptr curNode) {
 117
 118     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);
 119     parsing_printf("Calculate Meet for %lx\n", node->addr());
 120
 121     NodeIterator gbegin, gend;
 122     curNode->ins(gbegin, gend);
 123     BoundFact &curFact = boundFacts[curNode.get()];
 124
 125     if (gbegin != gend) {
 126         bool first = true;
 127         for (; gbegin != gend; ++gbegin) {
 128             SliceNode::Ptr meetSliceNode = boost::static_pointer_cast<SliceNode>(*gbegin);
 129             if (defined.find(*gbegin) == defined.end()) {
 130                 parsing_printf("\tIncoming node %lx has not been calculated yet\n", meetSliceNode->addr());
 131                 continue;
 132             }
 133             parsing_printf("\tMeet incoming edge from %lx\n", meetSliceNode->addr());
 134             BoundFact prevFact = boundFacts[(*gbegin).get()];
 135             ConditionalJumpBound(prevFact, *gbegin, curNode);
 136             if (first) {
 137                 first = false;
 138                 curFact = prevFact;
 139             } else
 140                 curFact.Intersect(prevFact);
 141         }
 142     } else {
 143         ConditionalJumpBound(curFact, Node::Ptr(), curNode);
 144         parsing_printf("Meet no incoming nodes\n");
 145         curFact.Print();
 146     }
 147 }
 148
 149 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode){
 150
 151     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);
 152     AbsRegion &ar = node->assign()->out();
 153
 154     BoundFact &curFact = boundFacts[curNode.get()];
 155     parsing_printf("Expanding assignment %s in instruction at %lx: %s.\n", node->assign()->format().c_str(), node->addr(), node->assign()->insn()->format().c_str());
 156     pair<AST::Ptr, bool> expandRet = SymEval::expand(node->assign(), false);
 157
 158     if (expandRet.first == NULL) {
 159         // If the instruction is outside the set of instrutions we
 160         // add instruction semantics. We assume this instruction
 161         // kills all bound fact.
 162         parsing_printf("\t No semantic support for this instruction. Kill all bound fact\n");
 163         return;
 164     }
 165     parsing_printf("\t AST after expanding (without simplify) %s\n", expandRet.first->format().c_str());
 166
 167     AST::Ptr calculation = SimplifyAnAST(expandRet.first, node->assign()->insn()->size());
 168
 169     parsing_printf("\t AST after expanding %s\n", calculation->format().c_str());
 170     parsing_printf("Calculating transfer function: Input facts\n");
 171     curFact.Print();
 172
 173     BoundCalcVisitor bcv(curFact);
 174     calculation->accept(&bcv);
 175
 176     if (bcv.IsResultBounded(calculation)) {
 177         parsing_printf("Genenerate bound fact for %s\n", ar.absloc().format().c_str());
 178         curFact.GenFact(ar.absloc(), bcv.GetResultBound(calculation));
 179     }
 180     else {
 181         parsing_printf("Kill bound fact for %s\n", ar.absloc().format().c_str());
 182         curFact.KillFact(ar.absloc());
 183     }
 184     parsing_printf("Calculating transfer function: Output facts\n");
 185     curFact.Print();
 186 }
 187
 188