IR_lowering.cpp

Go to the documentation of this file.

/*
 *
 *                   _/_/_/    _/_/   _/    _/ _/_/_/    _/_/
 *                  _/   _/ _/    _/ _/_/  _/ _/   _/ _/    _/
 *                 _/_/_/  _/_/_/_/ _/  _/_/ _/   _/ _/_/_/_/
 *                _/      _/    _/ _/    _/ _/   _/ _/    _/
 *               _/      _/    _/ _/    _/ _/_/_/  _/    _/
 *
 *             ***********************************************
 *                              PandA Project
 *                     URL: http://panda.dei.polimi.it
 *                       Politecnico di Milano - DEIB
 *                        System Architectures Group
 *             ***********************************************
 *              Copyright (C) 2004-2024 Politecnico di Milano
 *
 *   This file is part of the PandA framework.
 *
 *   The PandA framework 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 of the License, or
 *   (at your option) any later version.
 *
 *   This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
#include "IR_lowering.hpp"

#include "config_HAVE_ASSERTS.hpp" // for HAVE_ASSERTS

#include "Parameter.hpp"                    // for Parameter
#include "application_manager.hpp"          // for application_manager, app...
#include "custom_map.hpp"                   // for unordered_map, operator!=
#include "dbgPrintHelper.hpp"               // for DEBUG_LEVEL_VERY_PEDANTIC
#include "design_flow_graph.hpp"            // for DesignFlowGraph, DesignF...
#include "design_flow_manager.hpp"          // for DesignFlowManager, Desig...
#include "design_flow_step_factory.hpp"     // for DesignFlowManagerConstRef
#include "exceptions.hpp"                   // for THROW_ASSERT, THROW_UNRE...
#include "graph.hpp"                        // for vertex
#include "hash_helper.hpp"                  // for hash
#include "hls_device.hpp"                   // for HLS_device, HLS_deviceRef
#include "hls_manager.hpp"                  // for HLS_manager
#include "math_function.hpp"                // for floor_log2, exact_log2
#include "string_manipulation.hpp"          // for STR, GET_CLASS
#include "technology_flow_step.hpp"         // for TechnologyFlowStep_Type
#include "technology_flow_step_factory.hpp" // for TechnologyFlowStepFactory
#include "technology_manager.hpp"           // for LIBRARY_STD_FU, technolo...
#include "technology_node.hpp"              // for functional_unit, operation
#include "time_info.hpp"                    // for time_info
#include "tree_basic_block.hpp"             // for bloc
#include "tree_common.hpp"                  // for plus_expr_K, lshift_expr_K
#include "tree_helper.hpp"                  // for tree_helper
#include "tree_manager.hpp"                 // for tree_manager
#include "tree_manipulation.hpp"            // for tree_manipulation, Param...
#include "tree_node.hpp"                    // for tree_nodeRef, gimple_assign
#include "tree_reindex.hpp"
#include <cmath>   // for ceil
#include <cstddef> // for size_t
#include <limits>
#include <vector> // for vector

IR_lowering::IR_lowering(const ParameterConstRef Param, const application_managerRef _AppM, unsigned int _function_id,
                         const DesignFlowManagerConstRef _design_flow_manager)
    : FunctionFrontendFlowStep(_AppM, _function_id, IR_LOWERING, _design_flow_manager, Param)
{
   debug_level = parameters->get_class_debug_level(GET_CLASS(*this));
}

const CustomUnorderedSet<std::pair<FrontendFlowStepType, FrontendFlowStep::FunctionRelationship>>
IR_lowering::ComputeFrontendRelationships(const DesignFlowStep::RelationshipType relationship_type) const
{
   CustomUnorderedSet<std::pair<FrontendFlowStepType, FunctionRelationship>> relationships;
   switch(relationship_type)
   {
      case(DEPENDENCE_RELATIONSHIP):
      {
         relationships.insert(std::make_pair(BLOCK_FIX, SAME_FUNCTION));
         relationships.insert(std::make_pair(FIX_STRUCTS_PASSED_BY_VALUE, SAME_FUNCTION));
         relationships.insert(std::make_pair(FIX_VDEF, SAME_FUNCTION));
         relationships.insert(std::make_pair(FUNCTION_ANALYSIS, WHOLE_APPLICATION));
         relationships.insert(std::make_pair(HWCALL_INJECTION, SAME_FUNCTION));
         relationships.insert(std::make_pair(REBUILD_INITIALIZATION, SAME_FUNCTION));
         relationships.insert(std::make_pair(REMOVE_CLOBBER_GA, SAME_FUNCTION));
         relationships.insert(std::make_pair(SWITCH_FIX, SAME_FUNCTION));
         break;
      }
      case(INVALIDATION_RELATIONSHIP):
      {
         break;
      }
      case(PRECEDENCE_RELATIONSHIP):
      {
         break;
      }
      default:
         THROW_UNREACHABLE("");
   }
   return relationships;
}

IR_lowering::~IR_lowering() = default;

void IR_lowering::Initialize()
{
   TM = AppM->get_tree_manager();
   tree_man = tree_manipulationRef(new tree_manipulation(TM, parameters, AppM));
}

void IR_lowering::ComputeRelationships(DesignFlowStepSet& relationship,
                                       const DesignFlowStep::RelationshipType relationship_type)
{
   switch(relationship_type)
   {
      case(PRECEDENCE_RELATIONSHIP):
      {
         break;
      }
      case DEPENDENCE_RELATIONSHIP:
      {
         const DesignFlowGraphConstRef design_flow_graph = design_flow_manager.lock()->CGetDesignFlowGraph();
         const auto* technology_flow_step_factory = GetPointer<const TechnologyFlowStepFactory>(
             design_flow_manager.lock()->CGetDesignFlowStepFactory("Technology"));
         const std::string technology_flow_signature =
             TechnologyFlowStep::ComputeSignature(TechnologyFlowStep_Type::LOAD_TECHNOLOGY);
         const vertex technology_flow_step = design_flow_manager.lock()->GetDesignFlowStep(technology_flow_signature);
         const DesignFlowStepRef technology_design_flow_step =
             technology_flow_step ?
                 design_flow_graph->CGetDesignFlowStepInfo(technology_flow_step)->design_flow_step :
                 technology_flow_step_factory->CreateTechnologyFlowStep(TechnologyFlowStep_Type::LOAD_TECHNOLOGY);
         relationship.insert(technology_design_flow_step);
         break;
      }
      case INVALIDATION_RELATIONSHIP:
      {
         break;
      }
      default:
         THROW_UNREACHABLE("");
   }
   FunctionFrontendFlowStep::ComputeRelationships(relationship, relationship_type);
}


enum alg_code
{
   alg_unknown,
   alg_zero,
   alg_m,
   alg_shift,
   alg_add_t_m2,
   alg_sub_t_m2,
   alg_add_factor,
   alg_sub_factor,
   alg_add_t2_m,
   alg_sub_t2_m,
   alg_impossible
};

struct mult_cost
{
   short cost;    
   short latency; 
};

struct algorithm
{
   struct mult_cost cost;
   short ops;
   /* The size of the OP and LOG fields are not directly related to the
      word size, but the worst-case algorithms will be if we have few
      consecutive ones or zeros, i.e., a multiplicand like 10101010101...
      In that case we will generate shift-by-2, add, shift-by-2, add,...,
      in total wordsize operations.  */
   enum alg_code op[64];
   char log[64];
};

#define MULT_COST_LESS(X, Y) ((X).cost < (Y) || ((X).cost == (Y) && (X).latency < (Y)))

#define CHEAPER_MULT_COST(X, Y) ((X).cost < (Y).cost || ((X).cost == (Y).cost && (X).latency < (Y).latency))

static CustomUnorderedMap<std::pair<unsigned int, unsigned long long>, std::pair<enum alg_code, struct mult_cost>>
    alg_hash;

