xpcom/analysis/flow.js

   1 require({ version: '1.8' });
   2 require({ after_gcc_pass: 'cfg' });
   3
   4 include('treehydra.js');
   5
   6 include('util.js');
   7 include('gcc_util.js');
   8 include('gcc_print.js');
   9 include('unstable/adts.js');
  10 include('unstable/analysis.js');
  11 include('unstable/esp.js');
  12
  13 /* This implements the control flows-through analysis in bug 432917 */
  14 var Zero_NonZero = {}
  15 include('unstable/zero_nonzero.js', Zero_NonZero);
  16
  17 MapFactory.use_injective = true;
  18
  19 // Print a trace for each function analyzed
  20 let TRACE_FUNCTIONS = 0;
  21 // Trace operation of the ESP analysis, use 2 or 3 for more detail
  22 let TRACE_ESP = 0;
  23 // Print time-taken stats
  24 let TRACE_PERF = 0;
  25
  26 function process_tree(fndecl) {
  27   // At this point we have a function we want to analyze
  28   if (TRACE_FUNCTIONS) {
  29     print('* function ' + decl_name(fndecl));
  30     print('    ' + loc_string(location_of(fndecl)));
  31   }
  32   if (TRACE_PERF) timer_start(fstring);
  33
  34   let cfg = function_decl_cfg(fndecl);
  35
  36
  37   try {
  38     let trace = TRACE_ESP;
  39     let a = new FlowCheck(cfg, trace);
  40     a.run();
  41   } catch (e if e == "skip") {
  42     return
  43   }
  44   print("checked " + decl_name(fndecl))
  45   if (cfg.x_exit_block_ptr.stateIn.substates)
  46     for each (let substate in cfg.x_exit_block_ptr.stateIn.substates.getValues()) {
  47       for each (let v in substate.getVariables()) {
  48         let var_state= substate.get (v)
  49         let blame = substate.getBlame(v)
  50         if (var_state != ESP.TOP && typeof var_state == 'string')
  51           error(decl_name(fndecl) + ": Control did not flow through " +var_state, location_of(blame))
  52       }
  53     }
  54
  55   if (TRACE_PERF) timer_stop(fstring);
  56 }
  57
  58 let track_return_loc = 0;
  59 const FLOW_THROUGH = "MUST_FLOW_THROUGH"
  60
  61 function FlowCheck(cfg, trace) {
  62   let found = create_decl_set(); // ones we already found
  63   for (let bb in cfg_bb_iterator(cfg)) {
  64     for (let isn in bb_isn_iterator(bb)) {
  65       switch (isn.tree_code()) {
  66       case CALL_EXPR: {
  67         let fn = call_function_decl(isn)
  68         if (!fn || decl_name(fn) != FLOW_THROUGH)
  69           continue;
  70         this.must_flow_fn = fn
  71         break
  72       }
  73       case RETURN_EXPR: {
  74         let ret_expr = isn.operands()[0]
  75         if (track_return_loc && ret_expr)
  76           switch (ret_expr.tree_code()) {
  77           case GIMPLE_MODIFY_STMT:
  78             this.rval = ret_expr.operands()[1].tree_check(VAR_DECL)
  79             break;
  80           case RESULT_DECL:
  81             this.rval = ret_expr
  82             break;
  83           default:
  84             throw new Error("Unhandled return expression")
  85           }
  86       }
  87       }
  88     }
  89   }
  90   if (!this.must_flow_fn)
  91     throw "skip"
  92
  93   let psvar_list = [new ESP.PropVarSpec(this.must_flow_fn, true)]
  94
  95   if (this.rval)
  96     psvar_list.push(new ESP.PropVarSpec(this.rval))
  97
  98   this.zeroNonzero = new Zero_NonZero.Zero_NonZero()
  99   ESP.Analysis.call(this, cfg, psvar_list, Zero_NonZero.meet, trace);
 100 }
 101
 102 FlowCheck.prototype = new ESP.Analysis;
 103
 104 function char_star_arg2string(tree) {
 105   return TREE_STRING_POINTER(tree.tree_check(ADDR_EXPR).operands()[0].tree_check(ARRAY_REF).operands()[0])
 106 }
 107
 108 // State transition function. Mostly, we delegate everything to
 109 // another function as either an assignment or a call.
 110 FlowCheck.prototype.flowState = function(isn, state) {
 111   switch (TREE_CODE(isn)) {
 112   case CALL_EXPR: {
 113     let fn = call_function_decl(isn)
 114     if (fn == this.must_flow_fn)
 115       state.assignValue(fn, char_star_arg2string(call_arg(isn, 0)), isn)
 116     break
 117   }
 118   case LABEL_EXPR: {
 119     let label = decl_name(isn.operands()[0])
 120     for ([value, blame] in state.yieldPreconditions(this.must_flow_fn)) {
 121       if (label != value) continue
 122       // reached the goto label we wanted =D
 123       state.assignValue(this.must_flow_fn, ESP.TOP, isn)
 124     }
 125     break
 126   }
 127   case RETURN_EXPR: {
 128     for ([value, blame] in state.yieldPreconditions(this.must_flow_fn)) {
 129       if (typeof value != 'string') continue
 130       let loc;
 131       if (this.rval)
 132         for ([value, blame] in state.yieldPreconditions(this.rval)) {
 133           loc = value
 134           break
 135         }
 136       error("return without going through label "+ value, loc);
 137       return
 138     }
 139     break
 140   }
 141   case GIMPLE_MODIFY_STMT:
 142     if (track_return_loc && isn.operands()[0] == this.rval) {
 143       state.assignValue(this.rval, location_of(isn), isn)
 144       break
 145     }
 146   default:
 147     this.zeroNonzero.flowState(isn, state)
 148   }
 149 }
 150
 151 // State transition function to apply branch filters. This is kind
 152 // of boilerplate--we're just handling some stuff that GCC generates.
 153 FlowCheck.prototype.flowStateCond = function(isn, truth, state) {
 154   this.zeroNonzero.flowStateCond (isn, truth, state)
 155 }