diff mbox

[0/7] Type promotion pass and elimination of zext/sext

Message ID 5653B1D7.6090607@linaro.org
State New
Headers show

Commit Message

Kugan Vivekanandarajah Nov. 24, 2015, 12:39 a.m. UTC
Hi Richard,

Thanks for you comments. I am attaching  an updated patch with details
below.

On 19/11/15 02:06, Richard Biener wrote:
> On Wed, Nov 18, 2015 at 3:04 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Sat, Nov 14, 2015 at 2:15 AM, Kugan
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>
>>> Attached is the latest version of the patch. With the patches
>>> 0001-Add-new-SEXT_EXPR-tree-code.patch,
>>> 0002-Add-type-promotion-pass.patch and
>>> 0003-Optimize-ZEXT_EXPR-with-tree-vrp.patch.
>>>
>>> I did bootstrap on ppc64-linux-gnu, aarch64-linux-gnu and
>>> x64-64-linux-gnu and regression testing on ppc64-linux-gnu,
>>> aarch64-linux-gnu arm64-linux-gnu and x64-64-linux-gnu. I ran into three
>>> issues in ppc64-linux-gnu regression testing. There are some other test
>>> cases which needs adjustment for scanning for some patterns that are not
>>> valid now.
>>>
>>> 1. rtl fwprop was going into infinite loop. Works with the following patch:
>>> diff --git a/gcc/fwprop.c b/gcc/fwprop.c
>>> index 16c7981..9cf4f43 100644
>>> --- a/gcc/fwprop.c
>>> +++ b/gcc/fwprop.c
>>> @@ -948,6 +948,10 @@ try_fwprop_subst (df_ref use, rtx *loc, rtx
>>> new_rtx, rtx_insn *def_insn,
>>>    int old_cost = 0;
>>>    bool ok;
>>>
>>> +  /* Value to be substituted is the same, nothing to do.  */
>>> +  if (rtx_equal_p (*loc, new_rtx))
>>> +    return false;
>>> +
>>>    update_df_init (def_insn, insn);
>>>
>>>    /* forward_propagate_subreg may be operating on an instruction with
>>
>> Which testcase was this on?

After re-basing the trunk, I cannot reproduce it anymore.

>>
>>> 2. gcc.dg/torture/ftrapv-1.c fails
>>> This is because we are checking for the  SImode trapping. With the
>>> promotion of the operation to wider mode, this is i think expected. I
>>> think the testcase needs updating.
>>
>> No, it is not expected.  As said earlier you need to refrain from promoting
>> integer operations that trap.  You can use ! operation_no_trapping_overflow
>> for this.
>>

I have changed this.

>>> 3. gcc.dg/sms-3.c fails
>>> It fails with  -fmodulo-sched-allow-regmoves  and OK when I remove it. I
>>> am looking into it.
>>>
>>>
>>> I also have the following issues based on the previous review (as posted
>>> in the previous patch). Copying again for the review purpose.
>>>
>>> 1.
>>>> you still call promote_ssa on both DEFs and USEs and promote_ssa looks
>>>> at SSA_NAME_DEF_STMT of the passed arg.  Please call promote_ssa just
>>>> on DEFs and fixup_uses on USEs.
>>>
>>> I am doing this to promote SSA that are defined with GIMPLE_NOP. Is
>>> there anyway to iterate over this. I have added gcc_assert to make sure
>>> that promote_ssa is called only once.
>>
>>   gcc_assert (!ssa_name_info_map->get_or_insert (def));
>>
>> with --disable-checking this will be compiled away so you need to do
>> the assert in a separate statement.
>>
>>> 2.
>>>> Instead of this you should, in promote_all_stmts, walk over all uses
>>> doing what
>>>> fixup_uses does and then walk over all defs, doing what promote_ssa does.
>>>>
>>>> +    case GIMPLE_NOP:
>>>> +       {
>>>> +         if (SSA_NAME_VAR (def) == NULL)
>>>> +           {
>>>> +             /* Promote def by fixing its type for anonymous def.  */
>>>> +             TREE_TYPE (def) = promoted_type;
>>>> +           }
>>>> +         else
>>>> +           {
>>>> +             /* Create a promoted copy of parameters.  */
>>>> +             bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
>>>>
>>>> I think the uninitialized vars are somewhat tricky and it would be best
>>>> to create a new uninit anonymous SSA name for them.  You can
>>>> have SSA_NAME_VAR != NULL and def _not_ being a parameter
>>>> btw.
>>>
>>> I experimented with get_or_create_default_def. Here  we have to have a
>>> SSA_NAME_VAR (def) of promoted type.
>>>
>>> In the attached patch I am doing the following and seems to work. Does
>>> this looks OK?
>>>
>>> +         }
>>> +       else if (TREE_CODE (SSA_NAME_VAR (def)) != PARM_DECL)
>>> +         {
>>> +           tree var = copy_node (SSA_NAME_VAR (def));
>>> +           TREE_TYPE (var) = promoted_type;
>>> +           TREE_TYPE (def) = promoted_type;
>>> +           SET_SSA_NAME_VAR_OR_IDENTIFIER (def, var);
>>> +         }
>>
>> I believe this will wreck the SSA default-def map so you should do
>>
>>   set_ssa_default_def (cfun, SSA_NAME_VAR (def), NULL_TREE);
>>   tree var = create_tmp_reg (promoted_type);
>>   TREE_TYPE (def) = promoted_type;
>>   SET_SSA_NAME_VAR_OR_IDENTIFIER (def, var);
>>   set_ssa_default_def (cfun, var, def);
>>
>> instead.
I have changed this.