static void synth_mult(struct algorithm& alg_out, unsigned long long t, const struct mult_cost& cost_limit,
                       unsigned long long data_bitsize, tree_managerRef& TM)
{
   int m;
   struct algorithm alg_in, best_alg;
   struct mult_cost best_cost;
   struct mult_cost new_limit;
   short op_cost, op_latency;
   unsigned long long int orig_t = t;
   unsigned long long int q;
   auto maxm = static_cast<int>(std::min(32ull, data_bitsize));
   bool cache_hit = false;
   enum alg_code cache_alg = alg_zero;
   best_alg.cost.cost = std::numeric_limits<short>::max();
   best_alg.cost.latency = std::numeric_limits<short>::max();
   best_alg.ops = 0;

   alg_out.cost.cost = static_cast<short>(cost_limit.cost + 1);
   alg_out.cost.latency = static_cast<short>(cost_limit.latency + 1);

   if(cost_limit.cost < 0 || (cost_limit.cost == 0 && cost_limit.latency <= 0))
   {
      return;
   }

   if(t == 1)
   {
      alg_out.ops = 1;
      alg_out.cost.cost = 0;
      alg_out.cost.latency = 0;
      alg_out.op[0] = alg_m;
      return;
   }

   if(t == 0)
   {
      alg_out.ops = 1;
      alg_out.cost.cost = 0 /*zero_cost[speed]*/;
      alg_out.cost.latency = 0 /*zero_cost[speed]*/;
      alg_out.op[0] = alg_zero;
      return;
   }
   best_cost = cost_limit;
   if(alg_hash.find(std::make_pair(data_bitsize, t)) != alg_hash.end())
   {
      std::pair<enum alg_code, struct mult_cost> res = alg_hash.find(std::make_pair(data_bitsize, t))->second;
      cache_alg = res.first;
      if(cache_alg == alg_impossible)
      {
         if(!CHEAPER_MULT_COST(res.second, cost_limit))
         {
            return;
         }

      }
      else
      {
         if(CHEAPER_MULT_COST(cost_limit, res.second))
         {
            return;
         }
         cache_hit = true;

         switch(cache_alg)
         {
            case alg_shift:
               goto do_alg_shift;

            case alg_add_t_m2:
            case alg_sub_t_m2:
               goto do_alg_addsub_t_m2;

            case alg_add_factor:
            case alg_sub_factor:
               goto do_alg_addsub_factor;

            case alg_add_t2_m:
               goto do_alg_add_t2_m;

            case alg_sub_t2_m:
               goto do_alg_sub_t2_m;
            case alg_impossible:
            case alg_m:
            case alg_unknown:
            case alg_zero:
            default:
               THROW_ERROR("condition not expected");
         }
      }
   }

   if((t & 1) == 0)
   {
   do_alg_shift:
      m = static_cast<int>(floor_log2(t & -t)); /* m = number of low zero bits */
      if(m < maxm)
      {
         q = t >> m;
         /* The function expand_shift will choose between a shift and
                  a sequence of additions, so the observed cost is given as
                  MIN (m * add_cost[speed][mode], shift_cost[speed][mode][m]).  */
         op_cost = static_cast<short>(m * 1 /*add_cost[speed][mode]*/);
         if(0 /*shift_cost[speed][mode][m]*/ < op_cost)
         {
            op_cost = 0 /*shift_cost[speed][mode][m]*/;
         }
         new_limit.cost = static_cast<short>(best_cost.cost - op_cost);
         new_limit.latency = static_cast<short>(best_cost.latency - op_cost);
         synth_mult(alg_in, q, new_limit, data_bitsize, TM);

         alg_in.cost.cost = static_cast<short>(alg_in.cost.cost + op_cost);
         alg_in.cost.latency = static_cast<short>(alg_in.cost.latency + op_cost);
         if(CHEAPER_MULT_COST(alg_in.cost, best_cost))
         {
            best_cost = alg_in.cost;
            std::swap(alg_in, best_alg);
            best_alg.log[best_alg.ops] = static_cast<char>(m);
            best_alg.op[best_alg.ops] = alg_shift;
         }

         if(static_cast<long long int>(orig_t) < 0)
         {
            q = ~(~orig_t >> m);
            op_cost = static_cast<short>(m * 1) /*add_cost[speed][mode]*/;
            if(0 /*shift_cost[speed][mode][m]*/ < op_cost)
            {
               op_cost = 0 /*shift_cost[speed][mode][m]*/;
            }
            new_limit.cost = static_cast<short>(best_cost.cost - op_cost);
            new_limit.latency = static_cast<short>(best_cost.latency - op_cost);
            synth_mult(alg_in, q, new_limit, data_bitsize, TM);

            alg_in.cost.cost = static_cast<short>(alg_in.cost.cost + op_cost);
            alg_in.cost.latency = static_cast<short>(alg_in.cost.latency + op_cost);
            if(CHEAPER_MULT_COST(alg_in.cost, best_cost))
            {
               best_cost = alg_in.cost;
               std::swap(alg_in, best_alg);
               best_alg.log[best_alg.ops] = static_cast<char>(m);
               best_alg.op[best_alg.ops] = alg_shift;
            }
         }
      }
      if(cache_hit)
      {
         goto done;
      }
   }

   if((t & 1) != 0)
   {
      unsigned long long int w;

   do_alg_addsub_t_m2:
      for(w = 1; (w & t) != 0; w <<= 1)
      {
         ;
      }
      if(w == 0 || (w > 2
                    && t != 3))
      {
         op_cost = 1 /*add_cost[speed][mode]*/;
         new_limit.cost = static_cast<short>(best_cost.cost - op_cost);
         new_limit.latency = static_cast<short>(best_cost.latency - op_cost);
         synth_mult(alg_in, t + 1, new_limit, data_bitsize, TM);

         alg_in.cost.cost = static_cast<short>(alg_in.cost.cost + op_cost);
         alg_in.cost.latency = static_cast<short>(alg_in.cost.latency + op_cost);
         if(CHEAPER_MULT_COST(alg_in.cost, best_cost))
         {
            best_cost = alg_in.cost;
            std::swap(alg_in, best_alg);
            best_alg.log[best_alg.ops] = 0;
            best_alg.op[best_alg.ops] = alg_sub_t_m2;
         }
      }
      else
      {
         op_cost = 1 /*add_cost[speed][mode]*/;
         new_limit.cost = static_cast<short>(best_cost.cost - op_cost);
         new_limit.latency = static_cast<short>(best_cost.latency - op_cost);
         synth_mult(alg_in, t - 1, new_limit, data_bitsize, TM);

         alg_in.cost.cost = static_cast<short>(alg_in.cost.cost + op_cost);
         alg_in.cost.latency = static_cast<short>(alg_in.cost.latency + op_cost);
         if(CHEAPER_MULT_COST(alg_in.cost, best_cost))
         {
            best_cost = alg_in.cost;
            std::swap(alg_in, best_alg);
            best_alg.log[best_alg.ops] = 0;
            best_alg.op[best_alg.ops] = alg_add_t_m2;
         }
      }

      m = static_cast<int>(exact_log2(-orig_t + 1));
      if(m >= 0 && m < maxm)
      {
         op_cost = 1 /*shiftsub1_cost[speed][mode][m]*/;
         new_limit.cost = static_cast<short>(best_cost.cost - op_cost);
         new_limit.latency = static_cast<short>(best_cost.latency - op_cost);
         synth_mult(alg_in, static_cast<unsigned long long int>(-orig_t + 1) >> m, new_limit, data_bitsize, TM);

         alg_in.cost.cost = static_cast<short>(alg_in.cost.cost + op_cost);
         alg_in.cost.latency = static_cast<short>(alg_in.cost.latency + op_cost);
         if(CHEAPER_MULT_COST(alg_in.cost, best_cost))
         {
            best_cost = alg_in.cost;
            std::swap(alg_in, best_alg);
            best_alg.log[best_alg.ops] = static_cast<char>(m);
            best_alg.op[best_alg.ops] = alg_sub_t_m2;
         }
      }

      if(cache_hit)
      {
         goto done;
      }
   }

do_alg_addsub_factor:
   for(m = static_cast<int>(floor_log2(t - 1)); m >= 2; m--)
   {
      unsigned long long int d;

      d = (1ULL << m) + 1;
      if(t % d == 0 && t > d && m < maxm && (!cache_hit || cache_alg == alg_add_factor))
      {
         op_cost = 1 /*add_cost[speed][mode]*/ + 0 /*shift_cost[speed][mode][m]*/;
         // if (1/*shiftadd_cost[speed][mode][m]*/ < op_cost)
         //{
         //   op_cost = 1/*shiftadd_cost[speed][mode][m]*/;
         //   op_latency = op_cost;
         //}
         // else
         op_latency = 1 /*add_cost[speed][mode]*/;

         new_limit.cost = static_cast<short>(best_cost.cost - op_cost);
         new_limit.latency = static_cast<short>(best_cost.latency - op_latency);
         synth_mult(alg_in, t / d, new_limit, data_bitsize, TM);

         alg_in.cost.cost = static_cast<short>(alg_in.cost.cost + op_cost);
         alg_in.cost.latency = static_cast<short>(alg_in.cost.latency + op_latency);
         if(alg_in.cost.latency < op_cost)
         {
            alg_in.cost.latency = op_cost;
         }
         if(CHEAPER_MULT_COST(alg_in.cost, best_cost))
         {
            best_cost = alg_in.cost;
            std::swap(alg_in, best_alg);
            best_alg.log[best_alg.ops] = static_cast<char>(m);
            best_alg.op[best_alg.ops] = alg_add_factor;
         }
         break;
      }

      d = (1ULL << m) - 1;
      if(t % d == 0 && t > d && m < maxm && (!cache_hit || cache_alg == alg_sub_factor))
      {
         op_cost = 1 /*add_cost[speed][mode]*/ + 0 /*shift_cost[speed][mode][m]*/;
         // if (1/*shiftsub0_cost[speed][mode][m]*/ < op_cost)
         //{
         //   op_cost = 1/*shiftsub0_cost[speed][mode][m]*/;
         //   op_latency = op_cost;
         //}
         // else
         op_latency = 1 /*add_cost[speed][mode]*/;

         new_limit.cost = static_cast<short>(best_cost.cost - op_cost);
         new_limit.latency = static_cast<short>(best_cost.latency - op_latency);
         synth_mult(alg_in, t / d, new_limit, data_bitsize, TM);

         alg_in.cost.cost = static_cast<short>(alg_in.cost.cost + op_cost);
         alg_in.cost.latency = static_cast<short>(alg_in.cost.latency + op_latency);
         if(alg_in.cost.latency < op_cost)
         {
            alg_in.cost.latency = op_cost;
         }
         if(CHEAPER_MULT_COST(alg_in.cost, best_cost))
         {
            best_cost = alg_in.cost;
            std::swap(alg_in, best_alg);
            best_alg.log[best_alg.ops] = static_cast<char>(m);
            best_alg.op[best_alg.ops] = alg_sub_factor;
         }
         break;
      }
   }
   if(cache_hit)
   {
      goto done;
   }

   if((t & 1) != 0)
   {
   do_alg_add_t2_m:
      q = t - 1;
      q = q & -q;
      m = static_cast<int>(exact_log2(q));
      if(m >= 0 && m < maxm)
      {
         op_cost = 1 /*shiftadd_cost[speed][mode][m]*/;
         new_limit.cost = static_cast<short>(best_cost.cost - op_cost);
         new_limit.latency = static_cast<short>(best_cost.latency - op_cost);
         synth_mult(alg_in, (t - 1) >> m, new_limit, data_bitsize, TM);

         alg_in.cost.cost = static_cast<short>(alg_in.cost.cost + op_cost);
         alg_in.cost.latency = static_cast<short>(alg_in.cost.latency + op_cost);
         if(CHEAPER_MULT_COST(alg_in.cost, best_cost))
         {
            best_cost = alg_in.cost;
            std::swap(alg_in, best_alg);
            best_alg.log[best_alg.ops] = static_cast<char>(m);
            best_alg.op[best_alg.ops] = alg_add_t2_m;
         }
      }
      if(cache_hit)
      {
         goto done;
      }

   do_alg_sub_t2_m:
      q = t + 1;
      q = q & -q;
      m = static_cast<int>(exact_log2(q));
      if(m >= 0 && m < maxm)
      {
         op_cost = 1 /*shiftsub0_cost[speed][mode][m]*/;
         new_limit.cost = static_cast<short>(best_cost.cost - op_cost);
         new_limit.latency = static_cast<short>(best_cost.latency - op_cost);
         synth_mult(alg_in, (t + 1) >> m, new_limit, data_bitsize, TM);

         alg_in.cost.cost = static_cast<short>(alg_in.cost.cost + op_cost);
         alg_in.cost.latency = static_cast<short>(alg_in.cost.latency + op_cost);
         if(CHEAPER_MULT_COST(alg_in.cost, best_cost))
         {
            best_cost = alg_in.cost;
            std::swap(alg_in, best_alg);
            best_alg.log[best_alg.ops] = static_cast<char>(m);
            best_alg.op[best_alg.ops] = alg_sub_t2_m;
         }
      }
      if(cache_hit)
      {
         goto done;
      }
   }

done:
   if(!CHEAPER_MULT_COST(best_cost, cost_limit))
   {
      alg_hash[std::make_pair(data_bitsize, t)] = std::make_pair(alg_impossible, cost_limit);
      return;
   }

   if(!cache_hit)
   {
      mult_cost last_limit = {best_cost.cost, best_cost.latency};
      alg_hash[std::make_pair(data_bitsize, t)] = std::make_pair(best_alg.op[best_alg.ops], last_limit);
   }

   if(best_alg.ops == 64)
   {
      return;
   }

   alg_out = best_alg;
   alg_out.ops = static_cast<short>(best_alg.ops + 1);
}

