Faits :
A.
X._, né en 1994, a été incarcéré à la prison préventive de Martigny du 24 septembre 2013 au 11 juillet 2016 (hormis trois jours), puis à la prison de Sion depuis cette date.
Par jugement du Tribunal d'arrondissement du district de St-Maurice du 25 mars 2015, X._ a été reconnu coupable de meurtre (commis en 2013) et de brigandage et condamné à une peine privative de liberté de huit ans, sous déduction de la détention subie avant jugement. Le tribunal a renoncé à prononcer un placement dans un établissement pour jeunes adultes (<ref-law>) au motif que les experts l'avaient préconisé avec grande réserve, notamment en raison du manque de motivation de X._, dont la personnalité (type dyssociale avec prototype de psychopathie) était peu accessible à un traitement psychiatrique.
Statuant sur appel par jugement du 2 décembre 2015, le Tribunal cantonal du canton du Valais, Cour pénale II, a ramené la peine privative de liberté à sept ans et l'a suspendue au profit du placement de l'intéressé dans un établissement pour jeunes adultes (<ref-law>).
Dans le cadre de l'examen annuel de la mesure, le Tribunal d'application des peines et mesures (ci-après: TAPEM) a, par décision du 20 juin 2017, levé la mesure applicable aux jeunes adultes, faute d'établissement approprié (art. 62c al. 1 let. c CP) et a ordonné l'exécution du reste de la peine privative de liberté de sept ans (<ref-law>). Le TAPEM a constaté que les conditions de la libération conditionnelle n'étaient pas réalisées, l'intéressé n'ayant pas encore purgé les deux tiers de la peine (<ref-law>).
B.
Les 8 mai 2017 et 21 décembre 2017, X._ a déposé auprès du TAPEM, une requête en constatation de l'illicéité de sa détention. Le 19 février 2018, il a requis le constat de l'illicéité de ses conditions de détention depuis le 21 mai 2015.
Par décision du 15 mai 2018, le TAPEM a rejeté sa requête.
C.
Par ordonnance du 7 février 2019, la Chambre pénale du Tribunal cantonal du Valais a partiellement admis le recours formé par X._ contre la décision du TAPEM et a constaté que sa détention à la prison de Sion, subie entre le 2 novembre 2016 et le 20 juin 2017, a contrevenu à l'art. 5 par. 1 let. e CEDH. Pour le surplus, il a rejeté le recours s'agissant des conditions de détention (art. 3 CEDH) et a déclaré irrecevables les conclusions tendant à une indemnisation en renvoyant le recourant à agir par la voie civile.
D.
X._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'ordonnance du 7 février 2019. Il conclut avec suite de frais et dépens, principalement, à sa réforme en ce sens qu'il est constaté que sa détention à la prison de Sion subie entre le 21 novembre 2015 et le 20 juin 2017 a contrevenu à l'art. 5 par. 1 let. e CEDH, la cause étant renvoyée au Tribunal cantonal s'agissant du sort des frais et dépens cantonaux. Subsidiairement, il conclut à l'annulation de l'ordonnance et au renvoi de la cause au Tribunal cantonal pour nouvelle décision. Il sollicite en outre l'octroi de l'assistance judiciaire.

