diff mbox

[RFC] Elimination of zext/sext - type promotion pass

Message ID 556CE742.4090507@linaro.org
State New
Headers show

Commit Message

Kugan Vivekanandarajah June 1, 2015, 11:14 p.m. UTC
On 08/05/15 22:48, Richard Biener wrote:
> You compute which promotions are unsafe, like sources/sinks of memory
> (I think you miss call arguments/return values and also asm operands here).
> But instead of simply marking those SSA names as not to be promoted
> I'd instead split their life-ranges, thus replace
> 
>   _1 = mem;
> 
> with
> 
>   _2 = mem;
>   _1 = [zs]ext (_2, ...);
> 
> and promote _1 anyway.  So in the first phase I'd do that (and obviously
> note that _2 isn't to be promoted in the specific example).
> 
> For promotions that apply I wouldn't bother allocating new SSA names
> but just "fix" their types (assign to their TREE_TYPE).  This also means
> they have to become anonymous and if they didn't have a !DECL_IGNORED_P
> decl before then a debug stmt should be inserted at the point of the
> promotions.  So
> 
>   bar_3 = _1 + _2;
> 
> when promoted would become
> 
>  _4 = _1 + _2;
>  _3 = sext <_4, ...>;
>  # DEBUG bar = (orig-type) _4;  // or _3?
> 
> so you'd basically always promote defs (you have a lot of stmt/operand
> walking code I didn't look too closely at - but it looks like too much) and
> the uses get promoted automagically (because you promote the original
> SSA name). Promotion of constants has to remain, of course.


Thanks Richard. I experimented on this idea to understand it better.
Please see the attached prototype (I am still working on your other
comments which is not addressed here). Please have a look and let me
know if this is along what you would expect. I have few questions though.

1. In the following example above :
  char _1;
  _1 = mem;

when changing with

  char _2;
  int _1;
  _2 = mem;
  _1 = [zs]ext (_2, ...);

for the [zs]ext operation we now use BIT_AND_EXPR and ZEXT_EXPR which
(as of now) requires that the LHS and RHS are of the same type. Are you
suggesting that we should have a true ZEXT_EXPR and SEXT_EXPR which can
do the above in the gimple? I am now using CONVER_EXPR and which is the
source of many optimization issue.

2. for inline asm (a reduced test case that might not make much as a
stand alone test-case, but I ran into similar cases with valid programmes)

;; Function fn1 (fn1, funcdef_no=0, decl_uid=4220, cgraph_uid=0,
symbol_order=0)

fn1 (short int p1)
{
  <bb 2>:
  __asm__("" : "=r" p1_2 : "0" p1_1(D));
  return;

}


I am generating something like the following which ICEs. What is the
expected out?

;; Function fn1 (fn1, funcdef_no=0, decl_uid=4220, cgraph_uid=0,
symbol_order=0)

fn1 (short int p1)
{
  int _1;
  int _2;
  short int _5;

  <bb 2>:
  _1 = (int) p1_4(D);
  _5 = (short int) _1;
  __asm__("" : "=r" p1_6 : "0" _5);
  _2 = (int) p1_6;
  return;

}

Thanks a lot for your time,
Kugan

Comments

Kugan Vivekanandarajah June 19, 2015, 2:37 a.m. UTC | #1
ping?

Thanks,
Kugan

On 02/06/15 09:14, Kugan wrote:
> 
> 
> On 08/05/15 22:48, Richard Biener wrote:
>> You compute which promotions are unsafe, like sources/sinks of memory
>> (I think you miss call arguments/return values and also asm operands here).
>> But instead of simply marking those SSA names as not to be promoted
>> I'd instead split their life-ranges, thus replace
>>
>>   _1 = mem;
>>
>> with
>>
>>   _2 = mem;
>>   _1 = [zs]ext (_2, ...);
>>
>> and promote _1 anyway.  So in the first phase I'd do that (and obviously
>> note that _2 isn't to be promoted in the specific example).
>>
>> For promotions that apply I wouldn't bother allocating new SSA names
>> but just "fix" their types (assign to their TREE_TYPE).  This also means
>> they have to become anonymous and if they didn't have a !DECL_IGNORED_P
>> decl before then a debug stmt should be inserted at the point of the
>> promotions.  So
>>
>>   bar_3 = _1 + _2;
>>
>> when promoted would become
>>
>>  _4 = _1 + _2;
>>  _3 = sext <_4, ...>;
>>  # DEBUG bar = (orig-type) _4;  // or _3?
>>
>> so you'd basically always promote defs (you have a lot of stmt/operand
>> walking code I didn't look too closely at - but it looks like too much) and
>> the uses get promoted automagically (because you promote the original
>> SSA name). Promotion of constants has to remain, of course.
> 
> 
> Thanks Richard. I experimented on this idea to understand it better.
> Please see the attached prototype (I am still working on your other
> comments which is not addressed here). Please have a look and let me
> know if this is along what you would expect. I have few questions though.
> 
> 1. In the following example above :
>   char _1;
>   _1 = mem;
> 
> when changing with
> 
>   char _2;
>   int _1;
>   _2 = mem;
>   _1 = [zs]ext (_2, ...);
> 
> for the [zs]ext operation we now use BIT_AND_EXPR and ZEXT_EXPR which
> (as of now) requires that the LHS and RHS are of the same type. Are you
> suggesting that we should have a true ZEXT_EXPR and SEXT_EXPR which can
> do the above in the gimple? I am now using CONVER_EXPR and which is the
> source of many optimization issue.
> 
> 2. for inline asm (a reduced test case that might not make much as a
> stand alone test-case, but I ran into similar cases with valid programmes)
> 
> ;; Function fn1 (fn1, funcdef_no=0, decl_uid=4220, cgraph_uid=0,
> symbol_order=0)
> 
> fn1 (short int p1)
> {
>   <bb 2>:
>   __asm__("" : "=r" p1_2 : "0" p1_1(D));
>   return;
> 
> }
> 
> 
> I am generating something like the following which ICEs. What is the
> expected out?
> 
> ;; Function fn1 (fn1, funcdef_no=0, decl_uid=4220, cgraph_uid=0,
> symbol_order=0)
> 
> fn1 (short int p1)
> {
>   int _1;
>   int _2;
>   short int _5;
> 
>   <bb 2>:
>   _1 = (int) p1_4(D);
>   _5 = (short int) _1;
>   __asm__("" : "=r" p1_6 : "0" _5);
>   _2 = (int) p1_6;
>   return;
> 
> }
> 
> Thanks a lot for your time,
> Kugan
>
diff mbox