static bool choose_mult_variant(unsigned long long data_bitsize, long long int val, struct algorithm& alg,
                                enum mult_variant& variant, short int Mult_cost, tree_managerRef& TM)
{
   struct algorithm alg2;
   struct mult_cost limit;
   short int op_cost;

   if(Mult_cost < 0)
   {
      return false;
   }

   op_cost = static_cast<short>(2 * data_bitsize * 1 /*add_cost[speed][mode]*/);
   if(Mult_cost > op_cost)
   {
      Mult_cost = op_cost;
   }

   variant = basic_variant;
   limit.cost = Mult_cost;
   limit.latency = Mult_cost;
   synth_mult(alg, static_cast<unsigned long long int>(val), limit, data_bitsize, TM);

   /* This works only if the inverted value actually fits in an
      `unsigned int' */
   if(8 * sizeof(int) >= data_bitsize)
   {
      op_cost = 1 /*neg_cost[speed][mode]*/;
      if(MULT_COST_LESS(alg.cost, Mult_cost))
      {
         limit.cost = static_cast<short>(alg.cost.cost - op_cost);
         limit.latency = static_cast<short>(alg.cost.latency - op_cost);
      }
      else
      {
         limit.cost = static_cast<short>(Mult_cost - op_cost);
         limit.latency = static_cast<short>(Mult_cost - op_cost);
      }

      synth_mult(alg2, static_cast<unsigned long long int>(-val), limit, data_bitsize, TM);
      alg2.cost.cost = static_cast<short>(alg2.cost.cost + op_cost);
      alg2.cost.latency = static_cast<short>(alg2.cost.latency + op_cost);
      if(CHEAPER_MULT_COST(alg2.cost, alg.cost))
      {
         alg = alg2, variant = negate_variant;
      }
   }

   /* This proves very useful for division-by-constant.  */
   op_cost = 1 /*add_cost[speed][mode]*/;
   if(MULT_COST_LESS(alg.cost, Mult_cost))
   {
      limit.cost = static_cast<short>(alg.cost.cost - op_cost);
      limit.latency = static_cast<short>(alg.cost.latency - op_cost);
   }
   else
   {
      limit.cost = static_cast<short>(Mult_cost - op_cost);
      limit.latency = static_cast<short>(Mult_cost - op_cost);
   }

   synth_mult(alg2, static_cast<unsigned long long int>(val - 1), limit, data_bitsize, TM);
   alg2.cost.cost = static_cast<short>(alg2.cost.cost + op_cost);
   alg2.cost.latency = static_cast<short>(alg2.cost.latency + op_cost);
   if(CHEAPER_MULT_COST(alg2.cost, alg.cost))
   {
      alg = alg2, variant = add_variant;
   }

   return MULT_COST_LESS(alg.cost, Mult_cost);
}

