xpcom/analysis/flow.js

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