Patch

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index b59b5d9..16b2df1 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1491,6 +1491,7 @@  OBJS = \
 	tree-vect-slp.o \
 	tree-vectorizer.o \
 	tree-vrp.o \
+	gimple-ssa-type-promote.o \
 	tree.o \
 	valtrack.o \
 	value-prof.o \
diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c
index b190f91..bbf70ce 100644
--- a/gcc/cfgexpand.c
+++ b/gcc/cfgexpand.c
@@ -4809,6 +4809,10 @@  expand_debug_expr (tree exp)
     case FMA_EXPR:
       return simplify_gen_ternary (FMA, mode, inner_mode, op0, op1, op2);
 
+    case SEXT_EXPR:
+      return op0;
+
+
     default:
     flag_unsupported:
 #ifdef ENABLE_CHECKING
diff --git a/gcc/common.opt b/gcc/common.opt
index 6e15af2..56231b5 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2368,6 +2368,10 @@  ftree-vrp
 Common Report Var(flag_tree_vrp) Init(0) Optimization
 Perform Value Range Propagation on trees
 
+ftree-type-promote
+Common Report Var(flag_tree_type_promote) Init(1) Optimization
+Perform Type Promotion on trees
+
 funit-at-a-time
 Common Report Var(flag_unit_at_a_time) Init(1)
 Compile whole compilation unit at a time
diff --git a/gcc/expr.c b/gcc/expr.c
index 5a931dc..0badfa5 100644
--- a/gcc/expr.c
+++ b/gcc/expr.c
@@ -9249,6 +9249,21 @@  expand_expr_real_2 (sepops ops, rtx target, machine_mode tmode,
       target = expand_vec_cond_expr (type, treeop0, treeop1, treeop2, target);
       return target;
 
+    case SEXT_EXPR:
+	{
+	  rtx op0 = expand_normal (treeop0);
+	  rtx temp;
+	  if (!target)
+	    target = gen_reg_rtx (TYPE_MODE (TREE_TYPE (treeop0)));
+
+	  machine_mode inner_mode = smallest_mode_for_size (tree_to_shwi (treeop1),
+							    MODE_INT);
+	  temp = convert_modes (inner_mode,
+				TYPE_MODE (TREE_TYPE (treeop0)), op0, 0);
+	  convert_move (target, temp, 0);
+	  return target;
+	}
+
     default:
       gcc_unreachable ();
     }
diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 55196b5..3c42449 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -1007,6 +1007,10 @@  int_const_binop_1 (enum tree_code code, const_tree arg1, const_tree parg2,
       res = wi::bit_and (arg1, arg2);
       break;
 
+    case SEXT_EXPR:
+      res = wi::sext (arg1, arg2.to_uhwi ());
+      break;
+
     case RSHIFT_EXPR:
     case LSHIFT_EXPR:
       if (wi::neg_p (arg2))
diff --git a/gcc/gimple-ssa-type-promote.c b/gcc/gimple-ssa-type-promote.c
index e69de29..6ccda0c 100644
--- a/gcc/gimple-ssa-type-promote.c
+++ b/gcc/gimple-ssa-type-promote.c
@@ -0,0 +1,719 @@ 
+/* Type promotion of SSA names to minimise redundant zero/sign extension.
+   Copyright (C) 2015 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "flags.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "vec.h"
+#include "double-int.h"
+#include "input.h"
+#include "alias.h"
+#include "symtab.h"
+#include "wide-int.h"
+#include "inchash.h"
+#include "tree.h"
+#include "fold-const.h"
+#include "stor-layout.h"
+#include "calls.h"
+#include "predict.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "basic-block.h"
+#include "tree-ssa-alias.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "tree-pass.h"
+#include "gimple-pretty-print.h"
+#include "langhooks.h"
+#include "sbitmap.h"
+#include "domwalk.h"
+
+#include "tree-dfa.h"
+
+/* This pass applies type promotion to SSA names in the function and
+   inserts appropriate truncations.  Idea of this pass is to promote operations
+   such a way that we can minimise generation of subreg in RTL,
+   that intern results in removal of redundant zero/sign extensions.  This pass
+   will run prior to The VRP and DOM such that they will be able to optimise
+   redundant truncations and extensions.  This is based on the discussion from
+   https://gcc.gnu.org/ml/gcc-patches/2014-09/msg00472.html.
+
+*/
+
+static unsigned n_ssa_val;
+static sbitmap ssa_to_be_promoted_bitmap;
+static sbitmap ssa_sets_higher_bits_bitmap;
+
+/* Return the promoted type for TYPE.  */
+static tree
+get_promoted_type (tree type)
+{
+  tree promoted_type;
+  enum machine_mode mode;
+  int uns;
+  if (POINTER_TYPE_P (type)
+      || !INTEGRAL_TYPE_P (type)
+      || TYPE_PRECISION (type) == 1)
+    return type;
+  mode = TYPE_MODE (type);
+#ifdef PROMOTE_MODE
+  uns = TYPE_SIGN (type);
+  PROMOTE_MODE (mode, uns, type);
+#endif
+  uns = TYPE_SIGN (type);
+  promoted_type = lang_hooks.types.type_for_mode (mode, uns);
+  if (promoted_type
+      && (TYPE_PRECISION (promoted_type) > TYPE_PRECISION (type)))
+    type = promoted_type;
+  return type;
+}
+
+/* Return true if ssa NAME is already considered for promotion.  */
+static bool
+ssa_promoted_p (tree name)
+{
+  if (TREE_CODE (name) == SSA_NAME)
+    {
+      unsigned int index = SSA_NAME_VERSION (name);
+      if (index < n_ssa_val)
+	return bitmap_bit_p (ssa_to_be_promoted_bitmap, index);
+    }
+  return true;
+}
+
+
+/* Set ssa NAME to be already considered for promotion.  */
+static void
+set_ssa_promoted (tree name)
+{
+  if (TREE_CODE (name) == SSA_NAME)
+    {
+      unsigned int index = SSA_NAME_VERSION (name);
+      if (index < n_ssa_val)
+	bitmap_set_bit (ssa_to_be_promoted_bitmap, index);
+    }
+}
+
+/* Return single successor (excluding EH edge) for basic block BB.  If there
+   are more than one successors, return NULL.  */
+static basic_block
+get_single_successor_bb (basic_block bb)
+{
+  edge e, res = NULL;
+  edge_iterator ei;
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    if (!(e->flags & EDGE_EH))
+      {
+	if (res)
+	  return NULL;
+	res = e;
+      }
+  return res->dest;
+}
+
+/* Insert COPY_STMT along the edge from STMT to its successor.  */
+static void
+insert_stmt_on_edge (gimple stmt, gimple copy_stmt)
+{
+  edge_iterator ei;
+  edge e, edge = NULL;
+  basic_block bb = gimple_bb (stmt);
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    if (!(e->flags & EDGE_EH))
+      {
+	gcc_assert (edge == NULL);
+	edge = e;
+      }
+
+  gcc_assert (edge);
+  gsi_insert_on_edge_immediate (edge, copy_stmt);
+}
+
+/* Convert constant CST to TYPE.  */
+static tree
+convert_int_cst (tree type, tree cst, signop sign = SIGNED)
+{
+  wide_int wi_cons = fold_convert (type, cst);
+  wi_cons = wi::ext (wi_cons, TYPE_PRECISION (TREE_TYPE (cst)), sign);
+  return wide_int_to_tree (type, wi_cons);
+}
+
+
+/* Promote constants in STMT to TYPE.  If PROMOTE_COND_EXPR is true,
+ promote only the constants in conditions part of the COND_EXPR.  */
+static void
+promote_cst_in_stmt (gimple stmt, tree type,
+		     bool promote_cond_expr = false, signop sign = SIGNED)
+{
+  tree op;
+  ssa_op_iter iter;
+  use_operand_p oprnd;
+  int index;
+  tree op0, op1;
+
+  if (promote_cond_expr)
+    {
+      /* Promote constant in COND_EXPR.  */
+      gcc_assert (gimple_assign_rhs_code (stmt) == COND_EXPR);
+      op = gimple_assign_rhs1 (stmt);
+      op0 = TREE_OPERAND (op, 0);
+      op1 = TREE_OPERAND (op, 1);
+
+      if (TREE_CODE (op0) == INTEGER_CST)
+	op0 = convert_int_cst (type, op0, sign);
+      if (TREE_CODE (op1) == INTEGER_CST)
+	op1 = convert_int_cst (type, op1, sign);
+
+      tree new_op = build2 (TREE_CODE (op), type, op0, op1);
+      gimple_assign_set_rhs1 (stmt, new_op);
+      return;
+    }
+
+  switch (gimple_code (stmt))
+    {
+    case GIMPLE_ASSIGN:
+      op = gimple_assign_rhs1 (stmt);
+
+      if (op && TREE_CODE (op) == INTEGER_CST)
+	gimple_assign_set_rhs1 (stmt, convert_int_cst (type, op, sign));
+      op = gimple_assign_rhs2 (stmt);
+
+      if (op && TREE_CODE (op) == INTEGER_CST)
+	gimple_assign_set_rhs2 (stmt, convert_int_cst (type, op, sign));
+      op = gimple_assign_rhs3 (stmt);
+
+      if (op && TREE_CODE (op) == INTEGER_CST)
+	gimple_assign_set_rhs3 (stmt, convert_int_cst (type, op, sign));
+      break;
+
+    case GIMPLE_PHI:
+	{
+	  gphi *phi = as_a <gphi *> (stmt);
+	  FOR_EACH_PHI_ARG (oprnd, phi, iter, SSA_OP_USE)
+	    {
+	      op = USE_FROM_PTR (oprnd);
+	      index = PHI_ARG_INDEX_FROM_USE (oprnd);
+	      if (TREE_CODE (op) == INTEGER_CST)
+		SET_PHI_ARG_DEF (phi, index, convert_int_cst (type, op, sign));
+	    }
+	}
+      break;
+
+    case GIMPLE_COND:
+	{
+	  gcond *cond = as_a <gcond *> (stmt);
+	  op = gimple_cond_lhs (cond);
+
+	  if (op && TREE_CODE (op) == INTEGER_CST)
+	    gimple_cond_set_lhs (cond, convert_int_cst (type, op, sign));
+	  op = gimple_cond_rhs (cond);
+
+	  if (op && TREE_CODE (op) == INTEGER_CST)
+	    gimple_cond_set_rhs (cond, convert_int_cst (type, op, sign));
+	}
+
+    default:
+      break;
+    }
+}
+
+/* Create an ssa with TYPE to copy ssa VAR.  */
+static tree
+make_promoted_copy (tree var, gimple def_stmt, tree type)
+{
+  tree new_lhs = make_ssa_name (type, def_stmt);
+  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (var))
+    SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_lhs) = 1;
+  return new_lhs;
+}
+
+/* Zero/sign extend (depending on type) VAR and truncate to WIDTH bits.
+   Assign the zero/sign extended value in NEW_VAR.  gimple statement
+   that performs the zero/sign extension is returned.  */
+static gimple
+zero_sign_extend_stmt (tree new_var, tree var, int width)
+{
+  gcc_assert (TYPE_PRECISION (TREE_TYPE (var))
+	      == TYPE_PRECISION (TREE_TYPE (new_var)));
+  gcc_assert (TYPE_PRECISION (TREE_TYPE (var)) > width);
+  gimple stmt;
+
+  if (TYPE_UNSIGNED (TREE_TYPE (new_var)))
+    /* Zero extend.  */
+    stmt = gimple_build_assign (new_var,
+				BIT_AND_EXPR,
+				var, build_int_cst (TREE_TYPE (var),
+						    ((1ULL << width) - 1)));
+  else
+    /* Sign extend.  */
+    stmt = gimple_build_assign (new_var,
+				SEXT_EXPR,
+				var, build_int_cst (TREE_TYPE (var), width));
+  return stmt;
+}
+
+
+void duplicate_default_ssa (tree to, tree from)
+{
+  SET_SSA_NAME_VAR_OR_IDENTIFIER (to, SSA_NAME_VAR (from));
+  SSA_NAME_IS_DEFAULT_DEF (to) = SSA_NAME_IS_DEFAULT_DEF (from);
+  SSA_NAME_DEF_STMT (to) = SSA_NAME_DEF_STMT (from);
+  SET_SSA_NAME_VAR_OR_IDENTIFIER (from, NULL_TREE);
+  SSA_NAME_IS_DEFAULT_DEF (from)= 0;
+  SSA_NAME_IS_DEFAULT_DEF (to) = 1;
+  SSA_NAME_IS_DEFAULT_DEF (from) = 0;
+
+}
+
+
+/* Promote definition DEF to NEW_TYPE.  If the DEF is replaced and has to
+   be released, set RELEASE_DEF.  Also return COPY_OF_DEF with the original
+   type for any use statement that needs truncation.  */
+static void
+promote_definition (tree def,
+		    tree promoted_type)
+{
+  gimple def_stmt = SSA_NAME_DEF_STMT (def);
+  gimple copy_stmt = NULL;
+  basic_block bb;
+  gimple_stmt_iterator gsi;
+  tree original_type = TREE_TYPE (def);
+  gphi *phi;
+  tree new_def;
+  bool do_not_promote = false;
+
+  if (gimple_vuse (def_stmt) != NULL_TREE
+      || gimple_vdef (def_stmt) != NULL_TREE)
+    {
+      do_not_promote = true;
+    }
+  else
+    {
+      switch (gimple_code (def_stmt))
+	{
+	case GIMPLE_PHI:
+	    {
+	      phi = as_a <gphi *> (def_stmt);
+	      TREE_TYPE (def) = promoted_type;
+	      gimple_phi_set_result (phi, def);
+	      SET_PHI_RESULT (phi, def);
+	      SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE);
+	      promote_cst_in_stmt (def_stmt, promoted_type);
+	      break;
+	    }
+
+	case GIMPLE_ASM:
+	    {
+	      gasm *asm_stmt = as_a <gasm *> (def_stmt);
+	      for (unsigned int i = 0; i < gimple_asm_noutputs (asm_stmt); ++i)
+		{
+		  tree link = gimple_asm_output_op (asm_stmt, i);
+		  tree op = TREE_VALUE (link);
+		  if (op == def)
+		    {
+		      new_def = copy_ssa_name (def);
+		      duplicate_default_ssa (new_def, def);
+		      TREE_VALUE (link) = new_def;
+		      gimple_asm_set_output_op (asm_stmt, i, link);
+
+		      TREE_TYPE (def) = promoted_type;
+		      copy_stmt = gimple_build_assign (def, CONVERT_EXPR,
+						       new_def, NULL_TREE);
+		      SSA_NAME_DEF_STMT (def) = copy_stmt;
+		      gsi = gsi_for_stmt (def_stmt);
+		      gsi_insert_after (&gsi, copy_stmt, GSI_NEW_STMT);
+		      break;
+		    }
+		}
+	      break;
+	    }
+
+	case GIMPLE_NOP:
+	    {
+	      if (SSA_NAME_VAR (def) == NULL)
+		{
+		  TREE_TYPE (def) = promoted_type;
+		}
+	      else
+		{
+		  /* Create a promoted type copy of parameters.  */
+		  bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+		  bb = get_single_successor_bb (bb);
+		  gcc_assert (bb);
+		  gsi = gsi_after_labels (bb);
+		  new_def = copy_ssa_name (def);
+		  set_ssa_default_def (cfun, SSA_NAME_VAR (def), new_def);
+		  duplicate_default_ssa (new_def, def);
+		  TREE_TYPE (def) = promoted_type;
+		  copy_stmt = gimple_build_assign (def, CONVERT_EXPR,
+						   new_def, NULL_TREE);
+		  SSA_NAME_DEF_STMT (def) = copy_stmt;
+		  gsi_insert_before (&gsi, copy_stmt, GSI_NEW_STMT);
+		}
+	      break;
+	    }
+
+	case GIMPLE_ASSIGN:
+	    {
+	      enum tree_code code = gimple_assign_rhs_code (def_stmt);
+	      if (code == ARRAY_REF
+		  || code == LROTATE_EXPR
+		  || code == RROTATE_EXPR
+		  || code == VIEW_CONVERT_EXPR
+		  || code == BIT_FIELD_REF
+		  || code == REALPART_EXPR
+		  || code == IMAGPART_EXPR
+		  || code == REDUC_MAX_EXPR
+		  || code == REDUC_PLUS_EXPR
+		  || code == REDUC_MIN_EXPR)
+		{
+		  do_not_promote = true;
+		  break;
+		}
+
+	      if (CONVERT_EXPR_CODE_P (code))
+		{
+		  tree rhs = gimple_assign_rhs1 (def_stmt);
+		  if ((TYPE_PRECISION (TREE_TYPE (rhs)) == TYPE_PRECISION (promoted_type))
+		      && (TYPE_UNSIGNED (TREE_TYPE (rhs)) == TYPE_UNSIGNED (promoted_type)))
+		    {
+		      TREE_TYPE (def) = promoted_type;
+		      gimple copy_stmt =
+			zero_sign_extend_stmt (def, rhs,
+					       TYPE_PRECISION (original_type));
+		      SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE);
+		      gsi = gsi_for_stmt (def_stmt);
+		      gsi_replace (&gsi, copy_stmt, false);
+		    }
+		  else
+		    {
+		      do_not_promote = true;
+		    }
+		}
+	      else
+		{
+		  SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE);
+		  promote_cst_in_stmt (def_stmt, promoted_type);
+		  TREE_TYPE (def) = promoted_type;
+		  new_def = copy_ssa_name (def);
+		  gimple_set_lhs (def_stmt, new_def);
+		  gimple copy_stmt =
+		    zero_sign_extend_stmt (def, new_def,
+					   TYPE_PRECISION (original_type));
+		  gsi = gsi_for_stmt (def_stmt);
+		  gsi_insert_after (&gsi, copy_stmt, GSI_NEW_STMT);
+		}
+	      break;
+	    }
+
+	default:
+	  do_not_promote = true;
+	  break;
+	}
+    }
+
+  if (do_not_promote)
+    {
+      new_def = copy_ssa_name (def);
+      SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE);
+      TREE_TYPE (def) = promoted_type;
+      gimple_set_lhs (def_stmt, new_def);
+      copy_stmt = gimple_build_assign (def, CONVERT_EXPR,
+				       new_def, NULL_TREE);
+      gsi = gsi_for_stmt (def_stmt);
+      if (lookup_stmt_eh_lp (def_stmt) > 0)
+	insert_stmt_on_edge (def_stmt, copy_stmt);
+      else
+	gsi_insert_after (&gsi, copy_stmt, GSI_NEW_STMT);
+    }
+}
+
+
+/* Promote all the USE with NEW_USE.  */
+static unsigned int
+promote_all_uses (tree use, tree promoted_type, tree old_type)
+{
+  gimple stmt;
+  imm_use_iterator ui;
+  gimple_stmt_iterator gsi;
+  use_operand_p op;
+
+  /* Replace all the use with the promoted variable.  */
+  FOR_EACH_IMM_USE_STMT (stmt, ui, use)
+    {
+      bool do_not_promote = false;
+      if (gimple_vuse (stmt) != NULL_TREE
+	  || gimple_vdef (stmt) != NULL_TREE)
+	do_not_promote = true;
+      else
+	{
+	  switch (gimple_code (stmt))
+	    {
+
+	    case GIMPLE_DEBUG:
+		{
+		  gsi = gsi_for_stmt (stmt);
+		  gsi_remove (&gsi, true);
+		}
+	      break;
+	    case GIMPLE_ASM:
+		{
+		  gasm *asm_stmt = as_a <gasm *> (stmt);
+		  for (unsigned int i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
+		    {
+		      tree link = gimple_asm_input_op (asm_stmt, i);
+		      tree op = TREE_VALUE (link);
+		      if (op == use)
+			{
+			  tree temp = make_promoted_copy (use, NULL, old_type);
+			  gsi = gsi_for_stmt (stmt);
+			  gimple copy_stmt = gimple_build_assign (temp, CONVERT_EXPR,
+								  use, NULL_TREE);
+			  gsi_insert_before (&gsi, copy_stmt, GSI_NEW_STMT);
+			  TREE_VALUE (link) = temp;
+			  gimple_asm_set_input_op (asm_stmt, i, link);
+			  break;
+			}
+		    }
+		}
+	      break;
+
+	    case GIMPLE_ASSIGN:
+		{
+		  enum tree_code code = gimple_assign_rhs_code (stmt);
+		  tree lhs = gimple_assign_lhs (stmt);
+		  if (code == VIEW_CONVERT_EXPR
+		      || code == LROTATE_EXPR
+		      || code == RROTATE_EXPR
+		      || code == CONSTRUCTOR
+		      || code == BIT_FIELD_REF
+		      || code == COMPLEX_EXPR
+		      || code == ASM_EXPR
+		      || VECTOR_TYPE_P (TREE_TYPE (lhs)))
+		    {
+		      do_not_promote = true;
+		    }
+
+		  if (TREE_CODE_CLASS (code)
+		      == tcc_comparison)
+		    {
+		      if (TREE_TYPE (use) == promoted_type)
+			promote_cst_in_stmt (stmt, promoted_type);
+		    }
+
+		  if (CONVERT_EXPR_CODE_P (code))
+		    {
+		      tree lhs = gimple_assign_lhs (stmt);
+		      if ((TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (promoted_type))
+			  && (TYPE_UNSIGNED (TREE_TYPE (lhs)) == TYPE_UNSIGNED (promoted_type)))
+			{
+			  gimple copy_stmt =
+			    zero_sign_extend_stmt (lhs, use,
+						   TYPE_PRECISION (old_type));
+			  gsi = gsi_for_stmt (stmt);
+			  gsi_replace (&gsi, copy_stmt, false);
+			}
+		      else if (TYPE_PRECISION (TREE_TYPE (lhs)) < TYPE_PRECISION (old_type))
+			{
+			  /* do nothing */
+			}
+		      else
+			do_not_promote = true;
+		    }
+		}
+	      break;
+
+	    case GIMPLE_COND:
+		{
+		  tree temp = make_promoted_copy (use, NULL, TREE_TYPE (use));
+		  gimple copy_stmt =
+		    zero_sign_extend_stmt (temp, use,
+					   TYPE_PRECISION (old_type));
+		  gsi = gsi_for_stmt (stmt);
+		  gsi_insert_before (&gsi, copy_stmt, GSI_NEW_STMT);
+
+		  FOR_EACH_IMM_USE_ON_STMT (op, ui)
+		    SET_USE (op, temp);
+		  promote_cst_in_stmt (stmt, promoted_type, false,
+				       TYPE_SIGN (TREE_TYPE (use)));
+		  update_stmt (stmt);
+		}
+	      break;
+	    default:
+	      break;
+	    }
+	}
+
+      if (do_not_promote)
+	{
+	  tree temp;
+	  temp = copy_ssa_name (use);
+	  TREE_TYPE (temp) = old_type;
+	  gimple copy_stmt = gimple_build_assign (temp, CONVERT_EXPR,
+						  use, NULL_TREE);
+	  gsi = gsi_for_stmt (stmt);
+	  gsi_insert_before (&gsi, copy_stmt, GSI_NEW_STMT);
+	  FOR_EACH_IMM_USE_ON_STMT (op, ui)
+	    SET_USE (op, temp);
+	  update_stmt (stmt);
+	}
+    }
+
+  return 0;
+}
+
+/* Promote definition of NAME and all its uses.  */
+static unsigned int
+promote_def_and_uses (tree name)
+{
+  tree type;
+  if (TREE_CODE (name) != SSA_NAME
+      || POINTER_TYPE_P (TREE_TYPE (name))
+      || !INTEGRAL_TYPE_P (TREE_TYPE (name))
+      || VECTOR_TYPE_P (TREE_TYPE (name))
+      || ssa_promoted_p (name)
+      || (type = get_promoted_type (TREE_TYPE (name))) == TREE_TYPE (name))
+    return 0;
+  tree old_type = TREE_TYPE (name);
+  promote_definition (name, type);
+  promote_all_uses (name, type, old_type);
+  set_ssa_promoted (name);
+  return 0;
+}
+
+/* Promote all the stmts in the basic block.  */
+static void
+promote_all_stmts (basic_block bb)
+{
+  gimple_stmt_iterator gsi;
+  ssa_op_iter iter;
+  tree def;
+
+  for (gphi_iterator gpi = gsi_start_phis (bb);
+       !gsi_end_p (gpi); gsi_next (&gpi))
+    {
+      gphi *phi = gpi.phi ();
+      use_operand_p op;
+
+      FOR_EACH_PHI_ARG (op, phi, iter, SSA_OP_USE)
+	{
+	  def = USE_FROM_PTR (op);
+	  promote_def_and_uses (def);
+	}
+      def = PHI_RESULT (phi);
+      promote_def_and_uses (def);
+    }
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple stmt = gsi_stmt (gsi);
+
+      FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_USE | SSA_OP_DEF)
+	promote_def_and_uses (def);
+    }
+}
+
+
+class type_promotion_dom_walker : public dom_walker
+{
+public:
+  type_promotion_dom_walker (cdi_direction direction)
+    : dom_walker (direction) {}
+  virtual void before_dom_children (basic_block bb)
+    {
+      promote_all_stmts (bb);
+    }
+};
+
+/* Main entry point to the pass.  */
+static unsigned int
+execute_type_promotion (void)
+{
+  n_ssa_val = num_ssa_names;
+  ssa_to_be_promoted_bitmap = sbitmap_alloc (n_ssa_val);
+  bitmap_clear (ssa_to_be_promoted_bitmap);
+  ssa_sets_higher_bits_bitmap = sbitmap_alloc (n_ssa_val);
+  bitmap_clear (ssa_sets_higher_bits_bitmap);
+
+  calculate_dominance_info (CDI_DOMINATORS);
+  /* Walk the CFG in dominator order.  */
+  type_promotion_dom_walker (CDI_DOMINATORS)
+    .walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+
+  sbitmap_free (ssa_to_be_promoted_bitmap);
+  sbitmap_free (ssa_sets_higher_bits_bitmap);
+    free_dominance_info (CDI_DOMINATORS);
+  return 0;
+}
+
+namespace {
+const pass_data pass_data_type_promotion =
+{
+  GIMPLE_PASS, /* type */
+  "promotion", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_TREE_TYPE_PROMOTE, /* tv_id */
+  PROP_ssa, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  (TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all),
+};
+
+class pass_type_promotion : public gimple_opt_pass
+{
+public:
+  pass_type_promotion (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_type_promotion, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  opt_pass * clone () { return new pass_type_promotion (m_ctxt); }
+  virtual bool gate (function *) { return flag_tree_type_promote != 0; }
+  virtual unsigned int execute (function *)
+    {
+      return execute_type_promotion ();
+    }
+
+}; // class pass_type_promotion
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_type_promote (gcc::context *ctxt)
+{
+  return new pass_type_promotion (ctxt);
+}
+
diff --git a/gcc/passes.def b/gcc/passes.def
index 4690e23..dfa8a5b 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -271,6 +271,7 @@  along with GCC; see the file COPYING3.  If not see
 	  NEXT_PASS (pass_slp_vectorize);
       POP_INSERT_PASSES ()
       NEXT_PASS (pass_lower_vector_ssa);
+      NEXT_PASS (pass_type_promote);
       NEXT_PASS (pass_cse_reciprocals);
       NEXT_PASS (pass_reassoc);
       NEXT_PASS (pass_strength_reduction);
diff --git a/gcc/timevar.def b/gcc/timevar.def
index cf8f37d..57afa8d 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -269,6 +269,7 @@  DEFTIMEVAR (TV_GIMPLE_SLSR           , "straight-line strength reduction")
 DEFTIMEVAR (TV_VTABLE_VERIFICATION   , "vtable verification")
 DEFTIMEVAR (TV_TREE_UBSAN            , "tree ubsan")
 DEFTIMEVAR (TV_INITIALIZE_RTL        , "initialize rtl")
+DEFTIMEVAR (TV_TREE_TYPE_PROMOTE     , "tree type promote")
 
 /* Everything else in rest_of_compilation not included above.  */
 DEFTIMEVAR (TV_EARLY_LOCAL	     , "early local passes")
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 99b27c7..3332626 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -3805,6 +3805,18 @@  verify_gimple_assign_binary (gassign *stmt)
         return false;
       }
 
+    case SEXT_EXPR:
+      {
+	if (!INTEGRAL_TYPE_P (lhs_type)
+	    || !INTEGRAL_TYPE_P (rhs1_type)
+	    || TREE_CODE (rhs2) != INTEGER_CST)
+	  {
+	    error ("invalid operands in sext expr");
+	    return true;
+	  }
+	return false;
+      }
+
     case VEC_WIDEN_LSHIFT_HI_EXPR:
     case VEC_WIDEN_LSHIFT_LO_EXPR:
       {
@@ -5235,6 +5247,7 @@  gimple_verify_flow_info (void)
 
 	  if (found_ctrl_stmt)
 	    {
+	      dump_bb (stderr, gimple_bb (stmt), 0, 0);
 	      error ("control flow in the middle of basic block %d",
 		     bb->index);
 	      err = 1;
diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c
index 71d75d9..e19ac3d 100644
--- a/gcc/tree-inline.c
+++ b/gcc/tree-inline.c
@@ -3912,6 +3912,7 @@  estimate_operator_cost (enum tree_code code, eni_weights *weights,
     case BIT_XOR_EXPR:
     case BIT_AND_EXPR:
     case BIT_NOT_EXPR:
+    case SEXT_EXPR:
 
     case TRUTH_ANDIF_EXPR:
     case TRUTH_ORIF_EXPR:
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 172bd82..533e4a6 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -428,6 +428,7 @@  extern gimple_opt_pass *make_pass_fre (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_type_promote (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_return_slot (gcc::context *ctxt);
diff --git a/gcc/tree-pretty-print.c b/gcc/tree-pretty-print.c
index cf875c8..02bc101 100644
--- a/gcc/tree-pretty-print.c
+++ b/gcc/tree-pretty-print.c
@@ -1812,6 +1812,14 @@  dump_generic_node (pretty_printer *pp, tree node, int spc, int flags,
       }
       break;
 
+    case SEXT_EXPR:
+      pp_string (pp, "SEXT_EXPR <");
+      dump_generic_node (pp, TREE_OPERAND (node, 0), spc, flags, false);
+      pp_string (pp, ", ");
+      dump_generic_node (pp, TREE_OPERAND (node, 1), spc, flags, false);
+      pp_greater (pp);
+      break;
+
     case MODIFY_EXPR:
     case INIT_EXPR:
       dump_generic_node (pp, TREE_OPERAND (node, 0), spc, flags,
@@ -3432,6 +3440,9 @@  op_symbol_code (enum tree_code code)
     case MIN_EXPR:
       return "min";
 
+    case SEXT_EXPR:
+      return "sext from bit";
+
     default:
       return "<<< ??? >>>";
     }
diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c
index 9c39f65..05eef17 100644
--- a/gcc/tree-ssanames.c
+++ b/gcc/tree-ssanames.c
@@ -209,7 +209,8 @@  set_range_info (tree name, enum value_range_type range_type,
   unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
 
   /* Allocate if not available.  */
-  if (ri == NULL)
+  if (ri == NULL
+      || (precision != ri->get_min().get_precision()))
     {
       size_t size = (sizeof (range_info_def)
 		     + trailing_wide_ints <3>::extra_size (precision));
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 22587d0..9ceae8d 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -2413,6 +2413,7 @@  extract_range_from_binary_expr_1 (value_range_t *vr,
       && code != LSHIFT_EXPR
       && code != MIN_EXPR
       && code != MAX_EXPR
+      && code != SEXT_EXPR
       && code != BIT_AND_EXPR
       && code != BIT_IOR_EXPR
       && code != BIT_XOR_EXPR)
@@ -2989,6 +2990,49 @@  extract_range_from_binary_expr_1 (value_range_t *vr,
       extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
       return;
     }
+  else if (code == SEXT_EXPR)
+    {
+      gcc_assert (range_int_cst_p (&vr1));
+      unsigned int prec = tree_to_uhwi (vr1.min);
+      type = vr0.type;
+      wide_int tmin, tmax;
+      wide_int type_min, type_max;
+      wide_int may_be_nonzero, must_be_nonzero;
+
+      gcc_assert (!TYPE_UNSIGNED (expr_type));
+      type_min = wi::shwi (1 << (prec - 1),
+			   TYPE_PRECISION (TREE_TYPE (vr0.min)));
+      type_max = wi::shwi (((1 << (prec - 1)) - 1),
+			   TYPE_PRECISION (TREE_TYPE (vr0.max)));
+      if (zero_nonzero_bits_from_vr (expr_type, &vr0,
+				     &may_be_nonzero,
+				     &must_be_nonzero))
+	{
+	  HOST_WIDE_INT _may_be_nonzero = may_be_nonzero.to_uhwi ();
+
+	  if (_may_be_nonzero & (1 << (prec - 1)))
+	    {
+	      /* If to-be-extended sign bit can be one.  */
+	      tmin = type_min;
+	      tmax = may_be_nonzero & type_max;
+	    }
+	  else
+	    {
+	      /* If to-be-extended sign bit is zero.  */
+	      tmin = must_be_nonzero;
+	      tmax = may_be_nonzero;
+	    }
+	}
+      else
+	{
+	  tmin = type_min;
+	  tmax = type_max;
+	}
+      tmin = wi::sext (tmin, prec);
+      tmax = wi::sext (tmax, prec);
+      min = wide_int_to_tree (expr_type, tmin);
+      max = wide_int_to_tree (expr_type, tmax);
+    }
   else if (code == RSHIFT_EXPR
 	   || code == LSHIFT_EXPR)
     {
diff --git a/gcc/tree.def b/gcc/tree.def
index 56580af..57a1981 100644
--- a/gcc/tree.def
+++ b/gcc/tree.def
@@ -752,6 +752,9 @@  DEFTREECODE (BIT_XOR_EXPR, "bit_xor_expr", tcc_binary, 2)
 DEFTREECODE (BIT_AND_EXPR, "bit_and_expr", tcc_binary, 2)
 DEFTREECODE (BIT_NOT_EXPR, "bit_not_expr", tcc_unary, 1)
 
+/*  Sign-extend operation.  */
+DEFTREECODE (SEXT_EXPR, "sext_expr", tcc_binary, 2)
+
 /* ANDIF and ORIF allow the second operand not to be computed if the
    value of the expression is determined from the first operand.  AND,
    OR, and XOR always compute the second operand whether its value is