tree_nodeRef IR_lowering::expand_mult_const(const tree_nodeRef& op0, unsigned long long int ASSERT_PARAMETER(val),
                                            const struct algorithm& alg, enum mult_variant& variant,
                                            const tree_nodeRef& stmt, const blocRef& block, const tree_nodeRef& type,
                                            const std::string& srcp_default)
{
   long long int val_so_far = 0;
   tree_nodeRef accum, tem;
   int opno;
#if HAVE_ASSERTS
   auto data_bitsize = tree_helper::Size(tree_helper::CGetType(type));
   auto data_mask = data_bitsize >= 64 ? ~0ULL : (1ULL << data_bitsize) - 1;
#endif
   tree_nodeRef tem_ga;
   tree_nodeRef COST0 = TM->CreateUniqueIntegerCst(0, type);
   INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Expanding " + op0->ToString());

   /* ACCUM starts out either as OP0 or as a zero, depending on
      the first operation.  */

   if(alg.op[0] == alg_zero)
   {
      accum = COST0;
      val_so_far = 0;
   }
   else if(alg.op[0] == alg_m)
   {
      accum = op0;
      val_so_far = 1;
   }
   else
   {
      THROW_ERROR("condition not expected");
   }

   for(opno = 1; opno < alg.ops; opno++)
   {
      auto log = alg.log[opno];
      tree_nodeRef log_node;

      if(log == 0)
      {
         log_node = COST0;
      }
      else
      {
         log_node = TM->CreateUniqueIntegerCst(static_cast<long long int>(log), type);
      }

      switch(alg.op[opno])
      {
         case alg_shift:
            tem = tree_man->create_binary_operation(type, accum, log_node, srcp_default, lshift_expr_K);
            tem_ga = tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), tem, function_id, srcp_default);
            block->PushBefore(tem_ga, stmt, AppM);
            accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            val_so_far <<= log;
            break;

         case alg_add_t_m2:
            if(log_node != COST0)
            {
               tem = tree_man->create_binary_operation(type, op0, log_node, srcp_default, lshift_expr_K);
               tem_ga =
                   tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), tem, function_id, srcp_default);
               block->PushBefore(tem_ga, stmt, AppM);
               tem = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            }
            else
            {
               tem = op0;
            }
            if(accum != COST0)
            {
               accum = tree_man->create_binary_operation(type, accum, tem, srcp_default, plus_expr_K);
               tem_ga =
                   tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), accum, function_id, srcp_default);
               block->PushBefore(tem_ga, stmt, AppM);
               accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            }
            else
            {
               accum = tem;
            }
            val_so_far += 1LL << log;
            break;

         case alg_sub_t_m2:
            if(log_node != COST0)
            {
               tem = tree_man->create_binary_operation(type, op0, log_node, srcp_default, lshift_expr_K);
               tem_ga =
                   tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), tem, function_id, srcp_default);
               block->PushBefore(tem_ga, stmt, AppM);
               tem = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            }
            else
            {
               tem = op0;
            }
            if(accum != COST0)
            {
               accum = tree_man->create_binary_operation(type, accum, tem, srcp_default, minus_expr_K);
            }
            else
            {
               accum = tree_man->create_unary_operation(type, tem, srcp_default, negate_expr_K);
            }
            tem_ga =
                tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), accum, function_id, srcp_default);
            block->PushBefore(tem_ga, stmt, AppM);
            accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            val_so_far -= 1LL << log;
            break;

         case alg_add_t2_m:
            if(log_node != COST0 && accum != COST0)
            {
               accum = tree_man->create_binary_operation(type, accum, log_node, srcp_default, lshift_expr_K);
               tem_ga =
                   tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), accum, function_id, srcp_default);
               block->PushBefore(tem_ga, stmt, AppM);
               accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            }
            if(accum != COST0)
            {
               accum = tree_man->create_binary_operation(type, accum, op0, srcp_default, plus_expr_K);
               tem_ga =
                   tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), accum, function_id, srcp_default);
               block->PushBefore(tem_ga, stmt, AppM);
               accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            }
            else
            {
               accum = op0;
            }
            val_so_far = (val_so_far << log) + 1;
            break;

         case alg_sub_t2_m:
            if(log_node != COST0 && accum != COST0)
            {
               accum = tree_man->create_binary_operation(type, accum, log_node, srcp_default, lshift_expr_K);
               tem_ga =
                   tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), accum, function_id, srcp_default);
               block->PushBefore(tem_ga, stmt, AppM);
               accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            }
            if(accum != COST0)
            {
               accum = tree_man->create_binary_operation(type, accum, op0, srcp_default, minus_expr_K);
            }
            else
            {
               accum = tree_man->create_unary_operation(type, op0, srcp_default, negate_expr_K);
            }
            tem_ga =
                tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), accum, function_id, srcp_default);
            block->PushBefore(tem_ga, stmt, AppM);
            accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            val_so_far = (val_so_far << log) - 1;
            break;

         case alg_add_factor:
            if(log_node != COST0 && accum != COST0)
            {
               tem = tree_man->create_binary_operation(type, accum, log_node, srcp_default, lshift_expr_K);
               tem_ga =
                   tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), tem, function_id, srcp_default);
               block->PushBefore(tem_ga, stmt, AppM);
               tem = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            }
            else
            {
               tem = accum;
            }
            if(accum != COST0)
            {
               accum = tree_man->create_binary_operation(type, accum, tem, srcp_default, plus_expr_K);
               tem_ga =
                   tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), accum, function_id, srcp_default);
               block->PushBefore(tem_ga, stmt, AppM);
               accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            }
            else
            {
               accum = tem;
            }
            val_so_far += val_so_far << log;
            break;

         case alg_sub_factor:
            if(log_node != COST0 && accum != COST0)
            {
               tem = tree_man->create_binary_operation(type, accum, log_node, srcp_default, lshift_expr_K);
               tem_ga =
                   tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), tem, function_id, srcp_default);
               block->PushBefore(tem_ga, stmt, AppM);
               tem = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            }
            else
            {
               tem = accum;
            }
            if(accum != COST0)
            {
               accum = tree_man->create_binary_operation(type, tem, accum, srcp_default, minus_expr_K);
               tem_ga =
                   tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), accum, function_id, srcp_default);
               block->PushBefore(tem_ga, stmt, AppM);
               accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
            }
            else
            {
               accum = tem;
            }
            val_so_far = (val_so_far << log) - val_so_far;
            break;
         case alg_impossible:
         case alg_m:
         case alg_unknown:
         case alg_zero:
         default:
            THROW_UNREACHABLE("");
      }
   }

   if(variant == negate_variant)
   {
#if HAVE_ASSERTS
      val_so_far = -val_so_far;
#endif
      tem = tree_man->create_unary_operation(type, accum, srcp_default, negate_expr_K);
      tem_ga = tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), tem, function_id, srcp_default);
      block->PushBefore(tem_ga, stmt, AppM);
      accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
   }
   else if(variant == add_variant)
   {
#if HAVE_ASSERTS
      val_so_far = val_so_far + 1;
#endif
      tem = tree_man->create_binary_operation(type, accum, op0, srcp_default, plus_expr_K);
      tem_ga = tree_man->CreateGimpleAssign(type, tree_nodeRef(), tree_nodeRef(), tem, function_id, srcp_default);
      block->PushBefore(tem_ga, stmt, AppM);
      accum = GetPointer<gimple_assign>(GET_NODE(tem_ga))->op0;
   }

#if HAVE_ASSERTS
   val = val & data_mask;
   val_so_far = val_so_far & static_cast<long long int>(data_mask);
#endif
   THROW_ASSERT(val == static_cast<unsigned long long int>(val_so_far), "unexpected difference");
   INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Expanded " + op0->ToString());

   return accum;
}

