Make loop variable a constant in C++

user_8118147 0
Viewed 1325

I am currently creating arithmetic operators libraries for high level synthesis.

For this, I am also creating a library to manipulate bits and bit vectors like it would be done in VHDL. To make my libraries synthesizable, nearly everything must be resolved at compile time.

However, I have an issue with loops.

Indeed, I would like to be able to write things like that:

const int N = 5;
for(int i = 0; i < N-2; i++) {
    x.bit<i+2>() = x.bit<i>();
}

Of course, it does not compile since i is a variable and not a constant determined at compile time.

However, N being a constant, this code is strictly equivalent to:

x.bit<2>() = x.bit<0>();
x.bit<3>() = x.bit<1>();
x.bit<4>() = x.bit<2>();

which compiles and works perfectly.

Is there a way to make the compiler (gcc in my case) unroll the loop since N is constant? Or to define a macro or a constexpr which could do it with a clean syntax? This would be the equivalent of for generate in VHDL.

constexpr template-meta-programming c++11 templates c++
3 Answers

While constexpr has got much more powerful in C++14/17 it is not yet possible to mix this kind of compile time / template code with an ordinary loop. There is some talk of introducing a construct that might enable that in a future version of C++. For now you have a few choices, either recursive calls to a function with an integer template argument or probably simpler in this case a C++17 fold expression. You could also use C++11 variadic template expansion to get a similar result to fold expressions in this example, though fold expressions are more powerful.

Just saw your comment about being stuck with C++11, you're probably better off using the recursive function approach I think. I've added that approach to the example.

If you were able to use C++14 you might also want to consider moving entirely into constexpr function / type land so your bit<I>() function would not be templated but would be just a constexpr function bit(i). You could then use normal functions and loops. Given the C++11 restrictions on constexpr functions that is probably less useful in your case however. I've added an example using that approach.

#include <iostream>
#include <utility>

template <size_t N>
struct bits {
    bool bs[N];

    template <size_t I>
    constexpr const bool& bit() const {
        return bs[I];
    }
    template <size_t I>
    constexpr bool& bit() {
        return bs[I];
    }

    constexpr bool bit(int i) const { return bs[i]; }
    constexpr void bit(int i, bool x) { bs[i] = x; }
};

// Using C++17 fold expressions

template <size_t N, size_t... Is>
constexpr bits<N> set_bits_helper(bits<N> x, std::index_sequence<Is...>) {
    ((x.bit<Is + 2>() = x.bit<Is>()), ...);
    return x;
}

template <size_t N>
constexpr bits<N> set_bits(bits<N> x) {
    return set_bits_helper(x, std::make_index_sequence<N - 2>{});
}

// Using recursive template function, should work on C++11

template <size_t I, size_t N>
constexpr bits<N> set_bits_recursive_helper(bits<N> x, std::integral_constant<size_t, I>) {
    x.bit<N - I>() = x.bit<N - I - 2>();
    return set_bits_recursive_helper(x, std::integral_constant<size_t, I - 1>{});
}

template <size_t N>
constexpr bits<N> set_bits_recursive_helper(bits<N> x, std::integral_constant<size_t, 0>) { return x; }

template <size_t N>
constexpr bits<N> set_bits_recursive(bits<N> x) {
    return set_bits_recursive_helper(x, std::integral_constant<size_t, N - 2>{});
}

// Using non template constexpr functions
template <size_t N>
constexpr bits<N> set_bits_constexpr(bits<N> x) {
    for (int i = 0; i < N - 2; ++i) {
        x.bit(i + 2, x.bit(i));
    }
    return x;
}

// Test code to show usage

template <size_t N>
void print_bits(const bits<N>& x) {
    for (auto b : x.bs) {
        std::cout << b << ", ";
    }
    std::cout << '\n';
}

void test_set_bits() {
    constexpr bits<8> x{ 1, 0 };
    print_bits(x);
    constexpr auto y = set_bits(x);
    static_assert(y.bit<2>() == x.bit<0>());
    print_bits(y);
}

void test_set_bits_recursive() {
    constexpr bits<8> x{ 1, 0 };
    print_bits(x);
    constexpr auto y = set_bits_recursive(x);
    static_assert(y.bit<2>() == x.bit<0>());
    print_bits(y);
}

void test_set_bits_constexpr() {
    constexpr bits<8> x{ 1, 0 };
    print_bits(x);
    constexpr auto y = set_bits_constexpr(x);
    static_assert(y.bit<2>() == x.bit<0>());
    print_bits(y);
}