Considérant en droit :
1.
Le recourant ne discute d'aucune manière la motivation de l'ordonnance entreprise sous l'angle de la licéité des conditions de détention (art. 3 CEDH). Faute de développement et à défaut de conclusion sur ce point, il n'y a pas lieu de l'examiner (art. 42 al. 2 et 106 al. 2 LTF).
Est seule litigieuse en l'espèce, la question de l'illicéité de la détention. Le recourant conteste exclusivement la durée de la détention jugée illicite. Il prétend, dans son mémoire de recours, que sa détention était illicite à partir du 2 décembre 2015, date du prononcé de la mesure (<ref-law>). En cela, il s'écarte de ses conclusions formelles. Subsidiairement, il prétend qu'elle était à tout le moins illicite depuis le 2 juin 2016, à savoir, six mois après le jugement condamnatoire. Il se plaint d'une violation de l'art. 5 par. 1 CEDH et d'une interprétation arbitraire de la chronologie des faits sur ce point.
1.1.
1.1.1. Selon l'<ref-law>, si l'auteur avait moins de 25 ans au moment de l'infraction et qu'il souffre de graves troubles du développement de la personnalité, le juge peut ordonner son placement dans un établissement pour jeunes adultes aux conditions suivantes: l'auteur a commis un crime ou un délit en relation avec ces troubles (let. a); il est à prévoir que cette mesure le détournera de nouvelles infractions en relation avec ces troubles (let. b). Selon l'<ref-law>, les établissements pour jeunes adultes doivent être séparés des autres établissements prévus par le CP. Il incombe à l'autorité d'exécution de trouver une institution appropriée pour l'exécution de la mesure ordonnée par le juge (arrêt 6B_842/2016 du 10 mai 2017 consid. 3.1.2).
La mesure prévue à l'<ref-law> est ordonnée principalement en raison de l'état personnel du jeune adulte délinquant et de sa capacité à recevoir un soutien socio-pédagogique et thérapeutique pouvant influencer favorablement le développement de sa personnalité. Un tel placement doit par conséquent être réservé aux jeunes adultes qui peuvent encore être largement influencés dans leur développement et qui apparaissent accessibles à cette éducation. Moins l'intéressé semble encore malléable, moins cette mesure peut entrer en considération. En outre, les carences du développement pertinentes sous l'angle pénal doivent pouvoir être comblées par l'éducation, en tout cas dans la mesure où ce moyen permet de prévenir une future délinquance. Le placement implique une disposition minimale à coopérer, le jeune adulte devant présenter un minimum de motivation (cf. <ref-ruling> consid. 2.1.2 p. 52; arrêt 6B_1321/2017 du 26 avril 2018 consid. 4.1).
L'art. 62c al. 1 let. c CP prévoit la levée de la mesure s'il n'y a pas ou plus d'établissement approprié. Selon l'al. 2, si la durée de la privation de liberté entraînée par la mesure est inférieure à celle de la peine privative de liberté suspendue, le reste de la peine est exécuté (1ère phrase).
Par opposition au système moniste antérieur, le droit pénal des mineurs entré en vigueur le 1er janvier 2007 consacre, à l'instar du Code pénal pour les adultes, le système dualiste (dualistisch-vikariierend), dans lequel, dans la règle, en plus d'une mesure, une peine doit être prononcée si le mineur a agi de manière coupable (<ref-ruling> consid. 2.2 p. 362). Dans ce système, la mesure est exécutée prioritairement. La privation de liberté résultant de son exécution est imputée sur la peine, dont le solde, cas échéant positif, n'est pas exécuté dans l'hypothèse du succès de la mesure. Afin de favoriser l'effet attendu de la mesure (effet de resocialisation dans les mesures pour adultes; effet éducatif dans les mesures pour les mineurs ou effet thérapeutique), l'exécution de celle-ci remplace en grande part la peine elle-même et a la priorité sur cette dernière (<ref-ruling> consid. 2.2 p. 362).
1.1.2. En vertu de l'art. 5 par. 1 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é (art. 5 par. 1 let. e CEDH).
Dans sa jurisprudence, la CourEDH considère que pour respecter l'art. 5 par. 1 CEDH la détention doit avoir lieu " selon les voies légales " et " être régulière ". En la matière, elle renvoie pour l'essentiel à la législation nationale et consacre l'obligation d'en respecter les normes de fond comme de procédure. Elle exige de surcroît la conformité de toute privation de liberté au but de l'art. 5 CEDH: protéger l'individu contre l'arbitraire. Il doit exister un lien entre le motif censé justifier la privation de liberté et le lieu ainsi que les conditions de la détention. En principe, la " détention " d'une personne souffrant de troubles mentaux ne peut être considérée comme " régulière " aux fins de l'art. 5 par. 1 let. e CEDH que si elle s'effectue dans un hôpital, dans une clinique ou dans un autre établissement approprié. Le seul fait que l'intéressé ne soit pas intégré dans un établissement approprié n'a toutefois pas pour effet automatique de rendre sa détention irrégulière au regard de l'art. 5 par. 1 CEDH. Un équilibre raisonnable doit être ménagé entre les intérêts opposés en cause, étant entendu qu'un poids particulier doit être accordé au droit à la liberté. Dans cet esprit, la CourEDH prend en compte les efforts déployés par les autorités internes en vue de trouver un établissement adapté pour évaluer la régularité du maintien en détention dans l'intervalle (arrêts de la CourEDH Papillo c. Suisse du 27 janvier 2015 [requête n° 43368/08], § 41 ss et les arrêts cités; De Schepper c. Belgique du 13 octobre 2009, [requête n° 27428/07], § 48; cf. arrêt 6B_1264/2017 du 23 mai 2018 consid. 6.1).
Ces principes doivent également trouver application lorsque l'intéressé fait l'objet d'une mesure thérapeutique institutionnelle applicable aux jeunes adultes au sens de l'<ref-law> mais que, dans l'attente d'une place disponible dans un établissement idoine, il est détenu dans un établissement pénitentiaire fermé (arrêt 6B_842/2016 du 10 mai 2017 consid. 3.1.1). L'Etat a l'obligation de mettre à disposition en nombre suffisant des places dans des établissements appropriés. Un séjour dans un établissement d'exécution des peines est envisageable pour autant qu'il soit nécessaire afin de trouver un établissement approprié. Il faut notamment examiner l'intensité des efforts fournis par l'autorité pour trouver un tel lieu d'accueil. Si la détention s'étend sur une durée plus longue en raison de problèmes de capacité connus, elle est contraire à l'art. 5 CEDH (cf. <ref-ruling> consid. 5.8.1 p. 117 et les références citées).
1.1.3. Dans l'affaire Papillo, concernant la Suisse, la CourEDH s'est penchée sur la détention d'une personne souffrant de manie avec symptômes psychotiques, soumis à une mesure institutionnelle du fait de son irresponsabilité. Après le prononcé de cette mesure, l'intéressé était demeuré en détention durant près de deux mois, puis avait été interné dans une clinique pendant un peu plus de trois mois, avant d'être replacé en détention, où il resta, faute de trouver une place en institution acceptée par lui, durant dix mois. Sa liberté conditionnelle fut ensuite prononcée. Durant sa détention, il bénéficia de consultations médicales régulières et d'un traitement par neuroleptiques. Relevant en substance que les autorités avaient pris contact avec plusieurs institutions susceptibles d'accueillir le requérant, que ce dernier avait refusé de se rendre à un entretien auprès de l'une d'elles et qu'il avait bénéficié de consultations médicales régulières et d'un traitement neuroleptique, la CourEDH a jugé que la détention jusqu'à sa libération conditionnelle était conforme à l'art. 5 par. 1 let. e CEDH (arrêt CourEDH Papillo c. Suisse du 27 janvier 2015 [requête n° 43368/08], § 46 ss).
Dans un arrêt traitant d'un détenu soumis à un traitement institutionnel en milieu fermé (<ref-law>), contre lequel seule une peine pécuniaire avait été prononcée, le Tribunal fédéral a jugé, à l'aune de la jurisprudence européenne et en tenant compte des circonstances d'espèce (suivi psychologique et traitement psychopharmacologique), que la détention carcérale pour une durée d'un peu plus de cinq mois n'avait pas violé l'art. 5 par. 1 let. e CEDH (arrêt 6B_817/2014 du 2 avril 2015 consid. 3.5.2).
Dans une autre affaire, le Tribunal fédéral a considéré que la détention de l'intéressé pendant trois ans à la Prison des Îles à Sion, à titre d'internement, ne résultait pas de l'incurie des autorités cantonales et pouvait être considérée comme " régulière " au sens de la jurisprudence (arrêt 6B_1264/2017 du 23 mai 2018 consid. 6.8).
Dans une affaire où aucune autorité n'avait statué sur la licéité de la détention carcérale d'un jeune adulte faisant l'objet d'une mesure thérapeutique au sens de l'<ref-law> et ayant purgé sa peine privative de liberté, le Tribunal fédéral a renvoyé la cause à la cour cantonale pour qu'elle désigne l'autorité compétente pour statuer sur ce point. Il a donné acte au recourant de l'illicéité de sa détention, sans pour autant fixer de période déterminante ni développer les motifs de ce constat (arrêt 6B_842/2016 du 10 mai 2017 consid. 3.2.2).
Sous l'empire de l'ancien <ref-law>, le Tribunal fédéral a jugé qu'une détention de près de 3 mois ordonnée dans le but de " motiver " l'intéressé et de " préparer " la mesure ne reposait sur aucun fondement juridique (arrêt 1P.334/2003 du 17 juillet 2003 consid. 8.5-8.6). En revanche, la détention d'un condamné à une mesure pour jeunes adultes dans un établissement carcéral était conforme au droit fédéral matériel dans le cas d'une situation d'urgence transitoire de courte durée (arrêt 6A.20/2006 du 12 mai 2006 consid. 4.5).
1.2.
1.2.1. Reconnu coupable de meurtre et de brigandage, le recourant a initialement été condamné à une peine privative de liberté de huit ans, laquelle a été, en appel, ramenée à sept ans et suspendue au profit d'un placement applicable aux jeunes adultes (<ref-law>).
Il ressort de la décision de levée de la mesure que le tribunal de première instance avait renoncé à prononcer un placement au sens de l'<ref-law>, notamment en raison du manque de motivation du recourant et du fait qu'il était peu accessible au traitement psychothérapeutique. Le Tribunal cantonal a, quant à lui, ordonné la mesure car le recourant avait manifesté par la suite sa volonté de suivre un traitement dans une institution pour jeunes adultes. Les experts avaient préconisé cette mesure " autant dans un objectif sécuritaire que pour permettre à l'intéressé d'évoluer, peut-être, vers une réinsertion sociale et professionnelle, dans un milieu cadrant et initialement fermé " (décision du TAPEM du 20 juin 2017 consid. 3 p. 5 s.).
Saisie de la demande de constat de l'illicéité de la détention, le TAPEM a notamment fait mention du rapport d'évaluation psycho-criminologique du 12 juillet 2017, selon lequel le risque de passage à l'acte violent était élevé si le recourant venait à être prochainement transféré en milieu ouvert et si des autorisations de sorties lui étaient octroyées. Sur cette base, il s'est dit convaincu que la peine devait être subie dans un établissement garantissant un niveau de sécurité élevé. Outre l'intérêt sécuritaire de la mesure de placement, le TAPEM a relevé l'indication du recourant - dans un courrier adressé le 4 avril 2017 à cette autorité - que la mesure prévue à l'<ref-law> " ne sert strictement à rien que ce soit en prison ou bien dans [s]on futur " (décision du TAPEM du 15 mai 2018 consid. 2.2 p. 11 s. et p. 13).
1.2.2. Il ressort de l'ordonnance attaquée que l'Office des sanctions et des mesures d'accompagnement (ci-après: OSAMA), informée le 2 février 2016 de l'entrée en force du jugement du 5 (recte: 2) décembre 2015, a entrepris les démarches de placement auprès du centre éducatif de Pramont (seul établissement en Valais destiné à l'accueil des jeunes adultes), dès le 8 février 2016. Le 26 février 2016, le centre a indiqué avoir inscrit le recourant sur liste d'attente. Au vu du manque de places disponibles à Pramont, l'OSAMA a élargi ses démarches hors canton, à partir du 17 octobre 2016, sollicitant trois autres établissements, lesquels n'ont pas répondu favorablement. Le 31 mars 2017, l'établissement de Pramont a précisé à l'OSAMA que le centre donnait la priorité aux mineurs et ne disposait d'aucune possibilité à long terme pour accueillir le recourant.
La cour cantonale a considéré que le recourant avait été détenu trop longtemps dans un établissement inadapté. Elle s'est fondée sur la date de prise de connaissance par l'OSAMA du jugement prononçant le placement et a considéré qu'un délai d'attente de neuf mois était acceptable. Elle a retenu que le maintien en détention du recourant dans un établissement carcéral entre le 2 novembre 2016 et le 20 juin 2017 (levée de la mesure) avait contrevenu à l'art. 5 al. 1 let. e CEDH.
1.3. La question à trancher en l'espèce n'est pas de savoir si la décision de levée de la mesure de placement et d'exécution du reste de la peine privative de liberté de sept ans (art. 62 c al. 1 let. c et al. 2 CP) était justifiée. Une telle question aurait dû faire l'objet d'un recours contre la décision du 20 juin 2017.
Le recourant ne remet pas en cause que sa détention a été ordonnée selon les voies légales. Il s'agit exclusivement de déterminer si la cour cantonale a violé l'art. 5 par. 1 let. e CEDH en considérant que la détention était " régulière " jusqu'au 2 novembre 2016, à savoir 9 mois après la prise de connaissance par l'OSAMA, du prononcé de la mesure. Pour ce faire, il convient d'examiner les différents intérêts en cause.
En substance, le cas d'espèce concerne un jeune adulte ayant commis des crimes graves, peu accessible à un traitement psychothérapeutique et présentant un risque élevé de récidive. Une peine privative de liberté de sept ans a été prononcée et n'a pas été purgée jusqu'aux deux tiers au moment du prononcé de la mesure (<ref-law>). Le placement, recommandé avec réserve par les experts, visait tant l'éventuelle resocialisation du recourant que la sécurité, étant précisé qu'il devait avoir lieu dans un milieu cadrant et initialement fermé.
Dans ces circonstances, il y a lieu d'admettre un lien évident entre le motif justifiant la privation de liberté, d'une part, et le lieu de détention, d'autre part, et a fortiori le cadre et le régime que cela implique.
Par ailleurs, il y a lieu de relever les efforts fournis par l'OSAMA pour trouver une place dans un établissement approprié ainsi que le changement de politique d'accueil du centre de Pramont, pendant le délai d'attente (cf. ordonnance attaquée consid. 3.3.2.1 p. 10; décision du TAPEM du 20 juin 2017 consid. 3 p. 6 et 7, à teneur de laquelle, au moment de la condamnation du recourant, il y avait notoirement la possibilité de placer des jeunes adultes à Pramont, possibilité qui a disparu depuis que ce centre accueille des mineurs astreints à une mesure). Contrairement aux affaires de la CourEDH Brand c. Pays-Baset Morsink c. Pays-Bas, l'autorité d'exécution a été confrontée à une situation nouvelle et imprévue. Aussi, il ne s'agit pas d'un contexte dans lequel un manque structurel de capacité des établissements aurait été identifié depuis de nombreuses années (cf. arrêts CourEDH Brand c. Pays-Bas du 11 mai 2004; [requête n° 49902/99] § 58 ss et Morsink c. Pays-Bas du 11 mai 2004; [requête n° 48865/99] § 61 ss). Il est d'ailleurs relevé que, dans les affaires concernant la Suisse, la CourEDH n'a jamais conclu à l'existence d'un problème structurel dans la prise en charge des personnes délinquantes souffrant de troubles mentaux (arrêt CourEDH Papillo c. Suisse du 27 janvier 2015 [requête n° 43368/08], § 46; cf. arrêts 6B_154/2017 du 25 octobre 2017 consid. 2.5; 6B_705/2015 du 22 septembre 2015 consid. 1.4.2).
Si l'ordonnance entreprise ne fait pas mention d'un soutien socio-éducatif ou thérapeutique ou d'une formation pendant la détention du recourant, ce dernier ne soutient pas que de telles mesures auraient été nécessaires, ni qu'il les aurait requises, au contraire (cf. supra consid. 1.2.1: indication qu'une mesure au sens de l'<ref-law> ne servait strictement à rien). Ainsi, le cas du recourant n'apparaît pas comparable à ceux traités dans les arrêts précités concernant les Pays-Bas (arrêts du 11 mai 2004; [requête n° 49902/99] § 58 ss et [requête n° 48865/99] § 61 ss), dans lesquels les requérants avaient purgé leur peine. En outre, dans ces affaires, la mesure thérapeutique visait principalement leur resocialisation, de telle sorte que la détention transitoire dans une maison d'arrêt réduisait d'autant la durée du traitement et ses perspectives de succès.
1.3.1. S'agissant de la date à partir de laquelle la détention doit être jugée illicite, le recourant ne saurait rien déduire de l'arrêt 6B_842/2016, faute de toute précision sur ce point dans cette affaire. Au demeurant, l'arrêt porte principalement sur le droit d'obtenir une décision relative au caractère illicite de la détention par une autorité compétente. En tout état, il en ressort notamment qu'un séjour dans un établissement d'exécution des peines est envisageable pour autant qu'il soit nécessaire afin de trouver un établissement approprié, en fonction des efforts fournis par les autorités d'exécution (cf. arrêt 6B_842/2016 du 10 mai 2017 consid. 3.1.1 et les références citées). Cela étant et compte tenu de l'impossibilité pratique et financière d'assurer immédiatement une place à toute personne soumise à un traitement (cf. arrêts CourEDH Brand c. Pays-Bas du 11 mai 2004 [requête n° 49902/99], § 64; Morinsk c. Pays-Bas du 11 mai 2004 [requête n° 48865/99], § 67; arrêt 6B_817/2014 du 2 avril 2015 consid. 3.5.2), le recourant ne peut pas prétendre à un constat d'illicéité à partir du 2 décembre 2015, date du prononcé de la mesure. Au vu des circonstances et sur la base de la jurisprudence précitée, la cour cantonale pouvait admettre un délai de carence entre le prononcé de la mesure et la prise de connaissance, par l'autorité d'exécution, de l'entrée en force de celle-ci.
1.3.2. Admettant qu'un délai d'attente de six mois serait admissible avant d'être placé, le recourant requiert, à titre subsidiaire, que la détention soit jugée illicite à partir du 2 juin 2016. Or il est établi et incontesté que l'OSAMA a mis en oeuvre tous les moyens à disposition afin que l'intéressé puisse être transféré rapidement dans un établissement adapté aux jeunes adultes (ordonnance attaquée consid. 3.3.2.2 p. 11) et a élargi ses recherches dans trois établissements hors canton à partir du 17 octobre 2016. Compte tenu des circonstances entourant le prononcé de la mesure (cf. supra consid. 1.2.1) et des efforts fournis par l'OSAMA, on ne saurait reprocher à la cour cantonale d'avoir abusé de son pouvoir d'appréciation en considérant que la période de neuf mois depuis la prise de connaissance par l'autorité d'exécution de l'entrée en vigueur de la mesure, était conforme à l'art. 5 par. 1 let. e CEDH. Infondé, le recours doit être rejeté sur ce point.
Au vu de ce qui précède, il n'y a pas lieu d'entrer en matière sur le grief déduit de l'arbitraire dans la chronologie des faits, visant à établir la date à partir de laquelle la détention aurait dû être jugée illicite.
2.
Dénonçant la violation de son droit d'être entendu (art. 29 al. 2 Cst.) et se plaignant d'un déni de justice formel, le recourant prétend que la cour cantonale n'aurait pas traité deux griefs dont elle a été saisie, ou du moins, n'en aurait pas suffisamment motivé le rejet.
2.1. Selon la jurisprudence, l'autorité qui ne traite pas un grief relevant de sa compétence, motivé de façon suffisante et pertinent pour l'issue du litige, commet un déni de justice formel proscrit par l'art. 29 al. 1 Cst. (<ref-ruling> consid. 4.2 p. 157; <ref-ruling> consid. 2.1 p. 9). De même, la jurisprudence a déduit de l'art. 29 al. 2 Cst. l'obligation pour l'autorité de motiver sa décision, afin que l'intéressé puisse se rendre compte de la portée de celle-ci et exercer son droit de recours à bon escient (<ref-ruling> consid. 2.1 p. 145). Pour satisfaire à ces exigences, il suffit que l'autorité mentionne, au moins brièvement, les motifs qui l'ont guidée et sur lesquels elle a fondé son raisonnement. Elle ne doit pas se prononcer sur tous les moyens des parties, mais peut au contraire se limiter aux questions décisives (<ref-ruling> consid. 4.2 p. 157). La motivation peut d'ailleurs être implicite et résulter des différents considérants de la décision (<ref-ruling> consid. 3.2.1 p. 565).
2.2.
2.2.1. Le recourant prétend que la cour cantonale aurait ignoré son grief déduit d'une violation de l'<ref-law> (recte: 75 al. 3 CP, établissement d'un plan d'exécution de peine) et aurait ainsi mal déterminé le début de la période de détention illicite dans un établissement carcéral.
Constatant la violation de l'art. 5 par. 1 let. e CEDH, la cour cantonale a considéré qu'il n'apparaissait pas nécessaire d'examiner les autres griefs du recourant en lien avec cette disposition, en particulier l'opportunité d'un plan d'exécution (ordonnance entreprise, consid. 3.3.2.3 p. 11). Dans son mémoire de recours cantonal, le recourant prétendait, en substance, que, faute de plan d'exécution, sa détention était illicite. Il ne ressort nullement du mémoire de recours cantonal que la prétendue violation de l'<ref-law> permettrait de déterminer la période de détention illicite. Au contraire, ce grief servait d'appui à la démonstration de la violation de l'art. 5 CEDH, laquelle a été reconnue par la cour cantonale. Aussi, cette dernière n'a pas violé le droit d'être entendu du recourant en considérant expressément qu'il n'était pas nécessaire d'examiner la violation de l'<ref-law>.
2.2.2. Le recourant se méprend lorsqu'il prétend que la cour cantonale n'aurait pas examiné ses conditions de détention sous l'angle de l'art. 3 CEDH, de manière indépendante de l'art. 5 CEDH. En effet, après avoir posé les principes prévalant en matière de conditions de détention (ordonnance entreprise, consid. 4.2 p. 12 s.), la cour cantonale a examiné en détail la situation du recourant pour conclure expressément que ses conditions de détention n'étaient pas contraire à l'art. 3 CEDH (ordonnance entreprise, consid. 4.3 p. 13 s.). La cour cantonale n'a pas davantage commis de déni de justice sur ce point.
3.
Le recours doit être rejeté dans la mesure où il est recevable. L'assistance judiciaire a été refusée au recourant par ordonnance incidente du 29 mai 2019, faute pour lui d'avoir établi sa situation financière (cf. <ref-law>). Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais, Chambre pénale.
Lausanne, le 5 septembre 2019
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke