Adding utility functions for detecting and manipulating branches.

This PR pulls out some of the helper routines from the specialized_branched_loops code in PR #482 and provides some correctness testing for these visitors and mutators. These functions might be useful in other contexts, but the main reason for pulling them out into their own file is to help the readability of the specialize_branched_loops code, and make it easier to test them independently.
scope.begin() and scope.end() give you iterators for iterating through all
the stacks. You probably just want to inspect the top element of each
stack. However, I think it'd be more general if BranchesInVar accepted a
scope of vars and returned whether there was a branch in any of the vars in
the scope (similar to expr_uses_vars).

If there's a compelling reason to use a Scope\<Expr\>, then it just needs a
comment justifying why, and careful attention needs to be paid to
combinatorial explosion (i.e. there needs to be a test that specifically
constructs a nasty expression that might trip this up). Better to obviously
not explode than to not obviously explode. The latter requires a test.

On Tue, Nov 11, 2014 at 10:34 AM, Kree Cole-McLaughlin <
notifications@github.com> wrote:

> In src/BranchVisitors.cpp:
>
> > +    }
> > +
> > +    void visit(const Max *op) {
> > +        if (branch_on_minmax &&
> > +            (expr_uses_var(op->a, name, scope) ||
> > +             expr_uses_var(op->b, name, scope))) {
> > +            has_branches = true;
> > +        } else {
> > +            IRVisitor::visit(op);
> > +        }
> > +    }
> > +
> > +    template<class LetOp>
> > +    void visit_let(const LetOp *op) {
> > +        op->value.accept(this);
> > +        scope.push(op->name, op->value);
>
> I see your point, and for this visitor I think it would be possible to
> convert it to use this method. The main problem is the Scope<Expr> that
> is passed in, whose entries would not have been analyzed. To get around
> this I could change the way this visitor is used so that you pass it a
> Scope<int> (or Scope<T>) of variables that depend on the variable of
> interest.
>
> However, I can't quite see how this same approach would work with the
> linear solver, which is the other case where the Scope<Expr> that I am
> collecting in the specialize_branched_loops stuff gets used. In fact I
> have found a bug in this code, where this visitor (BranchesInVar) should
> actually only return true if the branch condition is linear in the
> variable, so I am going to have to modify it to use the linear solver to
> detect if the condition exprs are actually linear in the variable. Of
> course, I could do something similar to what you suggest and analyze bound
> variables for a linear dependence on the variable of interest.
>
> But eventually I do actually solve the linear equations and need the full
> exprs bound to each variable in the equation. So the question is whether it
> is worth having to track multiple scopes, e.g. one to store the variables
> that depend linearly on the variable of interest and another to store the
> actual exprs bound to each variable.
>
> Another way around this problem would be to provide a way to iterate over
> a scope in the stack order (or probably reverse stack order), rather than
> just via the map iterator. That way I could analyze incoming Scope<Expr>
> objects and build the tracking scope.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/halide/Halide/pull/547/files#r20169637>.
>