<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This tutorial describes one particular intermediate representation used by the Devito Compiler: the Iteration/Expression Tree (IET), a special type of Abstract Syntax Tree (AST).\n",
    "\n",
    "# Part II - Bottom Up\n",
    "\n",
    "In this section we build and play with toy IETs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",<commit_msg>updates 02_iet.ipynb until use of Callable<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This tutorial describes one particular intermediate representation used by the Devito Compiler: the Iteration/Expression Tree (IET), a special type of Abstract Syntax Tree (AST).\n",
    "\n",
    "# Part II - Bottom Up\n",
    "\n",
    "In this section we build and play with toy IETs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`Dimensions` are the building blocks of both `iterations` and `expressions`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'i': i, 'j': j, 'k': k, 't0': t0, 't1': t1}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from devito import SpaceDimension, TimeDimension\n",
    "\n",
    "dims = {'i': SpaceDimension(name='i'),\n",
    "        'j': SpaceDimension(name='j'),\n",
    "        'k': SpaceDimension(name='k'),\n",
    "        't0': TimeDimension(name='t0'),\n",
    "        't1': TimeDimension(name='t1')}\n",
    "\n",
    "dims"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Elements such as `scalars`, `constants` and `functions` are used to build `expressions`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from devito.types import Array, Scalar\n",
    "from devito import Constant, Function\n",
    "\n",
    "symbs = {'a': Scalar(name='a'),\n",
    "         'b': Constant(name='b'),\n",
    "         'c': Array(name='c', shape=(3,), dimensions=(dims['i'],)).indexify(),\n",
    "         'd': Array(name='d', \n",
    "                    shape=(3,3), \n",
    "                    dimensions=(dims['j'],dims['k'])).indexify(),\n",
    "         'e': Function(name='e', \n",
    "                       shape=(3,3,3), \n",
    "                       dimensions=(dims['t0'],dims['t1'],dims['i'])).indexify()}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`Time-functions` may be used too. This sort of representation requires an operating `domain` though. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Grid[extent=(1.0, 1.0), shape=(10, 10), dimensions=(x, y)]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from devito import Grid\n",
    "grid = Grid(shape=(10,10))\n",
    "grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': a, 'b': b, 'c': c[i], 'd': d[j, k], 'e': e[t0, t1, i], 'f': f[t, x, y]}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from devito import TimeFunction\n",
    "f = TimeFunction(name='f', grid=grid)\n",
    "symbs['f'] = f.indexify()\n",
    "symbs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`Expressions` are build from equations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<Expression a = b + c[i] + 5.0>\n",
      "<Expression d[j, k] = e[t0, t1, i] - f[t, x, y]>\n",
      "<Expression a = 4*a*b>\n",
      "<Expression a = 8.0*a + 6.0/b>\n"
     ]
    }
   ],
   "source": [
    "from devito.ir.iet import Expression\n",
    "from devito.ir.equations import DummyEq\n",
    "from devito.tools import pprint\n",
    "\n",
    "def get_exprs(a, b, c, d, e, f):\n",
    "    return [Expression(DummyEq(a, b + c + 5.)),\n",
    "            Expression(DummyEq(d, e - f)),\n",
    "            Expression(DummyEq(a, 4 * (b * a))),\n",
    "            Expression(DummyEq(a, (6. / b) + (8. * a)))]\n",
    "\n",
    "exprs = get_exprs(symbs['a'],\n",
    "                  symbs['b'],\n",
    "                  symbs['c'],\n",
    "                  symbs['d'],\n",
    "                  symbs['e'],\n",
    "                  symbs['f'])\n",
    "\n",
    "pprint(exprs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And `Iterations` are build to run over `Expressions`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from devito.ir.iet import Iteration\n",
    "\n",
    "def get_iters(dims):\n",
    "    return [lambda ex: Iteration(ex, dims['i'], (0, 3, 1)),\n",
    "            lambda ex: Iteration(ex, dims['j'], (0, 5, 1)),\n",
    "            lambda ex: Iteration(ex, dims['k'], (0, 7, 1)),\n",
    "            lambda ex: Iteration(ex, dims['t0'], (0, 4, 1)),\n",
    "            lambda ex: Iteration(ex, dims['t1'], (0, 4, 1))]\n",
    "\n",
    "iters = get_iters(dims)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we can see how blocks of `iterations` over `expressions` can be used to build loop nests. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<Iteration i::i::(0, 3, 1)::(0, 0)>\n",
      "  <Iteration j::j::(0, 5, 1)::(0, 0)>\n",
      "    <Iteration k::k::(0, 7, 1)::(0, 0)>\n",
      "      <Expression a = b + c[i] + 5.0>\n",
      "\n",
      "\n",
      "<Iteration i::i::(0, 3, 1)::(0, 0)>\n",
      "  <Expression a = b + c[i] + 5.0>\n",
      "  <Iteration j::j::(0, 5, 1)::(0, 0)>\n",
      "    <Iteration k::k::(0, 7, 1)::(0, 0)>\n",
      "      <Expression d[j, k] = e[t0, t1, i] - f[t, x, y]>\n",
      "\n",
      "\n",
      "<Iteration i::i::(0, 3, 1)::(0, 0)>\n",
      "  <Iteration t0::t0::(0, 4, 1)::(0, 0)>\n",
      "    <Expression a = b + c[i] + 5.0>\n",
      "  <Iteration j::j::(0, 5, 1)::(0, 0)>\n",
      "    <Iteration k::k::(0, 7, 1)::(0, 0)>\n",
      "      <Expression d[j, k] = e[t0, t1, i] - f[t, x, y]>\n",
      "      <Expression a = 4*a*b>\n",
      "  <Iteration t1::t1::(0, 4, 1)::(0, 0)>\n",
      "    <Expression a = 8.0*a + 6.0/b>\n"
     ]
    }
   ],
   "source": [
    "def get_block1(exprs, iters):\n",
    "    # Perfect loop nest:\n",
    "    # for i\n",
    "    #   for j\n",
    "    #     for k\n",
    "    #       expr0\n",
    "    return iters[0](iters[1](iters[2](exprs[0])))\n",
    "    \n",
    "def get_block2(exprs, iters):\n",
    "    # Non-perfect simple loop nest:\n",
    "    # for i\n",
    "    #   expr0\n",
    "    #   for j\n",
    "    #     for k\n",
    "    #       expr1\n",
    "    return iters[0]([exprs[0], iters[1](iters[2](exprs[1]))])\n",
    "\n",
    "def get_block3(exprs, iters):\n",
    "    # Non-perfect non-trivial loop nest:\n",
    "    # for i\n",
    "    #   for s\n",
    "    #     expr0\n",
    "    #   for j\n",
    "    #     for k\n",
    "    #       expr1\n",
    "    #       expr2\n",
    "    #   for p\n",
    "    #     expr3\n",
    "    return iters[0]([iters[3](exprs[0]),\n",
    "                     iters[1](iters[2]([exprs[1], exprs[2]])),\n",
    "                     iters[4](exprs[3])])\n",
    "\n",
    "block1 = get_block1(exprs, iters)\n",
    "block2 = get_block2(exprs, iters)\n",
    "block3 = get_block3(exprs, iters)\n",
    "\n",
    "pprint(block1), print('\\n')\n",
    "pprint(block2), print('\\n')\n",
    "pprint(block3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And, finally, we can build `callable` kernels that will be used for generating `.c` code. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "kernel no.1:\n",
      "void foo()\n",
      "{\n",
      "  for (int i = 0; i <= 3; i += 1)\n",
      "  {\n",
      "    for (int j = 0; j <= 5; j += 1)\n",
      "    {\n",
      "      for (int k = 0; k <= 7; k += 1)\n",
      "      {\n",
      "        a = b + c[i] + 5.0F;\n",
      "      }\n",
      "    }\n",
      "  }\n",
      "}\n",
      "\n",
      "kernel no.2:\n",
      "void foo()\n",
      "{\n",
      "  for (int i = 0; i <= 3; i += 1)\n",
      "  {\n",
      "    a = b + c[i] + 5.0F;\n",
      "    for (int j = 0; j <= 5; j += 1)\n",
      "    {\n",
      "      for (int k = 0; k <= 7; k += 1)\n",
      "      {\n",
      "        d[j][k] = e[t0][t1][i] - f[t][x][y];\n",
      "      }\n",
      "    }\n",
      "  }\n",
      "}\n",
      "\n",
      "kernel no.3:\n",
      "void foo()\n",
      "{\n",
      "  for (int i = 0; i <= 3; i += 1)\n",
      "  {\n",
      "    for (int t0 = 0; t0 <= 4; t0 += 1)\n",
      "    {\n",
      "      a = b + c[i] + 5.0F;\n",
      "    }\n",
      "    for (int j = 0; j <= 5; j += 1)\n",
      "    {\n",
      "      for (int k = 0; k <= 7; k += 1)\n",
      "      {\n",
      "        d[j][k] = e[t0][t1][i] - f[t][x][y];\n",
      "        a = 4*a*b;\n",
      "      }\n",
      "    }\n",
      "    for (int t1 = 0; t1 <= 4; t1 += 1)\n",
      "    {\n",
      "      a = 8.0F*a + 6.0F/b;\n",
      "    }\n",
      "  }\n",
      "}\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from devito.ir.iet import Callable\n",
    "\n",
    "kernels = [Callable('foo', block1, 'void', ()),\n",
    "           Callable('foo', block2, 'void', ()),\n",
    "           Callable('foo', block3, 'void', ())]\n",
    "\n",
    "print('kernel no.1:\\n' + str(kernels[0].ccode) + '\\n')\n",
    "print('kernel no.2:\\n' + str(kernels[1].ccode) + '\\n')\n",
    "print('kernel no.3:\\n' + str(kernels[2].ccode) + '\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
{'fraction_non_alphanumeric': 0.24558319416366353, 'fraction_numerical': 0.02285312472532302, 'mean_word_length': 1.8530591775325977, 'pattern_counts': {'":': 131, '<': 36, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2110489', 'n_tokens_mistral': 4779, 'n_tokens_neox': 4629, 'n_words': 938}