int main() {
    test_set_bits();
    test_set_bits_recursive();
    test_set_bits_constexpr();
}
user_1390910

Also without std::integer_sequence (but I suggest to implement a substitute and use it), in C++11 you can use template partial specialization.

I mean that you can implement something like

template <int I, int Sh, int N>
struct shiftVal
 {
   template <typename T>
   static int func (T & t)
    { return t.template bit<I+Sh>() = t.template bit<I>(),
             shiftVal<I+1, Sh, N>::func(t); }
 };

template <int I, int Sh>
struct shiftVal<I, Sh, I>
 {
   template <typename T>
   static int func (T &)
    { return 0; }
 };

and your cycle become 

shiftVal<0, 2, N-2>::func(x);

The following is a full working example

#include <array>
#include <iostream>

template <std::size_t N>
struct foo
 {
   std::array<int, N> arr;

   template <int I>
   int & bit ()
    { return arr[I]; }
 };


template <int I, int Sh, int N>
struct shiftVal
 {
   template <typename T>
   static int func (T & t)
    { return t.template bit<I+Sh>() = t.template bit<I>(),
             shiftVal<I+1, Sh, N>::func(t); }
 };

template <int I, int Sh>
struct shiftVal<I, Sh, I>
 {
   template <typename T>
   static int func (T &)
    { return 0; }
 };

int main ()
 {
   foo<10U>  f { { { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 } } };

   for ( auto const & i : f.arr )
      std::cout << i << ' ';

   std::cout << std::endl;

   shiftVal<0, 2, 10-2>::func(f);

   for ( auto const & i : f.arr )
      std::cout << i << ' ';

   std::cout << std::endl;
 }
user_60226560

Nobody else produce an example based on a C++11 simulation of std::integer_sequence (as suggested by W.F., Passer By and Sopel and the simpler solution, IMHO) so I propose the following one (of std::index_sequence and std::make_index_sequence in reality: simulate std::integer_sequence is more complicated)

template <std::size_t ...>
struct indexSequence
 { };

template <std::size_t N, std::size_t ... Next>
struct indexSequenceHelper : public indexSequenceHelper<N-1U, N-1U, Next...>
 { };

template <std::size_t ... Next>
struct indexSequenceHelper<0U, Next ... >
 { using type = indexSequence<Next ... >; };

template <std::size_t N>
using makeIndexSequence = typename indexSequenceHelper<N>::type;

So a function (with function helper) to reproduce the asked loop can be written as

template 

void shiftValHelper (T & t, indexSequence<Is...> const &)
 {
   using unused = int[];

   (void)unused { 0,
      (t.template bit<Is+Sh>() = t.template bit<Is>(), 0)... };
 }


template <std::size_t Sh, std::size_t N, typename T>
void shiftVal (T & t)
 { shiftValHelper<Sh>(t, makeIndexSequence<N>{}); }

and called ad follows

shiftVal<2, N-2>(x);

The following is a full working example

#include <array>
#include <iostream>

template <std::size_t ...>
struct indexSequence
 { };

template <std::size_t N, std::size_t ... Next>
struct indexSequenceHelper : public indexSequenceHelper<N-1U, N-1U, Next...>
 { };

template <std::size_t ... Next>
struct indexSequenceHelper<0U, Next ... >
 { using type = indexSequence<Next ... >; };

template <std::size_t N>
using makeIndexSequence = typename indexSequenceHelper<N>::type;


template <std::size_t N>
struct foo
 {
   std::array<int, N> arr;

   template <std::size_t I>
   int & bit ()
    { return arr[I]; }
 };


template <std::size_t Sh, typename T, std::size_t ... Is>
void shiftValHelper (T & t, indexSequence<Is...> const &)
 {
   using unused = int[];

   (void)unused { 0,
      (t.template bit<Is+Sh>() = t.template bit<Is>(), 0)... };
 }


template <std::size_t Sh, std::size_t N, typename T>
void shiftVal (T & t)
 { shiftValHelper<Sh>(t, makeIndexSequence<N>{}); }


int main ()
 {
   foo<10U>  f { { { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 } } };

   for ( auto const & i : f.arr )
      std::cout << i << ' ';

   std::cout << std::endl;

   shiftVal<2, 10-2>(f);

   for ( auto const & i : f.arr )
      std::cout << i << ' ';

   std::cout << std::endl;
 }
user_60226560
Related