Code generation for array map is wasteful

[RyanGlScott]

Consider the following, minimized Copilot example:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE TypeApplications #-}
module Main where

import Data.Proxy (Proxy(..))
import GHC.TypeLits (natVal)

import Copilot.Compile.C99 (compile)
import Language.Copilot

type N = 3

arr1, arr2 :: Stream (Array N Word32)
arr1 = extern "arr1" Nothing
arr2 = foldr (\idx acc -> acc !! constW32 idx =$ (+ constW32 (idx + 100))) arr1 [0..(n-1)]
  where
    n :: Word32
    n = fromInteger $ natVal $ Proxy @N

spec :: Spec
spec = trigger "trig" true [arg arr2]

main :: IO ()
main = do
  spec' <- reify spec
  compile "array-update" spec'

This takes an external array (arr1) and produces a new array arr2 by adding idx + 100 to each element of arr1, where idx is the corresponding element's index. In the example above where N (the size of the array) is 3, this means that we would add 0 + 100, 1 + 100, and 2 + 100, respectively, to each element of arr1. In principle, this should only require three additions, but if you look at the generated C code:

#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#include "array-update_types.h"
#include "array-update.h"

static uint32_t arr1_cpy[(3)];

static bool trig_0_guard(void) {
  return true;
}

static void trig_0_arg0(uint32_t trig_0_arg0_output[(3)]) {
  uint32_t _v0[(3)];
  uint32_t _v1[(3)];
  uint32_t _v2[(3)];
  uint32_t _v3[(3)];
  uint32_t _v4[(3)];
  uint32_t _v5[(3)];
  uint32_t _v6[(3)];
  (memcpy)((_v0), (arr1_cpy), ((3) * (sizeof(uint32_t))));
  ((_v0)[(uint32_t)(2)]) = (((arr1_cpy)[(uint32_t)(2)]) + ((uint32_t)(102)));
  (memcpy)((_v1), (arr1_cpy), ((3) * (sizeof(uint32_t))));
  ((_v1)[(uint32_t)(2)]) = (((arr1_cpy)[(uint32_t)(2)]) + ((uint32_t)(102)));
  (memcpy)((_v2), (_v0), ((3) * (sizeof(uint32_t))));
  ((_v2)[(uint32_t)(1)]) = (((_v1)[(uint32_t)(1)]) + ((uint32_t)(101)));
  (memcpy)((_v3), (arr1_cpy), ((3) * (sizeof(uint32_t))));
  ((_v3)[(uint32_t)(2)]) = (((arr1_cpy)[(uint32_t)(2)]) + ((uint32_t)(102)));
  (memcpy)((_v4), (arr1_cpy), ((3) * (sizeof(uint32_t))));
  ((_v4)[(uint32_t)(2)]) = (((arr1_cpy)[(uint32_t)(2)]) + ((uint32_t)(102)));
  (memcpy)((_v5), (_v3), ((3) * (sizeof(uint32_t))));
  ((_v5)[(uint32_t)(1)]) = (((_v4)[(uint32_t)(1)]) + ((uint32_t)(101)));
  (memcpy)((_v6), (_v2), ((3) * (sizeof(uint32_t))));
  ((_v6)[(uint32_t)(0)]) = (((_v5)[(uint32_t)(0)]) + ((uint32_t)(100)));
  (memcpy)((trig_0_arg0_output), (_v6), ((3) * (sizeof(uint32_t))));
}

void step(void) {
  uint32_t trig_0_arg_temp0[(3)];
  (memcpy)((arr1_cpy), (arr1), ((3) * (sizeof(uint32_t))));
  if ((trig_0_guard)()) {
    {(trig_0_arg0)((trig_0_arg_temp0));
     (trig)((trig_0_arg_temp0));}
  };
}

There are seven additions! As you increase the value of N, the number of additions grows exponentially:

N	Number of additions
3	7
4	15
5	31
6	63

It appears that Copilot isn't sharing Array sub-expressions like I would expect it to. If you add explicit sharing by using the local combinator:

arr2 = foldr (\idx cont acc -> local (acc !! constW32 idx =$ (+ constW32 (idx + 100))) cont) id [0..(n-1)] arr1
  where
    n :: Word32
    n = fromInteger $ natVal $ Proxy @N

Then the generated code produces exactly N additions, as expected.

Could we modify Copilot's handling of array accesses/updates to ensure that we don't needlessly duplicate sub-expressions?

[RyanGlScott]

One thing to note is that different languages have different ways of performing array maps idiomatically. In C, this would be accomplished with something like a for loop, while in Bluespec, this would be accomplished with the map function over Vectors. Having an "array map" primitive in Copilot would make it easier to pick the most idiomatic representation for each language.