tree_nodeRef IR_lowering::expand_smod_pow2(const tree_nodeRef& op0, unsigned long long int d, const tree_nodeRef& stmt,
                                           const blocRef& block, const tree_nodeRef& type,
                                           const std::string& srcp_default)
{
   unsigned long long int masklow;
   const auto logd = floor_log2(d);
   const auto bt = tree_man->GetBooleanType();

   const auto const0 = TM->CreateUniqueIntegerCst(0, type);
   const auto constm1 = TM->CreateUniqueIntegerCst(-1, type);
   const auto cond_op0 = tree_man->create_binary_operation(bt, op0, const0, srcp_default, lt_expr_K);
   const auto signmask_ga = tree_man->CreateGimpleAssign(
       bt, TM->CreateUniqueIntegerCst(0, bt), TM->CreateUniqueIntegerCst(1, bt), cond_op0, function_id, srcp_default);
   AppM->RegisterTransformation(GetName(), signmask_ga);
   block->PushBefore(signmask_ga, stmt, AppM);
   const auto cond_expr0 = tree_man->create_ternary_operation(
       type, GetPointer<gimple_assign>(GET_NODE(signmask_ga))->op0, constm1, const0, srcp_default, cond_expr_K);

   const auto signmask_condexpr =
       tree_man->CreateGimpleAssign(type, nullptr, nullptr, cond_expr0, function_id, srcp_default);

   AppM->RegisterTransformation(GetName(), signmask_condexpr);
   block->PushBefore(signmask_condexpr, stmt, AppM);

   auto signmask_var = GetPointer<gimple_assign>(GET_NODE(signmask_condexpr))->op0;
   const auto size = tree_helper::Size(type);

   if(logd > 63 || size < logd)
   {
      THROW_ERROR("unexpected condition");
   }
   masklow = (1ULL << logd) - 1;
   const auto Constmasklow = TM->CreateUniqueIntegerCst(static_cast<long long int>(masklow), type);

   if(!tree_helper::IsUnsignedIntegerType(type))
   {
      auto unsignedType = tree_man->CreateUnsigned(GET_NODE(type));
      const auto constshift = TM->CreateUniqueIntegerCst(static_cast<long long>(size - logd), unsignedType);
      auto ga_nop = tree_man->CreateNopExpr(signmask_var, unsignedType, tree_nodeRef(), tree_nodeRef(), function_id);
      auto nop_vd = GetPointer<gimple_assign>(GET_NODE(ga_nop))->op0;
      block->PushBefore(ga_nop, stmt, AppM);
      auto temp = tree_man->create_binary_operation(unsignedType, nop_vd, constshift, srcp_default, rshift_expr_K);
      auto temp_ga = tree_man->CreateGimpleAssign(unsignedType, nullptr, nullptr, temp, function_id, srcp_default);
      AppM->RegisterTransformation(GetName(), temp_ga);
      block->PushBefore(temp_ga, stmt, AppM);
      nop_vd = GetPointer<gimple_assign>(GET_NODE(temp_ga))->op0;
      ga_nop = tree_man->CreateNopExpr(nop_vd, type, tree_nodeRef(), tree_nodeRef(), function_id);
      block->PushBefore(ga_nop, stmt, AppM);
      signmask_var = GetPointer<gimple_assign>(GET_NODE(ga_nop))->op0;
   }
   else
   {
      const auto constshift = TM->CreateUniqueIntegerCst(static_cast<long long>(size - logd), type);
      auto temp = tree_man->create_binary_operation(type, signmask_var, constshift, srcp_default, rshift_expr_K);
      auto temp_ga = tree_man->CreateGimpleAssign(type, nullptr, nullptr, temp, function_id, srcp_default);
      AppM->RegisterTransformation(GetName(), temp_ga);
      block->PushBefore(temp_ga, stmt, AppM);
      signmask_var = GetPointer<gimple_assign>(GET_NODE(temp_ga))->op0;
   }

   auto temp = tree_man->create_binary_operation(type, op0, signmask_var, srcp_default, plus_expr_K);
   auto temp_ga = tree_man->CreateGimpleAssign(type, nullptr, nullptr, temp, function_id, srcp_default);
   AppM->RegisterTransformation(GetName(), temp_ga);
   block->PushBefore(temp_ga, stmt, AppM);
   auto temp_var = GetPointer<gimple_assign>(GET_NODE(temp_ga))->op0;

   temp = tree_man->create_binary_operation(type, temp_var, Constmasklow, srcp_default, bit_and_expr_K);
   temp_ga = tree_man->CreateGimpleAssign(type, nullptr, nullptr, temp, function_id, srcp_default);
   AppM->RegisterTransformation(GetName(), temp_ga);
   block->PushBefore(temp_ga, stmt, AppM);
   temp_var = GetPointer<gimple_assign>(GET_NODE(temp_ga))->op0;

   return tree_man->create_binary_operation(type, temp_var, signmask_var, srcp_default, minus_expr_K);
}

tree_nodeRef IR_lowering::expand_sdiv_pow2(const tree_nodeRef& op0, unsigned long long int d, const tree_nodeRef& stmt,
                                           const blocRef& block, const tree_nodeRef& type,
                                           const std::string& srcp_default)
{
   const auto logd = floor_log2(d);
   const auto bt = tree_man->GetBooleanType();
   const auto const0 = TM->CreateUniqueIntegerCst(0, type);

   const auto cond_op0 = tree_man->create_binary_operation(bt, op0, const0, srcp_default, lt_expr_K);
   const auto cond_op0_ga = tree_man->CreateGimpleAssign(
       bt, TM->CreateUniqueIntegerCst(0, bt), TM->CreateUniqueIntegerCst(1, bt), cond_op0, function_id, srcp_default);
   block->PushBefore(cond_op0_ga, stmt, AppM);
   const auto cond_op0_ga_var = GetPointer<gimple_assign>(GET_NODE(cond_op0_ga))->op0;
   tree_nodeRef t_ga;
   tree_nodeRef t2_ga;

   if(d == 2)
   {
      const auto const1 = TM->CreateUniqueIntegerCst(1, type);
      const auto cond_op =
          tree_man->create_ternary_operation(type, cond_op0_ga_var, const1, const0, srcp_default, cond_expr_K);
      t_ga = tree_man->CreateGimpleAssign(type, nullptr, nullptr, cond_op, function_id, srcp_default);
      block->PushBefore(t_ga, stmt, AppM);
      const auto cond_ga_var = GetPointer<gimple_assign>(GET_NODE(t_ga))->op0;

      const auto sum_expr = tree_man->create_binary_operation(type, op0, cond_ga_var, srcp_default, plus_expr_K);
      t2_ga = tree_man->CreateGimpleAssign(type, nullptr, nullptr, sum_expr, function_id, srcp_default);
   }
   else
   {
      const auto d_m1 = TM->CreateUniqueIntegerCst(static_cast<long long int>(d - 1), type);
      const auto t_expr = tree_man->create_binary_operation(type, op0, d_m1, srcp_default, plus_expr_K);
      t_ga = tree_man->CreateGimpleAssign(type, nullptr, nullptr, t_expr, function_id, srcp_default);
      block->PushBefore(t_ga, stmt, AppM);
      const auto t_ga_var = GetPointer<gimple_assign>(GET_NODE(t_ga))->op0;

      const auto cond_op =
          tree_man->create_ternary_operation(type, cond_op0_ga_var, t_ga_var, op0, srcp_default, cond_expr_K);
      t2_ga = tree_man->CreateGimpleAssign(type, nullptr, nullptr, cond_op, function_id, srcp_default);
   }
   block->PushBefore(t2_ga, stmt, AppM);

   const auto t2_ga_var = GetPointer<gimple_assign>(GET_NODE(t2_ga))->op0;
   const auto logdConst = TM->CreateUniqueIntegerCst(static_cast<long long>(logd), type);
   return tree_man->create_binary_operation(type, t2_ga_var, logdConst, srcp_default, rshift_expr_K);
}

tree_nodeRef IR_lowering::expand_MC(const tree_nodeRef& op0, const integer_cst* ic_node, const tree_nodeRef& old_target,
                                    const tree_nodeRef& stmt, const blocRef& block, const tree_nodeRef& type_expr,
                                    const std::string& srcp_default)
{
   if(!AppM->ApplyNewTransformation())
   {
      return old_target;
   }
   long long int ext_op1 = static_cast<long long>(tree_helper::get_integer_cst_value(ic_node));
   short int mult_plus_ratio = 3;
   auto data_bitsize = tree_helper::Size(op0);
   auto typeSize = tree_helper::Size(type_expr);
   if(typeSize < 64)
   {
      ext_op1 <<= 64 - typeSize;
      ext_op1 >>= 64 - typeSize;
   }
   if(GetPointer<HLS_manager>(AppM))
   {
      const HLS_deviceRef HLS_D = GetPointer<HLS_manager>(AppM)->get_HLS_device();
      bool use64bitMul = false;
      if(HLS_D->has_parameter("use_soft_64_mul") && HLS_D->get_parameter<size_t>("use_soft_64_mul"))
      {
         use64bitMul = true;
      }
      const technology_managerRef TechManager = HLS_D->get_technology_manager();
      auto fu_prec = std::max(8ull, ceil_pow2(data_bitsize));
      if(fu_prec >= 64 && use64bitMul)
      {
         fu_prec = 32;
      }
      auto component_name_mult =
          MULTIPLIER_STD + std::string("_") + STR(fu_prec) + "_" + STR(fu_prec) + "_" + STR(fu_prec) + "_0";
      technology_nodeRef mult_f_unit = TechManager->get_fu(component_name_mult, LIBRARY_STD_FU);
      THROW_ASSERT(mult_f_unit, "missing component: " + component_name_mult);
      auto* mult_fu = GetPointer<functional_unit>(mult_f_unit);
      technology_nodeRef mult_op_node = mult_fu->get_operation("mult_expr");
      THROW_ASSERT(mult_op_node, "missing mult_expr from " + component_name_mult);
      auto* mult_op = GetPointer<operation>(mult_op_node);
      double mult_delay = mult_op->time_m->get_execution_time();
      auto component_name_add = ADDER_STD + std::string("_") + STR(fu_prec) + "_" + STR(fu_prec) + "_" + STR(fu_prec);
      technology_nodeRef add_f_unit = TechManager->get_fu(component_name_add, LIBRARY_STD_FU);
      THROW_ASSERT(add_f_unit, "missing component: " + component_name_add);
      auto* add_fu = GetPointer<functional_unit>(add_f_unit);
      technology_nodeRef add_op_node = add_fu->get_operation("plus_expr");
      THROW_ASSERT(add_op_node, "missing plus_expr from " + component_name_add);
      auto* add_op = GetPointer<operation>(add_op_node);
      double add_delay = add_op->time_m->get_execution_time();
      mult_plus_ratio = static_cast<short int>(ceil(mult_delay / add_delay));
   }

   if(ext_op1 == 0)
   {
      return TM->CreateUniqueIntegerCst(0, type_expr);
   }
   else if(ext_op1 == 1)
   {
      return op0;
   }
   else if(ext_op1 == -1)
   {
      return tree_man->create_unary_operation(type_expr, op0, srcp_default, negate_expr_K);
   }
   else
   {
      if(ext_op1 < 0)
      {
         struct algorithm alg;
         enum mult_variant variant;
         short int max_cost =
             mult_plus_ratio; // static_cast<short
                              // int>(tree_helper::Size(tree_helper::CGetType(type_expr))/mult_cost_divisor);
         if(choose_mult_variant(data_bitsize, -ext_op1, alg, variant, max_cost, TM))
         {
            tree_nodeRef temp_expr = expand_mult_const(op0, static_cast<unsigned long long int>(-ext_op1), alg, variant,
                                                       stmt, block, type_expr, srcp_default);
            tree_nodeRef temp_expr_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(),
                                                                     temp_expr, function_id, srcp_default);
            block->PushBefore(temp_expr_ga, stmt, AppM);
            tree_nodeRef temp_expr_var = GetPointer<gimple_assign>(GET_NODE(temp_expr_ga))->op0;
            return tree_man->create_unary_operation(type_expr, temp_expr_var, srcp_default, negate_expr_K);
         }
         else
         {
            return old_target;
         }
      }
      else
      {
         auto coeff = static_cast<unsigned long long int>(ext_op1);
         if(EXACT_POWER_OF_2_OR_ZERO_P(coeff))
         {
            const auto l_shift = floor_log2(coeff);
            const auto l_shift_node = TM->CreateUniqueIntegerCst(static_cast<long long int>(l_shift), type_expr);
            return tree_man->create_binary_operation(type_expr, op0, l_shift_node, srcp_default, lshift_expr_K);
         }
         else
         {
            struct algorithm alg;
            enum mult_variant variant;
            short int max_cost =
                mult_plus_ratio; // static_cast<short
                                 // int>(tree_helper::Size(tree_helper::CGetType(type_expr))/mult_cost_divisor);

            if(choose_mult_variant(data_bitsize, static_cast<long long int>(coeff), alg, variant, max_cost, TM))
            {
               return expand_mult_const(op0, coeff, alg, variant, stmt, block, type_expr, srcp_default);
            }
            else
            {
               return old_target;
            }
         }
      }
   }
}

bool IR_lowering::expand_target_mem_ref(target_mem_ref461* tmr, const tree_nodeRef& stmt, const blocRef& block,
                                        const std::string& srcp_default, bool temp_addr)
{
   tree_nodeRef accum;
   tree_nodeRef type_sum;
   unsigned int params = 0;
   bool changed = false;

   if(tmr->idx)
   {
      ++params;
   }
   if(tmr->step)
   {
      ++params;
   }
   if(tmr->offset)
   {
      ++params;
   }
   if(tmr->idx2)
   {
      ++params;
   }

   if(params < 1)
   {
      return changed; 
   }

   if(tmr->idx)
   {
      if(tmr->step)
      {
         auto* ic_step_node = GetPointer<integer_cst>(GET_NODE(tmr->step));
         type_sum = ic_step_node->type;
         accum = expand_MC(tmr->idx, ic_step_node, tree_nodeRef(), stmt, block, type_sum, srcp_default);
         if(accum)
         {
            tree_nodeRef t_ga = tree_man->CreateGimpleAssign(type_sum, tree_nodeRef(), tree_nodeRef(), accum,
                                                             function_id, srcp_default);
            block->PushBefore(t_ga, stmt, AppM);
            INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(t_ga)->ToString());
            accum = GetPointer<gimple_assign>(GET_NODE(t_ga))->op0;
         }
         else
         {
            tree_nodeRef t_expr =
                tree_man->create_binary_operation(type_sum, tmr->idx, tmr->step, srcp_default, mult_expr_K);
            tree_nodeRef t_ga = tree_man->CreateGimpleAssign(type_sum, tree_nodeRef(), tree_nodeRef(), t_expr,
                                                             function_id, srcp_default);
            block->PushBefore(t_ga, stmt, AppM);
            INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(t_ga)->ToString());
            accum = GetPointer<gimple_assign>(GET_NODE(t_ga))->op0;
         }
         tmr->step = tree_nodeRef();
      }
      else
      {
         accum = tmr->idx;
      }
      tmr->idx = tree_nodeRef();
      changed = true;
   }
   if(tmr->offset)
   {
      if(tree_helper::GetConstValue(tmr->offset) != 0)
      {
         if(!type_sum)
         {
            type_sum = tree_man->GetSizeType();
         }

         const auto ne = tree_man->create_unary_operation(type_sum, tmr->offset, srcp_default, nop_expr_K);
         const auto casted_offset_ga =
             tree_man->CreateGimpleAssign(type_sum, tree_nodeRef(), tree_nodeRef(), ne, function_id, srcp_default);
         block->PushBefore(casted_offset_ga, stmt, AppM);
         INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
                        "---adding statement " + GET_NODE(casted_offset_ga)->ToString());
         const auto casted_offset_var = GetPointerS<gimple_assign>(GET_NODE(casted_offset_ga))->op0;

         if(accum)
         {
            const auto t_expr =
                tree_man->create_binary_operation(type_sum, casted_offset_var, accum, srcp_default, plus_expr_K);
            const auto t_ga = tree_man->CreateGimpleAssign(type_sum, tree_nodeRef(), tree_nodeRef(), t_expr,
                                                           function_id, srcp_default);
            block->PushBefore(t_ga, stmt, AppM);
            INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(t_ga)->ToString());
            accum = GetPointerS<gimple_assign>(GET_NODE(t_ga))->op0;
         }
         else
         {
            accum = casted_offset_var;
         }
      }
      tmr->offset = tree_nodeRef();
      changed = true;
   }

   if(tmr->idx2)
   {
      if(!type_sum)
      {
         type_sum = tree_man->GetSizeType();
      }
      auto type_index = tree_helper::get_type_index(TM, GET_INDEX_NODE(tmr->idx2));
      if(type_index != GET_INDEX_NODE(type_sum))
      {
         tree_nodeRef ne = tree_man->create_unary_operation(type_sum, tmr->idx2, srcp_default, nop_expr_K);
         tree_nodeRef casted_idx2_ga =
             tree_man->CreateGimpleAssign(type_sum, tree_nodeRef(), tree_nodeRef(), ne, function_id, srcp_default);
         block->PushBefore(casted_idx2_ga, stmt, AppM);
         INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
                        "---adding statement " + GET_NODE(casted_idx2_ga)->ToString());
         tree_nodeRef casted_idx2_var = GetPointer<gimple_assign>(GET_NODE(casted_idx2_ga))->op0;
         if(accum)
         {
            tree_nodeRef t_expr =
                tree_man->create_binary_operation(type_sum, accum, casted_idx2_var, srcp_default, plus_expr_K);
            tree_nodeRef t_ga = tree_man->CreateGimpleAssign(type_sum, tree_nodeRef(), tree_nodeRef(), t_expr,
                                                             function_id, srcp_default);
            block->PushBefore(t_ga, stmt, AppM);
            INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(t_ga)->ToString());
            accum = GetPointer<gimple_assign>(GET_NODE(t_ga))->op0;
         }
         else
         {
            accum = casted_idx2_var;
         }
      }
      else if(accum)
      {
         tree_nodeRef t_expr = tree_man->create_binary_operation(type_sum, accum, tmr->idx2, srcp_default, plus_expr_K);
         tree_nodeRef t_ga =
             tree_man->CreateGimpleAssign(type_sum, tree_nodeRef(), tree_nodeRef(), t_expr, function_id, srcp_default);
         block->PushBefore(t_ga, stmt, AppM);
         INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(t_ga)->ToString());
         accum = GetPointer<gimple_assign>(GET_NODE(t_ga))->op0;
      }
      else
      {
         accum = tmr->idx2;
      }
      changed = true;
      tmr->idx2 = tree_nodeRef();
   }

   if(GET_NODE(tmr->base)->get_kind() == addr_expr_K)
   {
      auto* ae = GetPointer<addr_expr>(GET_NODE(tmr->base));
      tree_nodeRef ae_expr = tree_man->create_unary_operation(ae->type, ae->op, srcp_default,
                                                              addr_expr_K); 
      tree_nodeRef ae_ga =
          tree_man->CreateGimpleAssign(ae->type, tree_nodeRef(), tree_nodeRef(), ae_expr, function_id, srcp_default);
      tree_nodeRef ae_vd = GetPointer<gimple_assign>(GET_NODE(ae_ga))->op0;
      GetPointer<gimple_assign>(GET_NODE(ae_ga))->temporary_address = temp_addr;
      block->PushBefore(ae_ga, stmt, AppM);
      INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(ae_ga)->ToString());
      tmr->base = ae_vd;
      changed = true;
   }
   if(accum)
   {
      tree_nodeRef type = tmr->type;
      tree_nodeRef pt = tree_man->GetPointerType(type, 8);

      tree_nodeRef ppe_expr =
          tree_man->create_binary_operation(pt, tmr->base, accum, srcp_default, pointer_plus_expr_K);
      tree_nodeRef ppe_ga =
          tree_man->CreateGimpleAssign(pt, tree_nodeRef(), tree_nodeRef(), ppe_expr, function_id, srcp_default);
      tree_nodeRef ppe_vd = GetPointer<gimple_assign>(GET_NODE(ppe_ga))->op0;
      tmr->base = ppe_vd;
      GetPointer<gimple_assign>(GET_NODE(ppe_ga))->temporary_address = temp_addr;
      block->PushBefore(ppe_ga, stmt, AppM);
      INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(ppe_ga)->ToString());
   }

   return changed;
}

