Repository: numba/numba
Pull request: Abandon branch pruning if an arg name is redefined.
This makes it so that branch pruning for a given input arg is
abandoned if an input arg is redefined in the user code as its
value potentially becomes non-const (and no const-prop analysis
yet to figure it out).

Fixes #4163

<!--

Thanks for wanting to contribute to Numba :)

First, if you need some help or want to chat to the core developers, please
visit https://gitter.im/numba/numba for real time chat or post to the Numba
mailing list https://groups.google.com/a/continuum.io/forum/#!forum/numba-users.

Here's some guidelines to help the review process go smoothly.

0. Please write a description in this text box of the changes that are being
   made.

1. Please ensure that you have written units tests for the changes made/features
   added.

2. If you are closing an issue please use one of the automatic closing words as
   noted here: https://help.github.com/articles/closing-issues-using-keywords/

3. If your pull request is not ready for review but you want to make use of the
   continuous integration testing facilities please label it with `[WIP]` and
   then remove the label when you'd like it to be reviewed.

4. Once review has taken place please do not add features or make changes out of
   the scope of those requested by the reviewer (doing this just add delays as
   already reviewed code ends up having to be re-reviewed/it is hard to tell
   what is new etc!). Further, please do not rebase your branch on master/force
   push/rewrite history, doing any of these causes the context of any comments
   made by reviewers to be lost. If conflicts occur against master they should
   be resolved by merging master into the branch used for making the pull
   request.

Many thanks in advance for your cooperation!

-->


Problem statement:
'<' not supported between instances of 'NoneType' and 'int'
After updating to numba , our code started to get the following error:

```
@jit(nopython=True)
def foo(array, a=None, b=None):
    if a is None:
        a =  0
    if b is None or b > array.shape[0]:
        b = array.shape[0]
    if a < 0 or b < 0:
        # raise error
    if b < a:
        # raise error
```
where `array` is a numpy array and `a` and `b` are `int` types.

This was working fine, however, after we got the new release we are getting the following error:
```
  File ".../conda/envs/py36-gpu/lib/python3.6/site-packages/numba/analysis.py", line 305, in prune_by_type
    take_truebr = condition.fn(lhs_cond, rhs_cond)
TypeError: Failed in nopython mode pipeline (step: dead branch pruning)
'<' not supported between instances of 'NoneType' and 'int'
```
I could fix it like this:

```
@jit(nopython=True)
def foo(array, a=0, b=None):
    if b is None:
        b =  array.shape[0]
    if b > array.shape[0]
        b = array.shape[0]
    if a < 0:
        # raise error
    if b < a:
        # raise error
```

Hints from issue discussion:
Thanks for the report. Which version of Numba are you using?

I think the issue is that the value of `a` is redefined in the code and not propagated.
Thanks for your response. 
I am using `numba==0.43.1`, the code was working as expected for previous versions.

Thanks, 0.43+ has new features to deal with a really common problem pattern whereby type inference would fail because it would need to evaluate all branches in code and get stuck trying to resolve one of them that is actually dead, for example `a+b` `(int + None)` in the second branch here is dead:
```python
from numba import njit

@njit
def foo(a, b=None):
    if b is None:
        return a
    else:
        return a + b

print(foo(10))
```
the new feature detects dead branches and removes them to permit more code to work.

The reason for the failure you are seeing is that in your sample code `a` gets redefined in a block and the new value isn't propagated to later call sites (it's still seeing `a=None`), hence comparison between `int` and `None` with `<`.
```python
@jit(nopython=True)
def foo(array, a=None, b=None):
    if a is None:
        a =  0
    if b is None or b > array.shape[0]:
        b = array.shape[0]
    if a < 0 or b < 0:
        # raise error
    if b < a:
        # raise error
```
a few potential fixes, 1) add a guard in branch pruning to abort when a comparison fails 2) full SSA base IR would probably help as the definition would be the phi-of-a and so not considered const-like? 3) thinking about 2) perhaps if there's a redefinition of a variable abort anyway.

Commit message: Abandon branch pruning if an arg name is redefined.

This makes it so that branch pruning for a given input arg is
abandoned if an input arg is redefined in the user code as its
value potentially becomes non-const (and no const-prop analysis
yet to figure it out).