>>
>>> I prefer to promote def as otherwise iterating over the uses and
>>> promoting can look complicated (have to look at all the different types
>>> of stmts again and do the right thing as It was in the earlier version
>>> of this before we move to this approach)
>>>
>>> 3)
>>>> you can also transparently handle constants for the cases where promoting
>>>> is required.  At the moment their handling is interwinded with the def
>>> promotion
>>>> code.  That makes the whole thing hard to follow.
>>>
>>>
>>> I have updated the comments with:
>>>
>>> +/* Promote constants in STMT to TYPE.  If PROMOTE_COND_EXPR is true,
>>> +   promote only the constants in conditions part of the COND_EXPR.
>>> +
>>> +   We promote the constants when the associated operands are promoted.
>>> +   This usually means that we promote the constants when we promote the
>>> +   defining stmnts (as part of promote_ssa). However for COND_EXPR, we
>>> +   can promote only when we promote the other operand. Therefore, this
>>> +   is done during fixup_use.  */
>>>
>>>
>>> 4)
>>> I am handling gimple_debug separately to avoid any code difference with
>>> and without -g option. I have updated the comments for this.
>>>
>>> 5)
>>> I also noticed that tree-ssa-uninit sometimes gives false positives due
>>> to the assumptions
>>> it makes. Is it OK to move this pass before type promotion? I can do the
>>> testings and post a separate patch with this if this OK.
>>
>> Hmm, no, this needs more explanation (like a testcase).
There are few issues I ran into. I will send a list with more info. For
example:

/* Test we do not warn about initializing variable with self. */
/* { dg-do compile } */
/* { dg-options "-O -Wuninitialized" } */

int f()
{
  int i = i;
  return i;
}


I now get:
kugan@kugan-desktop:~$
/home/kugan/work/builds/gcc-fsf-linaro/tools/bin/ppc64-none-linux-gnu-gcc -O
-Wuninitialized
/home/kugan/work/SVN/gcc/trunk/gcc/testsuite/c-c++-common/uninit-D.c
-fdump-tree-all
/home/kugan/work/SVN/gcc/trunk/gcc/testsuite/c-c++-common/uninit-D.c: In
function ā€˜fā€™:
/home/kugan/work/SVN/gcc/trunk/gcc/testsuite/c-c++-common/uninit-D.c:8:10:
warning: ā€˜iā€™ is used uninitialized in this function [-Wuninitialized]
   return i;




>>
>>> 6)
>>> I also removed the optimization that prevents some of the redundant
>>> truncation/extensions from type promotion pass, as it dosent do much as
>>> of now. I can send a proper follow up patch. Is that OK?
>>
>> Yeah, that sounds fine.
>>
>>> I also did a simple test with coremark for the latest patch. I compared
>>> the code size for coremark for linux-gcc with -Os. Results are as
>>> reported by the "size" utility. I know this doesn't mean much but can
>>> give some indication.
>>>         Base            with pass       Percentage improvement
>>> ==============================================================
>>> arm     10476           10372           0.9927453226
>>> aarch64 9545            9521            0.2514405448
>>> ppc64   12236           12052           1.5037593985
>>>
>>>
>>> After resolving the above issues, I would like propose that we  commit
>>> the pass as not enabled by default (even though the patch as it stands
>>> enabled by default - I am doing it for testing purposes).
>>
>> Hmm, we don't like to have passes that are not enabled by default with any
>> optimization level or for any target.  Those tend to bitrot quickly :(
>>
>> Did you do any performance measurements yet?

Ok, I understand. I did performance testing on AARch64 and saw some good
improvement for the earlier version. I will do it again for more targets
after getting it reviewed.

>>
>> Looking over the pass in detail now (again).
> 
> Ok, so still looking at the basic operation scheme.
> 
>       FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
>         {
>           use = USE_FROM_PTR (op);
>           if (TREE_CODE (use) == SSA_NAME
>               && gimple_code (SSA_NAME_DEF_STMT (use)) == GIMPLE_NOP)
>             promote_ssa (use, &gsi);
>           fixup_use (stmt, &gsi, op, use);
>         }
> 
>       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
>         promote_ssa (def, &gsi);
> 
> the GIMPLE_NOP handling in promote_ssa but when processing uses looks
> backwards.  As those are implicitely defined in the entry block you may
> better just iterate over all default defs before the dominator walk like so
> 
>   unsigned n = num_ssa_names;
>   for (i = 1; i < n; ++i)
>     {
>       tree name = ssa_name (i);
>       if (name
>           && SSA_NAME_IS_DEFAULT_DEF
>           && ! has_zero_uses (name))
>        promote_default_def (name);
>     }
> 

I have Changed this.

> I see promote_cst_in_stmt in both promote_ssa and fixup_use.  Logically
> it belongs to use processing, but on a stmt granularity.  Thus between
> iterating over all uses and iteration over all defs call promote_cst_in_stmt
> on all stmts.  It's a bit awkward as it expects to be called from context
> that knows whether promotion is necessary or not.
> 
> /* 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;
> }
> 
> as you are generating a copy statement I don't see why you need to copy
> SSA_NAME_OCCURS_IN_ABNORMAL_PHI (in no case new_lhs will
> be used in a PHI node directly AFAICS).  Merging make_promoted_copy
> and the usually following extension stmt generation plus insertion into
> a single helper would make that obvious.
> 

I have changed this.

> static unsigned int
> fixup_use (gimple *stmt, gimple_stmt_iterator *gsi,
>            use_operand_p op, tree use)
> {
>   ssa_name_info *info = ssa_name_info_map->get_or_insert (use);
>   /* If USE is not promoted, nothing to do.  */
>   if (!info)
>     return 0;
> 
> You should use ->get (), not ->get_or_insert here.
> 
>       gimple *copy_stmt = gimple_build_assign (temp, NOP_EXPR,
>                                                use, NULL_TREE);
> 

Changed this.

> you can avoid the trailing NULL_TREE here.
> 
>         gimple *copy_stmt =
>           zero_sign_extend_stmt (temp, use,
>                                  TYPE_UNSIGNED (old_type),
>                                  TYPE_PRECISION (old_type));
> 
> coding style says the '=' goes to the next line, thus
> 
>     gimple *copy_stmt
>        = zero_sign_extend_stmt ...


Changed this.
> 
> /* Zero/sign extend (depending on UNSIGNED_P) 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, bool unsigned_p, int width)
> {
> 
> looks like instead of unsigned_p/width you can pass in a  type instead.
> 
>     /* Sign extend.  */
>     stmt = gimple_build_assign (new_var,
>                                 SEXT_EXPR,
>                                 var, build_int_cst (TREE_TYPE (var), width));
> 
> use size_int (width) instead.
> 
> /* Convert constant CST to TYPE.  */
> static tree
> convert_int_cst (tree type, tree cst, signop sign = SIGNED)
> 
> no need for a default argument
> 
> {
>   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);
> }