tree_nodeRef IR_lowering::expand_mult_highpart(const tree_nodeRef& op0, unsigned long long int ml,
                                               const tree_nodeRef& type_expr, int data_bitsize,
                                               const std::list<tree_nodeRef>::const_iterator it_los,
                                               const blocRef& block, const std::string& srcp_default)
{
   int half_data_bitsize = data_bitsize / 2;
   tree_nodeRef mask_node =
       TM->CreateUniqueIntegerCst(static_cast<long long int>((1LL << half_data_bitsize) - 1), type_expr);
   tree_nodeRef half_data_bitsize_node =
       TM->CreateUniqueIntegerCst(static_cast<long long int>(half_data_bitsize), type_expr);

   tree_nodeRef u0_expr = tree_man->create_binary_operation(type_expr, op0, mask_node, srcp_default, bit_and_expr_K);
   tree_nodeRef u0_ga =
       tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), u0_expr, function_id, srcp_default);
   block->PushBefore(u0_ga, *it_los, AppM);
   tree_nodeRef u0_ga_var = GetPointer<gimple_assign>(GET_NODE(u0_ga))->op0;

   tree_nodeRef u1_expr =
       tree_man->create_binary_operation(type_expr, op0, half_data_bitsize_node, srcp_default, rshift_expr_K);
   tree_nodeRef u1_ga =
       tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), u1_expr, function_id, srcp_default);
   block->PushBefore(u1_ga, *it_los, AppM);
   tree_nodeRef u1_ga_var = GetPointer<gimple_assign>(GET_NODE(u1_ga))->op0;

   long long int v0 = static_cast<long long int>(ml) & ((1LL << half_data_bitsize) - 1);
   long long int v1;
   bool unsignedp = tree_helper::is_unsigned(TM, GET_INDEX_NODE(type_expr));
   if(unsignedp)
   {
      v1 = static_cast<long long int>(ml >> half_data_bitsize);
   }
   else
   {
      v1 = static_cast<long long int>(ml) >> half_data_bitsize;
   }

   tree_nodeRef u0v0_ga_var;
   tree_nodeRef v0_node;
   tree_nodeRef v1_node;
   if(v0 != 0)
   {
      if(v0 == 1)
      {
         u0v0_ga_var = u0_ga_var;
      }
      else
      {
         v0_node = TM->CreateUniqueIntegerCst(static_cast<long long int>(v0), type_expr);
         tree_nodeRef u0v0_expr =
             tree_man->create_binary_operation(type_expr, u0_ga_var, v0_node, srcp_default, mult_expr_K);
         tree_nodeRef u0v0_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), u0v0_expr,
                                                             function_id, srcp_default);
         block->PushBefore(u0v0_ga, *it_los, AppM);
         u0v0_ga_var = GetPointer<gimple_assign>(GET_NODE(u0v0_ga))->op0;
      }
   }
   tree_nodeRef u0v0h_ga_var;
   if(u0v0_ga_var)
   {
      tree_nodeRef u0v0h_expr = tree_man->create_binary_operation(type_expr, u0v0_ga_var, half_data_bitsize_node,
                                                                  srcp_default, rshift_expr_K);
      tree_nodeRef u0v0h_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), u0v0h_expr,
                                                           function_id, srcp_default);
      block->PushBefore(u0v0h_ga, *it_los, AppM);
      u0v0h_ga_var = GetPointer<gimple_assign>(GET_NODE(u0v0h_ga))->op0;
   }
   tree_nodeRef u0v0hU_ga_var;
   if(u0v0h_ga_var && !unsignedp)
   {
      tree_nodeRef u0v0hU_expr =
          tree_man->create_binary_operation(type_expr, u0v0h_ga_var, mask_node, srcp_default, bit_and_expr_K);
      tree_nodeRef u0v0hU_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), u0v0hU_expr,
                                                            function_id, srcp_default);
      block->PushBefore(u0v0hU_ga, *it_los, AppM);
      u0v0hU_ga_var = GetPointer<gimple_assign>(GET_NODE(u0v0hU_ga))->op0;
   }
   else
   {
      u0v0hU_ga_var = u0v0h_ga_var;
   }
   tree_nodeRef u1v0_ga_var;
   if(v0 != 0)
   {
      if(v0 == 1)
      {
         u1v0_ga_var = u1_ga_var;
      }
      else
      {
         tree_nodeRef u1v0_expr =
             tree_man->create_binary_operation(type_expr, u1_ga_var, v0_node, srcp_default, mult_expr_K);
         tree_nodeRef u1v0_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), u1v0_expr,
                                                             function_id, srcp_default);
         block->PushBefore(u1v0_ga, *it_los, AppM);
         u1v0_ga_var = GetPointer<gimple_assign>(GET_NODE(u1v0_ga))->op0;
      }
   }
   tree_nodeRef u0v0hu1v0_ga_var;
   if(u0v0hU_ga_var)
   {
      THROW_ASSERT(u1v0_ga_var, "unexpected condition");
      tree_nodeRef u0v0hu1v0_expr =
          tree_man->create_binary_operation(type_expr, u0v0hU_ga_var, u1v0_ga_var, srcp_default, plus_expr_K);
      tree_nodeRef u0v0hu1v0_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(),
                                                               u0v0hu1v0_expr, function_id, srcp_default);
      block->PushBefore(u0v0hu1v0_ga, *it_los, AppM);
      u0v0hu1v0_ga_var = GetPointer<gimple_assign>(GET_NODE(u0v0hu1v0_ga))->op0;
   }
   tree_nodeRef w1_ga_var;
   if(u0v0hu1v0_ga_var)
   {
      tree_nodeRef w1_expr =
          tree_man->create_binary_operation(type_expr, u0v0hu1v0_ga_var, mask_node, srcp_default, bit_and_expr_K);
      tree_nodeRef w1_ga =
          tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), w1_expr, function_id, srcp_default);
      block->PushBefore(w1_ga, *it_los, AppM);
      w1_ga_var = GetPointer<gimple_assign>(GET_NODE(w1_ga))->op0;
   }

   tree_nodeRef w2_ga_var;
   if(u0v0hu1v0_ga_var)
   {
      tree_nodeRef w2_expr = tree_man->create_binary_operation(type_expr, u0v0hu1v0_ga_var, half_data_bitsize_node,
                                                               srcp_default, rshift_expr_K);
      tree_nodeRef w2_ga =
          tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), w2_expr, function_id, srcp_default);
      block->PushBefore(w2_ga, *it_los, AppM);
      w2_ga_var = GetPointer<gimple_assign>(GET_NODE(w2_ga))->op0;
   }

   tree_nodeRef u0v1_ga_var;
   if(v1 != 0)
   {
      if(v1 == 1)
      {
         u0v1_ga_var = u0_ga_var;
      }
      else
      {
         v1_node = TM->CreateUniqueIntegerCst(static_cast<long long int>(v1), type_expr);
         tree_nodeRef u0v1_expr =
             tree_man->create_binary_operation(type_expr, u0_ga_var, v1_node, srcp_default, mult_expr_K);
         tree_nodeRef u0v1_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), u0v1_expr,
                                                             function_id, srcp_default);
         block->PushBefore(u0v1_ga, *it_los, AppM);
         u0v1_ga_var = GetPointer<gimple_assign>(GET_NODE(u0v1_ga))->op0;
      }
   }
   tree_nodeRef w1u0v1_ga_var;
   if(w1_ga_var)
   {
      if(u0v1_ga_var)
      {
         tree_nodeRef w1u0v1_expr =
             tree_man->create_binary_operation(type_expr, w1_ga_var, u0v1_ga_var, srcp_default, plus_expr_K);
         tree_nodeRef w1u0v1_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), w1u0v1_expr,
                                                               function_id, srcp_default);
         block->PushBefore(w1u0v1_ga, *it_los, AppM);
         w1u0v1_ga_var = GetPointer<gimple_assign>(GET_NODE(w1u0v1_ga))->op0;
      }
      else
      {
         w1u0v1_ga_var = w1_ga_var;
      }
   }
   else if(u0v1_ga_var)
   {
      w1u0v1_ga_var = u0v1_ga_var;
   }

   tree_nodeRef w1u0v1h_ga_var;
   if(w1u0v1_ga_var)
   {
      tree_nodeRef w1u0v1h_expr = tree_man->create_binary_operation(type_expr, w1u0v1_ga_var, half_data_bitsize_node,
                                                                    srcp_default, rshift_expr_K);
      tree_nodeRef w1u0v1h_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), w1u0v1h_expr,
                                                             function_id, srcp_default);
      block->PushBefore(w1u0v1h_ga, *it_los, AppM);
      w1u0v1h_ga_var = GetPointer<gimple_assign>(GET_NODE(w1u0v1h_ga))->op0;
   }
   tree_nodeRef u1v1_ga_var;
   if(v1 != 0)
   {
      if(v1 == 1)
      {
         u1v1_ga_var = u1_ga_var;
      }
      else
      {
         tree_nodeRef u1v1_expr =
             tree_man->create_binary_operation(type_expr, u1_ga_var, v1_node, srcp_default, mult_expr_K);
         tree_nodeRef u1v1_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), u1v1_expr,
                                                             function_id, srcp_default);
         block->PushBefore(u1v1_ga, *it_los, AppM);
         u1v1_ga_var = GetPointer<gimple_assign>(GET_NODE(u1v1_ga))->op0;
      }
   }
   tree_nodeRef w1u0v1hw2_ga_var;
   if(w1u0v1h_ga_var)
   {
      if(w2_ga_var)
      {
         tree_nodeRef w1u0v1hw2_expr =
             tree_man->create_binary_operation(type_expr, w1u0v1h_ga_var, w2_ga_var, srcp_default, plus_expr_K);
         tree_nodeRef w1u0v1hw2_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(),
                                                                  w1u0v1hw2_expr, function_id, srcp_default);
         block->PushBefore(w1u0v1hw2_ga, *it_los, AppM);
         w1u0v1hw2_ga_var = GetPointer<gimple_assign>(GET_NODE(w1u0v1hw2_ga))->op0;
      }
      else
      {
         w1u0v1hw2_ga_var = w1u0v1h_ga_var;
      }
   }
   else if(w2_ga_var)
   {
      w1u0v1hw2_ga_var = w2_ga_var;
   }

   tree_nodeRef res_ga_var;
   if(w1u0v1hw2_ga_var)
   {
      if(u1v1_ga_var)
      {
         tree_nodeRef res_expr =
             tree_man->create_binary_operation(type_expr, w1u0v1hw2_ga_var, u1v1_ga_var, srcp_default, plus_expr_K);
         tree_nodeRef res_ga = tree_man->CreateGimpleAssign(type_expr, tree_nodeRef(), tree_nodeRef(), res_expr,
                                                            function_id, srcp_default);
         block->PushBefore(res_ga, *it_los, AppM);
         res_ga_var = GetPointer<gimple_assign>(GET_NODE(res_ga))->op0;
      }
      else
      {
         res_ga_var = w1u0v1hw2_ga_var;
      }
   }
   else if(u1v1_ga_var)
   {
      res_ga_var = u1v1_ga_var;
   }
   else
   {
      res_ga_var = TM->CreateUniqueIntegerCst(static_cast<long long int>(0), type_expr);
   }
   return res_ga_var;
}

