Repository: pytorch
Issue: DecompositionInterpreter creates invalid graph
Labels: triaged,module: nvfuser

### 🐛 Describe the bug

In FX's NVFuser backend (see nvfuser.py), DecompositionInterpreter implicitly assumes all placeholder nodes should happen before other types of nodes to avoid name confliction. For example,
```
placeholder    _softmax_backward_data_default_11  _softmax_backward_data_default_11  ()                                                                                                                   {}
call_function  div_tensor_23                      aten.div.Tensor                    (_softmax_backward_data_default_11, 8.0)                                                                             {}
placeholder    t_default_1                        t_default_1                        ()                                                                                                                   {}
call_function  t_default_357                      aten.t.default                     (t_default_1,)                                                                                                       {}
placeholder    view_default_9                     view_default_9                     ()                                                                                                                   {}
call_function  transpose_int_67                   aten.transpose.int                 (view_default_9, 1, 2)                                                                                               {}
placeholder    _unsafe_view_default_1             _unsafe_view_default_1             ()                                                                                                                   {}
call_function  transpose_int_70                   aten.transpose.int                 (_unsafe_view_default_1, 1, 2)                                                                                       {}
placeholder    _unsafe_view_default               _unsafe_view_default               ()                                                                                                                   {}
call_function  transpose_int_69                   aten.transpose.int                 (_unsafe_view_default, 1, 2)                                                                                         {}
placeholder    t_default                          t_default                          ()                                                                                                                   {}
call_function  t_default_361                      aten.t.default                     (t_default,)                                                                                                         {}
placeholder    t_default_2                        t_default_2                        ()                                                                                                                   {}
call_function  t_default_353                      aten.t.default                     (t_default_2,)                                                                                                       {}
call_function  view_default_411                   aten.view.default                  (div_tensor_23, [24, 12, 12])                                                                                        {}
placeholder    _unsafe_view_default_104           _unsafe_view_default_104           ()
```
is decomposed into
```
placeholder    _softmax_backward_data_default_11  _softmax_backward_data_default_11  ()                                                                                                         {}
call_function  div_tensor                         aten.div.Tensor                    (_softmax_backward_data_default_11, 8.0)                                                                   {}
placeholder    t_default_1                        t_default_1                        ()                                                                                                         {}
call_function  t_default                          aten.t.default                     (t_default_1,)                                                                                             {}
placeholder    view_default_9                     view_default_9                     ()                                                                                                         {}
call_function  permute_default                    aten.permute.default               (view_default_9, [0, 2, 1])                                                                                {}
placeholder    _unsafe_view_default_1             _unsafe_view_default_1             ()                                                                                                         {}
call_function  permute_default_1                  aten.permute.default               (_unsafe_view_default_1, [0, 2, 1])                                                                        {}
placeholder    _unsafe_view_default               _unsafe_view_default               ()                                                                                                         {}
call_function  permute_default_2                  aten.permute.default               (_unsafe_view_default, [0, 2, 1])                                                                          {}
placeholder    t_default_2                        t_default                          ()                                                                                                         {}
call_function  t_default_3                        aten.t.default                     (t_default_2,)                                                                                             {}
placeholder    t_default_4                        t_default_2                        ()                                                                                                         {}
call_function  t_default_5                        aten.t.default                     (t_default_4,)                                                                                             {}
call_function  view_default                       aten.view.default                  (div_tensor, [24, 12, 12])                                                                                 {}
placeholder    _unsafe_view_default_104           _unsafe_view_default_104           ()                                                                                                         {}                                                                                {}
```
where you can see in the later graph, `t_default` is no longer a graph input, which must be wrong. A small repro can be found below.
```python
import torch

torch.manual_seed(0)

def define_correct():
    fx_graph = torch.fx.Graph()
    a = fx_graph.placeholder("a")
    c = fx_graph.placeholder("view")
    b = fx_graph.call_function(torch.ops.aten.view, (a, [4, 1]))
    d = fx_graph.call_function(torch.ops.aten.view, (c, [4, 1]))
    e = fx_graph.call_function(torch.ops.aten.div.Tensor, (b, 8.0))
    f = fx_graph.call_function(torch.ops.aten.add.Tensor, (d, e))
    fx_graph.output(f)
    return fx_graph

def define_wrong():
    fx_graph = torch.fx.Graph()
    a = fx_graph.placeholder("a")
    b = fx_graph.call_function(torch.ops.aten.view, (a, [4, 1]))
    c = fx_graph.placeholder("view")
    d = fx_graph.call_function(torch.ops.aten.view, (c, [4, 1]))
    e = fx_graph.call_function(torch.ops.aten.div.Tensor, (b, 8.0))
    f = fx_graph.call_function(torch.ops.aten.add.Tensor, (d, e))
    fx_graph.output(f)
    return fx_graph
        
fx_module_correct = torch.fx.GraphModule(torch.nn.Module(), define_correct())
fx_module_wrong = torch.fx.GraphModule(torch.nn.Module(), define_wrong())

x = torch.randn(2, 2)
y = torch.randn(2, 2)
z_correct = fx_module_correct(x, y)
z_wrong = fx_module_wrong(x, y)
print(z_correct, z_wrong)
#tensor([[-0.8919],
#        [-1.4353],
#        [ 0.1310],
#        [ 0.9091]])
#tensor([[ 1.7336],
#        [-0.3301],
#        [-2.4511],
#        [ 0.6395]])
```
`define_correct` and `define_wrong` should produce the same graph but their outputs doesn't match.

### Versions

Latest PyTorch should reproduce it. A simple fix is
```diff
--- a/torch/fx/interpreter.py
+++ b/torch/fx/interpreter.py
@@ -118,7 +118,7 @@ class Interpreter:
             args = self.module.graph.process_inputs(*args)
         self.args_iter : Iterator[Any] = iter(args)
 
-        for node in self.module.graph.nodes:
+        for node in sorted(self.module.graph.nodes, key=lambda n: 0 if n.op == 'placeholder' else 1):
             if node in self.env:
                 # Short circuit if we have this value. This could
                 # be used, for example, for partial evaluation
```

Should I submit a PR to expose sorting as an argument of `torch.fx.Interpreter.run`? Or people prefer another fix like

```diff
diff --git a/torch/fx/graph.py b/torch/fx/graph.py
index 7b942052a1..ae66f3bc9c 100644
--- a/torch/fx/graph.py
+++ b/torch/fx/graph.py
@@ -774,6 +774,8 @@ class Graph:
 
         candidate = name if name is not None else self._target_to_str(target)
         name = self._graph_namespace.create_name(candidate, None)
+        if op == "placeholder":
+            target = name
         n = Node(self, name, op, target, args, kwargs, type_expr)
 ```