For some of the operations, sign extended constants are created. For
example:

short unPack( unsigned char c )
{
    /* Only want lower four bit nibble */
    c = c & (unsigned char)0x0F ;

    if( c > 7 ) {
        /* Negative nibble */
        return( ( short )( c - 5 ) ) ;

    }
    else
    {
        /* positive nibble */
        return( ( short )c ) ;
    }
}


- 5 above becomes  + (-5). Therefore, If I sign extend the constant in
promotion (even though it is unsigned) results in better code. There is
no correctness issue.

I have now changed it based on your suggestions. Is this look better?


> 
> I wonder why this function is needed at all and you don't just call
> fold_convert (type, cst)?
> 
> /* Return true if the tree CODE needs the propmoted operand to be
>    truncated (when stray bits are set beyond the original type in
>    promoted mode) to preserve the semantics.  */
> static bool
> truncate_use_p (enum tree_code code)
> {
> 
> a conservatively correct predicate would implement the inversion,
> not_truncated_use_p because if you miss any tree code the
> result will be unnecessary rather than missed truncations.
> 

Changed it.

> static bool
> type_precision_ok (tree type)
> {
>   return (TYPE_PRECISION (type)
>           == GET_MODE_PRECISION (TYPE_MODE (type)));
> }
> 
> /* 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_ok (type))
> 
> the type_precision_ok check is because SEXT doesn't work
> properly for bitfield types?  I think we want to promote those
> to their mode precision anyway.  We just need to use
> sth different than SEXT here (the bitwise-and works of course)
> or expand SEXT from non-mode precision differently (see
> expr.c REDUCE_BIT_FIELD which expands it as a
> lshift/rshift combo).  Eventually this can be left for a followup
> though it might get you some extra testing coverage on
> non-promote-mode targets.

I will have a look at it.

> 
> /* 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;
> 
> better than this default assert you pass in an SSA name.

Changed it.

> 
> isn't the bitmap somewhat redundant with the hash-map?
> And you could combine both by using a vec<ssa_name_info *> indexed
> by SSA_NAME_VERSION ()?
> 
>          if ((TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
>                == tcc_comparison)
>               || truncate_use_p (gimple_assign_rhs_code (stmt)))
> 
> you always check for tcc_omparison when checking for truncate_use_p
> so just handle it there (well, as said above, implement conservative
> predicates).
> 
>   switch (gimple_code (stmt))
>     {
>     case GIMPLE_ASSIGN:
>       if (promote_cond
>           && gimple_assign_rhs_code (stmt) == COND_EXPR)
>         {
> 
> looking at all callers this condition is never true.
> 
>           tree new_op = build2 (TREE_CODE (op), type, op0, op1);
> 
> as tcc_comparison class trees are not shareable you don't
> need to build2 but can directly set TREE_OPERAND (op, ..) to the
> promoted value.  Note that rhs1 may still just be an SSA name
> and not a comparison.

Changed this.

> 
>     case GIMPLE_PHI:
>         {
>           /* Promote INTEGER_CST arguments to 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));
>             }
> 
> static unsigned int
> fixup_use (gimple *stmt, gimple_stmt_iterator *gsi,
>            use_operand_p op, tree use)
> {
>   ssa_name_info *info = ssa_name_info_map->get_or_insert (use);
>   /* If USE is not promoted, nothing to do.  */
>   if (!info)
>     return 0;
> 
>   tree promoted_type = info->promoted_type;
>   tree old_type = info->type;
>   bool do_not_promote = false;
> 
>   switch (gimple_code (stmt))
>     {
>  ....
>     default:
>       break;
>     }
> 
> do_not_promote = false is not conservative.  Please place a
> gcc_unreachable () in the default case.

We will have valid statements (which are not handled in switch) for
which we don't have to do any fix ups.

> 
> I see you handle debug stmts here but that case cannot be reached.
> 
> /* Promote use in GIMPLE_DEBUG stmts. Do this separately to avoid generating
>    different sequence with and without -g.  This can  happen when promoting
>    SSA that are defined with GIMPLE_NOP.  */
> 
> but that's only because you choose to unconditionally handle GIMPLE_NOP uses...

I have removed this.

Thanks,
Kugan

> 
> Richard.
> 
> 
>> Thanks,
>> Richard.
>>
>>> Thanks,
>>> Kugan
>>>
>>>

Comments

Kugan Vivekanandarajah Dec. 10, 2015, 12:27 a.m. UTC | #1
Hi Riachard,

Thanks for the reviews.

I think since we have some unresolved issues here, it is best to aim for
the next stage1. I however would like any feedback so that I can
continue to improve this.

https://gcc.gnu.org/ml/gcc-patches/2015-09/msg01063.html is also related
to https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67714. I don't think
there is any agreement on this. Or is there any better place to fix this?

Thanks,
Kugan
Richard Biener Dec. 16, 2015, 1:18 p.m. UTC | #2
On Thu, Dec 10, 2015 at 1:27 AM, Kugan
<kugan.vivekanandarajah@linaro.org> wrote:
> Hi Riachard,
>
> Thanks for the reviews.
>
> I think since we have some unresolved issues here, it is best to aim for
> the next stage1. I however would like any feedback so that I can
> continue to improve this.

Yeah, sorry I've been distracted lately and am not sure I'll get to
the patch before
christmas break.

> https://gcc.gnu.org/ml/gcc-patches/2015-09/msg01063.html is also related
> to https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67714. I don't think
> there is any agreement on this. Or is there any better place to fix this?

I don't know enough in this area to suggest anything.

Richard.

> Thanks,
> Kugan
diff mbox

Patch

From 89f526ea6f7878879fa65a2b869cac4c21dc7df0 Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
Date: Fri, 20 Nov 2015 14:14:52 +1100
Subject: [PATCH 2/3] Add type promotion pass

---
 gcc/Makefile.in               |   1 +
 gcc/auto-profile.c            |   2 +-
 gcc/common.opt                |   4 +
 gcc/doc/invoke.texi           |  10 +
 gcc/gimple-ssa-type-promote.c | 849 ++++++++++++++++++++++++++++++++++++++++++
 gcc/passes.def                |   1 +
 gcc/timevar.def               |   1 +
 gcc/tree-pass.h               |   1 +
 libiberty/cp-demangle.c       |   2 +-
 9 files changed, 869 insertions(+), 2 deletions(-)
 create mode 100644 gcc/gimple-ssa-type-promote.c

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 0fd8d99..4e1444c 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1512,6 +1512,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/auto-profile.c b/gcc/auto-profile.c
index c7aab42..f214331 100644
--- a/gcc/auto-profile.c
+++ b/gcc/auto-profile.c
@@ -1257,7 +1257,7 @@  afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge)
     FOR_EACH_EDGE (e, ei, bb->succs)
     {
       unsigned i, total = 0;
-      edge only_one;
+      edge only_one = NULL;
       bool check_value_one = (((integer_onep (cmp_rhs))
                                ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
                               ^ ((e->flags & EDGE_TRUE_VALUE) != 0));
diff --git a/gcc/common.opt b/gcc/common.opt
index 3eb520e..582e8ee 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2407,6 +2407,10 @@  fsplit-paths
 Common Report Var(flag_split_paths) Init(0) Optimization
 Split paths leading to loop backedges.
 
+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/doc/invoke.texi b/gcc/doc/invoke.texi
index 7cef176..21f94a6 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -9142,6 +9142,16 @@  Split paths leading to loop backedges.  This can improve dead code
 elimination and common subexpression elimination.  This is enabled by
 default at @option{-O2} and above.
 
+@item -ftree-type-promote
+@opindex ftree-type-promote
+This pass applies type promotion to SSA names in the function and
+inserts appropriate truncations to preserve the semantics.  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 optimization is enabled by default.
+
 @item -fsplit-ivs-in-unroller
 @opindex fsplit-ivs-in-unroller
 Enables expression of values of induction variables in later iterations
diff --git a/gcc/gimple-ssa-type-promote.c b/gcc/gimple-ssa-type-promote.c
new file mode 100644
index 0000000..5993e89
--- /dev/null
+++ b/gcc/gimple-ssa-type-promote.c
@@ -0,0 +1,849 @@ 
+/* 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 "backend.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "vec.h"
+#include "double-int.h"
+#include "input.h"
+#include "symtab.h"
+#include "wide-int.h"
+#include "inchash.h"
+#include "tree.h"
+#include "fold-const.h"
+#include "stor-layout.h"
+#include "predict.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 in turn 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.
+*/
+
+/* Structure to hold the type and promoted type for promoted ssa variables.  */
+struct ssa_name_info
+{
+  tree ssa;		/* Name of the SSA_NAME.  */
+  tree type;		/* Original type of ssa.  */
+  tree promoted_type;	/* Promoted type of ssa.  */
+};
+
+/* Obstack for ssa_name_info.  */
+static struct obstack ssa_name_info_obstack;
+
+static unsigned n_ssa_val;
+static sbitmap ssa_to_be_promoted_bitmap;
+static hash_map <tree, ssa_name_info *>  *ssa_name_info_map;
+
+static bool
+type_precision_ok (tree type)
+{
+  return (TYPE_PRECISION (type)
+	  == GET_MODE_PRECISION (TYPE_MODE (type)));
+}
+
+/* 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_ok (type))
+    return type;
+
+  mode = TYPE_MODE (type);
+#ifdef PROMOTE_MODE
+  uns = TYPE_SIGN (type);
+  PROMOTE_MODE (mode, uns, type);
+#endif
+  uns = TYPE_SIGN (type);
+  if (TYPE_PRECISION (type) == GET_MODE_PRECISION (mode))
+    return type;
+  promoted_type
+    = build_nonstandard_integer_type (GET_MODE_PRECISION (mode),
+				      uns);
+  gcc_assert (TYPE_PRECISION (promoted_type) == GET_MODE_PRECISION (mode));
+  return promoted_type;
+}
+
+/* Return true if ssa NAME is already considered for promotion.  */
+static bool
+ssa_promoted_p (tree name)
+{
+  gcc_assert (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)
+{
+  gcc_assert (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 true if the tree CODE needs the propmoted operand to be
+   truncated (when stray bits are set beyond the original type in
+   promoted mode) to preserve the semantics.  */
+static bool
+not_truncated_use_p (enum tree_code code)
+{
+  if (TREE_CODE_CLASS (code) == tcc_comparison
+      || code == TRUNC_DIV_EXPR
+      || code == CEIL_DIV_EXPR
+      || code == FLOOR_DIV_EXPR
+      || code == ROUND_DIV_EXPR
+      || code == TRUNC_MOD_EXPR
+      || code == CEIL_MOD_EXPR
+      || code == FLOOR_MOD_EXPR
+      || code == ROUND_MOD_EXPR
+      || code == LSHIFT_EXPR
+      || code == RSHIFT_EXPR
+      || code == MAX_EXPR
+      || code == MIN_EXPR)
+    return false;
+  else
+    return true;
+}
+
+
+/* Return true if LHS will be promoted later.  */
+static bool
+tobe_promoted_p (tree lhs)
+{
+  if (TREE_CODE (lhs) == SSA_NAME
+      && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+      && !VECTOR_TYPE_P (TREE_TYPE (lhs))
+      && !POINTER_TYPE_P (TREE_TYPE (lhs))
+      && !ssa_promoted_p (lhs)
+      && (get_promoted_type (TREE_TYPE (lhs))
+	  != TREE_TYPE (lhs)))
+    return true;
+  else
+    return false;
+}
+
+/* Convert and sign-extend constant CST to TYPE.  */
+static tree
+fold_convert_sext (tree type, tree cst)
+{
+  wide_int wi_cons = fold_convert (type, cst);
+  wi_cons = wi::ext (wi_cons, TYPE_PRECISION (TREE_TYPE (cst)), SIGNED);
+  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.
+
+   We promote the constants when the ssociated operands are promoted.
+   This usually means that we promote the constants when we promote the
+   defining stmnts (as part of promote_ssa). However for COND_EXPR, we
+   can promote only when we promote the other operand. Therefore, this
+   is done during fixup_use.  */
+
+static void
+promote_cst_in_stmt (gimple *stmt, tree type)
+{
+  tree op;
+  ssa_op_iter iter;
+  use_operand_p oprnd;
+  int index;
+  tree op0, op1;
+
+  switch (gimple_code (stmt))
+    {
+    case GIMPLE_ASSIGN:
+      if (gimple_assign_rhs_code (stmt) == COND_EXPR
+	  && TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt)) == 2)
+	{
+	  /* Promote INTEGER_CST that are tcc_compare arguments.  */
+	  op = gimple_assign_rhs1 (stmt);
+	  op0 = TREE_OPERAND (op, 0);
+	  op1 = TREE_OPERAND (op, 1);
+	  if (TREE_TYPE (op0) != TREE_TYPE (op1))
+	    {
+	      if (TREE_CODE (op0) == INTEGER_CST)
+		TREE_OPERAND (op, 0) = fold_convert (type, op0);
+	      if (TREE_CODE (op1) == INTEGER_CST)
+		TREE_OPERAND (op, 1) = fold_convert (type, op1);
+	    }
+	}
+      /* Promote INTEGER_CST in GIMPLE_ASSIGN.  */
+      if (not_truncated_use_p (gimple_assign_rhs_code (stmt)))
+	{
+	  op = gimple_assign_rhs3 (stmt);
+	  if (op && TREE_CODE (op) == INTEGER_CST)
+	    gimple_assign_set_rhs3 (stmt, fold_convert_sext (type, op));
+	  op = gimple_assign_rhs1 (stmt);
+	  if (op && TREE_CODE (op) == INTEGER_CST)
+	    gimple_assign_set_rhs1 (stmt, fold_convert_sext (type, op));
+	  op = gimple_assign_rhs2 (stmt);
+	  if (op && TREE_CODE (op) == INTEGER_CST)
+	    gimple_assign_set_rhs2 (stmt, fold_convert_sext (type, op));
+	}
+      else
+	{
+	  op = gimple_assign_rhs3 (stmt);
+	  if (op && TREE_CODE (op) == INTEGER_CST)
+	    gimple_assign_set_rhs3 (stmt, fold_convert (type, op));
+	  op = gimple_assign_rhs1 (stmt);
+	  if (op && TREE_CODE (op) == INTEGER_CST)
+	    gimple_assign_set_rhs1 (stmt, fold_convert (type, op));
+	  op = gimple_assign_rhs2 (stmt);
+	  if (op && TREE_CODE (op) == INTEGER_CST)
+	    gimple_assign_set_rhs2 (stmt, fold_convert (type, op));
+	}
+      break;
+
+    case GIMPLE_PHI:
+	{
+	  /* Promote INTEGER_CST arguments to 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, fold_convert (type, op));
+	    }
+	}
+      break;
+
+    case GIMPLE_COND:
+	{
+	  /* Promote INTEGER_CST that are GIMPLE_COND arguments.  */
+	  gcond *cond = as_a <gcond *> (stmt);
+	  op = gimple_cond_lhs (cond);
+	  if (op && TREE_CODE (op) == INTEGER_CST)
+	    gimple_cond_set_lhs (cond, fold_convert (type, op));
+
+	  op = gimple_cond_rhs (cond);
+	  if (op && TREE_CODE (op) == INTEGER_CST)
+	    gimple_cond_set_rhs (cond, fold_convert (type, op));
+	}
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Zero/sign extend VAR and truncate to INNER_TYPE.
+   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, tree inner_type)
+{
+  gcc_assert (TYPE_PRECISION (TREE_TYPE (var))
+	      == TYPE_PRECISION (TREE_TYPE (new_var)));
+  gcc_assert (TYPE_PRECISION (TREE_TYPE (var)) > TYPE_PRECISION (inner_type));
+  gimple *stmt;
+
+  if (TYPE_UNSIGNED (inner_type))
+    {
+      /* Zero extend.  */
+      tree cst
+	= wide_int_to_tree (TREE_TYPE (var),
+			    wi::mask (TYPE_PRECISION (inner_type), false,
+				      TYPE_PRECISION (TREE_TYPE (var))));
+      stmt = gimple_build_assign (new_var, BIT_AND_EXPR,
+				  var, cst);
+    }
+  else
+    /* Sign extend.  */
+    stmt = gimple_build_assign (new_var,
+				SEXT_EXPR,
+				var,
+				build_int_cst (TREE_TYPE (var),
+					       TYPE_PRECISION (inner_type)));
+  return stmt;
+}
+
+static void
+copy_default_ssa (tree to, tree from)
+{
+  SET_SSA_NAME_VAR_OR_IDENTIFIER (to, SSA_NAME_VAR (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 (to) = 1;
+  SSA_NAME_IS_DEFAULT_DEF (from) = 0;
+}
+
+/* Promote definition DEF to PROMOTED_TYPE.  If the stmt that defines def
+   is def_stmt, make the type of def promoted_type.  If the stmt is such
+   that, result of the def_stmt cannot be of promoted_type, create a new_def
+   of the original_type and make the def_stmt assign its value to newdef.
+   Then, create a NOP_EXPR to convert new_def to def of promoted type.
+
+   For example, for stmt with original_type char and promoted_type int:
+		char _1 = mem;
+	becomes:
+		char _2 = mem;
+		int _1 = (int)_2;
+
+   If the def_stmt allows def to be promoted, promote def in-place
+   (and its arguments when needed).
+
+   For example:
+		char _3 = _1 + _2;
+	becomes:
+		int _3 = _1 + _2;
+   Here, _1 and _2 will also be promoted.  */
+
+static void
+promote_ssa (tree def, gimple_stmt_iterator *gsi)
+{
+  gimple *def_stmt = SSA_NAME_DEF_STMT (def);
+  gimple *copy_stmt = NULL;
+  gimple_stmt_iterator gsi2;
+  tree original_type = TREE_TYPE (def);
+  tree new_def;
+  ssa_name_info *info;
+  bool do_not_promote = false;
+  tree promoted_type = get_promoted_type (TREE_TYPE (def));
+
+  if (!tobe_promoted_p (def))
+    return;
+
+  info = (ssa_name_info *) obstack_alloc (&ssa_name_info_obstack,
+					  sizeof (ssa_name_info));
+  info->type = original_type;
+  info->promoted_type = promoted_type;
+  info->ssa = def;
+  ssa_name_info_map->put (def, info);
+
+  switch (gimple_code (def_stmt))
+    {
+    case GIMPLE_PHI:
+      {
+	/* Promote def by fixing its type and make def anonymous.  */
+	TREE_TYPE (def) = promoted_type;
+	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)
+	  {
+	    /* Promote def and copy (i.e. convert) the value defined
+	       by asm to def.  */
+	    tree link = gimple_asm_output_op (asm_stmt, i);
+	    tree op = TREE_VALUE (link);
+	    if (op == def)
+	      {
+		new_def = copy_ssa_name (def);
+		set_ssa_promoted (new_def);
+		copy_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, NOP_EXPR, new_def);
+		SSA_NAME_IS_DEFAULT_DEF (new_def) = 0;
+		gimple_set_location (copy_stmt, gimple_location (def_stmt));
+		gsi2 = gsi_for_stmt (def_stmt);
+		gsi_insert_after (&gsi2, copy_stmt, GSI_NEW_STMT);
+		break;
+	      }
+	  }
+	break;
+      }
+
+    case GIMPLE_NOP:
+      {
+	gcc_unreachable ();
+      }
+
+    case GIMPLE_ASSIGN:
+      {
+	enum tree_code code = gimple_assign_rhs_code (def_stmt);
+	tree rhs = gimple_assign_rhs1 (def_stmt);
+	if (gimple_vuse (def_stmt) != NULL_TREE
+	    || gimple_vdef (def_stmt) != NULL_TREE
+	    || (ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
+		&& !operation_no_trapping_overflow (TREE_TYPE (def), code))
+	    || TREE_CODE_CLASS (code) == tcc_reference
+	    || TREE_CODE_CLASS (code) == tcc_comparison
+	    || code == LROTATE_EXPR
+	    || code == RROTATE_EXPR
+	    || code == VIEW_CONVERT_EXPR
+	    || code == REALPART_EXPR
+	    || code == IMAGPART_EXPR
+	    || code == REDUC_PLUS_EXPR
+	    || code == REDUC_MAX_EXPR
+	    || code == REDUC_MIN_EXPR
+	    || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
+	  {
+	    do_not_promote = true;
+	  }
+	else if (CONVERT_EXPR_CODE_P (code))
+	  {
+	    if (!type_precision_ok (TREE_TYPE (rhs)))
+	      {
+		do_not_promote = true;
+	      }
+	    else if (types_compatible_p (TREE_TYPE (rhs), promoted_type))
+	      {
+		/* As we travel statements in dominated order, arguments
+		   of def_stmt will be visited before visiting def.  If RHS
+		   is already promoted and type is compatible, we can convert
+		   them into ZERO/SIGN EXTEND stmt.  */
+		ssa_name_info *info = ssa_name_info_map->get_or_insert (rhs);
+		tree type;
+		if (info == NULL)
+		  type = TREE_TYPE (rhs);
+		else
+		  type = info->type;
+		if ((TYPE_PRECISION (original_type)
+		     > TYPE_PRECISION (type))
+		    || (TYPE_UNSIGNED (original_type)
+			!= TYPE_UNSIGNED (type)))
+		  {
+		    if (TYPE_PRECISION (original_type) < TYPE_PRECISION (type))
+		      type = original_type;
+		    gcc_assert (type != NULL_TREE);
+		    TREE_TYPE (def) = promoted_type;
+		    copy_stmt = zero_sign_extend_stmt (def, rhs, type);
+		    SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE);
+		    gsi_replace (gsi, copy_stmt, false);
+		  }
+		else
+		  {
+		    TREE_TYPE (def) = promoted_type;
+		    SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE);
+		  }
+	      }
+	    else
+	      {
+		/* If RHS is not promoted OR their types are not
+		   compatible, create NOP_EXPR that converts
+		   RHS to  promoted DEF type and perform a
+		   ZERO/SIGN EXTEND to get the required value
+		   from RHS.  */
+		ssa_name_info *info = ssa_name_info_map->get_or_insert (rhs);
+		if (info != NULL)
+		  {
+		    tree type = info->type;
+		    new_def = copy_ssa_name (rhs);
+		    SET_SSA_NAME_VAR_OR_IDENTIFIER (new_def, NULL_TREE);
+		    TREE_TYPE (def) = promoted_type;
+		    SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE);
+		    copy_stmt = zero_sign_extend_stmt (new_def, rhs, type);
+		    gimple_set_location (copy_stmt, gimple_location (def_stmt));
+		    gsi2 = gsi_for_stmt (def_stmt);
+		    gsi_insert_before (&gsi2, copy_stmt, GSI_NEW_STMT);
+		    gassign *new_def_stmt = gimple_build_assign (def, code, new_def);
+		    gsi_replace (gsi, new_def_stmt, false);
+		  }
+		else
+		  {
+		    TREE_TYPE (def) = promoted_type;
+		    SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE);
+		  }
+	      }
+	  }
+	else
+	  {
+	    /* Promote def by fixing its type and make def anonymous.  */
+	    promote_cst_in_stmt (def_stmt, promoted_type);
+	    SET_SSA_NAME_VAR_OR_IDENTIFIER (def, NULL_TREE);
+	    TREE_TYPE (def) = promoted_type;
+	  }
+	break;
+      }
+
+    default:
+      do_not_promote = true;
+      break;
+    }
+
+  if (do_not_promote)
+    {
+      /* Promote def and copy (i.e. convert) the value defined
+	 by the stmt that cannot be promoted.  */
+      new_def = copy_ssa_name (def);
+      set_ssa_promoted (new_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, NOP_EXPR, new_def);
+      gimple_set_location (copy_stmt, gimple_location (def_stmt));
+      gsi2 = gsi_for_stmt (def_stmt);
+      if (lookup_stmt_eh_lp (def_stmt) > 0
+	  || (gimple_code (def_stmt) == GIMPLE_CALL
+	      && gimple_call_ctrl_altering_p (def_stmt)))
+	gsi_insert_on_edge (FALLTHRU_EDGE (gimple_bb (def_stmt)),
+			    copy_stmt);
+      else
+	gsi_insert_after (&gsi2, copy_stmt, GSI_NEW_STMT);
+    }
+  reset_flow_sensitive_info (def);
+}
+
+/* Fix the (promoted) USE in stmts where USE cannot be be promoted.  */
+static unsigned int
+fixup_use (gimple *stmt, gimple_stmt_iterator *gsi,
+	   use_operand_p op, tree use)
+{
+  gimple *copy_stmt;
+  ssa_name_info **info = ssa_name_info_map->get (use);
+  /* If USE is not promoted, nothing to do.  */
+  if (!info || *info == NULL)
+    return 0;
+
+  tree promoted_type = (*info)->promoted_type;
+  tree old_type = (*info)->type;
+  bool do_not_promote = false;
+
+  switch (gimple_code (stmt))
+    {
+    case GIMPLE_DEBUG:
+      {
+	SET_USE (op, fold_convert (old_type, use));
+	update_stmt (stmt);
+	break;
+      }
+
+    case GIMPLE_ASM:
+    case GIMPLE_CALL:
+    case GIMPLE_RETURN:
+      {
+	/* USE cannot be promoted here.  */
+	do_not_promote = true;
+	break;
+      }
+
+    case GIMPLE_ASSIGN:
+      {
+	enum tree_code code = gimple_assign_rhs_code (stmt);
+	tree lhs = gimple_assign_lhs (stmt);
+	if (gimple_vuse (stmt) != NULL_TREE
+	    || gimple_vdef (stmt) != NULL_TREE
+	    || (ANY_INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+		&& !operation_no_trapping_overflow (TREE_TYPE (lhs), code))
+	    || code == VIEW_CONVERT_EXPR
+	    || code == LROTATE_EXPR
+	    || code == RROTATE_EXPR
+	    || code == CONSTRUCTOR
+	    || code == BIT_FIELD_REF
+	    || code == COMPLEX_EXPR
+	    || VECTOR_TYPE_P (TREE_TYPE (lhs)))
+	  {
+	    do_not_promote = true;
+	  }
+	else if (!not_truncated_use_p (code))
+	  {
+	    /* Promote the constant in comparison when other comparison
+	       operand is promoted.  All other constants are promoted as
+	       part of promoting definition in promote_ssa.  */
+	    if (TREE_CODE_CLASS (code) == tcc_comparison)
+	      promote_cst_in_stmt (stmt, promoted_type);
+	    /* In some stmts, value in USE has to be ZERO/SIGN
+	       Extended based on the original type for correct
+	       result.  */
+	    tree temp = make_ssa_name (TREE_TYPE (use), NULL);
+	    copy_stmt = zero_sign_extend_stmt (temp, use, old_type);
+	    gimple_set_location (copy_stmt, gimple_location (stmt));
+	    gsi_insert_before (gsi, copy_stmt, GSI_NEW_STMT);
+
+	    SET_USE (op, temp);
+	    update_stmt (stmt);
+	  }
+	else if (CONVERT_EXPR_CODE_P (code)
+	    || code == FLOAT_EXPR)
+	  {
+	    if (types_compatible_p (TREE_TYPE (lhs), promoted_type))
+	      {
+		/* Type of LHS and promoted RHS are compatible, we can
+		   convert this into ZERO/SIGN EXTEND stmt.  */
+		copy_stmt = zero_sign_extend_stmt (lhs, use, old_type);
+		gimple_set_location (copy_stmt, gimple_location (stmt));
+		set_ssa_promoted (lhs);
+		gsi_replace (gsi, copy_stmt, false);
+	      }
+	    else if (!tobe_promoted_p (lhs)
+		     || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+		     || (TYPE_UNSIGNED (TREE_TYPE (use)) != TYPE_UNSIGNED (TREE_TYPE (lhs))))
+	      {
+		tree temp = make_ssa_name (TREE_TYPE (use), NULL);
+		copy_stmt = zero_sign_extend_stmt (temp, use, old_type);
+		gimple_set_location (copy_stmt, gimple_location (stmt));
+		gsi_insert_before (gsi, copy_stmt, GSI_NEW_STMT);
+		SET_USE (op, temp);
+		update_stmt (stmt);
+	      }
+	  }
+	break;
+      }
+
+    case GIMPLE_COND:
+      {
+	/* In GIMPLE_COND, value in USE has to be ZERO/SIGN
+	   Extended based on the original type for correct
+	   result.  */
+	tree temp = make_ssa_name (TREE_TYPE (use), NULL);
+	copy_stmt = zero_sign_extend_stmt (temp, use, old_type);
+	gimple_set_location (copy_stmt, gimple_location (stmt));
+	gsi_insert_before (gsi, copy_stmt, GSI_NEW_STMT);
+	SET_USE (op, temp);
+	promote_cst_in_stmt (stmt, promoted_type);
+	update_stmt (stmt);
+	break;
+      }
+
+    default:
+      break;
+    }
+
+  if (do_not_promote)
+    {
+      /* FOR stmts where USE cannot be promoted, create an
+	 original type copy.  */
+      tree temp;
+      temp = copy_ssa_name (use);
+      SET_SSA_NAME_VAR_OR_IDENTIFIER (temp, NULL_TREE);
+      set_ssa_promoted (temp);
+      TREE_TYPE (temp) = old_type;
+      copy_stmt = gimple_build_assign (temp, NOP_EXPR, use);
+      gimple_set_location (copy_stmt, gimple_location (stmt));
+      gsi_insert_before (gsi, copy_stmt, GSI_NEW_STMT);
+      SET_USE (op, temp);
+      update_stmt (stmt);
+    }
+  return 0;
+}
+
+static void
+promote_all_ssa_defined_with_nop ()
+{
+  unsigned n = num_ssa_names, i;
+  gimple_stmt_iterator gsi2;
+  tree new_def;
+  basic_block bb;
+  gimple *copy_stmt;
+
+  for (i = 1; i < n; ++i)
+    {
+      tree name = ssa_name (i);
+      if (name
+	  && gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_NOP
+	  && tobe_promoted_p (name)
+	  && !has_zero_uses (name))
+	{
+	  tree promoted_type = get_promoted_type (TREE_TYPE (name));
+	  ssa_name_info *info;
+	  set_ssa_promoted (name);
+	  info = (ssa_name_info *) obstack_alloc (&ssa_name_info_obstack,
+						  sizeof (ssa_name_info));
+	  info->type = TREE_TYPE (name);
+	  info->promoted_type = promoted_type;
+	  info->ssa = name;
+	  ssa_name_info_map->put (name, info);
+
+	  if (SSA_NAME_VAR (name) == NULL)
+	    {
+	      /* Promote def by fixing its type for anonymous def.  */
+	      TREE_TYPE (name) = promoted_type;
+	    }
+	  else if (TREE_CODE (SSA_NAME_VAR (name)) != PARM_DECL)
+	    {
+	      tree var = create_tmp_reg (promoted_type);
+	      DECL_NAME (var) = DECL_NAME (SSA_NAME_VAR (name));
+	      set_ssa_default_def (cfun, SSA_NAME_VAR (name), NULL_TREE);
+	      TREE_TYPE (name) = promoted_type;
+	      SET_SSA_NAME_VAR_OR_IDENTIFIER (name, var);
+	      set_ssa_default_def (cfun, var, name);
+	    }
+	  else
+	    {
+	      /* Create a promoted copy of parameters.  */
+	      bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+	      gcc_assert (bb);
+	      gsi2 = gsi_after_labels (bb);
+	      /* Create new_def of the original type and set that to be the
+		 parameter.  */
+	      new_def = copy_ssa_name (name);
+	      set_ssa_promoted (new_def);
+	      set_ssa_default_def (cfun, SSA_NAME_VAR (name), new_def);
+	      copy_default_ssa (new_def, name);
+
+	      /* Now promote the def and copy the value from parameter.  */
+	      TREE_TYPE (name) = promoted_type;
+	      copy_stmt = gimple_build_assign (name, NOP_EXPR, new_def);
+	      SSA_NAME_DEF_STMT (name) = copy_stmt;
+	      gsi_insert_before (&gsi2, copy_stmt, GSI_NEW_STMT);
+	    }
+	  reset_flow_sensitive_info (name);
+	}
+    }
+}
+
+/* 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, use;
+  use_operand_p op;
+
+  for (gphi_iterator gpi = gsi_start_phis (bb);
+       !gsi_end_p (gpi); gsi_next (&gpi))
+    {
+      gphi *phi = gpi.phi ();
+      FOR_EACH_PHI_ARG (op, phi, iter, SSA_OP_USE)
+	{
+	  use = USE_FROM_PTR (op);
+	  fixup_use (phi, &gsi, op, use);
+	}
+
+      def = PHI_RESULT (phi);
+      promote_ssa (def, &gsi);
+    }
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple *stmt = gsi_stmt (gsi);
+      FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
+	{
+	  use = USE_FROM_PTR (op);
+	  fixup_use (stmt, &gsi, op, use);
+	}
+
+      FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
+	promote_ssa (def, &gsi);
+    }
+}
+
+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_name_info_map = new hash_map<tree, ssa_name_info *>;
+  ssa_to_be_promoted_bitmap = sbitmap_alloc (n_ssa_val);
+  bitmap_clear (ssa_to_be_promoted_bitmap);
+
+  /* Create the obstack where ssa_name_info will reside.  */
+  gcc_obstack_init (&ssa_name_info_obstack);
+
+  calculate_dominance_info (CDI_DOMINATORS);
+  promote_all_ssa_defined_with_nop ();
+  /* Walk the CFG in dominator order.  */
+  type_promotion_dom_walker (CDI_DOMINATORS)
+    .walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+  gsi_commit_edge_inserts ();
+
+  obstack_free (&ssa_name_info_obstack, NULL);
+  sbitmap_free (ssa_to_be_promoted_bitmap);
+  delete ssa_name_info_map;
+  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 1702778..26838f3 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -276,6 +276,7 @@  along with GCC; see the file COPYING3.  If not see
       POP_INSERT_PASSES ()
       NEXT_PASS (pass_simduid_cleanup);
       NEXT_PASS (pass_lower_vector_ssa);
+      NEXT_PASS (pass_type_promote);
       NEXT_PASS (pass_split_paths);
       NEXT_PASS (pass_cse_reciprocals);
       NEXT_PASS (pass_reassoc, false /* insert_powi_p */);
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 45e3b70..da7f2d5 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -279,6 +279,7 @@  DEFTIMEVAR (TV_VTABLE_VERIFICATION   , "vtable verification")
 DEFTIMEVAR (TV_TREE_UBSAN            , "tree ubsan")
 DEFTIMEVAR (TV_INITIALIZE_RTL        , "initialize rtl")
 DEFTIMEVAR (TV_GIMPLE_LADDRESS       , "address lowering")
+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-pass.h b/gcc/tree-pass.h
index dcd2d5e..376ad7d 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -441,6 +441,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/libiberty/cp-demangle.c b/libiberty/cp-demangle.c
index ff608a3..6722331 100644
--- a/libiberty/cp-demangle.c
+++ b/libiberty/cp-demangle.c
@@ -4353,7 +4353,7 @@  d_print_comp_inner (struct d_print_info *dpi, int options,
 
   /* Variable used to store the current templates while a previously
      captured scope is used.  */
-  struct d_print_template *saved_templates;
+  struct d_print_template *saved_templates = NULL;
 
   /* Nonzero if templates have been stored in the above variable.  */
   int need_template_restore = 0;
-- 
1.9.1