tree_nodeRef IR_lowering::array_ref_lowering(array_ref* AR, const std::string& srcp_default,
                                             std::pair<unsigned int, blocRef> block,
                                             std::list<tree_nodeRef>::const_iterator it_los, bool temp_addr)
{
   tree_nodeRef type = AR->type;

   tree_nodeRef pt = tree_man->GetPointerType(type, GetPointer<type_node>(GET_NODE(type))->algn);
   tree_nodeRef ae = tree_man->create_unary_operation(pt, AR->op0, srcp_default, addr_expr_K);
   tree_nodeRef ae_ga = tree_man->CreateGimpleAssign(pt, tree_nodeRef(), tree_nodeRef(), ae, function_id, srcp_default);
   INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(ae_ga)->ToString());
   GetPointer<gimple_assign>(GET_NODE(ae_ga))->temporary_address = temp_addr;
   tree_nodeRef ae_vd = GetPointer<gimple_assign>(GET_NODE(ae_ga))->op0;
   block.second->PushBefore(ae_ga, *it_los, AppM);

   tree_nodeRef offset_type = tree_man->GetSizeType();
   auto ar_op1_type_index = tree_helper::CGetType(AR->op1)->index;
   tree_nodeRef offset_node;
   if(ar_op1_type_index != GET_INDEX_NODE(offset_type))
   {
      tree_nodeRef ne = tree_man->create_unary_operation(offset_type, AR->op1, srcp_default, nop_expr_K);
      tree_nodeRef nop_ga =
          tree_man->CreateGimpleAssign(offset_type, tree_nodeRef(), tree_nodeRef(), ne, function_id, srcp_default);
      INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(nop_ga)->ToString());
      offset_node = GetPointer<gimple_assign>(GET_NODE(nop_ga))->op0;
      block.second->PushBefore(nop_ga, *it_los, AppM);
   }
   else
   {
      offset_node = AR->op1;
   }
   const auto ar_op0_type_node = tree_helper::CGetType(AR->op0);
   THROW_ASSERT(GET_CONST_NODE(ar_op0_type_node)->get_kind() == array_type_K,
                "array_type expected: @" + STR(ar_op0_type_node->index));
   auto data_bitsize = tree_helper::GetArrayElementSize(ar_op0_type_node);
   auto n_byte = compute_n_bytes(data_bitsize);
   const auto dims = tree_helper::GetArrayDimensions(ar_op0_type_node);
   for(size_t ind = 1; ind < dims.size(); ++ind)
   {
      n_byte *= dims.at(ind);
   }
   tree_nodeRef coef_node = TM->CreateUniqueIntegerCst(static_cast<long long>(n_byte), offset_type);
   tree_nodeRef m = tree_man->create_binary_operation(offset_type, offset_node, coef_node, srcp_default, mult_expr_K);
   tree_nodeRef m_ga =
       tree_man->CreateGimpleAssign(offset_type, tree_nodeRef(), tree_nodeRef(), m, function_id, srcp_default);
   INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(m_ga)->ToString());
   tree_nodeRef m_vd = GetPointer<gimple_assign>(GET_NODE(m_ga))->op0;
   block.second->PushBefore(m_ga, *it_los, AppM);

   tree_nodeRef pp = tree_man->create_binary_operation(pt, ae_vd, m_vd, srcp_default, pointer_plus_expr_K);
   tree_nodeRef pp_ga = tree_man->CreateGimpleAssign(pt, tree_nodeRef(), tree_nodeRef(), pp, function_id, srcp_default);
   INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---adding statement " + GET_NODE(pp_ga)->ToString());
   GetPointer<gimple_assign>(GET_NODE(pp_ga))->temporary_address = temp_addr;
   tree_nodeRef pp_vd = GetPointer<gimple_assign>(GET_NODE(pp_ga))->op0;
   block.second->PushBefore(pp_ga, *it_los, AppM);

   tree_nodeRef offset = TM->CreateUniqueIntegerCst(0, pt);
   return tree_man->create_binary_operation(type, pp_vd, offset, srcp_default, mem_ref_K);
}

bool IR_lowering::reached_max_transformation_limit(const tree_nodeRef& stmt)
{
   if(stmt)
   {
      const auto ga = GetPointer<const gimple_assign>(GET_CONST_NODE(stmt));
      if(ga)
      {
         const auto op0 = GET_CONST_NODE(ga->op0);
         const auto op1 = GET_CONST_NODE(ga->op1);
         if(op1->get_kind() == cond_expr_K)
         {
            return false;
         }
         if(not ga->init_assignment and op0->get_kind() == ssa_name_K and op1->get_kind() == var_decl_K)
         {
            return false;
         }
      }
   }
   if(not AppM->ApplyNewTransformation())
   {
      return true;
   }
   return false;
}