Faits:
A.
Par jugement du 17 août 2010, le Juge des districts de Martigny et St-Maurice a condamné Y._ pour contravention à la loi fédérale sur les stupéfiants (art. 19a LStup) et violation de l'art. 33 al. 1 let. a de la loi fédérale sur les armes, les accessoires d'armes et les munitions à une peine pécuniaire de 15 jours-amende et à une amende de 500 francs. Il l'a exempté de toute peine pour les faits en relation avec la violation des art. 123 al. 1 et 180 al. 1 CP (lésions corporelles simples et menaces) et a ordonné un traitement institutionnel dans un établissement psychiatrique ou pénitentiaire fermé ou dans la section fermée d'un établissement pénitentiaire ouvert (art. 59 al. 3 CP).
B.
B.a. Par ordonnance du 24 mai 2012, le Tribunal de l'application des peines et mesures du canton du Valais (TAPEM) a refusé à Y._ la libération conditionnelle, mis les frais à la charge de l'Etat du Valais et dit que ce dernier versera au conseil de Y._ une indemnité de 2'850 fr., débours par 350 fr. compris, à titre de dépens pour l'assistance judiciaire.
B.b. Par ordonnance du 9 juillet 2012, la Chambre pénale du Tribunal cantonal valaisan a rejeté, dans la mesure de sa recevabilité, le recours formé par Y._ et Me X._ contre l'ordonnance du 24 mai 2012. Elle a mis les frais de la procédure à la charge de l'Etat du Valais, au titre de l'assistance judiciaire gratuite, et dit que ce dernier versera au conseil de Y._ une indemnité de 1'000 fr. au même titre.
B.c. Par arrêt 6B_471/2012 - 6B_517/2012 du 21 janvier 2013, le Tribunal fédéral a partiellement admis le recours formé contre l'ordonnance du 9 juillet 2012 par Y._. Il a annulé celle-ci et renvoyé la cause à l'autorité précédente afin qu'elle établisse les éléments de fait permettant de poser un pronostic relatif aux chances de succès d'une libération conditionnelle, subsidiairement d'examiner l'instauration d'une mesure moins contraignante en milieu ouvert. Il a également constaté que la durée globale mise pour statuer consacrait une violation de l'art. 62d al. 1 CP et dit que Y._ devait bénéficier d'une dispense de frais de justice et obtenir une indemnité pour ses frais de défense tant devant le Tribunal fédéral que pour la procédure cantonale.
Par arrêt 6B_65/2013 du 11 février 2013, le Tribunal fédéral a dit que le recours de Me X._ contre l'ordonnance du 9 juillet 2012 était devenu sans objet compte tenu de l'arrêt 6B_471/2012 - 6B_517/2012 du 21 janvier 2013. Il a rayé la cause du rôle.
C.
Par décision du 1er mars 2013, le TAPEM a accordé la libération conditionnelle à Y._, dès son placement dans un établissement spécialisé dans la prise en charge de personnes souffrant de troubles psychiatriques, et fixé un délai d'épreuve de trois ans ainsi que des règles de conduite. Il lui a alloué une indemnité de dépens de 1'550 fr., débours compris.
D.
Par ordonnance du 23 avril 2013, la Chambre pénale du Tribunal cantonal du canton du Valais a joint les recours formés par Y._ contre l'ordonnance du 9 juillet 2012 et la décision du 1er mars 2013. Elle a réformé l'ordonnance du 9 juillet 2012, s'agissant des frais et dépens, en disant qu'il n'était pas perçu de frais et que l'Etat du Valais versera au conseil du recourant une indemnité réduite de 1'300 fr. au titre de l'assistance judiciaire pour la procédure devant le Tribunal cantonal. Elle a déclaré irrecevable le recours contre la décision du 1er mars 2013 et rejeté la demande d'assistance judiciaire y relative.
E.
Y._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'ordonnance du 23 avril 2013 (réf. 6B_507/2013). Il conclut, avec suite de frais et dépens, à l'annulation de cette décision et au renvoi de la cause au Tribunal cantonal pour qu'il constate un retard injustifié du TAPEM, le cas échéant avec allocation d'une indemnité (a), pour complément de l'instruction menée par cette autorité sur la légalité de ses conditions de détention du 17 septembre 2010 au 18 mars 2013, le cas échéant avec allocation d'une indemnité (b), pour octroi de l'assistance judiciaire complète pour la procédure devant le Tribunal cantonal (c) et pour exécution de l'arrêt 6B_471/2012 - 6B_517/2012 par l'allocation de dépens, et non d'une indemnité au titre de l'assistance judiciaire, pour la procédure devant le TAPEM et l'instance cantonale de recours (d). Il sollicite l'assistance judiciaire.
Me X._ forme un recours auprès du Tribunal pénal fédéral contre l'ordonnance du 23 avril 2013 (réf. 6B_445/2013). Il conclut à l'annulation de cette décision en tant qu'elle fixe l'indemnité d'avocat d'office pour l'ensemble de la procédure cantonale à 1'300 francs. Il requiert, avec suite de frais et dépens, que cette indemnité soit augmentée à 10'839 fr., soit 884 fr. de frais et débours, 7'955 fr. d'honoraires avec TVA p our la procédure devant le TAPEM et 2'000 fr. pour la procédure devant le Tribunal cantonal. Cette écriture a été transmise par le Tribunal pénal fédéral au Tribunal fédéral pour objet de sa compétence.
Interpellés sur le recours de Y._, le Ministère public du canton du Valais a renoncé à se déterminer, la Chambre pénale du Tribunal cantonal du canton du Valais a formulé des observations.
Considérant en droit:
1.
Les deux recours sont dirigés contre la même décision. Y._ réclame l'octroi de dépens en lieu et place d'une indemnité accordée au titre de l'assistance judiciaire. Me X._, conseil de Y._, se plaint du montant de cette dernière indemnité. Le sort du recours de Me X._ dépend par conséquent de celui de Y._. Il se justifie de joindre les causes et de statuer par un seul arrêt (art. 71 LTF et 24 PCF).
Recours de Y._ (6B_507/2013)
2.
Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (ATF 138 III 542 consid. 1 p. 542).
Le recourant conclut uniquement à l'annulation de l'ordonnance attaquée et au renvoi de la cause. Une telle manière de faire est correcte s'agissant des conclusions que le recourant déclare avoir prises devant l'autorité précédente sans que celle-ci n'entre en matière (cf. arrêt 2C_45/2011 du 3 octobre 2011 consid. 1.3). Elle ne l'est en principe pas s'agissant de l'indemnité de 1'300 fr., dont le recourant conteste la quotité et le titre auquel elle a été octroyée (cf. ATF 137 II 313 consid. 1.3 p. 317). Les motifs du recours et le libellé des conclusions en renvoi permettent toutefois de comprendre qu'il souhaite l'octroi non pas d'une indemnité au titre de l'assistance judiciaire mais de dépens, accordés à la partie qui obtient gain de cause, et ce pour un montant plus élevé. Cela suffit pour satisfaire aux exigences de forme déduites de l'art. 42 al. 1 et 2 LTF (cf. ATF 137 II 313 consid. 1.3 p. 317).
3.
Le recourant se plaint que l'indemnité pour les frais de défense, que le Tribunal fédéral avait invité l'autorité précédente à accorder au recourant pour la procédure cantonale (arrêt 6B_517/2012 - 6B_517/2012 du 21 janvier 2013 consid. 5.6), n'ait été prononcée par cette autorité qu'au titre de l'assistance judiciaire, réduite en conséquence de 30%, et n'ait porté que sur un montant de 1'300 fr. pour l'entier de la procédure cantonale. Il y voit une violation des art. 61 LTF, 30 et 36 de la loi valaisanne fixant le tarif des frais et dépens devant les autorités judiciaires ou administratives du 11 février 2009 (LTar/VS; RS/VS 173.8) et une fausse application de l'art. 135 al. 1 CPP.
3.1. L'autorité cantonale a rappelé que le recourant avait obtenu l'assistance judiciaire totale dans le cadre de la procédure cantonale, que le défenseur d'office était indemnisé par l'Etat du Valais conformément au tarif des avocats du canton du for du procès (art. 135 al. 1 CPP) quelle que soit l'issue de la procédure de recours. Elle a par conséquent modifié l'ordonnance du 9 juillet 2012 en ce sens qu'il n'était pas perçu de frais et que l'Etat du Valais versera à Me X._ une indemnité réduite de 1'300 fr. (précédemment 1'000 fr.) au titre de l'assistance judiciaire. Ce montant visait la procédure devant le Tribunal cantonal (ordonnance attaquée, dispositif, ch. 5 2; courrier de l'autorité précédente du 24 juillet 2013, p. 1). La décision du 24 mai 2012, mettant les frais à la charge de l'Etat demeurait inchangée.
3.2. L'arrêt de renvoi invitait l'autorité cantonale à statuer sans frais et à allouer des dépens pour la procédure cantonale. Une telle prescription ne visait pas à augmenter le montant à verser au conseil du recourant, celui-là n'étant pas lésé lui-même par la violation du principe de célérité, mais au contraire à s'assurer que le recourant ne supporterait pas de frais de procédure en rapport avec la constatation de cette violation. Or tel est le cas. En effet, le recourant ayant obtenu dans le cadre de la procédure cantonale concernée le bénéfice de l'assistance judiciaire, il n'a pas à supporter lui-même de frais envers son avocat, lequel a été indemnisé. De plus, l'autorité cantonale a gardé à la charge de l'Etat l'ensemble des frais de procédure (décision du 24 mai 2012 dispositif ch. 2 et ordonnance attaquée dispositif ch. 5 1), de sorte que les indemnités calculées au titre de l'assistance judiciaire en faveur de Me X._ (décision du 24 mai 2012 dispositif ch. 3 et ordonnance attaquée dispositif ch. 5 2) ne pourront pas être réclamées au recourant si sa situation économique devait s'améliorer. Il s'ensuit que le cadre de l'arrêt de renvoi a été respecté. Le grief est infondé.
3.3. Pour le surplus, la partie assistée d'un défenseur d'office n'a pas qualité pour contester devant le Tribunal fédéral l'indemnisation de son conseil, faute d'intérêt juridique sur ce point, l'avocat d'office n'ayant aucune prétention résiduelle à son égard (cf. ATF 122 I 322 consid. 3b p. 325 s.). Le recours est ainsi irrecevable en tant qu'il conteste la quotité des indemnités accordées au conseil d'office au titre de l'assistance judiciaire.
4.
Le recourant reproche à l'autorité cantonale de n'avoir pas statué sur ses conclusions, d'une part, en complément de l'instruction sur la légalité des conditions de sa détention entre le 17 septembre 2010 et le 18 mars 2013 et, d'autre part, en constat de la violation par le TAPEM du principe de célérité. Il dénonce une violation des art. 5 par. 1 let. e et par. 4 CEDH et 111 al. 3 LTF.
4.1. L'autorité précédente a repris les conclusions formulées dans le recours cantonal, dont celles mentionnées ci-dessus. Elle a rappelé que la libération conditionnelle du recourant avait été prononcée et que les conditions liées à celle-ci n'étaient pas contestées par ce dernier. Elle a ensuite considéré que le recourant réclamait uniquement l'octroi d'indemnités fondées sur la violation alléguée du principe de célérité (art. 5 par. 4 CEDH) et d'une détention irrégulière (art. 5 par. 1 let. e CEDH), que ces demandes d'indemnisation sortaient du cadre des procédures d'indemnisation prévues par le CPP et que toutes autres prétentions pour actes illicites d'un fonctionnaire ou d'un magistrat relevaient des autorités compétentes prévues par la législation ordinaire, à savoir en Valais par la loi sur la responsabilité des collectivités publiques et de leurs agents du 10 mai 1978 (RS/VS 170.1; ordonnance attaquée, p. 4 et 5). L'autorité précédente a en conséquence déclaré irrecevable le recours formé contre la décision du 21 mars 2013 et rejeté la demande d'assistance judiciaire formulée dans ce recours. Elle a ajouté que le reproche fait par le recourant au TAPEM d'être resté pratiquement inactif était inopérant, vu l'interpellation faite par ses soins (ordonnance attaquée, p. 5 et 6).
Ce raisonnement ne permet pas de comprendre si l'autorité cantonale a estimé n'être pas compétente pour se prononcer, non seulement sur l'indemnisation de violations de la CEDH, mais également sur l'examen et le constat de ces violations ou si elle a considéré qu'elle n'avait plus à entrer en matière sur ces demandes d'examen et de constat, le recourant ayant été libéré conditionnellement par le TAPEM.
4.2. L'art. 5 CEDH peut être invoqué par la personne soumise à un traitement institutionnel dans un établissement psychiatrique ou pénitentiaire fermé ou dans la section fermée d'un établissement pénitentiaire ouvert au sens de l'art. 59 al. 3 CP (cf. ATF 136 IV 156 consid. 3.2 p. 161). Conformément à l'art. 5 par. 4 CEDH, la personne soumise à une telle mesure a donc droit d'introduire un recours devant un tribunal, afin qu'il statue à bref délai sur la légalité de sa détention et ordonne sa libération si la détention est illégale.
En matière de détention provisoire, également soumise à l'exigence de célérité posée par l'art. 5 par. 4 CEDH, la jurisprudence a jugé que le prévenu qui estime avoir subi, du fait de la mise en détention provisoire, un traitement prohibé par l'art. 3 CEDH, dispose d'un droit propre à ce que les agissements dénoncés fassent l'objet d'une enquête prompte et impartiale. Même si les violations alléguées se rapportent au régime carcéral auquel le détenu a été soumis, et non au principe même de la mise en détention qui était l'objet de la décision du tribunal des mesures de contrainte, c'est à cette juridiction, investie du contrôle de la détention, qu'il appartient d'intervenir en cas d'allégations crédibles de traitement prohibés (ATF 139 IV 41 consid. 3.1 p. 43 et références citées).
Cette jurisprudence doit être transposée au présent cas où le recourant était soumis à un traitement institutionnel en milieu fermé. Dans cette hypothèse et afin d'assurer à l'intéressé une enquête prompte, c'est à l'autorité investie du contrôle de cette mesure de privation de liberté d'intervenir en cas d'allégations crédibles de violations de la CEDH, d'examiner et de constater, cas échéant, de telles violations. En l'espèce, cette autorité est le TAPEM (décision du 1er mars 2013, p. 4). C'est donc ce tribunal qui devait examiner le grief de violation de la CEDH et le trancher, pour peu qu'il ait été correctement soulevé. L'autorité précédente, en tant qu'autorité de recours des décisions du TAPEM (ordonnance attaquée, p. 4), était compétente pour examiner la décision du TAPEM à cet égard, de même que pour étudier et cas échéant constater la violation du principe de célérité par le TAPEM. Si elle pouvait renvoyer le recourant à agir devant les autorités cantonales compétentes en matière d'indemnisation, elle ne le pouvait que sur l'indemnité, non sur le constat préalable de la violation de la CEDH invoquée (dans ce sens ATF 137 I 296 consid. 6 p. 303).
Il résulte de ce qui précède que l'autorité précédente était compétente pour examiner les deux griefs de violation de la CEDH invoqués.
4.3. Reste à savoir si elle devait entrer en matière sur ceux-ci, alors que le recourant avait été libéré conditionnellement - par décision du 1er mars 2013 exécutée le 18 mars 2013.
Aux termes de l'art. 111 al. 3 LTF, l'autorité qui précède immédiatement le Tribunal fédéral doit pouvoir examiner au moins les griefs visés aux art. 95 à 98 LTF. Le principe de l'épuisement des instances est observé, au sens de l'art. 111 al. 3 LTF, lorsque le recourant est à même d'invoquer, devant la dernière autorité cantonale, tous les griefs qu'il pourra par la suite soulever devant le Tribunal fédéral, sans qu'il ne soit pour autant nécessaire que l'autorité analyse ces questions d'office. Pour déterminer si le Tribunal cantonal était en droit de ne pas entrer en matière sur le recours de l'intéressé, il convient donc de vérifier de quelle manière, confronté à une situation similaire dans laquelle la libération du recourant serait intervenue ou la décision attendue aurait été rendue en cours de procédure devant le Tribunal fédéral, ce dernier l'aurait résolue. Si le Tribunal fédéral était entré en matière, le Tribunal cantonal aurait dû, conformément à l'art. 111 al. 3 LTF, se prononcer sur le fond (cf. ATF 137 I 296 consid. 4.1 p. 298 s. et les références citées).
La qualité pour recourir auprès du Tribunal fédéral suppose en principe un intérêt actuel et pratique à obtenir l'annulation de la décision attaquée. Cet intérêt doit exister tant au moment du dépôt du recours qu'à celui où l'arrêt est rendu. A priori, il n'existe plus lorsqu'une personne recourant contre sa détention est libérée durant la période de recours. Le Tribunal fédéral a néanmoins jugé que l'autorité de recours doit entrer en matière pour examiner le caractère licite de la détention d'une personne libérée en cours de la procédure, dans la mesure où la partie recourante invoque d'une manière défendable une violation de l'art. 5 CEDH (ATF 137 I 296 consid. 4.3 p. 299 ss et les références citées).
Dans une telle hypothèse, le recourant doit se prévaloir expressément, devant les autorités judiciaires, d'une violation de la CEDH et rendre défendable son grief, ce qui présuppose une obligation de motivation accrue comparable à celle déjà prévue à l'art. 106 al. 2 LTF (ATF 137 I 296 consid. 4.3.4 p. 302).
4.4. Le recourant reproche à l'autorité précédente de n'avoir pas jugé le refus du TAPEM d'examiner la légalité de sa détention aux Etablissements de la plaine de l'Orbe au regard de l'art. 5 par. 1 let. e et par. 4 CEDH. Il se plaint également de la régularité de son séjour à la Prison des Iles.
4.4.1. Selon l'art. 5 par. 1 let. e CEDH, toute personne a droit à la liberté et à la sûreté. Nul ne peut être privé de sa liberté, sauf selon les voies légales et s'il s'agit, notamment, de la détention régulière d'un aliéné. Selon la jurisprudence de la Cour européenne, un individu ne peut passer pour « aliéné » au sens de l'art. 5 par. 1 let. e CEDH et subir une privation de liberté que si les trois conditions suivantes au moins se trouvent réunies : premièrement, son aliénation doit avoir été établie de manière probante ; deuxièmement, le trouble doit revêtir un caractère ou une ampleur légitimant l'internement ; troisièmement, l'internement ne peut se prolonger valablement sans la persistance de pareil trouble. Il faut également un certain lien entre, d'une part, le motif invoqué pour la privation de liberté autorisée et, de l'autre, le lieu et le régime de la détention. En principe, la « détention » d'une personne comme malade mental ne sera « régulière » au regard de l'article 5 par. 1 let. e CEDH que si elle se déroule dans un hôpital, une clinique ou un autre établissement approprié (arrêt de la CourEDH Stanev c/ Bulgarie du 17 janvier 2012, par. 145 et 147 et arrêts cités).
Aux termes de l'art. 59 al. 2 CP, le traitement institutionnel des troubles mentaux s'effectue dans un établissement psychiatrique approprié ou dans un établissement d'exécution des mesures. Le législateur vise, en premier lieu, les cliniques psychiatriques publiques ou privées qui offrent un traitement approprié pour les troubles mentaux en cause. Comme les cliniques psychiatriques ne sont pas toujours prêtes et à même de prendre en charge des patients peu coopératifs, le législateur a prévu que de telles mesures pouvaient également être exécutées au sein d'un établissement spécialisé d'exécution des mesures. Celui-ci doit être dirigé ou surveillé par un médecin. Il faut en outre qu'il dispose des installations nécessaires ainsi que d'un personnel disposant d'une formation appropriée et placé sous surveillance médicale (arrêts 6B_538/2013 du 14 octobre 2013 consid. 6.1.1; 6B_384/2010 du 15 décembre 2010 consid. 2.1.1; 6B_629/2009 du 21 décembre 2009 consid. 1.2.1). L'art. 59 al. 3 CP prévoit que, tant qu'il existe un risque de fuite ou de récidive, le traitement doit être exécuté dans un établissement fermé. Il peut aussi être effectué dans un établissement pénitentiaire au sens de l'art. 76 al. 2 CP, dans la mesure où le traitement thérapeutique nécessaire est assuré par du personnel qualifié (art. 59 al. 3 2e phrase CP).
4.4.2. A la suite du jugement du 17 août 2010 ordonnant un traitement institutionnel dans un établissement psychiatrique ou pénitentiaire fermé ou dans la section fermée d'un établissement pénitentiaire ouvert, le recourant est demeuré à la Prison des Iles jusqu'au 3 mars 2011. A cette date, il a été transféré aux EPO où il a séjourné jusqu'au 18 mars 2013. Le recours en matière pénale reprend les arguments formulés devant l'autorité précédente (recours, p. 10 renvoyant aux p. 5 et 6 et recours du 21 mars 2013, p. 6 à 8). Il en résulte que le recourant conteste la réalisation de la condition d'un établissement approprié estimant que la nécessité de déroger à un tel établissement ne se présumait pas. Au milieu de nombreuses réflexions d'ordre général impropres à rendre, pour peu qu'elles soient recevables, défendable son grief de violation de l'art. 5 par. 1 let. e CEDH concernant sa détention, le recourant formule deux critiques concrètes à savoir qu'il a été enfermé en cellule 23 h sur 24 h et n'a pas bénéficié de soins psychiatriques. De telles critiques de son séjour ne permettent pas d'être infirmées par les faits retenus dans l'ordonnance attaquée. L'ordonnance du 9 juillet 2012, p. 2, relève quant à elle que le directeur des établissements pénitentiaires du Valais (EPV), invité à faire exécuter la mesure institutionnelle prononcée le 17 août 2010, a signalé, par courrier du 11 octobre 2010, que les établissements susceptibles d'accueillir le recourant étaient pleins et disposaient d'une liste d'attente d'environ 8 mois. Un examen sommaire du dossier ne permet pas de penser que le recourant ait bénéficié de soins psychiatriques à la Prison des Iles. Au vu de ces éléments, le grief invoqué était prima facie défendable.
4.4.3. Il découle de ce qui précède que, si le recourant avait été libéré après avoir porté son recours devant le Tribunal fédéral, les conditions permettant à ce dernier de déroger à l'exigence de l'intérêt actuel et d'examiner le fond du litige auraient été réunies. Par conséquent, en n'entrant pas en matière sur le grief de violation de l'art. 5 par. 1 let. e CEDH invoqué par le recourant, le Tribunal cantonal a privé celui-ci de la possibilité de faire valoir ce moyen devant le Tribunal fédéral et a donc violé l'art. 111 al. 3 LTF. En empêchant le recourant de faire examiner l'illicéité alléguée, la décision querellée a en outre violé l'art. 5 par. 4 CEDH. La présente cause devra dès lors être renvoyée à l'instance précédente pour qu'elle entre en matière sur le grief invoqué. Si elle aboutit à la conclusion que la détention subie était illégale, il lui appartiendra soit de se prononcer elle-même, pour des motifs liés à l'économie de la procédure, sur l'indemnisation requise par le recourant soit de transmettre la cause à l'autorité cantonale compétente en matière de responsabilité de l'Etat (ATF 137 I 296 consid. 6 p. 303 s.). Le grief de violation de l'art. 5 par. 1 let. e et par. 4 CEDH apparaissant prima facie défendable, l'assistance judiciaire demandée devra lui être accordée (art. 29 al. 3 Cst.).
4.5. S'agissant de la violation du principe de célérité, consacré par l'art. 5 par. 4 CEDH, le recourant se plaint, en détaillant les étapes de la procédure ouverte à la suite de sa requête du 14 septembre 2012, que le TAPEM ait tranché celle-ci après 131 jours.
En l'espèce, cette requête, formulée par le recourant lui-même, tendait à obtenir le contrôle annuel de la mesure thérapeutique institutionnelle au sens de l'art. 62d al. 1 CP (décision du 1er mars 2013, p. 2). A réception, le TAPEM a écrit au recourant pour lui indiquer qu'une décision ayant été rendue à ce sujet le 24 mai 2012, le prochain contrôle aura lieu en mai 2013. Sur recours du conseil du recourant, l'autorité précédente a toutefois considéré, le 11 octobre 2012, que le TAPEM devait entrer en matière sur la requête et la traiter comme une demande de réexamen. Par la suite, le recourant a joint à sa demande initiale d'autres questions, notamment quant à la légalité de sa détention, et requis l'administration de mesures d'instruction "avant toute décision". Une telle manière de faire n'était pas propre à permettre au TAPEM de statuer rapidement sur la requête initiale du recourant. Cela étant, rien n'explique, dans les circonstances d'espèces, que cette autorité ait attendu deux semaines pour transmettre au recourant copie du rapport médical visé par l'art. 62d al. 1 CP, ni qu'elle ait mis plus de quarante jours pour se déterminer sur les mesures d'instruction à nouveau requises par le recourant. Une telle manière de faire n'apparaît pas, dans les circonstances spécifiques du cas d'espèce dans lequel une violation du principe de célérité a déjà été constatée, compatible avec ce principe. Le grief est ainsi non seulement défendable, mais également fondé de sorte que l'autorité cantonale aurait dû entrer en matière.
Pour des motifs d'économie de procédure, il convient de constater dans le présent considérant la violation du principe de célérité par le TAPEM. Bien que le recours en matière pénale ne soit admis que partiellement, le recourant sera dispensé de frais de justice et une indemnité pour ses frais de défense lui sera accordée (cf. ATF 139 IV 179 consid. 2.7 p. 186; 137IV 118 consid. 2.2 p. 121 et 92 consid. 3.2.3 p. 98). Le recourant avait demandé à bénéficier de l'assistance judiciaire dans la procédure cantonale. Dans le cadre du renvoi (supra consid. 4.4.3), celle-ci devra donc également lui être accordée s'agissant du pan de la procédure concernant la violation du principe de célérité et les frais définitivement mis, pour cette question, à charge de l'Etat.
5.
Il résulte de ce qui précède que le recours doit être partiellement admis, l'ordonnance attaquée annulée et la cause renvoyée à l'autorité cantonale pour nouvelle instruction et nouvelle décision dans le sens des considérants. Le recours doit être rejeté pour le surplus dans la mesure où il est recevable.
Vu le sort du recours et le constat de violation du principe de célérité qui précède, il se justifie, pour la procédure devant le Tribunal fédéral, d'accorder une indemnité de dépens au recourant à la charge du canton du Valais (art. 68 al. 1 et 2 LTF) et de renoncer à percevoir des frais judiciaires pour la présente procédure (art. 66 al. 4 LTF). La requête d'assistance judiciaire est dès lors sans objet.
Recours de Me X._ (6B_445/2013)
Le recourant se plaint de l'insuffisance des indemnités au titre de l'assistance judiciaire que lui ont accordées le TAPEM par 2'850 fr. et l'autorité précédente par 1'300 francs.
6.
La décision attaquée ayant trait à la fixation d'une indemnité de défenseur d'office dans le cadre d'une défense pénale, le recours en matière pénale auprès du Tribunal fédéral est ouvert (arrêt 6B_638/2012 du 10 décembre 2012 consid. 1).
7.
Le CPP n'est pas directement applicable à la procédure de libération conditionnelle d'une mesure thérapeutique (cf. art. 439 al. 1 CPP). L'art. 135 al. 3 let. b CPP, réservant la compétence du Tribunal pénal fédéral, est ainsi sans portée.
8.
Dans la mesure où elles ne résultent pas du jugement attaqué, les pièces produites par le recourant sont irrecevables (art. 99 al. 1 LTF). Les griefs que le recourant fonde sur ces pièces suivent le même sort.
9.
Le recourant soutient que l'indemnité au titre de l'assistance judiciaire de 1'300 fr., prévue au ch. 5.2 du dispositif de l'ordonnance attaquée, serait choquante dès lors qu'elle concernerait l'entier de la procédure cantonale. Ce grief est infondé: le dispositif prévoit expressément que ce montant ne vise que la procédure devant le Tribunal cantonal.
Le recourant ne présente pour le surplus aucune critique spécifique quant à cette indemnité. Sa conclusion visant à en obtenir l'augmentation doit par conséquent être écartée.
10.
10.1. S'agissant de la procédure devant le TAPEM, l'ordonnance du 9 juillet 2012 (p. 18 et 19) retient que l'art. 36 LTar/VS prévoit qu'en cas de procédure devant cette autorité les honoraires sont fixés entre 300 et 2'200 francs. L'art. 29 LTar/VS permet une augmentation du tarif dans les causes ayant nécessité un travail particulier. Aux termes de l'art. 30 al. 1 LTar/VS, le conseil juridique habilité à se faire indemniser en vertu des dispositions en matière d'assistance judiciaire perçoit, en sus du remboursement de ses débours justifiés, des honoraires correspondant au 70 % des honoraires fixés aux art. 31 à 40 LTar/VS, mais au moins à une rémunération équitable telle que définie par la jurisprudence du Tribunal fédéral. L'autorité cantonale a confirmé le montant de 2'500 fr. accordé par l'autorité de première instance, retenant treize heures de démarches nécessaires au traitement de la cause et un tarif horaire de 182 fr. (70% x 260 fr.), plus TVA. Elle a également approuvé le montant des débours alloués à hauteur de 350 francs.
10.2. Sauf dans les cas cités expressément à l'art. 95 LTF - non réalisés ici -, la violation du droit cantonal ne constitue pas un motif de recours en tant que tel. La partie recourante peut uniquement se plaindre de ce que l'application du droit cantonal par l'autorité précédente consacre une violation du droit fédéral au sens de l'art. 95 let. a LTF, en particulier qu'elle est arbitraire (ATF 138 V 67 consid. 2.2 p. 69). Le Tribunal fédéral n'examine le moyen fondé sur la violation d'un droit constitutionnel ou du droit cantonal que si le grief a été invoqué et motivé de manière précise (art. 106 al. 2 LTF).
10.3. Le recourant estime que les autorités cantonales ont ignoré l'art. 29 LTar/VS précité. Tel n'est pas le cas, les autorités cantonales ayant implicitement appliqué cette disposition en accordant, respectivement en confirmant un montant supérieur à la fourchette prévue par l'art. 36 LTar/VS. Pour le surplus, le recourant ne démontre pas que l'application de l'art. 29 LTar/VS imposait, sous peine de tomber dans l'arbitraire, l'allocation d'une indemnité plus élevée.
10.4. Le recourant soutient que l'autorité cantonale n'a pas tenu compte, de manière arbitraire, de plusieurs démarches résultant de sa liste d'opérations. La reprise des différentes démarches de cette liste, en invoquant en substance que chacune d'elles ne pouvait, sous peine d'arbitraire, être considérée comme non nécessaire au traitement de la cause constitue une argumentation de nature purement appellatoire, insuffisante à démontrer que le nombre d'heures retenu par l'autorité précédente était insoutenable. Le grief est à cet égard irrecevable.
10.5. Le recourant estime que les décisions des autorités cantonales violeraient la liberté économique et l'interdiction de l'arbitraire dès lors qu'elles ne respecteraient pas la rémunération horaire minimale fixée par la jurisprudence à hauteur de 180 fr. en 2006 et de 200 fr. en 2012.
L'indemnité allouée à l'avocat d'office doit en principe, pour être compatible avec l'interdiction de l'arbitraire (art. 9 Cst.) et la garantie de la liberté économique (art. 27 Cst.), correspondre à une rémunération horaire de l'ordre de 180 fr., TVA non comprise, sous réserve de circonstances particulières liées notamment aux charges fixes plus ou moins élevées suivant le canton dans lequel pratique l'avocat concerné (cf. ATF 137 III 185 consid. 5.4 p. 190; 132 I 201 consid. 7 et 8 p. 205 ss; plus récemment arrêts 9C_735/2011 du 22 juin 2012 consid. 3 et 6B_502/2013 du 3 octobre 2013 consid. 3.2).
Dans un arrêt 2C_725/2010 du 31 octobre 2011, cité par le recourant, le Tribunal fédéral a jugé, ad consid. 2, que l'on pouvait tout au plus inférer de la cherté notoire de la vie à Genève que l'indemnité horaire pour un conseil d'office prévue par la législation cantonale genevoise à hauteur de 200 fr. constituait un minimum si l'on tenait compte du montant de 180 fr. préconisé par l'ATF 132 I 201 en 2006 (moyenne nationale) et de l'augmentation des prix intervenue depuis lors (entre 3 et 4 %).
Le recourant n'exerce pas dans le canton de Genève, de sorte qu'il ne peut, faute d'élément recevable allant dans ce sens, rien tirer de cet arrêt en sa faveur. Le montant minimal horaire de 180 fr. a pour le surplus été confirmé récemment s'agissant d'un avocat exerçant dans le canton du Valais (arrêt 6B_502/2013 du 3 octobre 2013 consid. 3.2). Ce taux horaire a été respecté (cf. supra consid. 10.1 ). Le grief de violation de la liberté économique et d'arbitraire est dès lors infondé.
10.6. Le recourant critique également le montant des débours octroyés par 350 fr. alors qu'il demandait un remboursement de 884 francs. Il invoque que le TAPEM n'aurait rien donné pour les déplacements (recours, p. 13). Il ne le démontre toutefois pas, l'autorité précédente ayant retenu que les débours octroyés couvraient les frais de déplacement pour les visites au client et la séance (ordonnance du 9 juillet 2012, p. 19). Il ne formule pour le surplus aucun grief recevable sur ce point. Son moyen doit dès lors être rejeté, dans la mesure de sa recevabilité.
11.
Il résulte de ce qui précède que le recours doit être rejeté, dans la mesure de sa recevabilité, aux frais du recourant (art. 66 al. 1 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1.
Les causes 6B_445/2013 et 6B_507/2013 sont jointes.
2.
Le recours 6B_507/2013 est partiellement admis, l'ordonnance attaquée est annulée et la cause renvoyée à l'autorité cantonale pour nouvelle décision. Le recours est rejeté pour le surplus dans la mesure où il est recevable.
3.
Il n'est pas perçu de frais pour la cause 6B_507/2013.
4.
Le canton du Valais versera à Y._ une indemnité de 3'000 fr. à titre de dépens pour la procédure 6B_507/2013 devant le Tribunal fédéral.
5.
La demande d'assistance judiciaire de Y._ est sans objet.
6.
Le recours 6B_445/2013 est rejeté dans la mesure où il est recevable.
7.
Les frais judiciaires pour la cause 6B_445/2013, arrêtés à 2'000 fr., sont mis à la charge de Me X._.
8.
Le présent arrêt est communiqué aux parties et à la Chambre pénale du Tribunal cantonal du canton du Valais.
Lausanne, le 14 janvier 2014
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Cherpillod