gcc/gimple-harden-conditionals.cc

   1 /* Harden conditionals.
   2    Copyright (C) 2021 Free Software Foundation, Inc.
   3    Contributed by Alexandre Oliva <oliva@adacore.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "backend.h"
  25 #include "tree.h"
  26 #include "fold-const.h"
  27 #include "gimple.h"
  28 #include "gimplify.h"
  29 #include "tree-pass.h"
  30 #include "ssa.h"
  31 #include "gimple-iterator.h"
  32 #include "tree-cfg.h"
  33 #include "basic-block.h"
  34 #include "cfghooks.h"
  35 #include "cfgloop.h"
  36 #include "diagnostic.h"
  37 #include "intl.h"
  38
  39 namespace {
  40
  41 /* These passes introduces redundant, but reversed conditionals at
  42    compares, such as those used in conditional branches, and those
  43    that compute boolean results.  This doesn't make much sense for
  44    abstract CPUs, but this kind of hardening may avoid undesirable
  45    execution paths on actual CPUs under such attacks as of power
  46    deprivation.  */
  47
  48 /* Define a pass to harden conditionals other than branches.  */
  49
  50 const pass_data pass_data_harden_compares = {
  51   GIMPLE_PASS,
  52   "hardcmp",
  53   OPTGROUP_NONE,
  54   TV_NONE,
  55   PROP_cfg | PROP_ssa, // properties_required
  56   0,        // properties_provided
  57   0,        // properties_destroyed
  58   0,        // properties_start
  59   TODO_update_ssa
  60   | TODO_cleanup_cfg
  61   | TODO_verify_il, // properties_finish
  62 };
  63
  64 class pass_harden_compares : public gimple_opt_pass
  65 {
  66 public:
  67   pass_harden_compares (gcc::context *ctxt)
  68     : gimple_opt_pass (pass_data_harden_compares, ctxt)
  69   {}
  70   opt_pass *clone () { return new pass_harden_compares (m_ctxt); }
  71   virtual bool gate (function *) {
  72     return flag_harden_compares;
  73   }
  74   virtual unsigned int execute (function *);
  75 };
  76
  77 /* Define a pass to harden conditionals in branches.  This pass must
  78    run after the above, otherwise it will re-harden the checks
  79    introduced by the above.  */
  80
  81 const pass_data pass_data_harden_conditional_branches = {
  82   GIMPLE_PASS,
  83   "hardcbr",
  84   OPTGROUP_NONE,
  85   TV_NONE,
  86   PROP_cfg | PROP_ssa, // properties_required
  87   0,        // properties_provided
  88   0,        // properties_destroyed
  89   0,        // properties_start
  90   TODO_update_ssa
  91   | TODO_cleanup_cfg
  92   | TODO_verify_il, // properties_finish
  93 };
  94
  95 class pass_harden_conditional_branches : public gimple_opt_pass
  96 {
  97 public:
  98   pass_harden_conditional_branches (gcc::context *ctxt)
  99     : gimple_opt_pass (pass_data_harden_conditional_branches, ctxt)
 100   {}
 101   opt_pass *clone () { return new pass_harden_conditional_branches (m_ctxt); }
 102   virtual bool gate (function *) {
 103     return flag_harden_conditional_branches;
 104   }
 105   virtual unsigned int execute (function *);
 106 };
 107
 108 }
 109
 110 /* If VAL is an SSA name, return an SSA name holding the same value,
 111    but without the compiler's knowing that it holds the same value, so
 112    that uses thereof can't be optimized the way VAL might.  Insert
 113    stmts that initialize it before *GSIP, with LOC.
 114
 115    Otherwise, VAL must be an invariant, returned unchanged.  */
 116
 117 static inline tree
 118 detach_value (location_t loc, gimple_stmt_iterator *gsip, tree val)
 119 {
 120   if (TREE_CONSTANT (val) || TREE_CODE (val) != SSA_NAME)
 121     {
 122       gcc_checking_assert (is_gimple_min_invariant (val));
 123       return val;
 124     }
 125
 126   tree ret = copy_ssa_name (val);
 127
 128   /* Output asm ("" : "=g" (ret) : "0" (val));  */
 129   vec<tree, va_gc> *inputs = NULL;
 130   vec<tree, va_gc> *outputs = NULL;
 131   vec_safe_push (outputs,
 132                  build_tree_list
 133                  (build_tree_list
 134                   (NULL_TREE, build_string (2, "=g")),
 135                   ret));
 136   vec_safe_push (inputs,
 137                  build_tree_list
 138                  (build_tree_list
 139                   (NULL_TREE, build_string (1, "0")),
 140                   val));
 141   gasm *detach = gimple_build_asm_vec ("", inputs, outputs,
 142                                        NULL, NULL);
 143   gimple_set_location (detach, loc);
 144   gsi_insert_before (gsip, detach, GSI_SAME_STMT);
 145
 146   SSA_NAME_DEF_STMT (ret) = detach;
 147
 148   return ret;
 149 }
 150
 151 /* Build a cond stmt out of COP, LHS, RHS, insert it before *GSIP with
 152    location LOC.  *GSIP must be at the end of a basic block.  The succ
 153    edge out of the block becomes the true or false edge opposite to
 154    that in FLAGS.  Create a new block with a single trap stmt, in the
 155    cold partition if the function is partitioned,, and a new edge to
 156    it as the other edge for the cond.  */
 157
 158 static inline void
 159 insert_check_and_trap (location_t loc, gimple_stmt_iterator *gsip,
 160                        int flags, enum tree_code cop, tree lhs, tree rhs)
 161 {
 162   basic_block chk = gsi_bb (*gsip);
 163
 164   gcond *cond = gimple_build_cond (cop, lhs, rhs, NULL, NULL);
 165   gimple_set_location (cond, loc);
 166   gsi_insert_before (gsip, cond, GSI_SAME_STMT);
 167
 168   basic_block trp = create_empty_bb (chk);
 169
 170   gimple_stmt_iterator gsit = gsi_after_labels (trp);
 171   gcall *trap = gimple_build_call (builtin_decl_explicit (BUILT_IN_TRAP), 0);
 172   gimple_set_location (trap, loc);
 173   gsi_insert_before (&gsit, trap, GSI_SAME_STMT);
 174
 175   if (dump_file)
 176     fprintf (dump_file,
 177              "Adding reversed compare to block %i, and trap to block %i\n",
 178              chk->index, trp->index);
 179
 180   if (BB_PARTITION (chk))
 181     BB_SET_PARTITION (trp, BB_COLD_PARTITION);
 182
 183   int true_false_flag = flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 184   gcc_assert (true_false_flag);
 185   int neg_true_false_flag = (~flags) & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 186
 187   /* Remove the fallthru bit, and set the truth value for the
 188      preexisting edge and for the newly-created one.  In hardcbr,
 189      FLAGS is taken from the edge of the original cond expr that we're
 190      dealing with, so the reversed compare is expected to yield the
 191      negated result, and the same result calls for a trap.  In
 192      hardcmp, we're comparing the boolean results of the original and
 193      of the reversed compare, so we're passed FLAGS to trap on
 194      equality.  */
 195   single_succ_edge (chk)->flags &= ~EDGE_FALLTHRU;
 196   single_succ_edge (chk)->flags |= neg_true_false_flag;
 197   edge e = make_edge (chk, trp, true_false_flag);
 198   e->goto_locus = loc;
 199
 200   if (dom_info_available_p (CDI_DOMINATORS))
 201     set_immediate_dominator (CDI_DOMINATORS, trp, chk);
 202   if (current_loops)
 203     add_bb_to_loop (trp, current_loops->tree_root);
 204 }
 205
 206 /* Split edge E, and insert_check_and_trap (see above) in the
 207    newly-created block, using detached copies of LHS's and RHS's
 208    values (see detach_value above) for the COP compare.  */
 209
 210 static inline void
 211 insert_edge_check_and_trap (location_t loc, edge e,
 212                             enum tree_code cop, tree lhs, tree rhs)
 213 {
 214   int flags = e->flags;
 215   basic_block src = e->src;
 216   basic_block dest = e->dest;
 217   location_t eloc = e->goto_locus;
 218
 219   basic_block chk = split_edge (e);
 220   e = NULL;
 221
 222   single_pred_edge (chk)->goto_locus = loc;
 223   single_succ_edge (chk)->goto_locus = eloc;
 224
 225   if (dump_file)
 226     fprintf (dump_file,
 227              "Splitting edge %i->%i into block %i\n",
 228              src->index, dest->index, chk->index);
 229
 230   gimple_stmt_iterator gsik = gsi_after_labels (chk);
 231
 232   bool same_p = (lhs == rhs);
 233   lhs = detach_value (loc, &gsik, lhs);
 234   rhs = same_p ? lhs : detach_value (loc, &gsik, rhs);
 235
 236   insert_check_and_trap (loc, &gsik, flags, cop, lhs, rhs);
 237 }
 238
 239 /* Harden cond stmts at the end of FUN's blocks.  */
 240
 241 unsigned int
 242 pass_harden_conditional_branches::execute (function *fun)
 243 {
 244   basic_block bb;
 245   FOR_EACH_BB_REVERSE_FN (bb, fun)
 246     {
 247       gimple_stmt_iterator gsi = gsi_last_bb (bb);
 248
 249       if (gsi_end_p (gsi))
 250         continue;
 251
 252       gcond *cond = dyn_cast <gcond *> (gsi_stmt (gsi));
 253       if (!cond)
 254         continue;
 255
 256       /* Turn:
 257
 258          if (x op y) goto l1; else goto l2;
 259
 260          into:
 261
 262          if (x op y) goto l1'; else goto l2';
 263          l1': if (x' cop y') goto l1'trap; else goto l1;
 264          l1'trap: __builtin_trap ();
 265          l2': if (x' cop y') goto l2; else goto l2'trap;
 266          l2'trap: __builtin_trap ();
 267
 268          where cop is a complementary boolean operation to op; l1', l1'trap,
 269          l2' and l2'trap are newly-created labels; and x' and y' hold the same
 270          value as x and y, but in a way that does not enable the compiler to
 271          optimize the redundant compare away.
 272       */
 273
 274       enum tree_code op = gimple_cond_code (cond);
 275       tree lhs = gimple_cond_lhs (cond);
 276       tree rhs = gimple_cond_rhs (cond);
 277       location_t loc = gimple_location (cond);
 278
 279       enum tree_code cop = invert_tree_comparison (op, HONOR_NANS (lhs));
 280
 281       if (cop == ERROR_MARK)
 282         /* ??? Can we do better?  */
 283         continue;
 284
 285       insert_edge_check_and_trap (loc, EDGE_SUCC (bb, 0), cop, lhs, rhs);
 286       insert_edge_check_and_trap (loc, EDGE_SUCC (bb, 1), cop, lhs, rhs);
 287     }
 288
 289   return 0;
 290 }
 291
 292 /* Instantiate a hardcbr pass.  */
 293
 294 gimple_opt_pass *
 295 make_pass_harden_conditional_branches (gcc::context *ctxt)
 296 {
 297   return new pass_harden_conditional_branches (ctxt);
 298 }
 299
 300 /* Harden boolean-yielding compares in FUN.  */
 301
 302 unsigned int
 303 pass_harden_compares::execute (function *fun)
 304 {
 305   basic_block bb;
 306   /* Go backwards over BBs and stmts, so that, even if we split the
 307      block multiple times to insert a cond_expr after each compare we
 308      find, we remain in the same block, visiting every preexisting
 309      stmt exactly once, and not visiting newly-added blocks or
 310      stmts.  */
 311   FOR_EACH_BB_REVERSE_FN (bb, fun)
 312     for (gimple_stmt_iterator gsi = gsi_last_bb (bb);
 313          !gsi_end_p (gsi); gsi_prev (&gsi))
 314       {
 315         gassign *asgn = dyn_cast <gassign *> (gsi_stmt (gsi));
 316         if (!asgn)
 317           continue;
 318
 319         /* Turn:
 320
 321            z = x op y;
 322
 323            into:
 324
 325            z = x op y;
 326            z' = x' cop y';
 327            if (z == z') __builtin_trap ();
 328
 329            where cop is a complementary boolean operation to op; and x'
 330            and y' hold the same value as x and y, but in a way that does
 331            not enable the compiler to optimize the redundant compare
 332            away.
 333         */
 334
 335         enum tree_code op = gimple_assign_rhs_code (asgn);
 336
 337         enum tree_code cop;
 338
 339         switch (op)
 340           {
 341           case EQ_EXPR:
 342           case NE_EXPR:
 343           case GT_EXPR:
 344           case GE_EXPR:
 345           case LT_EXPR:
 346           case LE_EXPR:
 347           case LTGT_EXPR:
 348           case UNEQ_EXPR:
 349           case UNGT_EXPR:
 350           case UNGE_EXPR:
 351           case UNLT_EXPR:
 352           case UNLE_EXPR:
 353           case ORDERED_EXPR:
 354           case UNORDERED_EXPR:
 355             cop = invert_tree_comparison (op,
 356                                           HONOR_NANS
 357                                           (gimple_assign_rhs1 (asgn)));
 358
 359             if (cop == ERROR_MARK)
 360               /* ??? Can we do better?  */
 361               continue;
 362
 363             break;
 364
 365             /* ??? Maybe handle these too?  */
 366           case TRUTH_NOT_EXPR:
 367             /* ??? The code below assumes binary ops, it would have to
 368                be adjusted for TRUTH_NOT_EXPR, since it's unary.  */
 369           case TRUTH_ANDIF_EXPR:
 370           case TRUTH_ORIF_EXPR:
 371           case TRUTH_AND_EXPR:
 372           case TRUTH_OR_EXPR:
 373           case TRUTH_XOR_EXPR:
 374           default:
 375             continue;
 376           }
 377
 378         /* These are the operands for the verification.  */
 379         tree lhs = gimple_assign_lhs (asgn);
 380         tree op1 = gimple_assign_rhs1 (asgn);
 381         tree op2 = gimple_assign_rhs2 (asgn);
 382         location_t loc = gimple_location (asgn);
 383
 384         /* Vector booleans can't be used in conditional branches.  ???
 385            Can we do better?  How to reduce compare and
 386            reversed-compare result vectors to a single boolean?  */
 387         if (VECTOR_TYPE_P (TREE_TYPE (op1)))
 388           continue;
 389
 390         gcc_checking_assert (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE);
 391
 392         tree rhs = copy_ssa_name (lhs);
 393
 394         gimple_stmt_iterator gsi_split = gsi;
 395         /* Don't separate the original assignment from debug stmts
 396            that might be associated with it, and arrange to split the
 397            block after debug stmts, so as to make sure the split block
 398            won't be debug stmts only.  */
 399         gsi_next_nondebug (&gsi_split);
 400
 401         bool same_p = (op1 == op2);
 402         op1 = detach_value (loc, &gsi_split, op1);
 403         op2 = same_p ? op1 : detach_value (loc, &gsi_split, op2);
 404
 405         gassign *asgnck = gimple_build_assign (rhs, cop, op1, op2);
 406         gimple_set_location (asgnck, loc);
 407         gsi_insert_before (&gsi_split, asgnck, GSI_SAME_STMT);
 408
 409         /* We wish to insert a cond_expr after the compare, so arrange
 410            for it to be at the end of a block if it isn't.  */
 411         if (!gsi_end_p (gsi_split))
 412           {
 413             gsi_prev (&gsi_split);
 414             split_block (bb, gsi_stmt (gsi_split));
 415             gsi_next (&gsi_split);
 416             gcc_checking_assert (gsi_end_p (gsi_split));
 417
 418             single_succ_edge (bb)->goto_locus = loc;
 419
 420             if (dump_file)
 421               fprintf (dump_file, "Splitting block %i\n", bb->index);
 422           }
 423
 424         gcc_checking_assert (single_succ_p (bb));
 425
 426         insert_check_and_trap (loc, &gsi_split, EDGE_TRUE_VALUE,
 427                                EQ_EXPR, lhs, rhs);
 428       }
 429
 430   return 0;
 431 }
 432
 433 /* Instantiate a hardcmp pass.  */
 434
 435 gimple_opt_pass *
 436 make_pass_harden_compares (gcc::context *ctxt)
 437 {
 438   return new pass_harden_compares (ctxt);
 439 }