# \[RFC\] CSE Optimization **URL:** \ **Category:** RFC\ **Created:** [October 9, 2020, 10:09am UTC](https://discuss.tvm.apache.org/t/rfc-cse-optimization/8130 "2020-10-09T10:09:29Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![ArmageddonKnight](https://discuss.tvm.apache.org/user_avatar/discuss.tvm.apache.org/armageddonknight/32/1709_2.png) [@ArmageddonKnight](https://discuss.tvm.apache.org/u/ArmageddonKnight)\ **Post date:** [October 9, 2020, 10:09am UTC](https://discuss.tvm.apache.org/t/rfc-cse-optimization/8130/1 "2020-10-09T10:09:29Z")
## Motivation **C** ommon **S** ubexpression **E** limination is a compiler optimization that effectively avoids repeated computation of the same expression. It is needed in the AutoDiff submodule to improve its performance. As an example, consider a compute definition that is as simple as the tanh activation function: ```auto Y = tanh(X) ``` whose gradient definitions are ```auto dX = (1 - tanh(X) * tanh(X)) * dY ``` We can clearly see that the value of `dX` is evaluated for **3 times** in this example: once in the forward pass, and twice in the backward pass. Although such re-evaluation might not be a big deal here (because tanh is a relatively lightweight operator), one can probably imagine the trouble that this will bring as the operators become more complicated, as our examples in the later text will show. ## Key Ideas To illustrate our idea better, we consider the compute definition for the BatchNorm operator and its gradient on the placeholder γ: ![](https://discuss.tvm.apache.org/uploads/default/original/2X/6/60481fef5fc8af2265bf941ed132174eb2ec7d6d.gif), ![](https://discuss.tvm.apache.org/uploads/default/original/2X/5/5c771d2c1ac7b7768949c73154b032d8131a50ed.gif) To avoid re-evaluating the normalized x (denoted as x\_hat), we must complete the following steps: 1. **Analysis** 2. **Transform (Forward)** 3. **Transform (Backward)** As one might notice, those steps are in essence inferring the feature maps (a.k.a. backward dependency). In legacy machine learning frameworks (e.g., MXNet, TensorFlow) and deep learning libraries (e.g., cuDNN), this is done in a manual, hard-coded way. But here we are doing this automatically, that is, the feature maps are determined in such a way that the amount of computation needed to evaluate the backward gradients is minimized. ## Implementation Details To implement CSE, we need to go through the following steps: 1. Tensor AutoInliner 2. CSE Optimizer 3. Tensor Expression Tree @yzhliu ---
**Author:** ![yzhliu](https://discuss.tvm.apache.org/user_avatar/discuss.tvm.apache.org/yzhliu/32/28_2.png) [@yzhliu](https://discuss.tvm.apache.org/u/yzhliu)\ **Post date:** [October 15, 2020, 5:18pm UTC](https://discuss.tvm.apache.org/t/rfc-cse-optimization/8130/2 "2020-10-15T17:18:29Z")
Thanks for the RFC. Nice finding and it looks good to me overall. Could you also provide an example of how the user api looks like? Besides, what information does Tensor Expression Tree provide in addition to Tensor? ---
**Author:** ![ArmageddonKnight](https://discuss.tvm.apache.org/user_avatar/discuss.tvm.apache.org/armageddonknight/32/1709_2.png) [@ArmageddonKnight](https://discuss.tvm.apache.org/u/ArmageddonKnight)\ **Post date:** [October 16, 2020, 5:19pm UTC](https://discuss.tvm.apache.org/t/rfc-cse-optimization/8130/3 "2020-10-16T17:19:18Z")
- The user API looks like the following: ```auto /*! * \brief Eliminate common subexpressions among \p in_args and between them and \p output . * * \param output The output tensor. * \param input_grads The gradients of input tensors. */ std::pair > CSE(const Tensor& output, const std::vector& input_grads); ``` - The tensor expression tree does not provide extra information. It is just an useful data structure for comparison purposes. ---
**Author:** ![yzhliu](https://discuss.tvm.apache.org/user_avatar/discuss.tvm.apache.org/yzhliu/32/28_2.png) [@yzhliu](https://discuss.tvm.apache.org/u/yzhliu)\ **Post date:** [October 16, 2020, 5:51pm UTC](https://discuss.tvm.apache.org/t/rfc-cse-optimization/8130/4 "2020-10-16T17:51:40Z")
@tqchen @junrushao how much of the work do you think we can reuse once we move to [https://discuss.tvm.apache.org/t/rfc-tensorir-a-schedulable-ir-for-tvm](https://discuss.tvm.apache.org/t/rfc-tensorir-a-schedulable-ir-for-tvm)? ---
**Author:** ![tqchen](https://discuss.tvm.apache.org/user_avatar/discuss.tvm.apache.org/tqchen/32/5_2.png) [@tqchen](https://discuss.tvm.apache.org/u/tqchen)\ **Post date:** [October 16, 2020, 9:41pm UTC](https://discuss.tvm.apache.org/t/rfc-cse-optimization/8130/5 "2020-10-16T21:41:28Z")
I think there are two potential ways to think about it. We can either try to do CSE in the Expr level, or we can do CSE in the TE level. I think both will bring some of the benefit, so it would be helpful to support both variants ---
**Author:** ![junrushao](https://discuss.tvm.apache.org/user_avatar/discuss.tvm.apache.org/junrushao/32/205_2.png) [@junrushao](https://discuss.tvm.apache.org/u/junrushao)\ **Post date:** [October 17, 2020, 4:00am UTC](https://discuss.tvm.apache.org/t/rfc-cse-optimization/8130/6 "2020-10-17T04:00:21Z")
I agree with @tqchen. CSE is not hard to implement, and CSE on both sides provides different benefits. So we can potentially support both variants. ---
**Author:** ![mikeseven](https://discuss.tvm.apache.org/user_avatar/discuss.tvm.apache.org/mikeseven/32/535_2.png) [@mikeseven](https://discuss.tvm.apache.org/u/mikeseven)\ **Post date:** [October 18, 2020, 1:50am UTC](https://discuss.tvm.apache.org/t/rfc-cse-optimization/8130/7 "2020-10-18T01:50:36Z")
I suppose CSE would solve my question earlier where 2 identical adds with the same tensor shapes where not simplified as 1 add with both tensors added?