Fixes #4163

Patch to review:
diff --git a/numba/analysis.py b/numba/analysis.py
index add81bacf64..e356cea02f7 100644
--- a/numba/analysis.py
+++ b/numba/analysis.py
@@ -302,7 +302,10 @@ def prune_by_type(branch, condition, blk, *conds):
         lhs_none = isinstance(lhs_cond, types.NoneType)
         rhs_none = isinstance(rhs_cond, types.NoneType)
         if lhs_none or rhs_none:
-            take_truebr = condition.fn(lhs_cond, rhs_cond)
+            try:
+                take_truebr = condition.fn(lhs_cond, rhs_cond)
+            except:
+                return False, None
             if DEBUG > 0:
                 kill = branch.falsebr if take_truebr else branch.truebr
                 print("Pruning %s" % kill, branch, lhs_cond, rhs_cond,
@@ -313,7 +316,10 @@ def prune_by_type(branch, condition, blk, *conds):
 
     def prune_by_value(branch, condition, blk, *conds):
         lhs_cond, rhs_cond = conds
-        take_truebr = condition.fn(lhs_cond, rhs_cond)
+        try:
+            take_truebr = condition.fn(lhs_cond, rhs_cond)
+        except:
+            return False, None
         if DEBUG > 0:
             kill = branch.falsebr if take_truebr else branch.truebr
             print("Pruning %s" % kill, branch, lhs_cond, rhs_cond, condition.fn)
@@ -364,9 +370,11 @@ def resolve_input_arg_const(input_arg):
             for arg in [condition.lhs, condition.rhs]:
                 resolved_const = Unknown()
                 if arg.name in func_ir.arg_names:
-                    # it's an e.g. literal argument to the function
-                    resolved_const = resolve_input_arg_const(arg.name)
-                    prune = prune_by_type
+                    # make sure there's no redefinition of an arg name
+                    if len(func_ir._definitions[arg.name]) == 1:
+                        # it's an e.g. literal argument to the function
+                        resolved_const = resolve_input_arg_const(arg.name)
+                        prune = prune_by_type
                 else:
                     # it's some const argument to the function, cannot use guard
                     # here as the const itself may be None
diff --git a/numba/tests/test_analysis.py b/numba/tests/test_analysis.py
index 062def4f938..c49354178d2 100644
--- a/numba/tests/test_analysis.py
+++ b/numba/tests/test_analysis.py
@@ -81,6 +81,9 @@ def assert_prune(self, func, args_tys, prune, *args):
                 expect_removed.append(branch.falsebr)
             elif prune is None:
                 pass  # nothing should be removed!
+            elif prune == 'both':
+                expect_removed.append(branch.falsebr)
+                expect_removed.append(branch.truebr)
             else:
                 assert 0, "unreachable"
 
@@ -92,9 +95,9 @@ def assert_prune(self, func, args_tys, prune, *args):
         try:
             self.assertEqual(new_labels, original_labels - set(expect_removed))
         except AssertionError as e:
-            print("new_labels", new_labels)
-            print("original_labels", original_labels)
-            print("expect_removed", expect_removed)
+            print("new_labels", sorted(new_labels))
+            print("original_labels", sorted(original_labels))
+            print("expect_removed", sorted(expect_removed))
             raise e
 
         cres = compile_isolated(func, args_tys)
@@ -376,3 +379,127 @@ def bug(a,b):
         self.assertEqual(bug(np.arange(10).reshape((2, 5)), 10), [])
         self.assertEqual(bug(np.arange(10).reshape((2, 5)), None), [])
         self.assertFalse(bug.nopython_signatures)
+
+
+    def test_redefined_variables_are_not_considered_in_prune(self):
+        # see issue #4163, checks that if a variable that is an argument is
+        # redefined in the user code it is not considered const
+
+        def impl(array, a=None):
+            if a is None:
+                a = 0
+            if a < 0:
+                return 10
+            return 30
+
+        self.assert_prune(impl,
+                          (types.Array(types.float64, 2, 'C'),
+                           types.NoneType('none'),),
+                          [None, None],
+                          np.zeros((2, 3)), None)
+
+    def test_comparison_operators(self):
+        # see issue #4163, checks that a variable that is an argument and has
+        # value None survives TypeError from invalid comparison which should be
+        # dead
+
+        def impl(array, a=None):
+            x = 0
+            if a is None:
+                return 10 # dynamic exec would return here
+            # static analysis requires that this is executed with a=None,
+            # hence TypeError
+            if a < 0:
+                return 20
+            return x
+
+        self.assert_prune(impl,
+                          (types.Array(types.float64, 2, 'C'),
+                           types.NoneType('none'),),
+                          [False, 'both'],
+                          np.zeros((2, 3)), None)
+
+        self.assert_prune(impl,
+                          (types.Array(types.float64, 2, 'C'),
+                           types.float64,),
+                          [None, None],
+                          np.zeros((2, 3)), 12.)
+
+    def test_redefinition_analysis_same_block(self):
+        # checks that a redefinition in a block with prunable potential doesn't
+        # break
+
+        def impl(array, x, a=None):
+            b = 0
+            if x < 4:
+                b = 12
+            if a is None:
+                a = 0
+            else:
+                b = 12
+            if a < 0:
+                return 10
+            return 30 + b + a
+
+        self.assert_prune(impl,
+                          (types.Array(types.float64, 2, 'C'),
+                           types.float64, types.NoneType('none'),),
+                          [None, None, None],
+                          np.zeros((2, 3)), 1., None)
+
+    def test_redefinition_analysis_different_block_can_exec(self):
+        # checks that a redefinition in a block that may be executed prevents
+        # pruning
+
+        def impl(array, x, a=None):
+            b = 0
+            if x > 5:
+                a = 11 # a redefined, cannot tell statically if this will exec
+            if x < 4:
+                b = 12
+            if a is None: # cannot prune, cannot determine if re-defn occurred
+                b += 5
+            else:
+                b += 7
+                if a < 0:
+                    return 10
+            return 30 + b
+
+        self.assert_prune(impl,
+                          (types.Array(types.float64, 2, 'C'),
+                           types.float64, types.NoneType('none'),),
+                          [None, None, None, None],
+                          np.zeros((2, 3)), 1., None)
+
+
+    def test_redefinition_analysis_different_block_cannot_exec(self):
+        # checks that a redefinition in a block guarded by something that
+        # has prune potential
+
+        def impl(array, x=None, a=None):
+            b = 0
+            if x is not None:
+                a = 11
+            if a is None:
+                b += 5
+            else:
+                b += 7
+            return 30 + b
+
+        self.assert_prune(impl,
+                          (types.Array(types.float64, 2, 'C'),
+                           types.NoneType('none'), types.NoneType('none')),
+                          [True, None],
+                          np.zeros((2, 3)), None, None)
+
+        self.assert_prune(impl,
+                          (types.Array(types.float64, 2, 'C'),
+                           types.NoneType('none'), types.float64),
+                          [True, None],
+                          np.zeros((2, 3)), None, 1.2)
+
+        self.assert_prune(impl,
+                          (types.Array(types.float64, 2, 'C'),
+                           types.float64, types.NoneType('none')),
+                          [None, None],
+                          np.zeros((2, 3)), 1.2, None)


Code review comments:
diff_hunk: @@ -313,7 +316,10 @@ def prune_by_type(branch, condition, blk, *conds):
 
     def prune_by_value(branch, condition, blk, *conds):
         lhs_cond, rhs_cond = conds
-        take_truebr = condition.fn(lhs_cond, rhs_cond)
+        try:
+            take_truebr = condition.fn(lhs_cond, rhs_cond)
+        except:
path: numba/analysis.py
text: @user1:
Use `except Exception` instead

@author:
done 7322229

diff_hunk: @@ -302,7 +302,10 @@ def prune_by_type(branch, condition, blk, *conds):
         lhs_none = isinstance(lhs_cond, types.NoneType)
         rhs_none = isinstance(rhs_cond, types.NoneType)
         if lhs_none or rhs_none:
-            take_truebr = condition.fn(lhs_cond, rhs_cond)
+            try:
+                take_truebr = condition.fn(lhs_cond, rhs_cond)
+            except:
path: numba/analysis.py
text: @user1:
Use `except Exception` instead

@author:
done 7322229